不确定环境下多无人机协同搜索算法研究

张莹莹， 周德云， 夏 欢

(西北工业大学，西安 710129)

0 引言

随着航空技术的发展，无人机(UAV)在军事和民用两个方面都发挥着重要的作用，而区域搜索是UAV的常见任务之一。通常UAV在执行搜索任务之前，对搜索区域的信息知之甚少，甚至一无所知，因此，无人机是在一个不确定甚至是未知的环境下执行搜索任务的。在这种情况下，相对于单架无人机来说，多架UAV协同对区域进行搜索，能够更全面彻底地搜索任务区域、更好地发现目标和获取情报信息。因此，本文对不确定环境下多UAV协同搜索问题进行了研究。针对不确定环境下的多UAV协同搜索问题，文献［1］将模型预测控制(MPC)和遗传算法结合起来，采用遗传算法进行路径规划。但是，一般的遗传算法只考虑了种群内部的竞争，而协同进化遗传算法不仅考虑单个种群之间的竞争，还考虑到多个种群，以及生物与环境的竞争、合作与共生的关系。因此，本文研究基于协同进化遗传算法的多UAV协同搜索算法，进一步提高搜索效能。

论文采用搜索概率图来描述搜索环境的不确定性，搜索概率图中包含了UAV对搜索环境的先验信息，减小了搜索的盲目性。采用协同进化遗传算法进行多UAV协同搜索路径规划，可在线滚动生成局部最优路径，满足实时性要求。

1 多机协同区域搜索问题建模

1.1 环境模型

假设搜索区域为一平面矩形区域，其中分布着NT个目标，NV架UAV进入任务区域后对目标进行搜索。本文将搜索区域划分为Lx×Ly的离散单元，称所有单元的集合 E={(m，n)|m=1，2，…，Lx，n=1，2，…，Ly}为搜索环境，(m，n)表示位于第m行第n列的单元。单元格(m，n)中目标的真实状态为 Smn∈{0，1}，Smn=1表示存在目标。

为了便于研究，本文做出以下假设:1)每个单元格最多存在一个目标，该目标可以以Pikill的概率摧毁进入该单元的UAV;2)UAV具有自主避障的能力，因此不考虑环境中的障碍物;3)各架UAV之间可以互相通信，且不考虑通信延迟，即UAV可以即时得到其他UAV的信息。

1.2 UAV的状态模型

k时刻，UAVi的位置为(mi(k)，ni(k));存活状态为 δi(k)∈{0，1}(δi(k)=1 表示未被摧毁);航向为Oi(k)∈{0，1，2，3，4，5，6，7}(各数字代表航向如图 1所示)。假设UAV在一个时刻内只移动一步，即从当前单元移动到相邻的某个单元。受转弯特性的限制，UAV在k+1时刻的航向只能是在k时刻航向的基础上向左转 45°、直行或向右转 45°，即 Oi(k+1)∈{(Oi(k) －1)mod 8，Oi(k)，(Oi(k)+1)mod 8}，如图1所示，其中空心箭头为k时刻航向，实心箭头表示k+1时刻航向。

图1 无人机航向示意图Fig.1 Sketch map of the orientation of UAV

1.3 搜索概率图模型

为每个单元(m，n)定义一个目标存在概率Pmn(k)∈［0，1］和不确定度 χmn(k)∈［0，1］。Pmn(k)描述了 k时刻单元格(m，n)存在目标的可能性，Pmn(k)=1表示存在目标的概率最大;χmn(k)描述了UAV对单元格(m，n)处信息的不确定性程度，χmn(k)=1表示UAV对该处的目标信息一无所知。

搜索过程中，UAV根据机载传感器的探测信息对概率图进行实时更新。若UAV在k时刻访问单元格(m，n)，则传感器获得探测信息 bk∈{0，1}(bk=1表示UAV在单元格(m，n)探测到目标)，则k+1时刻当bk=1时，单元格(m，n)的目标存在概率更新如式(1)所示，bk=0时如式(2)所示。

其中Pd∈［0，1］为传感器的探测概率(即单元格(m，n)中存在目标，并被传感器检测到的概率)，Pf∈［0，1］为虚警率。

不确定度的更新如式(3)所示。

定义阈值 θ，当单元格(m，n)的目标存在概率Pmn(k)≥θ时，认为该单元格中存在目标。

2 协同搜索路径规划算法

2.1 协同进化遗传算法

