不确定环境下的多无人机协同搜索航路规划

吴文超，黄长强，宋磊，唐上钦，白壬潮

(1.空军工程大学 工程学院，陕西 西安710038;2.空军装备部，北京100843)

利用无人机(UAV)执行侦察任务在众多领域都得到了广泛应用，如对敌区目标情况进行侦察监视，在公海、沙漠或山区展开搜索营救以及对矿藏的资源勘察等。相对于有人驾驶飞机，UAV 成本低，可操纵性好，尤其适合于执行危险的任务［1］。由于单架UAV 在信息收集方面的局限性，多架UAV 协同执行复杂搜索任务吸引了越来越多的关注［2-3］。一些穷举覆盖航路规划模型，如Zamboni 搜索方法已经得到了发展应用［4-6］。然而该方法缺乏灵活性，如在设计某地区的UAV 森林火灾侦察路线时，不能对该区域的湖泊以及其他无林地带进行规避，在载油有限和时间紧张的情况下，将影响到对其他更有价值区域的侦察活动。文献［7］中提出的搜索算法可以对整个环境展开遍历搜索，但没有考虑UAV 的机动限制和搜索环境的动态特性。如UAV的物理机动性能会限制其最小转弯半径，而在大部分穷举搜索算法中，允许UAV 向任何方向运动［8］。此外，任务时间和机载燃油的限制可能不允许UAV完全覆盖整个环境，从而需要对目标存在概率较高的特定区域进行重点侦察。文献［9］对UAV 的协同搜索展开了研究，UAV 在搜索过程中一定程度上可以避开已知区域，但是其算法无法保证对禁飞区实现完全回避。文献［10］基于遗传算法设计了UAV 的侦察航路，其研究是在假设目标位置已知情况下进行的，在环境中的目标分布信息很少的情况下，应用受到了限制。本文主要针对不确定环境下的多UAV 协同搜索问题展开研究，所谓不确定环境指的是在该环境中关于目标的分布是有限的(甚至没有)先验信息。

1 协同搜索的问题描述

一种典型的UAV 协同搜索在线规划和飞行控制框架如图1所示。它包括上层决策(任务规划)和由传感器、跟踪控制器和飞行器本体组成的底层控制2 部分。UAV 接收地面站发送的任务，同时借助本机传感器或它机传感器(通过数据链)实时更新环境信息，进行航路规划产生参考飞行航迹，而后跟踪控制器根据UAV 的动力学模型产生激励输入信号，控制UAV 沿参考轨迹飞行。

与相互独立控制的单架UAV 相比，多架UAV协同搜索能够提供更有效的侦察能力。多架UAV在不确定环境中进行协同搜索时，一般需要满足以下原则［11-12］:

1)在条件允许的情况下覆盖尽可能多的区域。

2)为了提高搜索效率，应对环境中的无回报区域(环境信息完全已知区域)尽可能进行规避，而对环境中目标存在概率较大的区域进行重点侦察。

3)满足UAV 机动限制要求，在数据通讯延迟和编队中的某架UAV 出现故障时不影响其他UAV的协同搜索任务。

4)保证UAV 飞行安全。

需要说明:当对环境信息完全不确定的情况下应当尽可能的进行区域覆盖，以求获得尽可能多的目标信息，而当存在部分先验已知信息时，需要对目标存在概率很小的区域进行规避，对目标存在概率较大的区域进行重点侦察。所以第1)、2)条只是应用的前提条件不同，并不矛盾。第3)条是从应用角度提出的，要求得到的路径具有物理可行性，并能够适应突发事件的发生。第4)条是从安全角度提出的，由于政治、军事或地理方面的原因，UAV 在搜索过程中要保证彻底避免进入禁飞区。另外由于UAV 可以在不同高度下航行，因此本文不考虑UAV之间的碰撞规避问题。

根据上述原则，本文将环境划分为目标信息未知环境，已知环境和禁飞区，并对这3 种区域区别对待:UAV 主要针对未知环境展开搜索;UAV 应当尽量避免对已知环境进行搜索(但在受到转弯限制的情况下可以经过);UAV 必须完全避开禁飞区。下面就路径决策算法设计以及针对3 种区域的不同对策设计展开研究。

2 协同搜索航路规划

2.1 环境模型

本文使用笛卡尔栅格识别地图描述环境，每一栅格被赋予一个值代表UAV 关于该区域目标分布的感知能力。设环境E 为一个Lx×Ly的有界区域，将UAV 在t=kT 时刻对于(x，y)坐标处的目标分布的不确定性能力表示为η(x，y，k)，且满足η(x，y，k)∈［0，1］.η(x，y，k)值越大，表示的不确定性越高，如果η(x，y，k)=1，表示UAV 在t 时刻完全不知道目标在单元(x，y)的分布情况。

