持续监视问题多无人机协同搜索策略*

王嘉博，刘 莉，王 祝，许 萌

(北京理工大学宇航学院，北京 100081)

0 引言

无人机对目标空间执行持续监视任务[1]广泛应用于气象监测、地形测绘、战术侦察和地外探索等领域[2]，典型的侦察无人机包括“全球鹰(Global Hawk)”、“捕食者(Predator)”和“折叠式扫描鹰(ScanEagle Compressed Carriage，SECC)”等。然而，在现实任务环境中，由于持续监视任务的复杂性和多样性，单架无人机独自完成持续监视任务变得十分艰难，因此多无人机协同搜索成为一种有效的解决方案[3－4]。多无人机协同搜索策略研究正逐渐成为研究热点。

本研究从持续监视问题的基本概念入手，针对贪婪搜索策略和分布式协议搜索策略两种基准策略[5]在执行持续监视任务时因重复搜索和频繁转场导致搜索代价无功消耗的不足，将模糊聚类方法引入协同搜索策略，提出了基于模糊c均值聚类的多无人机协同搜索策略(FCM搜索策略)。仿真结果表明，FCM搜索策略具有搜索效率高与稳定性强的优点。

1 持续监视问题描述

持续监视问题可描述为对某一群体或地点保持密切观察。对敌军进行频繁照相是持续监视问题的经典应用。持续监视问题要求对目标空间长时间频繁甚至连续不断的进行观察覆盖，使得对目标空间内不同区域进行两次搜索的时间间隔最短。持续监视问题相对于其它搜索问题，是一种更为复杂的搜索问题。其特点是目标在搜索空间出现的位置与时间均未知且不确定，要求对所有单元格持续均匀的进行搜索。为研究搜索策略方便，将持续监视问题作如下简化:

1)将需要持续监视的物理目标空间定义为二维几何空间;

2)对目标空间用近似单元格分解方法进行网格划分;

3)为避免“漏扫”，假设每个单元格的中心与无人机传感器的中心重合时，传感器投影能够覆盖该单元格;

4)为每个单元格定义一个关联寿命(Associated Age)，代表从上一次被搜索到目前所经过的时间。图1描述了三架无人机执行持续监视任务的示意图。

持续监视问题的目标可转化为所有单元格的最大关联时间最小化问题(如式(1)所示)，即不能让目标空间内留有任何一块区域长时间未被搜索。

图1 持续监视任务问题描述示意图

其中Ai为第i个单元格的关联寿命。为了提高协同搜索策略的工程实用性，将无人机动力学约束引入协同搜索策略，研究二者之间的耦合关系对协同搜索任务的影响。

2 FCM搜索策略

FCM搜索策略是一种基于空间缩减和空间分解的搜索策略。其基本思想是将模糊数学的方法引入多无人机协同搜索领域，将目标区域的单元格以关联寿命和空间位置为特征矢量进行聚类划分，减少了无人机转场次数，降低了搜索代价的无功消耗，提高了搜索性能。

2.1 FCM搜索策略描述

目前常用的搜索策略大多数为基于搜索信息的方法，无人机以单元格每个时刻的搜索信息作为搜索标志量进行决策。FCM搜索策略采用与文献[1]相同的搜索信息——当量时间作为搜索的标志量。当量时间的表达式如式(2)所示。

其中:νj表示第j个单元格的当量时间，ω0为权重系数(在单无人机两单元一维模型中，取 ω0=－1/Vmission)，δ1j为无人机到第j个单元格的距离。引入当量时间后，无人机在进行搜索决策时，首先计算每个单元格的当量时间，然后选择当量时间最大的单元格作为目标单元格进行搜索。

FCM搜索策略是指无人机在获取目标区域内单元格的关联寿命和当量时间信息后，通过聚类划分对目标空间进行缩减。然后将缩减后的空间进行二次聚类划分，完成目标空间的分解。将每个聚类分配给一架无人机，每架无人机根据单元格每一时刻的当量时间进行搜索，从而减少转场所带来的搜索代价的无功消耗，提高搜索效率。FCM搜索策略的流程如图 2所示。

图2 FCM搜索策略流程图

1)初始化:目标空间网格化分解[1，5]，设置无人机数量，初始化无人机位置。

2)获取(或更新)单元格的关联寿命。

3)以单元格关联寿命为特征值，对所有单元格进行模糊c均值聚类划分，将所有单元格划分为高关联寿命单元格聚类和低关联寿命单元格聚类，删除低关联寿命单元格聚类，缩减搜索目标空间。

4)以单元格的空间位置为观测样本的特征矢量，以无人机数量为聚类数，对高关联寿命聚类的单元格进行第二次模糊c均值聚类划分;根据无人机与二次聚类划分后的单元格聚类中心的空间相对位置，分配一架无人机就近对某一聚类进行搜索。

5)无人机计算其隶属聚类内所有单元格的当量时间信息，根据基本搜索策略对其隶属聚类内单元格进行搜索。FCM搜索策略的示意图如图3所示。

