无人机多机协作探索煤矿灾变环境算法

刘 栋，童敏明，路红蕊

(中国矿业大学 信息与控制工程学院，江苏 徐州 221008)

(*通信作者电子邮箱726770366@qq.com)

无人机多机协作探索煤矿灾变环境算法

刘 栋*，童敏明，路红蕊

(中国矿业大学 信息与控制工程学院，江苏 徐州 221008)

(*通信作者电子邮箱726770366@qq.com)

针对目前煤矿灾变环境下救援机器人探索效率低的问题，提出了一种使用无人机多机协同探索煤矿灾变环境的改进型边界探索算法。该算法在效用值边界探索算法的基础上增加了对无人机导航角度因素的考虑，同时引入分散度函数作为评判机制来构建目标函数，并使用蚁群算法对该目标函数进行求解。最后利用Matlab软件在栅格化地图上进行了仿真实验。实验结果表明，和效用值边界探索算法相比，改进型边界探索算法减少了探测过程中的重复覆盖和拥挤现象，缩短了探测时间，降低了约30%的能量消耗，提高了无人机多机系统的整体探索效率。

无人机多机；边界探索；分散度函数；环境侦测；探索效率

0 引言

煤矿灾害事故发生后，快速有效地进行抢险救援是减少人员伤亡和财产损失的重要工作。由于灾后矿井环境未知，在灾害抢险救援的决策指挥中，关键是需要快速获取灾后矿井的环境信息，采用无人机(Unmanned Aerial Vehicle, UAV)进入矿井进行环境侦测可以较好地解决这一问题[1]。环境侦测的无人机不仅可以探测灾后矿井的环境信息，如瓦斯、一氧化碳等有毒气体，为救护队伍的安全提供信息，还可搜寻被困或受伤矿工的信息。

单无人机在获取和处理信息方面存在效率低、鲁棒性差、环境侦测存在盲区等问题[2]。为了解决这个问题，本文拟研究多个无人机的协同探索方法。无人机多机(multiple Unmanned Aerial Vehicles, multi-UAV)协作探索按照控制结构不同，主要可以分为两大类[3]：一类是集中式协作探索；另一类是分布式协作探索。分布式协作探索的每个无人机都拥有独立的控制器，使得系统具有较好的容错性和鲁棒性，所以本文将分布式协作方式运用于多无人机系统来探索矿井灾变环境。文献[4]建立的机器人内部传感器的效率模型为减函数，机器人之间通过Voronoi图的划分来实现对未知环境的协作探索；文献[5]提出一种基于分布式模型预测控制的多无人机协同探测策略，通过结合纳什最优和粒子群优化算法，能大幅度降低算法迭代过程中的计算量；文献[6]提出了基于效用值的协作探索算法。这些方法在一定程度上使移动机器人的拥挤问题得以解决，但总的来说上述方法考虑的因素都还不够全面，在对环境的探测过程中会存在小区域遗漏和重复覆盖问题，且探测时间和能耗都达不到理想要求。为此，本文提出一种新的改进型边界探索算法(以下简称：改进型算法)，同时将距离和角度因素考虑进去，并引入分散机制，这样可以使无人机之间更好地协作获取灾后复杂矿井环境的信息，为安全救灾提供保障。

1 基于效用值的边界探索算法

1.1 栅格化地图

栅格是一个单位长度的正方形，又称之为单元格。一幅二维地图可以划分为许多大小相同的栅格，其中：障碍物区域设置栅格占用值为1，用黑色表示；空闲区域设置栅格占用值为0，用白色表示；未知区域设置栅格占用值为0.5，用灰色表示。环境探测的二维地图可以通过矩阵来描述，由于矿井灾变环境未知，地图的矩阵初始值均设为0.5。无人机在侦测过程中，若传感器检测到未知区域的单元格，其值将会更新：1表示障碍物，0表示无障碍物。与未知区域单元格相邻的自由栅格均属边界栅格，其占用值为0。本文把和边界栅格的距离值小于d的部分均归属为边界区域，该区域可表示为T={t|‖t-s‖≤d,s∈Sf}。其中：Sf为边界栅格的集合；d为无人机的尺寸，其取值为一个单元格的大小。