协同进化［2］是指生物与生物、生物与环境之间在进化过程中的某种依存关系。也就是说协同进化算法不仅考虑单个种群之间的竞争，而且考虑多个种群，以及生物与环境的竞争、合作与共生的关系，多个物种通过相互间的作用，促使多个种群同时向前进化。协同进化算法主要分为两大类:竞争型协同进化算法和合作型协同进化算法。对于多UAV协同区域搜索这样一个既有竞争，更注重合作的博弈格局，合作型协同进化算法是一种适宜的选择。合作型协同进化按照多UAV之间的合作与约束关系，通过对群体间有利于合作的个体进行适应度加强，促使群体向着有利于产生相互合作和共同适应行为的方向进化。因此本文采用合作型协同进化算法进行多UAV协同区域搜索的路径规划。

2.2 基于协同进化遗传的多UAV协同搜索算法

本文采用滚动优化思想，即在k时刻，限定各UAV向前规划q步(q＞1为规划路径步数)路径，UAV只执行规划路径的第一步，k+1时刻，基于新的系统状态和环境信息重新规划路径。文中使用NV个子种群分别进化NV架UAV的搜索路径，若在k时刻，UAVi位于单元格(m，n)内，则k时刻路径规划的结果为以(m，n)为起点的长度为q的路径。

2.2.1 编码

本文以航向角增量为控制量，如1.2节所述，UAV受转弯特性限制，k时刻UAV的动作集U={－1，0，1}，其中－1表示左转、0表示直行、1表示右转。本文以UAV的动作u∈U为基因进行编码，染色体长度为路径规划步数q，如图2所示为q=6时的染色体结构。每条染色体均可解码为可行路径解空间中的一个解(候选路径)。k时刻，若UAVi的航向为1，则染色体－1，1，1，0，－1，1 代表的路径如图3 所示。

图2 染色体示意图Fig.2 Sketch map of chromosome

图3 路径示意图Fig.3 Sketch map of path

2.2.2 适应度

求子种群的适应度时，待评价个体必须和其他种群的个体结合，组成完整的解。其中，选择的其他种群的个体称为代表个体，论文中选择其他子种群的最优个体作为代表个体。对于初始子种群，选择沿着个体代表的路径进行搜索获得报酬ρ最大的个体作为代表个体。ρ的计算公式如式(4)所示。由于不考虑通信延迟，各子种群可以即时获得其他子种群的代表个体，并与待评价个体结合，计算待评价个体的适应度。

待评价个体的适应度定义为在不与其他UAV发生碰撞的前提下(即UAV按待评价个体所示路径移动，在下一时刻所处的单元格与其他UAV按其代表个体所示路径移动，在下一时刻所处的单元格不相同)，沿着该个体代表的路径进行搜索所能获得的报酬。如果沿着该路径飞行会与其他UAV发生碰撞，该路径就不可行，应在其适应度函数中增加惩罚项。

设UAVi按第i个种群的第l个个体所示路径移动，到k+1时刻时，位于单元格(mil(k+1)，nil(k+1))内，UAVj按第j个种群的代表个体所示路径移动，k+1时刻，位于单元格(mj(k+1)，nj(k+1))内，则当时，不会发生碰撞，则适应度函数 Fil为待评价个体代表路径的报酬ρ，见式(4);当时，UAVi与UAVj在k+1时刻可能发生碰撞，如果存在一个 j(j=1，2，…，Nv，且，使得，则令适应度为零，见式(5)，若，则增加惩罚项，见式(6)。

式中:ω1，ω2，ω3为加权系数，且 ω1+ ω2+ ω3=1，ω 为惩罚因子。Rc－1，c为沿规划路径，UAV在相邻两步之间移动的距离。ρf为发现目标报酬，计算式为

ρu为不确定度降低报酬，计算式为

2.2.3 进化算子

子种群的进化操作选取如下:采用轮盘赌方法进行选择操作;交叉操作中，对任意两个父代染色体，当产生的随机数小于交叉概率Pc时，随机选择交叉点，进行单点交叉;变异操作中，当产生的随机数小于变异概率Pm时，随机选择一点进行变异。

2.2.4 算法步骤

本文提出的用于多UAV协同区域搜索路径规划的协同进化遗传算法的步骤如下所述。

Step 1 确定算法的控制参数，包括进化子种群的规模Psize，基因的交叉概率Pc，变异概率Pm，协同进化的代数T，算法的终止条件Tstop。

Step 2 令k=0，对UAVi，产生k时刻的q步最优路径。

1)令t=0，随机生成Psize个染色体长度为q的个体。

2)利用其他进化子种群的代表个体，根据式(4)～式(5)计算每个待评价个体的适应值，并进行选择、交叉和变异操作。

3)选择最优个体作为代表个体。

4)判断是否满足进化停止条件t=T，若满足，则停止进化，并输出优化的q步路径;否则，令t=t+1，转Step2中第2)步。

Step 3 执行最优路径的第一项，移动UAVi，并更新单元格和UAVi的状态。

Step 4 判断是否满足算法终止条件k=Tstop，若满足，则算法停止;否则，令k=k+1，转Step2中第1)步。