图3 FCM搜索策略示意图

2.2 两次聚类过程

目标空间内单元格的状态信息是FCM协同搜索算法进行聚类划分和搜索决策的重要依据。X={x1，x2，…，xn}⊂Rs为目标空间内单元格的状态信息集。其中 n为目标空间内单元格的数量，xk=(xkAge，xkx，xky)T为第k个单元格状态信息的特征矢量。其中，xkAge为第k个单元格当前时刻的关联寿命，(xkx，xky)为第k个单元格中心点的空间位置。FCM搜索策略将分别以单元格的关联寿命和空间位置为特征矢量，进行两次聚类划分。

2.2.1 对所有单元格进行聚类划分

第一次聚类划分的样本集合为所有单元格X1={x1，x2，…，xn}⊂ Rs，其中 n 为目标空间内单元格的数量，特征量xk=xkAge为第k个单元格的关联寿命。对给定样本集合即所有单元格按照一定的准则用模糊聚类算法产生X1的c1划分。其中c1=2，即划分为高关联寿命单元格和低关联寿命单元格两类聚类。表征聚类性能的目标函数为:

其中，样本xk(第k个单元格)与第i类聚类中心pi之间的距离度量的一般表达式定义为:

聚类的准则为取Jm(U，P)的极小值:

求解得到使得Jm(U，P)取得极小值的μik和pi的值:

由式(6)可求得高低关联寿命单元格的最佳模糊分类矩阵U*和两个聚类中心P*。如此便可将低关联寿命单元格从所有单元格中滤除，仅对具有高关联寿命的单元格进行任务分配，有助于提高搜索的针对性。

2.2.2 对高关联寿命单元格进行聚类划分

尽管第一次聚类划分滤除了目标空间内的低关联寿命单元格，但如果将所有无人机都部署在整个缩减后的目标空间内执行搜索任务，将导致无人机在搜索中多次途经低关联寿命单元格而降低搜索效率。为解决这一问题，FCM搜索策略对高关联寿命单元格按照单元格中心的空间位置进行第二次聚类划分，将其划分为与无人机数量相等的若干个聚类，完成任务空间的分解。

第二次聚类划分的样本集合为经过第一次聚类划分后所得到的高关联寿命单元格聚类X2={xhigh1，xhigh2，…，xhighm}⊂Rs，其中m为当前高关联寿命单元格数量，聚类特征矢量为 xhighk=(xhighk，X，xhighk，Y)T。xhighk，X，xhighk，Y分别表示第 k 个高关联寿命单元格中心位置的X坐标和Y坐标。按照与第一次聚类划分相类似的方法产生X2的c2划分。其中c2为无人机数量。

2.3 无人机搜索任务分配

经过两次聚类划分后，得到iUAV类(个)聚类。随后部署离聚类中心距离最近的无人机对隶属于该聚类的高关联寿命单元格进行搜索，即:

其中:pi为第i个聚类的聚类中心，pUAV，j为第j个无人机当前的空间位置。多无人机协同搜索任务便可简化为每架无人机对隶属于一个聚类的若干高关联寿命单元格单独执行搜索任务。

2.4 考虑动力学约束的FCM搜索策略

为了使搜索策略更具实用性，需要在设计搜索策略时考虑无人机的动力学(即最小转弯半径)约束。无人机动力学会在以下方面对搜索策略产生影响:

1)无人机搜索航迹;

2)无人机与单元格的距离。

图4 动力学约束对无人机搜索航迹的影响示意图

如图4所示，在搜索航迹方面，不考虑无人机最小转弯半径约束的情况下，默认无人机的可用过载无穷大，可以瞬间完成转弯，无人机的飞行航迹是一条直线段。而考虑无人机最小转弯半径约束的情况下，无人机的航迹是由一条直线段和一段或两段圆弧段组成，其中圆弧段的半径不小于无人机的最小转弯半径

无人机考虑动力学约束时的最短可行航迹可通过几何关系建立，航迹长度可以通过几何关系解析得到。根据Dubins模型，任意具有初始航向角和目标航向角的两点间，最短轨迹由一条直线段和两条半径与最小转弯半径相等的弧线段组成。文中在Dubins模型的基础上稍作简化，不设置目标点的航向角要求，原因如下:

1)不设置目标点的航向角，可以进一步缩短搜索航迹的长度，从而使无人机更快的飞抵目标点;

2)不设置目标点的航向角，可以减少无人机转弯的次数，使搜索航迹更具有可飞性。

修改后的无人机最短可飞航迹就变成由一条直线段和一条半径与最小转弯半径相等的弧线段组成(如图5所示)。

图5 最短可飞航迹示意图

通过上述最短可飞航迹模型得到最短可飞航迹的航迹长度lmin后，搜索策略的搜索标志量——当量时间的表达式可修正为 νj=max{(Aj+ ω0lmin1，j)，0}。