1.2 基于效用值的边界探索算法

基于效用值的边界探索算法(以下简称：效用值算法)的探索目的是使效用值最大化，也就是为无人机指派飞行代价小、信息增益大的边界。

假设无人机i移动到边界j的代价是cij，那么效用值

uij=dj-cij

(1)

若信息增益dj越大，无人机飞行时的移动代价cij越小，则效用值uij就会越大。可以从所有无人机的效用值中寻找出最大的效用值，获得具有最大效用值的组合：

〈i′,j′〉arg max{uij}

(2)

然后将边界j′指派给无人机i′。更新其他边界的信息增益及效用值，重复前面的最大化过程，使每一个无人机都被分配相应的任务。

这种仅考虑距离与信息增益的效用值导航算法不能解决探测过程中的重复覆盖问题[7-8]。该算法为得到最大的效用值，无人机偏向于飞行至相对开阔的边界。在探索前期，无人机能够获得较大的信息增益；而探索后期，由于环境中的未知区域被分隔成了零散的小块状，无人机若要逐一地探索，就会造成重复覆盖，致使探索效率降低。

2 改进型边界探索算法

下面将对上述效用值算法进行改进，在保持该算法优点的同时，达到既使无人机能迅速有序地在复杂的灾变环境中分散开来，又能减少重复覆盖现象的目的。

若不计边界宽度，则无人机向边界移动的过程可用一条曲线来表示。设曲线两端点处分别为A和B，则边界在无人机坐标系中可以表示为：

T={(r,θ)|r=r(θ),a≤θ≤b}

(3)

其中：端点A对应角度a，端点B对应角度b。

2.1 吸引度函数的构建

2.1.1 距离吸引度函数

无人机以距离近的边界为目标来构建距离吸引度函数，该函数表示如下：

(4)

式中:V0、r1、r2为常数。r1=Rmax，2Rmax≤r2≤4Rmax，Rmax表示无人机传感器的检测半径。

如果边界单元格与无人机目前位置间的连线存在障碍物，Vr的值将会变小，这意味着无人机飞行至该位置将会消耗更多的能量和时间。将距离较近的栅格视为目标点，可使复杂环境下飞行的多个无人机快速分散开来。但无人机快速分散时，总会存在一些未知区域未被探测到。此时，无人机要继续探测这些未知区域，必定会经过之前检测过的部分区域，从而导致重复覆盖。

2.1.2 角度吸引度函数

为使无人机在分散过程中快速又有序地移动，增加了角度吸引度函数[9]。从A点沿着边界逆时针方向绕过Δθ大小的角度。若绕过的夹角超过边界终点B，则B为锚点。选择锚点的目的是为了使边界能够完全被覆盖到。若Δθ太大，目标点距边界的起始位置过远，会导致部分边界不能被传感器检测出来；若Δθ太小，目标点距边界起始位置过近，传感器的覆盖范围将会存在与障碍物相交的部分，导致某些区域将无法被探测到。通过实验我们发现，当Δθ的值处于45°～60°范围时，能够体现出较好的效果。

(5)

(6)

式中：K为常数；前一项Vk表示在同一边界之内运算，后一项为不同边界之间的运算。

将以上距离和角度因素综合在一起，则总的吸引度评价函数可描述为：

V(t)=β×Vr+(1-β)×(Vθ+Vk)

(7)

式中β为权重因子，一般令β=0.5。

2.2 分散度函数

分散度函数可以对无人机之间的相互位置进行估计[10]，引入分散度函数，使无人机之间存在一定的相互排斥，避免多个无人机出现相互拥挤的情况。如果一块区域没有无人机，那么分散度值比较高；若分散度值过小，说明该区域太拥挤，无人机之间需适当避让。

