第15卷第3期 智能系统学报 Vol.15 No.3 2020年5月 CAAI Transactions on Intelligent Systems May 2020 D0L:10.11992tis.201908022 无人机群多目标协同主动感知的自组织映射方法 王华鲜'，华容，刘华平2，赵怀林，孙富春2 (1,上海应用技术大学电气与电子工程学院，上海201499,2.清华大学智能技术与系统国家重点实验室，北京 100084) 摘要：针对主动感知问题多为单机器人系统的主动视觉问题，本文提出了基于自组织映射特征网络的异构机 器人主动感知框架，为无人机团队规划出遍历所有目标所需时间最短的平滑路径。首先把多目标主动感知场 景建模为带邻域的多旅行商问题，然后使用自组织映射网络为无人机团队规划出旅行时间最短的闭环轨迹，最 后利用三阶贝塞尔曲线对轨迹做平滑处理。仿真结果和对比实验表明，本文的方法在多目标主动感知的应用 中有着较好的效果。 关键词：多机器人系统；主动感知；旅行商问题；自组织映射网络；路径规划；异构机器人；贝塞尔曲线；路径 平滑 中图分类号：TP391.9文献标志码：A文章编号：1673-4785(2020)03-0609-06 中文引用格式：王华鲜，华容，刘华平，等.无人机群多目标协同主动感知的自组织映射方法.智能系统学报，2020,15(3)： 609-614. 英文引用格式：WANG Huaxian,HUA Rong,.LIU Huaping,etal.Self-organizing feature map method for multi-target active per- ception of unmanned aerial vehicle systemsJl.CAAI transactions on intelligent systems,2020,15(3):609-614. Self-organizing feature map method for multi-target active perception of unmanned aerial vehicle systems WANG Huaxian',HUA Rong',LIU Huaping,ZHAO Huailin',SUN Fuchun (1.School of Electrical and Electronics Engineering,Shanghai Institute of Technology,Shanghai 201499,China,2.State Key Lab of Intelligent Technology and Systems,Tsinghua University,Beijing 100084,China) Abstract:It is known that the robots fitted with cameras,also sometimes called as unmanned aerial vehicles,are used to monitor inaccessible areas.The data sent by robots are analyzed through various artificial neural networks.Active vis- ion is particularly important to cope with problems like occlusions,limited field of view,and limited resolution of the camera.In view of the active vision difficulty faced in active perception system,this paper proposes an active percep- tion framework of heterogeneous robots based on the self-organizing feature map,a type of multi-objective active learn- ing algorithm,and plans the shortest smooth path for the drone team to traverse all the targets.First,the multi-target act- ive perception scene is modeled as multiple traveling salesmen problem with neighborhood.After that,the self-organiz- ing mapping network is used to find the shortest closed-loop track for travel time,and then the track is smoothed with the third-order Bezier curve,a parametric curve.The simulation results and comparative experiments show that pro- posed method has better effects in the application of multi-objective active perception. Keywords:multi-robot system;active perception;traveling salesman problem;self-organizing mapping network;path planning;heterogeneous robot,Bezier curve;path smoothing 移动机器人利用传感器和感知算法来了解周 可能或危险的环境中，帮助人类解决环境监测、 围的环境，因此越来越多地应用于人类有限、不 搜救、寻源、主动感知等问题)。尽管通过改善 收稿日期：2019-08-19. 机器人感知方式来提高信息收集质量的方法已经 基金项目：国家自然科学基金项目(U1613212:上海市“联盟计 被研究了近30年，然而大多数的机器人系统的任 划”项目(LM201756). 通信作者：刘华平.E-mail:hpliu(@tsinghua.edu.cn 务执行方式是被动的。虽然单机器人系统具有
DOI: 10.11992/tis.201908022 无人机群多目标协同主动感知的自组织映射方法 王华鲜1 ，华容1 ，刘华平2 ，赵怀林1 ，孙富春2 （1. 上海应用技术大学 电气与电子工程学院，上海 201499; 2. 清华大学 智能技术与系统国家重点实验室，北京 100084） 摘 要：针对主动感知问题多为单机器人系统的主动视觉问题，本文提出了基于自组织映射特征网络的异构机 器人主动感知框架，为无人机团队规划出遍历所有目标所需时间最短的平滑路径。首先把多目标主动感知场 景建模为带邻域的多旅行商问题，然后使用自组织映射网络为无人机团队规划出旅行时间最短的闭环轨迹，最 后利用三阶贝塞尔曲线对轨迹做平滑处理。仿真结果和对比实验表明，本文的方法在多目标主动感知的应用 中有着较好的效果。 关键词：多机器人系统；主动感知；旅行商问题；自组织映射网络；路径规划；异构机器人；贝塞尔曲线；路径 平滑 中图分类号：TP391.9 文献标志码：A 文章编号：1673−4785(2020)03−0609−06 中文引用格式：王华鲜, 华容, 刘华平, 等. 无人机群多目标协同主动感知的自组织映射方法 [J]. 智能系统学报, 2020, 15(3): 609–614. 英文引用格式：WANG Huaxian, HUA Rong, LIU Huaping, et al. Self-organizing feature map method for multi-target active perception of unmanned aerial vehicle systems[J]. CAAI transactions on intelligent systems, 2020, 15(3): 609–614. Self-organizing feature map method for multi-target active perception of unmanned aerial vehicle systems WANG Huaxian1 ，HUA Rong1 ，LIU Huaping2 ，ZHAO Huailin1 ，SUN Fuchun2 (1. School of Electrical and Electronics Engineering, Shanghai Institute of Technology, Shanghai 201499, China; 2. State Key Lab of Intelligent Technology and Systems, Tsinghua University, Beijing 100084, China) Abstract: It is known that the robots fitted with cameras, also sometimes called as unmanned aerial vehicles, are used to monitor inaccessible areas. The data sent by robots are analyzed through various artificial neural networks. Active vision is particularly important to cope with problems like occlusions, limited field of view, and limited resolution of the camera. In view of the active vision difficulty faced in active perception system, this paper proposes an active perception framework of heterogeneous robots based on the self-organizing feature map, a type of multi-objective active learning algorithm, and plans the shortest smooth path for the drone team to traverse all the targets. First, the multi-target active perception scene is modeled as multiple traveling salesmen problem with neighborhood. After that, the self-organizing mapping network is used to find the shortest closed-loop track for travel time, and then the track is smoothed with the third-order Bézier curve, a parametric curve. The simulation results and comparative experiments show that proposed method has better effects in the application of multi-objective active perception. Keywords: multi-robot system; active perception; traveling salesman problem; self-organizing mapping network; path planning; heterogeneous robot; Bézier curve; path smoothing 移动机器人利用传感器和感知算法来了解周 围的环境，因此越来越多地应用于人类有限、不 可能或危险的环境中，帮助人类解决环境监测、 搜救、寻源、主动感知等问题[1-3]。尽管通过改善 机器人感知方式来提高信息收集质量的方法已经 被研究了近 30 年，然而大多数的机器人系统的任 务执行方式是被动的[4]。虽然单机器人系统具有 收稿日期：2019−08−19. 基金项目：国家自然科学基金项目 (U1613212)；上海市“联盟计 划”项目 (LM201756). 通信作者：刘华平. E-mail：hpliu@tsinghua.edu.cn. 第 15 卷第 3 期 智 能 系 统 学 报 Vol.15 No.3 2020 年 5 月 CAAI Transactions on Intelligent Systems May 2020
·610- 智能系统学报 第15卷 相对较强的性能，但有些任务本身可能过于复 数倍增长，同时可行解以及路径长度的计算量将 杂，甚至不可能完成，例如空间上相互独立的任 正比于l/2。现有的方法在目标数量较少时有着 务。在多机器人系统中，异构机器人可以针对 不错的效果，但是当目标较多时会出现计算量大 不同层次的任务进行专门化设计，可以应用于复 耗时长且不能得到较好的结果。因此，本文提 杂的感知任务中。 出使用SOM来解决这一难题。 现有的主动感知方法是反应性的，不受历史 状态的影响，是一个马尔可夫过程。状态感知的 质量会影响算法性能，可以通过选择最优感知位 置来改进6。这通常是一个短视问题，从控制策 略上来说是贪婪的”。最近，研究者们把主动感 知问题从主动视觉扩展到了更为复杂的场景和任 务：1)主动的目标识别、检测与跟踪；2)广阔的环 境，如农场；3)具有丰富的社会知识、求知能力和 图1多目标主动感知场景 非近视性的规划方法。但是这些感知任务大都是 Fig.1 Multi-target active perception scene 单机器人系统⑧，且很少应用在多目标场景。 13 自组织映射特征网络 为了弥补这一差距，本文提出了一个基于自 如图2所示，SOM是一种竞争性的双层神经 组织映射网络(self-organizing map,SOM)的分散式 网络且在输出层的样本空间中形成新的拓扑结 异构机器人的框架来解决多目标主动感知的任 构2。在SOM的训练过程中，多个神经元通过 务。在发现多目标的位置后，自组织映射算法为 竞争协作完成对输入样本的模式分类。网络中的 无人机团队规划出一条时间最短的路径，从而执 输入神经元x与输出神经元y通过权值ω相 行监视、拍照等任务。 连，同时，近邻的输出神经元之间也通过权值相 连。SOM的输出结果保持自组织的拓扑结构， 1相关工作 映射到多维的向量空间中。 1.1主动感知 被动感知与主动感知的区别在于环境状态量 输出神经元身 是否与智能体有交互。在被动感知中，智能体使 用一组被动观察量来分类、估计、预测或推断与 权值⊙ 环境相关的一些信息。在主动感知中，智能体 通过采取行动并观察环境如何变化，以动态的方 输人神经元x 式与环境交互更改状态。在此过程中，通过环 境状态的变化，观察变得依赖于行动。 图2典型的SOM结构 文献「3-4]证明了主动感知系统的性能高度 Fig.2 Typical SOM structure diagram 依赖于机器人所选择的观测位置，但是其目标函 2问题建模 数为机器人团队的观测奖励，且不同位置的观测 奖励值是预先设定的。本文的研究目的是让机 图1中给出了异构机器人的主动感知框架。 器人团队最小化旅行时间同时遍历所有目标，在 无人机团队中一部分通过搭载的传感器设备搜索 这个过程中无人机团队的路径点是SOM算法规 区域的目标，另一部分执行快速遍历的主动感知 划出来的而不是从提前设定的一系列路径点序列 任务。任务目标是在满足旅行预算的前提下为 中进行选择。 机器人团队R={,2,…,R}规划一个由路径点序 1.2带邻域的多旅行商问题 列X={x1,2,,x}组成的平滑路径，使其能够监 图1给出了本文的研究场景，这是一个带邻 视环境中的每一个目标N={m1,2,…,nw小，并使得 域的多旅行商问题(multiple traveling salesman 团队的旅行时间Tsum=tn+in+tn+…+tn最短。考 problem with k-neighbourhood,k-MTSP)10 k-MTSP 虑到实际环境中，被感知目标并非无体积的质 是典型的NP-hard问题，不能在多项式时间内 点，而且机器人上一般搭载有感知设备，如雷达、 求出最优解。对于n个目标来说，存在着[(m-1)]2 深度相机等。因此目标w是一个圆形的感知区 条可能的路径。可行解的数目随着n的增加呈指 域Sw∈R,其感知半径为k。无人机只需要访问
相对较强的性能，但有些任务本身可能过于复 杂，甚至不可能完成，例如空间上相互独立的任 务 [5]。在多机器人系统中，异构机器人可以针对 不同层次的任务进行专门化设计，可以应用于复 杂的感知任务中。 现有的主动感知方法是反应性的，不受历史 状态的影响，是一个马尔可夫过程。状态感知的 质量会影响算法性能，可以通过选择最优感知位 置来改进[2，6]。这通常是一个短视问题，从控制策 略上来说是贪婪的[7]。最近，研究者们把主动感 知问题从主动视觉扩展到了更为复杂的场景和任 务：1) 主动的目标识别、检测与跟踪；2) 广阔的环 境，如农场；3) 具有丰富的社会知识、求知能力和 非近视性的规划方法。但是这些感知任务大都是 单机器人系统[8] ，且很少应用在多目标场景。 为了弥补这一差距，本文提出了一个基于自 组织映射网络 (self-organizing map,SOM) 的分散式 异构机器人的框架来解决多目标主动感知的任 务。在发现多目标的位置后，自组织映射算法为 无人机团队规划出一条时间最短的路径，从而执 行监视、拍照等任务。 1 相关工作 1.1 主动感知 被动感知与主动感知的区别在于环境状态量 是否与智能体有交互。在被动感知中，智能体使 用一组被动观察量来分类、估计、预测或推断与 环境相关的一些信息[9]。在主动感知中，智能体 通过采取行动并观察环境如何变化，以动态的方 式与环境交互更改状态[6]。在此过程中，通过环 境状态的变化，观察变得依赖于行动。 文献 [3-4] 证明了主动感知系统的性能高度 依赖于机器人所选择的观测位置，但是其目标函 数为机器人团队的观测奖励，且不同位置的观测 奖励值是预先设定的[3]。本文的研究目的是让机 器人团队最小化旅行时间同时遍历所有目标，在 这个过程中无人机团队的路径点是 SOM 算法规 划出来的而不是从提前设定的一系列路径点序列 中进行选择。 1.2 带邻域的多旅行商问题 图 1 给出了本文的研究场景，这是一个带邻 域的多旅行商问题 (multiple traveling salesman problem with k-neighbourhood, k-MTSP)[10]。k-MTSP 是典型的 NP-hard 问题，不能在多项式时间内 求出最优解。对于 n 个目标来说，存在着 [(n−1)!]/2 条可能的路径。可行解的数目随着 n 的增加呈指 数倍增长，同时可行解以及路径长度的计算量将 正比于 n!/2。现有的方法在目标数量较少时有着 不错的效果，但是当目标较多时会出现计算量大 耗时长且不能得到较好的结果[11]。因此，本文提 出使用 SOM 来解决这一难题。 图 1 多目标主动感知场景 Fig. 1 Multi-target active perception scene 1.3 自组织映射特征网络 xi yj ωi j 如图 2 所示，SOM 是一种竞争性的双层神经 网络且在输出层的样本空间中形成新的拓扑结 构 [12-16]。在 SOM 的训练过程中，多个神经元通过 竞争协作完成对输入样本的模式分类。网络中的 输入神经元 与输出神经元 通过权值 相 连，同时，近邻的输出神经元之间也通过权值相 连 [3]。SOM 的输出结果保持自组织的拓扑结构， 映射到多维的向量空间中。 输出神经元 yj 权值 ωij 输入神经元 xi 图 2 典型的 SOM 结构 Fig. 2 Typical SOM structure diagram 2 问题建模 R = {r1,r2,· · ·,rR} X = {x1, x2,· · ·, xi} N = {n1,n2, · · ·,nN} Tsum = tr1 +tr2 +tr3 +· · ·+trR sN ∈ R 图 1 中给出了异构机器人的主动感知框架。 无人机团队中一部分通过搭载的传感器设备搜索 区域的目标，另一部分执行快速遍历的主动感知 任务[17]。任务目标是在满足旅行预算的前提下为 机器人团队 规划一个由路径点序 列 组成的平滑路径，使其能够监 视环境中的每一个目标 ，并使得 团队的旅行时间 最短。考 虑到实际环境中，被感知目标并非无体积的质 点，而且机器人上一般搭载有感知设备，如雷达、 深度相机等。因此目标 nN 是一个圆形的感知区 域 ，其感知半径为 k。无人机只需要访问 ·610· 智 能 系 统 学 报 第 15 卷
第3期 王华鲜，等：无人机群多目标协同主动感知的自组织映射方法 ·611· 到感知区域的任意位置，即可执行捕获任务 的结果陷入局部最优，感应位置组成的样本空间 x-wl≤k。这是一个k-MTSP问题，目标函数为 以随机的顺序输入给SOM,每一轮的迭代都是 最小化旅行时间，即 SOM对输入空间的一个自适应过程9。 minmizeT(X=∑T(X) S,S2,…,Sw SOM规划出的平滑路径都有旅行消耗 Fl V-V c:≥0，定义为无人机在路径X上的时间。机器人 团队有总的旅行预算时间b,≥0。当SOM为机器 人团队规划出一次路径时，会计算出当前轮次的 旅行消耗，选择获胜机器人R,即 R,←argmin 6 C≤b 图4SOM训练过程 3感知路径生成 Fig.4 SOM training process 如图5所示，SOM输出的拓扑结构中，与目 图3给出了应用于大规模场景多目标感知的 标位置s最佳匹配的神经元是拓扑结构中距离目 SOM训练结构。 标欧氏距离最近的点。然后在点P:处创建获胜 输人神经元 输出神经元 神经元。 神经元权重 ,获胜神经元 (a)点P,在神经元外 (b)点P,在神经元内 V N=k 图5获胜神经元的几何关系 目标感知位置 生成路径点 Fig.5 Geometry of the winner neuron 最后阶段，=X 可行的迭代方法是线段(P,s)中的某一个点 图3SOM训练结构 Fig.3 SOM training structure 逐渐趋近于邻域长度k。该几何迭代过程有两种 情况：1)如果p,已经位于领域内，那么只需要在 定义SOM输入层的兴奋神经元邻域为 P,处创建获胜神经元，网络不需要进行自适应的 Tic=exp (1) 过程；2)如果P,位于感知区域外部，那么需要按 22 照标准SOM的方法进行迭代。标准的SOM学习 式中x)是获胜神经元的索引。学习增益σ随 可以看作神经元朝向5。的移动同时产生一个新 着时间的推移而减少，即 的神经元使v变为v,即 r(t)=oexp(-t|T。) (2) V=v+μfc,d)(wsp-v) (4) 拓扑邻域更新了获胜神经元的权重，同时邻 式中：μ为学习率；f(σ，d)是邻域函数；σ是网络 域内的其他神经元权重也进行了更新，但幅度较 的学习增益；d是v到v的欧氏距离。邻域函数 小，以此保障具有输人空间映射结构的训练样本 定义了周围被调整的竞争性神经元，并且具有 向目标逼近。权重更新方式为 SOM中针对TSP进行调整的标准形式： △wi=7t)·T(t)(-ω) (3) e号，d<0.2M 式中：0为依赖于时间的学习率，)=%exp(-t/π，) f(σ，d0= 其他 (5) 图4给出了某训练阶段示意图。本文SOM 0 的输入样本是群体目标的感应位置S∈R,输出 在每轮训练结束后，学习率根据 结果是经过训练后的路径点v={,2,其中 0=(1-) (6) k是当前网络中神经元的数量，多轮迭代后即为 逐渐减少，“是增益减少比率。此外，在每一个学 无人机团队的路径点序列X。为了避免网络训练 习阶段之后，都会进行一个环再生，以去除所有
∥xi −nN∥ ⩽ k 到感知区域的任意位置，即可执行捕获任务 。这是一个 k-MTSP 问题，目标函数为 最小化旅行时间，即 minmizeT(X) = ∑n i=1 T (Xi) ci ⩾ 0 Xi bi ⩾ 0 Rr S O M 规划出的平滑路径都有旅行消耗 ，定义为无人机在路径 上的时间。机器人 团队有总的旅行预算时间 。当 SOM 为机器 人团队规划出一次路径时，会计算出当前轮次的 旅行消耗，选择获胜机器人 ，即 Rr ← argmin( cq bq ) , ci ⩽ bi 3 感知路径生成 图 3 给出了应用于大规模场景多目标感知的 SOM 训练结构。 输入神经元 输出神经元 获胜神经元 目标感知位置 生成路径点 最后阶段, v=X 神经元权重 S1 S2 S3 SN v1 v2 v3 vk N=k . . . . . . . . . . . . 图 3 SOM 训练结构 Fig. 3 SOM training structure 定义 SOM 输入层的兴奋神经元邻域为 Tj,I(x) = exp − S 2 j,I(x) 2σ2 (1) 式中 I(x) 是获胜神经元的索引 σ [18]。学习增益 随 着时间的推移而减少，即 σ(t) = σ0 exp(−t/τσ) (2) 拓扑邻域更新了获胜神经元的权重，同时邻 域内的其他神经元权重也进行了更新，但幅度较 小，以此保障具有输入空间映射结构的训练样本 向目标逼近。权重更新方式为 ∆ωji = η(t)·Tj,I(x)(t)· ( xi −ωji) (3) η(t) η(t) = η0 exp( −t/τη ) 式中： 为依赖于时间的学习率， 。 sN ∈ R v = {v1, v2,... vk} Xi 图 4 给出了某训练阶段示意图。本文 SOM 的输入样本是群体目标的感应位置 ，输出 结果是经过训练后的路径点 ，其中 k 是当前网络中神经元的数量，多轮迭代后即为 无人机团队的路径点序列 。为了避免网络训练 的结果陷入局部最优，感应位置组成的样本空间 以随机的顺序输入给 SOM，每一轮的迭代都是 SOM 对输入空间的一个自适应过程[19]。 r3 r2 r1 κ v1 , v2 , ..., vk S1 , S2 , ..., SN 图 4 SOM 训练过程 Fig. 4 SOM training process ps v ∗ 如图 5 所示，SOM 输出的拓扑结构中，与目 标位置 s 最佳匹配的神经元是拓扑结构中距离目 标欧氏距离最近的点。然后在点 处创建获胜 神经元 。 vi vi vi+1 vi+1 Ps s Ps p s s p N sN κ κ v* v* (a) 点Ps在神经元外 (b) 点Ps在神经元内 图 5 获胜神经元的几何关系 Fig. 5 Geometry of the winner neuron ps ps ps sp v ′ 可行的迭代方法是线段 (ps，sn ) 中的某一个点 逐渐趋近于邻域长度 k。该几何迭代过程有两种 情况：1）如果 已经位于领域内，那么只需要在 处创建获胜神经元，网络不需要进行自适应的 过程；2）如果 位于感知区域外部，那么需要按 照标准 SOM 的方法进行迭代。标准的 SOM 学习 可以看作神经元朝向 的移动同时产生一个新 的神经元使 v 变为 , 即 v ′ = v+µ f(σ,d) ( v ∗ sp −v ) (4) µ f (σ,d) σ d ν ν ∗ 式中： 为学习率； 是邻域函数； 是网络 的学习增益； 是 到 的欧氏距离。邻域函数 定义了周围被调整的竞争性神经元，并且具有 SOM 中针对 TSP 进行调整的标准形式： f(σ,d) = e −d 2 σ2 , d < 0.2M 0, 其他 (5) 在每轮训练结束后，学习率根据 σ=(1−α)σ (6) 逐渐减少，α 是增益减少比率。此外，在每一个学 习阶段之后，都会进行一个环再生，以去除所有 第 3 期 王华鲜，等：无人机群多目标协同主动感知的自组织映射方法 ·611·
·612· 智能系统学报 第15卷 竞争失败的神经元。 过70~80次的迭代，算法收敛，得出最终结果。 如果所有获胜神经元都明显接近各自的，从 由于SOM是一种竞争性神经网络，所以不同轮 而使其在每个神经元的k邻域内，则SOM的迭代 次的获胜神经元及兴奋神经元邻域是不同的，这 过程将终止。然后，连接获胜神经元的光滑曲线 就造成了目标覆盖率并不是线性单调函数，如图7 序列是主动感知问题的可行解决方案。如果网络 所示。相对应的每一轮迭代结果的无人机旅行时 收敛速度不够快，可以在最大迭代轮次之后终止 间也不是迭代轮次的单调函数，自适应过程的旅 学习过程，并且可以通过遍历环并使用与获胜神 行时间会产生随机振荡，但是在过程中会趋于稳 经元关联的5p来构建可行的解决方案。对于已 定，如图8所示。 用的学习速率μ=0.5，网络收敛的同时对SOM的 初始学习增益按照σ=12.41n+0.6,增益递减率 a=0.1,网络在不到100个学习轮次内稳定。 为了避免无人机飞行过程中大角度转弯带来 的不稳定性，对SOM生成的路径进行三阶分段 贝塞尔平滑处理2： X(r)=B(1-t)3+3B1t(1-t)2+3B2T2(1-T)+Bt(7) (a)第I次迭代 b)第30次迭代 式中：T∈[O,1);B、B3为每段分段Bezier曲线的 起点和终点的位置；B1、B2决定了每段分段Bezi- er曲线起点和终点处的切线。无人机的闭环轨迹 曲线由多个分段Bezier曲线组成，为保证轨迹连 续，无人机闭环轨迹中相邻两个分段贝塞尔曲线 X-1、X的路径点需满足B=B%。闭环轨迹中第 (c)第60次迭代 (d)第80次迭代 i-l个分段Bezier曲线起点的切线t和第i个分 图6SOM迭代过程 段Bezier曲线终点的切线t,切线tl的长度 Fig.6 SOM iterative process 和切线的长度分别为 200 t=B-B哈，6=B-B (8) 180 店=，6= (9) 160 无人机群体轨迹平滑满足： t=后 (10) 4实验结果及分析 100 80 本文进行了一系列仿真实验来验证提出的算 11 21314151617181 迭代次数 法效果。所有实验均使用C+编程，并在装有2.5Hz 频率下i5-7300HQ中央处理器的操作系统上进行 图7单次实验的旅行时间 仿真，仿真结果数据用MATLAB2016b进行处 Fig.7 Traveling time of a single experiment 理。由于单次实验结果不具有代表性，本文在相 100 同条件下进行了20次实验，以此来分析SOM在 90 大规模场景下多目标主动感知任务的效果。无人 80 机的水平初始速度v=5m/s,目标数为31，竖直与 60 水平方向的加速度为0，无人机近似地认为是在 0 二维平面内匀速运动。场景中群体目标的感知邻 域半径k为5m,SOM的训练次数为100，学习率 20 10 为0.5。 0 1121 314151617181 图6展示了SOM算法的迭代过程。初始阶 迭代次数 段，把异构无人机团队测得的目标位置坐标作为 图8单次实验的目标发现率 初始样本输入到SOM网络中进行训练，最终经 Fig.8 Target discovery rate of a single experiment
竞争失败的神经元。 sp µ = 0.5 σ = 12.41n+0.6 α = 0.1 如果所有获胜神经元都明显接近各自的，从 而使其在每个神经元的 k 邻域内，则 SOM 的迭代 过程将终止。然后，连接获胜神经元的光滑曲线 序列是主动感知问题的可行解决方案。如果网络 收敛速度不够快，可以在最大迭代轮次之后终止 学习过程，并且可以通过遍历环并使用与获胜神 经元关联的 来构建可行的解决方案。对于已 用的学习速率 ,网络收敛的同时对 SOM 的 初始学习增益按照 ,增益递减率 ，网络在不到 100 个学习轮次内稳定。 为了避免无人机飞行过程中大角度转弯带来 的不稳定性，对 SOM 生成的路径进行三阶分段 贝塞尔平滑处理[20] ： X (τ) = B0 (1−τ) 3+3B1τ(1−τ) 2+3B2τ 2 (1−τ)+B3τ 3 (7) τ ∈ [0,1] B0、B3 B1 B2 Xi−1、Xi B i−1 3 = B i 0 t i−1 a t i b t i−1 a l i−1 a t i b l i b 式中： ； 为每段分段 Bezier 曲线的 起点和终点的位置； 、 决定了每段分段 Bezier 曲线起点和终点处的切线。无人机的闭环轨迹 曲线由多个分段 Bezier 曲线组成，为保证轨迹连 续，无人机闭环轨迹中相邻两个分段贝塞尔曲线 的路径点需满足 。闭环轨迹中第 i-1 个分段 Bezier 曲线起点的切线 和第 i 个分 段 Bezier 曲线终点的切线 ，切线 的长度 和切线 的长度 分别为 t i−1 a = B i−1 1 − B i−1 0 , t i b = B i 3 − B i 2 (8) l i−1 a = t i−1 a , l i b = t i b (9) 无人机群体轨迹平滑满足: l i−1 a t i b = l i b t i−1 a (10) 4 实验结果及分析 v = 5 m/s 本文进行了一系列仿真实验来验证提出的算 法效果。所有实验均使用 C++编程，并在装有 2.5 Hz 频率下 i5-7300HQ 中央处理器的操作系统上进行 仿真，仿真结果数据用 MATLAB2016b 进行处 理。由于单次实验结果不具有代表性，本文在相 同条件下进行了 20 次实验，以此来分析 SOM 在 大规模场景下多目标主动感知任务的效果。无人 机的水平初始速度 ，目标数为 31，竖直与 水平方向的加速度为 0，无人机近似地认为是在 二维平面内匀速运动。场景中群体目标的感知邻 域半径 k 为 5 m，SOM 的训练次数为 100，学习率 为 0.5。 图 6 展示了 SOM 算法的迭代过程。初始阶 段，把异构无人机团队测得的目标位置坐标作为 初始样本输入到 SOM 网络中进行训练，最终经 过 70～80 次的迭代，算法收敛，得出最终结果。 由于 SOM 是一种竞争性神经网络，所以不同轮 次的获胜神经元及兴奋神经元邻域是不同的，这 就造成了目标覆盖率并不是线性单调函数，如图 7 所示。相对应的每一轮迭代结果的无人机旅行时 间也不是迭代轮次的单调函数，自适应过程的旅 行时间会产生随机振荡，但是在过程中会趋于稳 定，如图 8 所示。 (a) 第1次迭代 (b) 第30次迭代 (c) 第60次迭代 (d) 第80次迭代 图 6 SOM 迭代过程 Fig. 6 SOM iterative process 时间/s 200 180 160 140 120 100 80 1 11 21 31 41 51 61 71 81 迭代次数 图 7 单次实验的旅行时间 Fig. 7 Traveling time of a single experiment 目标发现率/% 100 90 80 70 60 50 40 30 20 10 0 1 11 21 31 41 51 61 71 81 迭代次数 图 8 单次实验的目标发现率 Fig. 8 Target discovery rate of a single experiment ·612· 智 能 系 统 学 报 第 15 卷
第3期 王华鲜，等：无人机群多目标协同主动感知的自组织映射方法 ·613· 为了验证无人机数量对结果的影响，本文在 相同的实验条件下改变无人机数量进行测试。实 验结果表明，有限增加无人机数量可以减少总旅 行时间，如图9所示。 125 120 115 110 图10搭建gazeb0仿真环境 105 Fig.10 Building a simulation environment in gazebo 100 95 4 5 6 无人机数量架 图9无人机数量与总旅行时间的关系 Fig.9 Relationship between the number of UAVs and the total travel time 为了评估本文提出的方法，在相同的场景条 件下使用遗传算法、蚁群算法、粒子群优化算法啊 进行对比实验，取20次实验的平均值，如表1所 示。实验结果表明，本文的方法得出的无人机团 图11 gazebo中的算法测试结果 Fig.11 Algorithm test results in gazebo 队旅行时间较短，可以应用于大规模场景下多目 标群体智能的主动感知问题。 5结束语 表1不同算法的旅行时间 本文使用SOM完成了海域多目标主动感知 Table 1 Traveling time for different algorithms 任务。仿真实验表明，本文使用的方法为无人机 算法 旅行时间 团队规划出了一条时间最短的平滑路径。通过与 SOM 117.45 其他算法对比，本文使用的SOM算法在解决带 遗传算法 邻域的多旅行商问题时耗时较短。随着最优化理 130.61 蚁群算法 论在机器学习领域的进一步发展，将会进一步降 134.78 低旅行商问题的复杂度。 粒子群优化 135.58 参考文献： 本文在gazebo中搭建了仿真环境，进一步评 估提出算法的可行性。如图10所示，黑色物体代 [1]ATANASOV N.LE NY J.DANIILIDIS K,et al.Decent- 表四旋翼无人机。彩色立方体代表真实世界中的 ralized active information acquisition:Theory and applica- 物体，把模型点云数据处理为八叉树结构，方便 tion to multi-robot SLAM[C]//2015 IEEE International 数理分析，不同颜色代表物体在三维空间中具有 Conference on Robotics and Automation (ICRA).Seattle. 不同的高度，红色最低紫色最高。无人机的初始 USA:2015:4775-4782. [2]GIFFORD C M.WEBB R.BLEY J.et al.A novel low- 位置和目标点随机给出，算法根据环境数据和目 cost,limited-resource approach to autonomous multi-robot 标点的三维坐标规划出最短的路径。在gazebo exploration and mapping[J].Robotics and autonomous sys- 中的仿真结果如图11所示，底部栅格代表仿真模 tems,2010,58(2:186-202 型的分辨率，在给定目标点后，算法为无人机在 [3]BEST G,FAIGL J,FITCH R.Online planning for multi- 三维空间中规划出了一条时间最短的路径，由图 robot active perception with self-organising maps[J]. 中的灰色空心立方体表示。仿真结果进一步验证 Autonomous robots,2018,42(4):715-738. 了算法结果。 [4]BEST G,CLIFF O M,PATTEN T,et al.Dec-MCTS:De-
为了验证无人机数量对结果的影响，本文在 相同的实验条件下改变无人机数量进行测试。实 验结果表明，有限增加无人机数量可以减少总旅 行时间，如图 9 所示。 旅行时间/s 120 125 115 110 105 100 95 2 5 6 7 8 3 4 无人机数量/架 图 9 无人机数量与总旅行时间的关系 Fig. 9 Relationship between the number of UAVs and the total travel time 为了评估本文提出的方法，在相同的场景条 件下使用遗传算法、蚁群算法、粒子群优化算法[15] 进行对比实验，取 20 次实验的平均值，如表 1 所 示。实验结果表明，本文的方法得出的无人机团 队旅行时间较短，可以应用于大规模场景下多目 标群体智能的主动感知问题。 表 1 不同算法的旅行时间 Table 1 Traveling time for different algorithms s 算法 旅行时间 SOM 117.45 遗传算法 130.61 蚁群算法 134.78 粒子群优化 135.58 本文在 gazebo 中搭建了仿真环境，进一步评 估提出算法的可行性。如图 10 所示，黑色物体代 表四旋翼无人机。彩色立方体代表真实世界中的 物体，把模型点云数据处理为八叉树结构，方便 数理分析，不同颜色代表物体在三维空间中具有 不同的高度，红色最低紫色最高。无人机的初始 位置和目标点随机给出，算法根据环境数据和目 标点的三维坐标规划出最短的路径。在 gazebo 中的仿真结果如图 11 所示，底部栅格代表仿真模 型的分辨率，在给定目标点后，算法为无人机在 三维空间中规划出了一条时间最短的路径，由图 中的灰色空心立方体表示。仿真结果进一步验证 了算法结果。 图 10 搭建 gazebo 仿真环境 Fig. 10 Building a simulation environment in gazebo 图 11 gazebo 中的算法测试结果 Fig. 11 Algorithm test results in gazebo 5 结束语 本文使用 SOM 完成了海域多目标主动感知 任务。仿真实验表明，本文使用的方法为无人机 团队规划出了一条时间最短的平滑路径。通过与 其他算法对比，本文使用的 SOM 算法在解决带 邻域的多旅行商问题时耗时较短。随着最优化理 论在机器学习领域的进一步发展，将会进一步降 低旅行商问题的复杂度。 参考文献： ATANASOV N, LE NY J, DANIILIDIS K, et al. Decentralized active information acquisition: Theory and application to multi-robot SLAM[C]//2015 IEEE International Conference on Robotics and Automation (ICRA). Seattle, USA: 2015: 4775−4782. [1] GIFFORD C M, WEBB R, BLEY J, et al. A novel lowcost, limited-resource approach to autonomous multi-robot exploration and mapping[J]. Robotics and autonomous systems, 2010, 58(2): 186–202. [2] BEST G, FAIGL J, FITCH R. Online planning for multirobot active perception with self-organising maps[J]. Autonomous robots, 2018, 42(4): 715–738. [3] [4] BEST G, CLIFF O M, PATTEN T, et al. Dec-MCTS: De- 第 3 期 王华鲜，等：无人机群多目标协同主动感知的自组织映射方法 ·613·
·614… 智能系统学报 第15卷 centralized planning for multi-robot active perception[J]. 2019,14(2:246-253 The international journal of robotics research,2019. OU Weiqi,YIN Hui,XU Hongli,et al.A multi-object 38(2/3):316-337. tracking algorithm based on trajectory reconstruction on [5]FITCH R.ISLER V.TOKEKAR P.et al.Guest editorial: Multi-Egocentric video[J].CAAI transactions on intelli- special issue on active perception[J].Autonomous robots. gent systems,2019,142:246-253. 2018,42(2):175-176. [18]李景灿，丁世飞.基于人工鱼群算法的孪生支持向量 [6]CHEN Shengyong,LI Youfu,KWOK N M.Active vision 机U.智能系统学报，2019,14(6)：1121-1126. in robotic systems:A survey of recent developments[J]. LI Jingcan,DING Shifei.Twin support vector machine The international journal of robotics research,2011, based on artificial fish swarm algorithm[J].CAAI transac- 30(11):1343-1377. tions on intelligent systems,2019,14(6):1121-1126. [7]BAJCSY R.Active perception[J].Proceedings of the [19]张飞，白伟，乔耀华，等.基于改进D*算法的无人机室 IEEE,1988.76(8):966-1005. 内路径规划[).智能系统学报，2019,14(4)：662-669， [8]BAJCSY R,ALOIMONOS Y,TSOTSOS JK.Revisiting ZHANG Fei,BAI Wei,QIAO Yaohua,et al.UAV in- active perception[J].Autonomous robots,2018,42(2): door path planning based on improved D*algorithm[J]. 177-196. CAAI transactions on intelligent systems,2019,14(4) [9]CHARROW B.Information-theoretic active perception for 662-669. multi-robot teams[D].Philadelphia,USA:University of [20]刘建华，刘华平，杨建国，等.测距式传感器同时定位与 Pennsylvania,2015. 地图创建综述).智能系统学报，2015,10(5)：655-662 [10]GIBSON J J.The ecological approach to visual percep- LIU Jianhua,LIU Huaping,YANG Jianguo,et al.A sur- tion[M].New York,USA:Psychology Press,2013 vey of range-only SLAM for mobile robots[J].CAAl [11]PATTEN T,ZILLICH M,FITCH R,et al.Viewpoint transactions on intelligent systems,2015,10(5):655-662. evaluation for online 3-D active object classification[J]. 作者简介： IEEE robotics and automation letters,2016,1(1):73-81 王华鲜，硕士研究生，主要研究方 [12]YAN Zhi,JOUANDEAU N,CHERIF AA.A survey and 向为主动感知与多机器人协作。 analysis of multi-robot coordination[J].International journal of advanced robotic systems,2013,10(12):399. [13]SCHLOTFELDT B,THAKUR D,ATANASOV N,et al. Anytime planning for decentralized multirobot active in- formation gathering[J].IEEE robotics and automation let- ters.2018,3(2):1025-1032. 华容，教授，上海市徐汇区智能交 [14]FAIGL J,HOLLINGER G A.Unifying multi-goal path 通协会理事长，主要研究方向为轨道 planning for autonomous data collection[C]//IEEE/RSJ 交通控制运行、机器人路径规划与多 目标优化研究。发表学术论文30 International Conference on Intelligent Robots and Sys- 余篇。 tems.Chicago,USA:2014. [15]BEKTAS T.The multiple traveling salesman problem:an overview of formulations and solution procedures[]. 0mega,2006,343):209-219. 孙富春，教授，博士生导师，EEE [16]MOHAJER A,BAVAGHAR M.FARROKHI H.Mobil- Senior Member,.国家863计划专家组 成员，中国人工智能学会副理事长，中 ity-aware load balancing for reliable self-organization net- 国人工智能学会智能控制与智能管理 works:multi-agent deep reinforcement learning[J].Reli- 专业委员会副主任兼秘书长，主要研 ability engineering and system safety,2020,202:107056. 究方向为智能控制与机器人、多模态 [17刀欧伟奇，尹辉，许宏丽，等.一种基于Multi-Egocentric视 数据感知、模式识别。主持国家自然 频运动轨迹重建的多目标跟踪算法.智能系统学报， 科学基金5项。发表学术论文200余篇
centralized planning for multi-robot active perception[J]. The international journal of robotics research, 2019, 38(2/3): 316–337. FITCH R, ISLER V, TOKEKAR P, et al. Guest editorial: special issue on active perception[J]. Autonomous robots, 2018, 42(2): 175–176. [5] CHEN Shengyong, LI Youfu, KWOK N M. Active vision in robotic systems: A survey of recent developments[J]. The international journal of robotics research, 2011, 30(11): 1343–1377. [6] BAJCSY R. Active perception[J]. Proceedings of the IEEE, 1988, 76(8): 966–1005. [7] BAJCSY R, ALOIMONOS Y, TSOTSOS J K. Revisiting active perception[J]. Autonomous robots, 2018, 42(2): 177–196. [8] CHARROW B. Information-theoretic active perception for multi-robot teams[D]. Philadelphia, USA: University of Pennsylvania, 2015. [9] GIBSON J J. The ecological approach to visual perception[M]. New York, USA: Psychology Press, 2013. [10] PATTEN T, ZILLICH M, FITCH R, et al. Viewpoint evaluation for online 3-D active object classification[J]. IEEE robotics and automation letters, 2016, 1(1): 73–81. [11] YAN Zhi, JOUANDEAU N, CHERIF A A. A survey and analysis of multi-robot coordination[J]. International journal of advanced robotic systems, 2013, 10(12): 399. [12] SCHLOTFELDT B, THAKUR D, ATANASOV N, et al. Anytime planning for decentralized multirobot active information gathering[J]. IEEE robotics and automation letters, 2018, 3(2): 1025–1032. [13] FAIGL J, HOLLINGER G A. Unifying multi-goal path planning for autonomous data collection[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. Chicago, USA: 2014. [14] BEKTAS T. The multiple traveling salesman problem: an overview of formulations and solution procedures[J]. Omega, 2006, 34(3): 209–219. [15] MOHAJER A, BAVAGHAR M, FARROKHI H. Mobility-aware load balancing for reliable self-organization networks: multi-agent deep reinforcement learning[J]. Reliability engineering and system safety, 2020, 202: 107056. [16] 欧伟奇, 尹辉, 许宏丽, 等. 一种基于 Multi-Egocentric 视 频运动轨迹重建的多目标跟踪算法 [J]. 智能系统学报, [17] 2019, 14(2): 246–253. OU Weiqi, YIN Hui, XU Hongli, et al. A multi-object tracking algorithm based on trajectory reconstruction on Multi-Egocentric video[J]. CAAI transactions on intelligent systems, 2019, 14(2): 246–253. 李景灿, 丁世飞. 基于人工鱼群算法的孪生支持向量 机 [J]. 智能系统学报, 2019, 14(6): 1121–1126. LI Jingcan, DING Shifei. Twin support vector machine based on artificial fish swarm algorithm[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1121–1126. [18] 张飞, 白伟, 乔耀华, 等. 基于改进 D*算法的无人机室 内路径规划 [J]. 智能系统学报, 2019, 14(4): 662–669. ZHANG Fei, BAI Wei, QIAO Yaohua, et al. UAV indoor path planning based on improved D* algorithm[J]. CAAI transactions on intelligent systems, 2019, 14(4): 662–669. [19] 刘建华, 刘华平, 杨建国, 等. 测距式传感器同时定位与 地图创建综述 [J]. 智能系统学报, 2015, 10(5): 655–662. LIU Jianhua, LIU Huaping, YANG Jianguo, et al. A survey of range-only SLAM for mobile robots[J]. CAAI transactions on intelligent systems, 2015, 10(5): 655–662. [20] 作者简介： 王华鲜，硕士研究生，主要研究方 向为主动感知与多机器人协作。 华容，教授，上海市徐汇区智能交 通协会理事长，主要研究方向为轨道 交通控制运行、机器人路径规划与多 目标优化研究。发表学术论文 3 0 余篇。 孙富春，教授，博士生导师，IEEE Senior Member，国家 863 计划专家组 成员，中国人工智能学会副理事长，中 国人工智能学会智能控制与智能管理 专业委员会副主任兼秘书长，主要研 究方向为智能控制与机器人、多模态 数据感知、模式识别。主持国家自然 科学基金 5 项。发表学术论文 200 余篇。 ·614· 智 能 系 统 学 报 第 15 卷
