群无人机动态环境分布式持续覆盖算法

晋一宁， 吴炎烜， 范宁军

(北京理工大学 机电学院，北京 100081)



群无人机动态环境分布式持续覆盖算法

晋一宁， 吴炎烜， 范宁军

(北京理工大学 机电学院，北京 100081)

动态环境具有多变性和不确定性，为将动态环境的不确定性控制在一定范围内，需要群无人机对其进行持续覆盖以便完成感知、监视、侦察等任务. 提出了一种考虑无人机飞行动力学约束的分布式协同覆盖算法，无需先验知识、无需事先进行路径规划. 各无人机独立地根据局部感知和局部通信所获信息进行在线覆盖决策，使整个群无人机系统涌现出持续覆盖行为. 提出的方法通信次数少，仅需邻居无人机的位置信息进行合作，且对无人机的前飞航向没有数量约束. 仿真结果表明，此分布式算法可实现群无人机对动态环境的持续覆盖，算法性能稳定，具有很好的灵活性和可扩展性.

群无人机；持续覆盖； 分布式协同

无人机(unmanned aerial vehicle，UAV)通过装载传感器，可在战场区域中执行监视、侦察、数据收集、目标搜索等任务，无需考虑人员耐受性和伤亡. 而覆盖战场区域是进行上述任务的基础和前提. 由于单架无人机覆盖能力有限，通常需要一群无人机(swarm UAVs)相互协作地执行覆盖任务.

现有的覆盖研究多针对单次覆盖问题，而面对复杂多变的战场区域，单次覆盖已不能满足对信息获取的需求，要对整个区域进行持续、重复的覆盖，以便及时地更新战场信息. 前人常用区域划分法[1-6]来解决多无人机完全覆盖问题，此为集中式控制策略，若有无人机损毁，则需重新进行区域划分和分配. 且Nigam等[7]指出区域划分法不适于无人机数量过多的情况，提出了一种反应式协作策略，虽为分布式控制，但需全局通信来获取所有无人机的位置. 彭辉等[8]提出一种分布式滚动优化法，其信息交换量大、实时性差. 且滚动优化法的计算量会随无人机前飞航向的增多而呈指数性增长，所以文献[9-10]等都假设无人机只有3个前进航向. 而群无人机系统是一类群机器人(swarm robotics)系统，由大量能力有限的无人机个体组成，个体需要在不知道全局信息的情况下，通过局部通信和交互合作完成复杂任务. 所以群无人机系统需要采用基于局部信息的分布式合作法，且由于个体能力的限制，要尽量减少通信量和计算量.

目前，尚无关于群无人机仅通过局部通信实现对动态环境持续覆盖的全分布式协作研究的公开资料. 本文提出一种适用于群无人机的分布式协作方法，核心思路是每个无人机独立地存储一个覆盖决策图，每个时刻仅利用自身传感器采集到的信息和与邻居无人机局部通信获得的邻居无人机位置信息来更新覆盖决策图，并根据图进行在线覆盖决策. 该方法通信次数少，不仅满足飞行动力学约束，且对无人机的前进航向没有数量约束.

1 持续覆盖问题描述

本文以微小型固定翼无人机为研究平台. 在群无人机系统中有n个无人机，用集合U={U1，U2，…，Un，n≥2}表示. 为方便研究覆盖问题，对无人机作如下假设：

① 机载探测传感器：设机载探测传感器中心与无人机几何中心重叠，采用简化的圆盘探测模型来对机载传感器建模，rsen为传感器的探测半径. 也就是说，只要目标区域在传感器探测范围内就被覆盖.

本文要研究的问题可以描述为：由n个无人机组成的群无人机进入目标区域后，在各无人机有限的续航时间ttotal内，持续地对目标区域进行覆盖，无人机仅知道目标区域的地理位置信息和边界信息. 设计一种满足无人机动力学约束的群无人机分布式覆盖协作方法，使目标区域内不能留有任何一块区域长时间未被覆盖，即使目标区域内所有栅格的两次被覆盖时间间隔最短，可以表示为

(1)

式中tij为目标区域内任意栅格G(i，j)(1≤i≤M，1≤j≤N)从上一次被覆盖到当前时刻所经过的时间.

2 持续覆盖策略

为便于各无人机记录和传递目标区域的覆盖信息、实现合作，采用离散信息图的形式对各类所需信息进行建模. 每个图的数据结构都是一个与栅格数量对应的M×N的矩阵.

2.1 区域价值图

区域价值图Q(t)代表覆盖该区域的收益. 无人机在飞行途中建立并更新一种信息素图χ(t)，以此记录自己覆盖过的地方. 信息素浓度越高的区域，代表无人机覆盖的次数越多，其存在的不确定性越低，覆盖该区域的收益也越低. 对于无人机Uk，信息素图中栅格G(i，j)的信息素值更新如下式所示

(2)

式中：ξkij为信息素增益值；η为信息素衰减因子；Γ(pk(t))为 无人机Uk在位置pk(t)时机载传感器对目标区域的覆盖域.