边界区域T全部单元格的初始分散度值设置为U(t)=U0。若无人机在边界栅格t′位置处，邻近栅格的分散度值则会变小，无人机相互间的排斥作用越大，此时其他无人机应该选择避让。单元格t处分散度函数的值更新为如下式(8)：

Unew(t)=Uold(t)-α×(1-‖t-t′‖/Rmax)

(8)

式中α=(0.2～0.8)U0。当‖t-t′‖>Rmax，无需更新分散度值。根据分散度值的大小，可以指示该区域无人机的飞行航迹，从而有效避免无人机出现拥挤。

2.3 算法流程

综合考虑上述分析的吸引度与分散度因素对无人机飞行航迹的影响，可将目标函数描述为如下表达式：

L=∑V+γ×U

(9)

其中γ为参数，用来调节无人机之间的分散程度。求出目标函数L的最大值，便可得到有效指示无人机探测未知矿井环境的最佳方案。这是一个组合优化问题，本文使用了蚁群算法[11-12]对该问题求解。

设排列Π表示所有可能的无人机任务分配方案的集合,其元素π(i)表示将目标点ti指派给无人机i。算法流程如下：

1)确定边界栅格的集合T。

2)初始化Lmax，令其为0；计算出边界栅格对无人机的吸引度V。

3)对分散度函数进行初始化U(t)=U0，L0=0。

4)按照排列Π为无人机i分配栅格π(i)，更新目标函数如下：

Li=Li-1+V(i,π(i))+γ×U(π(i))

(10)

5)更新分散度函数U(t′)。

6)若分配未结束，重复4)、5)步。

7)若L>Lmax，则Lmax=L，最佳任务分配方案的排列Πbest=Π。

8)继续进行迭代运算，直至找到无人机的最佳任务分配方案。

3 仿真实验与分析

本文使用Matlab搭建仿真环境，建立的栅格地图大小为60×72。比较β=1和β=0.5两种情况下无人机多机协作探索的性能表现。当β=1时，表示效用值算法；β=0.5时，表示改进型算法。假设无人机的传感器探测范围为Rmax=10，其他参数设为：Δθ=π/4，V0=200，K=20/π，U0=80，α=0.5U0，γ=1。无人机的初始位置设为地图中央，无人机的尺寸可以视为一个质点，且无人机之间的相互位置预先已知，在任务执行过程中能够保持通信。本文用3架无人机(分别编号为1、2、3)来模拟矿井灾变环境下无人机对未知环境的探测情况。

3.1 仿真结果

基于效用值算法和改进型边界探索算法的导航轨迹图分别如图1和图2所示，将3架无人机的初始位置均设置在地图中央。在初始位置处时，各无人机均只能检测到传感器所能探测的有限范围。

3.2 实验结果分析

效用值算法和改进型算法的时间与覆盖率的关系对比如图3所示，其中覆盖率用来描述已探测区域的面积与地图整个面积之比。从图3可看出：两种算法在前期的探测进度差别不大；但在后期，同样的覆盖率，效用值边界探索算法所需的时间明显长于改进型算法，其原因在于效用值边界探索算法后期出现了重复覆盖现象，这与上述仿真实验探测分析吻合。同时，对全部地图的侦测，改进型算法所花费的时间明显少于效用值算法，证明了重复覆盖将会降低探索效率。

能量消耗与覆盖率关系对比如图4所示。其中，无人机向正向方向飞行需耗费10个单位的能量，向对角方向飞行需耗费14个单位的能量[13]，拐弯45°、90°、135°、180°分别耗费4、6、8、10个单位的能量。通过图4可以看出，改进型算法所消耗的能量相对效用值算法降低了约30%，这是由于探索后期效用值算法中出现的无人机路径重复覆盖会导致更多的能量消耗。

图1 效用值边界探索算法仿真结果Fig. 1 Simulation results of boundary exploration algorithm of utility value

图2 改进型算法仿真结果Fig. 2 Simulation results of improved algorithm

图5是两种算法飞行距离方差对比。无人机飞行距离的方差可反映出任务分配是否合理[14]。飞行距离方差可通过以下公式计算：

(11)

(12)