2.2 UAV 模型

假定所有UAV 以定常速度v 运动，θmax为UAV物理操纵性能限制最大转弯角，UAV 的运动数学模型如下:

当某架UAV 经过某区域(x，y)时，有

式中:p 为机载传感器对目标的探测能力。如果对某单元多次搜索，η(x，y，k)趋向于0.

2.3 路径决策算法

UAV 使用识别地图储存关于环境的不确定知识，通过数据融合算法载入UAV 传感器，随着识别地图不断更新，航路点决策函数利用地图确定搜索特定环境区域的值，并且产生航路导引每架UAV 进行搜索。这种航路应该考虑到UAV 的操纵限制，即首先要求产生的航路物理可行，然后利用回报函数定义一种控制问题(该回报函数表征探索目标的收益)，最终选择一条可产生最大回报的航路。算法设计如下:

首先将路径规划问题时间离散化，即只允许UAV 在离散时间间隔T 内做出决策。假定UAVi 在时刻t=kT 的位置为pi(k)，将pi(k+1)的可能位置离散化为m 个点，每个点的位置可以表示为(k+1)，j=1，2，…，m，则UAVi 在时刻t=kT 的所有可能点的位置可以表示为如下集合:(k+1)={p1i(k+1)，…(k+1)，…(k+1)}UAV 从pi(k)运动到下一位置pi(k+1)的距离为dt，并且应满足±θm的角度范围限制。考虑到UAV 之间的数据传输延迟，UAVi 的开始q 个位置，pi(1)，pi(2)，…，pi(q)需要提前做出选择。当UAVi 在时刻t 位于位置pi(k)时，它已经决定了下面的q 个位置:pi(k+1)，pi(k+2)，…，pi(k+q).当UAV 到达pi(k)后，它开始选择位置pi(k+q+1)，将在时刻t=k+q+1 到达。只考虑UAV 3 种航路选择状态:左转θmax，直飞，右转θmax，即m 值取3，当q=3 时的航路搜索树如图2所示。

3 搜索回报函数

协同航路搜索的关键是设计一个搜索回报函数，对每条可行路径的回报值进行评估。根据前面提出的协同航路规划方法，每架UAV 使用回报函数J 选择它的搜索航路:

式中:J1，J2，J3为航路选择点的对应回报标准;ωi为相应的权重，0≤ωi≤1，且为重要性因子，γ≥1.收益标准的优先性通过调整权重ωi实现，航路选择点的重要性通过调整γ 来体现。如果UAVi 在时刻t=kT 选择第j∈［1，2，…，m］条路径，则J1(i，j，k)，J2(i，j，k)分别计算如下:

图2 3 步航路搜索树示意图Fig.2 Illustration of recursive 3-step planning tree

式中:(x，y)为UAVi 沿第j 条航路飞行的航路点;η(x，y;k)为UAVi 在时刻k 关于点(x，y)的不确定值。从(7)式和(8)式可以看出，J1(i，j，k)表示当前位置pi(k)与(k-1)之间不确定性减少的程度，J2(i，j，k)表示(k)，(k)，…(k)的平均不确定度。

UAV 之间通过数据链传输实现信息共享，在UAV 相互之间距离很近，运动方向大致相同或相反的情况下容易出现航路重叠。为避免出现这种情况，将其他UAV 视为软障碍，运用一种人工势场算法使一定距离范围内的其他UAV 对UAVi 施加综合抗力Fi(k)，使UAVi 从(k+q+1)中选择航路点pi(k+q+1)，实现航路规避。

在时刻k 由其他所有UAV 作用到UAVi 上的综合抗力可以表示为

其中:

式中:Fi(k)为在时刻t=kT 由相邻UAV 作用到UAVi 上的综合抗力;Rij为UAVi 与UAVj 的距离;Rij为对应的单位向量。k1取值对应于距离Rij为0时的抗力大小。设计参数μ ＞0，对应于抗力随距离增加而减少的速率。Rmax、βmax、φmax分别为UAVj 与UAVi 之间产生抗力作用的最大允许距离、最大允许角度和最大允许方位角之差。如图3所示。

式中:k2为非负参数;αi(j，k)为综合抗力Fi(k)与(k+q+1)中每一可行路径的方位差。从协同的观点来看，显然应该选择具有最小αi(j，k)的航路。

将(6)式标准化，有

Jn为标准化代价函数，计算如下