当无人机Uk有通信邻居无人机时，可以与邻居无人机交换各自存储的信息素图，再结合自己的信息素图按下式进行更新.

(3)

然后再根据式(4)用信息素值计算区域价值图Q(t).

(4)

2.2 分散航向图

根据虚拟力理论[8]，假设当无人机质心之间的距离小于等于rrep时，无人机之间会产生大小相同、方向相反的虚拟排斥力F. 定义Uk的排斥邻居无人机的集合为

(5)

式中rrep为排斥力产生距离，rrep≥2vΔt. 为了简化计算，此处设虚拟排斥力F的值为固定的单位斥力.

t时刻，无人机Uk的优选航向角φkpref(t)的更新原则为

(6)

分散航向图H(t)记录的是t时刻，无人机从当前位置飞向某个栅格G(i，j)中心点的航向角与优选航向角的契合度以及最大转弯角的约束信息. 于是，本文设计了一个分段函数作为分散航向值计算函数为

(7)

分散航向图的建立目的是使群无人机分散开来覆盖更广的区域，并避免短期内的重复覆盖，可同时实现一定程度的避碰，但若完全实现避踫，还需进一步研究.

2.3 任务倾向性图

当有多个无人机飞向同一目的地时，在集中式控制方法中，将离目的地最近的无人机分配去执行相应的覆盖任务会得到更高的效费比. 换个角度来看，上述任务分配可以转化为无人机倾向于覆盖离自己更近的栅格. 因此，本文提出一种基于距离的间接任务分配方式，设计一个基于距离的任务倾向性图D(t). 对于无人机Uk，任务倾向性值的计算方法为

(8)

式中：dk→ij(t)为t时刻无人机Uk从当前位置飞向栅格G(i，j)的距离；dmax为覆盖区域对角线的长度.

2.4 覆盖决策图

用一个M×N的矩阵C(t)表示无人机的覆盖决策图，决策图里的每个数值代表无人机飞向每个栅格的概率. 对于无人机Uk，栅格G(i，j)的覆盖决策变量的计算方法如下

(9)

式中：ωq为区域价值权重；ωh为分散航向权重；ωd为任务倾向性权重.

在群无人机执行区域覆盖任务时，每个决策时刻，各无人机都根据局部感知和局部通信所得信息更新自身的覆盖决策图C(t)，再采用贪婪策略，直接选择决策变量值最大的栅格作为下一步覆盖的目标栅格. 对于无人机Uk有

(10)

式中Gk(x，y)为覆盖决策值最高的栅格.

3 仿真结果与比较

本文用Matlab来验证提出的分布式协作算法用于执行持续覆盖任务的有效性. 算法性能以目标区域中每个时刻所有栅格最大未覆盖时长tMET、整个覆盖过程中的最大未覆盖时长tTMET、整个覆盖过程中的平均未覆盖时长tAMET作为评价指标，根据式(11)进行计算.

(11)

式中T(t)为未覆盖时长全局监测图. 对于栅格G(i，j)，其计算方法如下，

(12)

式中Γ(P(t))为 群无人机的机载探测传感器对目标区域的覆盖域.

第1组仿真，分别对群无人机中有5，10，15个无人机的情况进行了仿真，所得结果如图1所示. 图中折线表示目标区域中tMET随时间的变化，横线表示平均未覆盖时长tAMET，五角星为整个覆盖过程中的最大未覆盖时长tTMET.

由图1可以看出，目标区域中tMET上升到一定的值后总会下降，表明群无人机通过协作完成了对目标区域的持续、无盲区覆盖，并保证覆盖区域中不会有长期未被覆盖的点. 另外，目标区域内工作的无人机个数越多，tAMET越小，表明各点被覆盖的频率越高.

图2展示了图1中n=10的群无人机在t=[0 min，3 min]时段的航迹. 图下方的箭头所指处为各无人机的初始位置，箭头指向为初始航向，虚线框为需要覆盖的目标区域. 从图2中各无人机的飞行航迹可看出，引入无人机最大转弯角约束后，无人机的覆盖航迹平滑、在转弯时无突变尖锐的拐角，所有航迹都物理可飞.

第2组仿真，分别针对不同的群无人机规模进行了50次仿真，每次仿真中，各无人机的初始位置与航向都是随机的，仿真的统计结果如图3所示.

由图3可以看出，虽然初始位置与初始航向随机化，但不论群无人机规模大小，tAMET和tTMET都在有限的范围内波动，表明本文提出的覆盖控制算法性能稳定. 另外，无人机个数越多，未覆盖时长波动越小，充分证明了所提算法能有效地协同大规模的群无人机进行持续覆盖.

另外，统计了上述仿真中无人机之间的通信次数如表1所示.

表1 群无人机通信次数

从表1可以看出，由于本文所提算法采用的是间歇式局部通信，因此通信量远少于需要全局通信的算法.

4 结 论