式中:n是无人机的个数，本文取n=3；si表示第i个无人机飞行的距离。各无人机飞行的距离相差越大，方差就越大，这意味着算法对多无人机系统任务分配不合理。从图5可以看出，在探测中、后期，效用值算法中各无人机之间的飞行距离存在很大差异。中期存在的较大方差是图1(d)中3号无人机飞行至下方较宽边界所致，后期则是由无人机之间的任务分配不合理、无人机的探索路线出现了较大的重复覆盖所致。在整个探测过程中改进型边界探索算法不存在很大的方差，说明各无人机之间的任务分配相对合理。在本文中，由于构建的地图较大，且方差是3个无人机飞行距离偏差的平方和，所以，方差在10 000以内属于正常现象。

图3 时间与覆盖率的关系对比Fig. 3 Relationship comparison of time and coverage

图4 能量消耗与覆盖率的关系对比Fig. 4 Relationship comparison of energy consumption and coverage

图5 飞行距离方差对比Fig. 5 Comparison of flight distance variance

4 结语

本文提出使用多无人机协作探索煤矿灾变环境，对无人机多机系统使用改进型算法解决了探测过程中小块未知区域的遗漏问题，减少了探测过程中的重复覆盖和拥挤现象。相比效用值算法，改进后的算法缩短了探测时间，降低了能量的消耗，且各无人机间的任务分配更为合理，提高了矿井灾变环境下未知区域的探测效率。

虽然改进后的算法提高了探测效率，但是还存在一定的不足，很多现实的客观因素没有考虑进去，如各传感器产生的噪声误差、无人机之间数据交换丢包误差、外界环境导致的非线性误差都会对实验有一定的影响，如何将这些误差融入算法中进行滤波与补偿会在以后的工作中进行重点研究。

References)

[1] 田子建,高学浩,张梦霞.基于改进人工势场的矿井导航装置路径规划[J].煤炭学报,2016,41(S2):589-597. (TIAN Z J, GAO X H, ZHANG M X. Path planning based on the improved artificial potential field of coalmine dynamic target navigation [J]. Journal of China Coal Society, 2016, 41(S2): 589-597.)

[2] 高云园,郭云飞,韦巍.协作多机器人用于未知环境完全探测和地图构建[J].仪器仪表学报,2007,28(7):1259-1264. (GAO Y Y, GUO Y F, WEI W. Coordinated multi-robots for complete exploration and map-building in unknown environment [J]. Chinese Journal of Scientific Instrument, 2007, 28(7): 1259-1264)

[3] 张民强,宋建梅,薛瑞彬.通信距离受限下多无人机分布式协同搜索[J].系统工程理论与实践,2015,35(11):2980-2986. (ZHANG M Q, SONG J M, XUE R B. Multiple UAVs cooperative search under limited communication range [J]. Systems Engineering — Theory & Practice, 2015, 35(11):2980-2986)

[4] GURUPRASAD K R, GHOSE D. Multi-Agent search strategy based on centroidal Voronoi configuration [C]// ICRA 2010： Proceedings of the IEEE International Conference on Robotics and Automation. Piscataway, NJ: IEEE, 2010:3550-3555.

[5] 彭辉,沈林成,朱华勇.基于分布式模型预测控制的多UAV协同区域搜索[J]. 航空学报,2010,31(3):593-601. (PENG H, SHEN L C, ZHU H Y. Multiple UAV cooperative area search based on distributed model predictive control [J]. Acta Aeronautica et Astronautica Sinica, 2010, 31(3): 593-601.)

[6] STACHNISS C. Coordinated multi-robot exploration [J]. IEEE Transactions on Robotics, 2009, 21(3): 376-386.

[7] YAMAUCHI B. Frontier-based exploration using multiple robot [C] // AGENTS ’98: Proceedings of the 2nd International Conference on Autonomous Agents. New York: ACM, 1998: 47-53.

