«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2020, Vol. 15 Issue (3): 609-614  DOI: 10.11992/tis.201908022
0

引用本文  

王华鲜, 华容, 刘华平, 等. 无人机群多目标协同主动感知的自组织映射方法[J]. 智能系统学报, 2020, 15(3): 609-614. DOI: 10.11992/tis.201908022.
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. DOI: 10.11992/tis.201908022.

基金项目

国家自然科学基金项目(U1613212);上海市“联盟计划”项目(LM201756)

通信作者

刘华平. E-mail:hpliu@tsinghua.edu.cn

作者简介

王华鲜,硕士研究生,主要研究方向为主动感知与多机器人协作;
华容,教授,上海市徐汇区智能交通协会理事长,主要研究方向为轨道交通控制运行、机器人路径规划与多目标优化研究。发表学术论文30余篇;
孙富春,教授,博士生导师,国家杰出青年,IEEE Senior Member,国家863计划专家组成员,中国人工智能学会副理事长,中国人工智能学会智能控制与智能管理专业委员会副主任兼秘书长,主要研究方向为智能控制与机器人、多模态数据感知、模式识别。主持国家自然科学基金5项。发表学术论文200余篇

文章历史

收稿日期:2019-08-19
无人机群多目标协同主动感知的自组织映射方法
王华鲜 1, 华容 1, 刘华平 2, 赵怀林 1, 孙富春 2     
1. 上海应用技术大学 电气与电子工程学院,上海 201499;
2. 清华大学 智能技术与系统国家重点实验室,北京 100084
摘要:针对主动感知问题多为单机器人系统的主动视觉问题,本文提出了基于自组织映射特征网络的异构机器人主动感知框架,为无人机团队规划出遍历所有目标所需时间最短的平滑路径。首先把多目标主动感知场景建模为带邻域的多旅行商问题,然后使用自组织映射网络为无人机团队规划出旅行时间最短的闭环轨迹,最后利用三阶贝塞尔曲线对轨迹做平滑处理。仿真结果和对比实验表明,本文的方法在多目标主动感知的应用中有着较好的效果。
关键词多机器人系统    主动感知    旅行商问题    自组织映射网络    路径规划    异构机器人    贝塞尔曲线    路径平滑    
Self-organizing feature map method for multi-target active perception of unmanned aerial vehicle systems
WANG Huaxian 1, HUA Rong 1, LIU Huaping 2, ZHAO Huailin 1, SUN Fuchun 2     
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.
Key words: 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]。虽然单机器人系统具有相对较强的性能,但有些任务本身可能过于复杂,甚至不可能完成,例如空间上相互独立的任务[5]。在多机器人系统中,异构机器人可以针对不同层次的任务进行专门化设计,可以应用于复杂的感知任务中。