提出了一种将未覆盖时长和飞行动力学约束结合考虑的分布式协作方法，使群无人机实现了对动态目标区域的持续不间断覆盖. 此算法不需要先验知识，无需无人机事先进行路径规划，也不需要进行全局通信，只需要无人机进行局部感知和与邻居无人机进行局部通信，只用交换邻居无人机的位置信息，通信次数少，算法简单，可实现在线决策. 并且，由于算法是全分布式的，无人机可以自由地加入或退出覆盖任务而不影响整个系统的运行，也能实现不同速度无人机之间的协作，因此具有良好的可扩展性和灵活性. 通过仿真表明此算法性能稳定，在一定的无人机数量下，可以将各栅格的未覆盖时长控制在一定的范围内，使目标区域中不存在长期未被覆盖的点. 而且此算法能有效地协同大规模的群无人机进行持续覆盖.

[1] 薛颂东，曾建潮.群机器人研究综述[J].模式识别与人工智能，2008，21(2):177-185.

Xue Songdong， Zeng Jianxhao. Swarm robotics: a survey[J]. Pattern Recognition and Artificial Intelligence， 2008，21(2):177-185. (in Chinese)

[2] Sahin E， Winfield Alan F T. Special issue on swarm robotics[J]. Swarm Intelligence， 2008，2(2-4):69-72.

[3] Sivakumar A， Tan C K Y. UAV swarm coordination using cooperative control for establishing a wireless communications backbone[C]∥Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems. Toronto, Canada, 2010:1157-1164.

[4] Mohsen Mehdizade. A decomposition strategy for optimal coverage of an area of interest using heterogeneous team of UAVs[D]. Quebec， Canada: Concordia University， 2012:77-100.

[5] 唐胜景，宋祥，郭杰，等.基于遗传算法的无人机模糊-积分控制器设计[J].北京理工大学学报，2013，33(12)：1274-1278.

Tang Shengjing, Song Xiang, Guo Jie, et al. Fuzzy-integration controller design of UAV based on genetic algrithm[J]. Transactions of Beijing Institute of Technology, 2013,33(12):1274-1278. (in Chinese)

[6] 关震宇，杨东晓，李杰，等.基于Dubins路径的无人机避障规划算法[J].北京理工大学学报，2014，34(6)：570-575.

Guan Zhenyu, Yang Dongxiao, Li Jie, et al. Obstacle avoidance planning algrithm for UAV based on Dubins path[J]. Transactions of Beijing Institute of Technology, 2014,34(6):570-575. (in Chinese)

[7] Nigam N， Kroo I. Control and design of multiple unmanned air vehicles for a persistent surveillance task[J]. AIAA， 2009(1852):1-19.

[8] 彭辉，沈林成，朱华勇.基于分布式模型预测控制的多无人机协同区域覆盖[J].航空学报，2010，31(3):593-601.

Peng Hui， Shen Lincheng， Zhu Huayong. Multiple UAV cooperative area search based on distributed model predictive control[J]. Acta Aeronautica Et Astronautica Sinica， 2010，31(3):593-601. (in Chinese)

[9] 吴文超，黄长强，宋磊.不确定环境下的多无人机协同搜索航路规划[J].兵工学报，2011，32(11):1337-1342.

Wu Wenchao， Huang Changqiang， Song Lei. Cooperative search and path planning of multi-unmanned air vehicles in uncertain environment[J]. Acta Armamentarii， 2011，32(11):1337-1342. (in Chinese)

[10] Spears D， Kerr W， Spears W. Physics-based robot swarms for coverage problems[J]. International Journal on Intelligent Control and Systems， 2006，11:24-40.

(责任编辑：刘雨)

Distributed Cooperative Control of Swarm UAVs for Dynamic Environment Persistent Coverage

JIN Yi-ning， WU Yan-xuan， FAN Ning-jun

(School of Mechatronical Engineering， Beijing Institute of Technology， Beijing 100081， China)

In order to control the uncertainty of dynamic environment into a certain scope, it is necessary for swarm UAVs to continuously cover the environment so as to achieve some perception, watch and spy task. A distributed collaborative coverage method was proposed based on the kinematic constraints of UAV, doing without prior knowledge and advanced path planning. Each UAV made its coverage decision online only based on the information gotten from the real-time local sensing and the local communications, making the swarm UAVs have persistent coverage ability. The information needed to be exchanged was very little, and only position information needed to be exchanged within local inter-UAV communication, which made the algorithm simpler and more practical. The simulation results show that, the distributed collaborative coverage method can adapt swarm UAVs for persistent coverage to dynamic environment, the performance of the algorithm is stable, flexible and scalable.

swarm UAVs; persistent coverage; distributed cooperation

2014-11-15

北京理工大学基础研究基金资助项目(20120242009)

晋一宁(1986—)，女，博士生，E-mail:yn.jin@foxmail.com；吴炎烜(1981—)，男，博士，讲师，E-mail:alexwyx@bit.edu.cn.

范宁军(1949—)，男，博士，教授，E-mail:ningjunfan@bit.edu.cn.

V 279; TP 18

A

1001-0645(2016)06-0588-05

10.15918/j.tbit1001-0645.2016.06.007