[8] 陈海,何开锋,钱炜祺.多无人机协同覆盖路径规划[J].航空学报,2016,37(3):928-935. (CHEN H, HE K F, QIAN W Q. Cooperative coverage path planning for multiple UAVs [J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(3): 928-935.)

[9] 胡中华.基于智能优化算法的无人机航迹规划若干关键技术研究[D].南京：南京航空航天大学,2011:21-23. (HU Z H. Research on some key techniques of UAV path planning based on intelligent optimization algorithm [D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2011: 21-23.)[10] 王芳.基于量子蚁群算法的多无人机协同航迹规划研究[D].哈尔滨：哈尔滨工业大学,2015:57-59. (WANG F. Collaborative path planning of UAVs based on quantum ant colony algorithm [D]. Harbin: Harbin Institute of Technology, 2015: 57-59.)

[11] STÜTZLE T, DORIGO M. ACO Algorithms for the Quadratic Assignment Problem [M]. Maidenhead, UK: McGraw-Hill Ltd., 1999: 5-18.

[12] 杨华江.求解未知环境下多无人机任务自组织的蚁群算法研究[D].长沙：国防科学技术大学,2007:33-37. (YANG H J. Research on ant colony algorithm for self-organization of UAVs’ mission in unknown environment [D]. Changsha: National University of Defense Technology, 2007: 33-37.)

[13] MEI Y, LU Y-H, LEE C S G, et al. Energy-efficient mobile robot exploration [C]// ICRA 2006: Proceedings of the 2006 IEEE International Conference on Robotics and Automation. Piscataway, NJ: IEEE, 2006: 505-511.

[14] 孙小雷,齐乃明,董程,等.无人机任务分配与航迹规划协同控制方法[J].系统工程与电子术,2015,37(12):2772-2776. (SUN X L, QI N M, DONG C, et al. Cooperative control algorithm of task assignment and path planning for multiple UAVs [J]. Systems Engineering and Electronics, 2015, 37(12): 2772-2776.)

This work is partially supported by “the 13th Five-Year Plan” National Key Research and Development Program of China (2016YFC0801808).

LIUDong, born in 1991, M. S. candidate. Her research interests include artificial intelligence, signal processing.

TONGMinming, born in 1956, Ph. D., professor. His research interests include artificial intelligence, data analysis and processing, image processing.

LUHongrui, born in 1991, M. S. candidate. Her research interests include artificial intelligence, image processing.

Algorithmforexploringcoalminedisasterenvironmentbymulti-UAVcooperation

LIU Dong*, TONG Minming, LU Hongrui

(SchoolofInformationandControlEngineering,ChinaUniversityofMiningandTechnology,XuzhouJiangsu221008,China)

Focusing on the low efficiency of the rescue robot in the coal mine disaster environment, a new improved boundary exploration algorithm based on multiple Unmanned Aerial Vehicles (multi-UAV) was proposed. Based on the utility value boundary exploration algorithm, the flight angle parameter of UAV was considered, and the distribution function was introduced as a judgment mechanism to construct the objective function. Finally, the ant colony algorithm was used to solve the objective function. Simulation experiments were carried out on a rasterized map with Matlab software. The simulation results show that the improved boundary exploration algorithm can reduce the phenomenon of repeated coverage and crowding, shorten the detection time, meanwhile the energy required by UAV is reduced by about 30%, thus improving the overall exploration efficiency of multi-UAV system.

multiple Unmanned Aerial Vehicle (multi-UAV); boundary exploration; distribution function; environment detection; exploration efficiency

TP242.6

A

2017- 02- 20;

2017- 04- 05。

“十三五”国家重点研发计划项目(2016YFC0801808)。

刘栋(1991—)，女，湖南岳阳人，硕士研究生，主要研究方向：人工智能、信号处理； 童敏明 (1956—)，男，浙江龙游人，教授，博士，主要研究方向：人工智能、数据分析与处理、图像处理； 路红蕊 (1991—)，女，河南濮阳人，硕士研究生，主要研究方向：人工智能、图像处理。

1001- 9081(2017)08- 2401- 04

10.11772/j.issn.1001- 9081.2017.08.2401