现有的主动感知方法是反应性的,不受历史状态的影响,是一个马尔可夫过程。状态感知的质量会影响算法性能,可以通过选择最优感知位置来改进[26]。这通常是一个短视问题,从控制策略上来说是贪婪的[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来解决这一难题。

Download:
图 1 多目标主动感知场景 Fig. 1 Multi-target active perception scene
1.3 自组织映射特征网络

图2所示,SOM是一种竞争性的双层神经网络且在输出层的样本空间中形成新的拓扑结构[12-16]。在SOM的训练过程中,多个神经元通过竞争协作完成对输入样本的模式分类。网络中的输入神经元 ${x_i}$ 与输出神经元 ${y_j}$ 通过权值 ${\omega _{ij}}$ 相连,同时,近邻的输出神经元之间也通过权值相连[3]。SOM的输出结果保持自组织的拓扑结构,映射到多维的向量空间中。

Download:
图 2 典型的SOM结构 Fig. 2 Typical SOM structure diagram
2 问题建模

图1中给出了异构机器人的主动感知框架。无人机团队中一部分通过搭载的传感器设备搜索区域的目标,另一部分执行快速遍历的主动感知任务[17]。任务目标是在满足旅行预算的前提下为机器人团队 $R = \left\{ {{r_1},{r_2}, \cdot \cdot \cdot ,{r_R}} \right\}$ 规划一个由路径点序列 $X = \left\{ {{x_1},{x_2}, \cdot \cdot \cdot ,{x_i}} \right\}$ 组成的平滑路径,使其能够监视环境中的每一个目标 $N = \left\{ {{n_1},{n_2},} \right. \left.{ \cdot \cdot \cdot ,{n_N}} \right\}$ ,并使得团队的旅行时间 ${T_{\rm{sum}}} = {t_{{r_1}}} + {t_{{r_2}}} + {t_{{r_3}}} + \cdot \cdot \cdot + {t_{{r_R}}}$ 最短。考虑到实际环境中,被感知目标并非无体积的质点,而且机器人上一般搭载有感知设备,如雷达、深度相机等。因此目标nN是一个圆形的感知区域 ${s_N} \in {R}$ ,其感知半径为k。无人机只需要访问到感知区域的任意位置,即可执行捕获任务 $\left\| {{x_i} - {n_N}} \right\| \leqslant k$ 。这是一个k-MTSP问题,目标函数为最小化旅行时间,即

$ \min {\rm{mize}} T(X)=\displaystyle \sum\limits_{i=1}^{n} T\left(X_{i}\right) $

SOM规划出的平滑路径都有旅行消耗 ${c_i} \geqslant 0$ ,定义为无人机在路径 ${X_i}$ 上的时间。机器人团队有总的旅行预算时间 ${b_i} \geqslant 0$ 。当SOM为机器人团队规划出一次路径时,会计算出当前轮次的旅行消耗,选择获胜机器人 ${R}_{r}$ ,即

$ R_{r} \leftarrow \arg \min \left(\dfrac{c_{q}}{b_{q}}\right), \quad c_{i} \leqslant b_{i}。$
3 感知路径生成

图3给出了应用于大规模场景多目标感知的SOM训练结构。

Download:
图 3 SOM训练结构 Fig. 3 SOM training structure

定义SOM输入层的兴奋神经元邻域为

$ {T_{j,I(x)}} = \exp \left( - \dfrac{{S_{j,I(x)}^2}}{{2{\sigma ^2}}}\right) $ (1)

式中I(x)是获胜神经元的索引[18]。学习增益 $ \mathrm{\sigma } $ 随着时间的推移而减少,即

$ \sigma(t)=\sigma_{0} \exp \left(-t / \tau_{\sigma}\right) $ (2)

拓扑邻域更新了获胜神经元的权重,同时邻域内的其他神经元权重也进行了更新,但幅度较小,以此保障具有输入空间映射结构的训练样本向目标逼近。权重更新方式为

$ \Delta \omega_{j i}=\eta(t) \cdot T_{j, I(x)}(t) \cdot\left(x_{i}-\omega_{j i}\right) $ (3)

式中: $\eta(t) $ 为依赖于时间的学习率 , $\eta(t)= \eta_{0} \exp \left(-t / \tau_{\eta}\right)$

图4给出了某训练阶段示意图。本文SOM的输入样本是群体目标的感应位置 ${s_N} \in {R}$ ,输出结果是经过训练后的路径点 $ v=\{{v}_{1},{v}_{2},\dots {v}_{k}\} $ ,其中k是当前网络中神经元的数量,多轮迭代后即为无人机团队的路径点序列 $ {X}_{i} $ 。为了避免网络训练的结果陷入局部最优,感应位置组成的样本空间以随机的顺序输入给SOM,每一轮的迭代都是SOM对输入空间的一个自适应过程[19]

Download:
图 4 SOM训练过程 Fig. 4 SOM training process

图5所示,SOM输出的拓扑结构中,与目标位置s最佳匹配的神经元是拓扑结构中距离目标欧氏距离最近的点。然后在点 $ {p}_{s} $ 处创建获胜神经元 $ {v}^{*} $

Download:
图 5 获胜神经元的几何关系 Fig. 5 Geometry of the winner neuron

可行的迭代方法是线段(ps,sn)中的某一个点逐渐趋近于邻域长度k。该几何迭代过程有两种情况:1)如果 $ {p}_{s} $ 已经位于领域内,那么只需要在 $ {p}_{s} $ 处创建获胜神经元,网络不需要进行自适应的过程;2)如果 $ {p}_{s} $ 位于感知区域外部,那么需要按照标准SOM的方法进行迭代。标准的SOM学习可以看作神经元朝向 $ {s}_{p} $ 的移动同时产生一个新的神经元使v变为 $ {v}' $ , 即

$ v^{\prime}=v+\mu f(\sigma, d)\left(v^{*} s_{p}-v\right) $ (4)

式中: $ \mu $ 为学习率; $ f\left(\sigma ,d\right) $ 是邻域函数; $ \sigma $ 是网络的学习增益; $ d $ $ \nu $ $ {\nu }^{*} $ 的欧氏距离。邻域函数定义了周围被调整的竞争性神经元,并且具有SOM中针对 TSP 进行调整的标准形式:

$ f(\sigma ,d) = \left\{ \begin{array}{l} \operatorname{e} ^\frac{{ - {d^2}}}{{{\sigma ^2}}},\;\quad d < 0.2M \\ 0,\;\quad {\text{其他}} \\ \end{array} \right. $ (5)

在每轮训练结束后,学习率根据

$ \sigma {\rm{ = }}\left( {{\rm{1 - }}\alpha } \right)\sigma $ (6)

逐渐减少, $ \alpha $ 是增益减少比率。此外,在每一个学习阶段之后,都会进行一个环再生,以去除所有竞争失败的神经元。

如果所有获胜神经元都明显接近各自的,从而使其在每个神经元的k邻域内,则SOM的迭代过程将终止。然后,连接获胜神经元的光滑曲线序列是主动感知问题的可行解决方案。如果网络收敛速度不够快,可以在最大迭代轮次之后终止学习过程,并且可以通过遍历环并使用与获胜神经元关联的 $ {s}_{p} $ 来构建可行的解决方案。对于已用的学习速率 $ \mu =0.5 $ ,网络收敛的同时对SOM的初始学习增益按照 $ \sigma =12.41n+0.6 $ ,增益递减率 $ \alpha =0.1 $ ,网络在不到100 个学习轮次内稳定。

为了避免无人机飞行过程中大角度转弯带来的不稳定性,对SOM生成的路径进行三阶分段贝塞尔平滑处理[20]

$ {X\left(\tau \right)=B}_{0}{(1-\tau )}^{3}+3{B}_{1}\tau {(1-\tau )}^{2}+\\ 3{B}_{2}{\tau }^{2}\left(1-\tau \right)+{B}_{3}{\tau }^{3} $ (7)

式中: $ \tau \in \left[0,1\right] $ ${{B}_{0}{\text{、}}B}_{3}$ 为每段分段Bezier曲线的起点和终点的位置; $ {B}_{1}$ ${B}_{2} $ 决定了每段分段Bezier曲线起点和终点处的切线。无人机的闭环轨迹曲线由多个分段Bezier曲线组成,为保证轨迹连续,无人机闭环轨迹中相邻两个分段贝塞尔曲线 ${X}_{i-1}{\text{、}}{X}_{i}$ 的路径点需满足 $ {B}_{3}^{i-1}={B}_{0}^{i} $ 。闭环轨迹中第i-1个分段Bezier曲线起点的切线 $ {t}_{a}^{i-1} $ 和第i个分段Bezier曲线终点的切线 $ {t}_{b}^{i} $ ,切线 $ {t}_{a}^{i-1} $ 的长度 $ {l}_{a}^{i-1} $ 和切线 $ {t}_{b}^{i} $ 的长度 $ {l}_{b}^{i} $ 分别为

$ t_a^{i - 1} = B_1^{i - 1} - B_0^{i - 1},\quad t_b^i = B_3^i - B_2^i\\ $ (8)
$ l_a^{i - 1} = \left\| {t_a^{i - 1}} \right\|,\quad l_b^i = \left\| {t_b^i} \right\| $ (9)

无人机群体轨迹平滑满足:

$ l_a^{i - 1}t_b^i = l_b^it_a^{i - 1} $ (10)
4 实验结果及分析

本文进行了一系列仿真实验来验证提出的算法效果。所有实验均使用C++编程,并在装有2.5 Hz频率下i5-7300HQ中央处理器的操作系统上进行仿真,仿真结果数据用MATLAB2016b进行处理。由于单次实验结果不具有代表性,本文在相同条件下进行了20次实验,以此来分析SOM在大规模场景下多目标主动感知任务的效果。无人机的水平初始速度 $v = 5\;{\rm{m }}/ {\rm{s}}$ ,目标数为31,竖直与水平方向的加速度为0,无人机近似地认为是在二维平面内匀速运动。场景中群体目标的感知邻域半径k为5 m,SOM的训练次数为100,学习率为0.5。

图6展示了SOM算法的迭代过程。初始阶段,把异构无人机团队测得的目标位置坐标作为初始样本输入到SOM网络中进行训练,最终经过70~80次的迭代,算法收敛,得出最终结果。由于SOM是一种竞争性神经网络,所以不同轮次的获胜神经元及兴奋神经元邻域是不同的,这就造成了目标覆盖率并不是线性单调函数,如图7所示。相对应的每一轮迭代结果的无人机旅行时间也不是迭代轮次的单调函数,自适应过程的旅行时间会产生随机振荡,但是在过程中会趋于稳定,如图8所示。

Download:
图 6 SOM迭代过程 Fig. 6 SOM iterative process
Download:
图 7 单次实验的旅行时间 Fig. 7 Traveling time of a single experiment
Download:
图 8 单次实验的目标发现率 Fig. 8 Target discovery rate of a single experiment

为了验证无人机数量对结果的影响,本文在相同的实验条件下改变无人机数量进行测试。实验结果表明,有限增加无人机数量可以减少总旅行时间,如图9所示。

Download:
图 9 无人机数量与总旅行时间的关系 Fig. 9 Relationship between the number of UAVs and the total travel time

为了评估本文提出的方法,在相同的场景条件下使用遗传算法、蚁群算法、粒子群优化算法[15]进行对比实验,取20次实验的平均值,如表1所示。实验结果表明,本文的方法得出的无人机团队旅行时间较短,可以应用于大规模场景下多目标群体智能的主动感知问题。

表 1 不同算法的旅行时间 Tab.1 Traveling time for different algorithms

本文在gazebo中搭建了仿真环境,进一步评估提出算法的可行性。如图10所示,黑色物体代表四旋翼无人机。彩色立方体代表真实世界中的物体,把模型点云数据处理为八叉树结构,方便数理分析,不同颜色代表物体在三维空间中具有不同的高度,红色最低紫色最高。无人机的初始位置和目标点随机给出,算法根据环境数据和目标点的三维坐标规划出最短的路径。在gazebo中的仿真结果如图11所示,底部栅格代表仿真模型的分辨率,在给定目标点后,算法为无人机在三维空间中规划出了一条时间最短的路径,由图中的灰色空心立方体表示。仿真结果进一步验证了算法结果。

Download:
图 10 搭建gazebo仿真环境 Fig. 10 Building a simulation environment in gazebo
Download:
图 11 gazebo中的算法测试结果 Fig. 11 Algorithm test results in gazebo
5 结束语

本文使用SOM完成了海域多目标主动感知任务。仿真实验表明,本文使用的方法为无人机团队规划出了一条时间最短的平滑路径。通过与其他算法对比,本文使用的SOM算法在解决带邻域的多旅行商问题时耗时较短。随着最优化理论在机器学习领域的进一步发展,将会进一步降低旅行商问题的复杂度。

参考文献
[1] 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. (0)
[2] GIFFORD C M, WEBB R, BLEY J, et al. A novel low-cost, limited-resource approach to autonomous multi-robot exploration and mapping[J]. Robotics and autonomous systems, 2010, 58(2): 186-202. DOI:10.1016/j.robot.2009.09.014 (0)
[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. DOI:10.1007/s10514-017-9691-4 (0)
[4] BEST G, CLIFF O M, PATTEN T, et al. Dec-MCTS: Decentralized planning for multi-robot active perception[J]. The international journal of robotics research, 2019, 38(2/3): 316-337. (0)
[5] FITCH R, ISLER V, TOKEKAR P, et al. Guest editorial: special issue on active perception[J]. Autonomous robots, 2018, 42(2): 175-176. DOI:10.1007/s10514-018-9695-8 (0)
[6] 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. DOI:10.1177/0278364911410755 (0)
[7] BAJCSY R. Active perception[J]. Proceedings of the IEEE, 1988, 76(8): 966-1005. DOI:10.1109/5.5968 (0)
[8] BAJCSY R, ALOIMONOS Y, TSOTSOS J K. Revisiting active perception[J]. Autonomous robots, 2018, 42(2): 177-196. DOI:10.1007/s10514-017-9615-3 (0)
[9] CHARROW B. Information-theoretic active perception for multi-robot teams[D]. Philadelphia, USA: University of Pennsylvania, 2015. (0)
[10] GIBSON J J. The ecological approach to visual perception[M]. New York, USA: Psychology Press, 2013. (0)
[11] 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. DOI:10.1109/LRA.2015.2506901 (0)
[12] 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. DOI:10.5772/57313 (0)
[13] 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. DOI:10.1109/LRA.2018.2794608 (0)
[14] 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. (0)
[15] BEKTAS T. The multiple traveling salesman problem: an overview of formulations and solution procedures[J]. Omega, 2006, 34(3): 209-219. DOI:10.1016/j.omega.2004.10.004 (0)
[16] 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. DOI:10.1016/j.ress.2020.107056 (0)
[17] 欧伟奇, 尹辉, 许宏丽, 等. 一种基于Multi-Egocentric视频运动轨迹重建的多目标跟踪算法[J]. 智能系统学报, 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. DOI:10.11992/tis.201709003 (0)
[18] 李景灿, 丁世飞. 基于人工鱼群算法的孪生支持向量机[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. DOI:10.11992/tis.201905025 (0)
[19] 张飞, 白伟, 乔耀华, 等. 基于改进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. DOI:10.11992/tis.201803031 (0)
[20] 刘建华, 刘华平, 杨建国, 等. 测距式传感器同时定位与地图创建综述[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. DOI:10.11992/tis.201403017 (0)