图3 UAV 抗力产生条件示意图Fig.3 Sketch of rivaling force conditions between UAVs

4 禁飞区回避决策设计

针对禁飞区回避问题一种可能的方法是将禁飞区内的搜索回报函数设定为最小值。但是这并不能保证UAV 不会进入禁飞区。如图4中当UAV 以航向角θ=90°飞到节点b2时，受最大转弯角的限制，当可选节点均位于禁飞区时，UAV 将无法避免进入禁飞区。下面介绍一种新的解决办法，以θmax=45°为例进行说明。

解决的思路是在UAV 要选择的位置还没有进入禁飞区时提前做出选择，当pi(k+q+1)与禁飞区的边界距离小于1 个步长dt 的距离时，如图4阴影部分所示，UAV 开始从b1，b2，b3三个位置中做出选择。图4中UAV 从a1进入b2时，由于受到转弯限制，UAV 无法避开禁飞区，因此b2为不可行点，即使b2点具有比b1和b3更高的收益也必须放弃，而此时b1和b3为可行点，UAV 可分别到达点c1和c7，展开下一步搜索。需要注意的是当UAV 从b1和b3的正下方进入时，这2 点又都变成了不可行点，因此判断某点是否可行点取决于该点的位置和UAV 进入该点的角度。针对图4中的矩形禁飞区进一步分析可发现，当x1≤xb≤x2并且y1- dt≤yb＜y1时，如果(xb，yb)处UAV 的航向角为90°，则该点为不可行点，航向角为45°时则该点为可行点。同理可对阴影框的其他部分进行分析。为了保证下一步搜索时UAV 不会进入禁飞区，将所有位于禁飞区内的选择点不论航向角大小均列为不可行点。

设M={(xi，yi)，θi}为阴影区内的所有点和所有航向角的集合;Mf为阴影区内所有可行点和可行航向角的集合，则在图4中Mf应满足(14)式～(21)式:

需要说明的是，(14)式～(21)式只针对图4.随着禁飞区位置和形状的不同，Mf会有所变化，需要根据具体情况分析，但分析策略类似。

UAV 整个搜索程序如下:

1)任务参数初始化。

2)for k=1 to n.

3)if pi(k+q+1)∈E.

4)if (pi(k+q+1)，θi(k+q+1))∉M.

5)计算pi(k+q+1)的m 个可能位置处的回报函数J，选择J 值最大的航路。

6)else 根据pi(k+q+1)的m 个可能位置是否满足Mf中可行点的条件从中选取m'个可行位置和对应的可行航向角，选择J 值最大的航路。

7)end if.

8)else 执行转弯程序，使UAV 回到环境中。

9)end if.

10)k=k+1.

11)end for.

5 仿真实验分析

设E(x，y)为待侦察区域，50 km≤x≤200 km，50 km≤y≤200 km，A 为根据先验知识不需要进行侦察的区域，B 为禁飞区。假定在每一样本时间内，UAV 只允许在-45°～45°之间的角度进行直飞，左转或右转。

实验1 设需要进行重点侦察的区域F(x，y)坐标为:130 km≤x≤180 km，60 km≤y≤110 km.剩余部分为完全不确定区域，即η(x，y)=1，ω1=1/3，ω2=1/3，ω3=1/3，(x，y)∈F 时，γ=3，(x，y)∉F时，γ=1.机载传感器对目标的探测能力p=0.6.5 架UAV 从不同基地起飞开始执行侦察任务，其起飞点坐标分别为(50，50)，(80，50)，(110，50)，(140，50)，(170，50)，运行60 步长的仿真结果如图5所示。

图5 设置重点搜索区域的5 架UAV 协同搜索仿真结果Fig.5 Simulation results of cooperative search with a key search zone for five UAVs

由图5可知，UAV1 有一段航路经过A 区，而UAV1 和UAV2 尽管一度接近禁飞区但最后都顺利避开。由于对F(x，y)搜索能获得更高的收益，该区航路明显比较密集。

实验2 为了便于与其他算法进行比较，设γ为常数，取值1，其他参数设定同试验1.试验分2部分进行:首先运行80 步长，然后假定UAV1、UAV4 和UAV5 设备故障返航，分别对UAV2 和UAV3 运行20 步长，分别运用Zamboni 搜索、随机搜索和本文的协同搜索算法进行仿真，仿真结果分别如图6～图8所示(UAV2 和UAV3 的后半段航迹用星号线表示)。

图6 5 架UAV 的Zamboni 搜索仿真结果Fig.6 Simulation results of Zamboni search for five UAVs