3 数值仿真与效能分析

为了证明FCM搜索策略的高效性，与两种基准策略:贪婪搜索策略[6](Greedy Search Strategy)和多无人机反应式搜索策略[5](Multi-agent Reactive Policy，MRP)针对持续监视任务进行仿真，然后根据仿真结果对各自搜索效能进行对比分析。假设搜索目标空间的范围为2km×2km，无人机数量为4架，单元格边长为200m，无人机速度为Vmission=50m/s。三种多无人机搜索策略在1000s仿真时间内的仿真搜索航迹如图6～图8所示，三种搜索策略暂不考虑动力学约束。

图6 Greedy策略4架无人机搜索航迹仿真结果

图7 MRP策略4架无人机搜索航迹仿真结果

从上述三种搜索策略的搜索航迹图中可以看出，两种基准搜索策略(Greedy策略和MRP策略)在搜索航迹上有明显的重叠，并且无人机在执行搜索任务时大范围转场，导致搜索性能降低。而FCM搜索策略通过对目标区域的模糊聚类划分，缩减目标区域，减少了搜索航迹的重叠以及大范围的转场，节约了搜索代价。

对比三种多无人机协同搜索策略的搜索性能。任务初始条件为:搜索目标空间的范围为2km×2km，单元格边长为200m，无人机速度为Vmission=50m/s，分别对无人机数量为2架、4架和6架的情况进行测试。每种情况分别进行50次试验，在1000s仿真时间内，所有单元格的最大关联寿命的变化情况如图9～图11所示。

图8 FCM策略4架无人机搜索航迹仿真结果

图9 2UAV三种策略最大关联寿命仿真结果对比

如表1所示，在无人机数量相等的情况下FCM搜索策略的搜索性能优于其它两种基准搜索策略。另外，Greedy搜索策略和MRP搜索策略在任务条件相同的情况下，随无人机数量的增加，最大关联寿命反而逐渐增大，FCM搜索策略的最大关联寿命随无人机数量的增加而减少。说明这两种基准搜索策略的协同性能较差，FCM搜索策略的在协同性能方面优于两种基准搜索策略。

图10 4UAV三种策略最大关联寿命仿真结果对比

图11 6UAV三种策略最大关联寿命仿真结果对比

表1 三种多无人机搜索策略在不同无人机数量情况下的最大关联寿命

上述仿真结果表明，FCM搜索策略性能优于其它两种基准搜索策略。为提高FCM搜索策略的工程实用性，将无人机动力学约束引入FCM搜索策略。任务初始条件为:搜索目标空间的范围为2km×2km，单元格边长为200m，无人机速度为Vmission=50m/s，无人机数量为6架，在300s仿真时间内，搜索航迹如图 12所示。

图12 引入无人机动力学约束6架无人机FCM搜索策略航迹仿真结果

从图12中可以看出，引入无人机动力学约束后，无人机的搜索航迹没有尖锐的拐点，所有航迹均为物理可飞航迹。所以，引入动力学约束的FCM策略在兼顾良好搜索性能的同时，也有良好的工程实用性。

表2给出了FCM搜索策略在不同无人机最小半径情况下的单元格最大关联寿命。随着无人机最小转弯半径的增大，单元格的最大关联寿命也随之增大，搜索性能下降。

表2 FCM搜索策略在不同无人机最小转弯半径情况下的最大关联寿命

4 结论

文中针对持续监视问题，对多无人机协同搜索策略开展研究。针对常见多无人机协同搜索策略的不足，将模糊数学的理论引入协同搜索领域，提出了基于模糊c均值聚类的多无人机协同搜索策略，克服了常见多无人机协同搜索策略由于重复搜索以及频繁转场导致搜索代价无功消耗的不足，提高了搜索性能。将无人机动力学约束引入协同搜索策略，使搜索策略更具实用价值。通过数值仿真与常见多无人机协同搜索策略的比较研究结果表明，FCM搜索策略具有搜索性能高与稳定性强的优点。

[1]Nigam N.Control and design of multiple unmanned air vehicles for persistent surveillance[D].Stanford University，2009.

[2]彭辉.分布式多无人机协同区域搜索中的关键问题研究[D].长沙:国防科学技术大学，2009.

[3]Phillip R，Chandler M P，Steven R，et al.Distributed control for multiple uavs with strongly coupled tasks[C]//AIAA Guidance，Navigation，And Control Conference And Exhibit，2003.

[4]Chandler P R.Cooperative control of a team of uavs for tactical missions[C]//AIAA 1st Intelligent Systems Technical Conference，2004.

[5]Baum M L，Passino K M.A search theoretic approach to cooperative control for uninhabited air vehicle[C]//AIAA Guidance，Navigation，And Control Conference And Exhibit，2002.

[6]田菁，陈岩，沈林成.不确定环境中多无人机协同搜索算法[J].电子与信息学报，2007，29(10):2325－2328.