3 仿真分析

设定仿真环境为30×30的矩形区域，环境中随机分布着10个目标，3架UAV对搜索区域进行搜索，初始位置分别为:(1，1)，(6，1)，(11，1)。设 Pd=0.9，Pf=0.1，路径规划长度q=5，进化子种群的规模Psize=100，交叉概率Pc=0.7，变异概率Pm=0.05，目标对进入其所在单元格的UAV的摧毁概率Pkill=0.1，仿真时间取为Tstop=100。初始环境如图4所示。其中黑色三角表示UAV的初始位置，黑色菱形表示真实的目标位置，该位置UAV未知，p为由先验信息得知的区域单元格目标存在概率。

图4 目标分布图Fig.4 The distribution of targets

图5 和图6分别为使用协同进化算法和使用遗传算法进行路径规划的结果。当目标被发现后，由黑色的小方块表示，从图中可以清楚地看出找到了多少目标，漏掉了多少目标。

图5 协同进化遗传算法的路径规划Fig.5 The path planning of CEGA

图6 一般遗传算法的路径规划Fig.6 The path planning of GA

图7 给出了在相同时间内，分别使用协同进化算法和遗传算法发现目标的数量和时刻。图8为分别使用两种算法，在相同时间内，对环境不确定度的影响。从图中可以看出:两种算法中，无人机在进入任务区域后都是对目标概率较高的区域优先进行搜索，避免了对目标概率为0的区域的无效搜索。在相同的时间内，由于协同进化算法考虑了协同因素，使多架UAV之间较好地进行协调，避免了对同一区域的重复搜索，优化了搜索效能。故使用协同进化算法比使用遗传算法对环境不确定度的降低程度稍大一点，并且使用协同进化算法可以发现更多的目标。因此，与遗传算法相比，协同进化算法具有更好的搜索效能。

图7 两种算法发现目标图Fig.7 Targets finded by two algorithms

图8 两种算法对环境不确定度的影响Fig.8 Effect of the two algorithms on environmental uncertainty

4 结束语

本文针对不确定环境下的多UAV协同搜索问题，进行了分析，建立了环境模型和搜索概率图模型，并根据滚动优化思想，提出了基于协同进化算法的多UAV协同搜索的路径规划方法。仿真结果表明，协同进化算法充分利用了多UAV之间的协同信息，比遗传算法具有更高的搜索效能。

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

［2］ 焦李成，刘静，钟伟才.协同进化计算与多智能体系统［M］.北京:科学出版社，2006.

［3］ 夏欢，周德云，陈龙建.多无人机协同搜索路径规划方法研究［C］//中国航空学会航空武器系统分会2010年学术年会暨第三届“中国航空武器装备试验与发展学术论坛”论文集，2010:432-436.

［4］ 申晓宁，郭毓，陈庆伟，等.基于多目标协同进化算法的多机器人路径规划［J］.南京航空航天大学学报，2008，40(2):245-249.

［5］ FLINT M，POLYCARPOU M，GAUCHERAND E F.Cooperative control for multiple autonomous UAV's searching for targets［C］//Proc.of the 4lst IEEE Conference on Decision and Control，2002(3):2823-2828.

［6］ POLYCARPOU M，YANG Y，PASSINO K.A cooperative search framework for distributed agents［C］//Proceedings of the 2001 IEEE International Symposium on Intelligent Control，2001:1-6.

［7］ YANG Y，HILINAI A A，POLYCARPOU M M.Decentralized cooperative search in UAV's using opportunistic learning［DB/OL］.http://www.ece.uc.edu/aminai/papers/yang gnco2.pdf，2002.

［8］ FLINT M，POLYCARPOU M，GAUCHER F.Cooperative path-planning for autonomous vehicles using dynamic programming［DB/OL］.http://www.nt.ntnu.no/users/skoge/poroleedings/ifac2002/data/content/01694/1694.pdf，2001.

［9］ DECKER D D.Decision factors for cooperative multiple warhead UAV target classifycation and attack with control application［D］.Xi'an:Air Force Institute of Technology，2004.

［10］ 刘国兴，李敏强.基于协同进化的多目标优化算法研究［D］.天津:天津大学，2008.

［11］ 沈延航，周洲，祝小平.基于搜索理论的多无人机协同控制方法研究［J］.西北工业大学学报，2006，24(3):367-370.

［12］ 李子文，夏洁.无人侦察机路径规划方法研究［J］.系统仿真学报，2008(S1):490-494.

［13］ PENG H，SU F，BU Y L，et al.Cooperative area search for multiple UAVs based on RRT and decentralized receding horizon optimization［C］//Proceedings of the 7th Asian Control Conference，2009:298-303.