图7 5 架UAV 的随机搜索仿真结果Fig.7 Simulation results of random search for five UAVs

由图6和图7可以看出，Zamboni 搜索和随机搜索的航迹不会受到区域A 和B 的影响，而图8中的协同搜索只有一架UAV 的航迹经过区域A，所有UAV 都避开了区域B.另外，Zamboni 覆盖算法和协同搜索算法几乎没有路径重叠，而随机搜索出现了多处多架UAV 航迹段重叠的情况。在3 架UAV 故障后，Zamboni 算法中的UAV2 和UAV3 仍然按照既定航线搜索，故障UAV 未完成的任务将得不到执行，算法不具有鲁棒性。图7中UAV3 后20 步长中的航迹与UAV1 出现了重叠，这也降低了搜索收益。而从图8可以看出UAV2 和UAV3 后20 步长中仍能保持之前的协同搜索策略，并且依然能够避开禁飞区。

图9为搜索效率随仿真步长的变化情况。由于多处航路经过区域A 和B，造成Zamboni 算法的侦察效率比协同搜索低，而部分UAV 故障导致在仿真后半段搜索效率几乎没有提高;随机搜索不仅多处航路经过区域A 和B，而且出现多处航路重叠，所以搜索效率也不高;与前2 种非协同方法相比，协同搜索可以使搜索环境的不确定度减少的更快。

图8 5 架UAV 的协同搜索仿真结果Fig.8 Simulation results of cooperative search for five UAVs

图9 5 架UAV 在3 种搜索样式下的搜索效率Fig.9 Search efficiencies in three search patterns for five UAVs

6 结论

通过对目标信息未知环境，已知环境和禁飞区实施不同对策，解决了UAV 在不确定环境中的协同搜索问题。仿真实验结果表明，本文提出的协同搜索算法对未知环境可以实施重点侦察，在机载燃油充足的情况下也可以展开覆盖搜索。对已知环境能够实现较好的规避，并完全避免了UAV 进入禁飞区。UAV 在整个仿真过程中都能够满足机动限制，并能够在友机故障的情况下继续实现协同。与3 种非协同搜索算法相比，本文提出的协同搜索算法具有更高的搜索效率。

References)

［1］ Schoenwald D A.AUVs:in space，air，water，and on the ground［J］.IEEE Control Syst，2000，20(6):15-18.

［2］ Chandler P，Rasmussen S，Pachter M.UAV cooperative path planning［C］∥Proceedings of AIAA Guidance，Navigation，and Control Conference and Exhibit.Denver:American Institute of Aeronautics and Astronautics，2000:1255-1265.

［3］ Chandler P，Pachter M，Rasmussen S.Hierarchical control for autonomous teams［C］∥Proceedings of AIAA Guidance，Navigation，and Control Conference and Exhibit.Montreal:American Institute of Aeronautics and Astronautics，2001:632-642.

［4］ Svennebring J，Koenig S.Building terrain-covering ant robots:a feasibility study［J］.Autonomous Robots，2004，16(3):313-332.

［5］ Wagner I A，Lindenbaum M，Bruckstein A M.MAC versus PC:determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains［J］.International Journal of Robotics Research，2000，19(1):12-31.

［6］ Yang S，Luo C.A neural network approach to complete coverage path planning［J］.IEEE Transactions on Systems，Man and Cybernetics，2004，34(1):718-725.

［7］ Choset H.Coverage for robotics:a survey of recent results［J］.Annals of Mathematics and Artificial Intelligence，2001，31:113-126.

［8］ Sujit P B，Ghose D.Search using multiple UAVs with flight time constraints［J］.IEEE Transactions on Aerospace and Electronic Systems，2004，40(2):491-510.

［9］ Yang Y.Cooperative search by uninhabited air vehicles in dynamic environment［D］.Cincinnati:University of Cincinnati，2005.

［10］ 柳长安，王和平，李为吉.无人机的侦察航路规划［J］.西北工业大学学报，2003，21(4):490-493.LIU Chang-an，WANG He-ping，LI Wei-ji.On path planning for more efficient reconnaissance of UAV［J］.Journal of Northwestern Polytechnical University，2003，21(4):490-493.(in Chinese)

［11］ Polycarpou M，Yang Y，Passino K.A cooperative search framework for distributed agents［C］∥Proceedings of the 2001 IEEE International Symposium on Intelligent Control.Mexico:Institute of Electrical and Electronics Engineers，2001:1-6.

［12］ Butenko S，Murphey R，Pardalos P.Cooperative control:models，applications and algorithms［M］.Dordrecht:Kluwer Academic Publishers，2003:283-321.