基于协同进化算法的多无人机协同区域搜索算法

基于协同进化算法的多无人机协同区域搜索算法

0不确定环境下的多uav协同搜索问题随着航空技术的发展，无人机（iuv）在军事和民用方面发挥着重要作用，区域搜索是uv的一般任务之一。通常UAV在执行搜索任务之前,对搜索区域的信息知之甚少,甚至一无所知,因此,无人机是在一个不确定甚至是未知的环境下执行搜索任务的。在这种情况下,相对于单架无人机来说,多架UAV协同对区域进行搜索,能够更全面彻底地搜索任务区域、更好地发现目标和获取情报信息。因此,本文对不确定环境下多UAV协同搜索问题进行了研究。针对不确定环境下的多UAV协同搜索问题,文献将模型预测控制(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)每个单元格最多存在一个目标,该目标可以以Pikillkilli的概率摧毁进入该单元的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)mod8,Oi(k),(Oi(k)+1)mod8},如图1所示,其中空心箭头为k时刻航向,实心箭头表示k+1时刻航向。1.3探测概率及不确定度评价为每个单元(m,n)定义一个目标存在概率Pmn(k)∈和不确定度χmn(k)∈。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)所示。Pmn(k+1)=PdPmn(k)(Pd−Pf)Pmn(k)+PfΡmn(k+1)=ΡdΡmn(k)(Ρd-Ρf)Ρmn(k)+Ρf(1)Pmn(k+1)=(1−Pd)Pmn(k)(1−Pf)+(Pf−Pd)Pmn(k)Ρmn(k+1)=(1-Ρd)Ρmn(k)(1-Ρf)+(Ρf-Ρd)Ρmn(k)(2)其中Pd∈为传感器的探测概率(即单元格(m,n)中存在目标,并被传感器检测到的概率),Pf∈为虚警率。不确定度的更新如式(3)所示。χmn(k+1)=0.5×χmn(k)(3)定义阈值θ,当单元格(m,n)的目标存在概率Pmn(k)≥θ时,认为该单元格中存在目标。2合作搜索路径规划算法2.1争、合作与共生的关系协同进化是指生物与生物、生物与环境之间在进化过程中的某种依存关系。也就是说协同进化算法不仅考虑单个种群之间的竞争,而且考虑多个种群,以及生物与环境的竞争、合作与共生的关系,多个物种通过相互间的作用,促使多个种群同时向前进化。协同进化算法主要分为两大类:竞争型协同进化算法和合作型协同进化算法。对于多UAV协同区域搜索这样一个既有竞争,更注重合作的博弈格局,合作型协同进化算法是一种适宜的选择。合作型协同进化按照多UAV之间的合作与约束关系,通过对群体间有利于合作的个体进行适应度加强,促使群体向着有利于产生相互合作和共同适应行为的方向进化。因此本文采用合作型协同进化算法进行多UAV协同区域搜索的路径规划。2.2uavk-1和k-1路径本文采用滚动优化思想,即在k时刻,限定各UAV向前规划q步(q>1为规划路径步数)路径,UAV只执行规划路径的第一步,k+1时刻,基于新的系统状态和环境信息重新规划路径。文中使用NV个子种群分别进化NV架UAV的搜索路径,若在k时刻,UAVi位于单元格(m,n)内,则k时刻路径规划的结果为以(m,n)为起点的长度为q的路径。2.2.1可扩张型的uav基因编码及求解本文以航向角增量为控制量,如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.2.2单元格+1ij求子种群的适应度时,待评价个体必须和其他种群的个体结合,组成完整的解。其中,选择的其他种群的个体称为代表个体,论文中选择其他子种群的最优个体作为代表个体。对于初始子种群,选择沿着个体代表的路径进行搜索获得报酬ρ最大的个体作为代表个体。ρ的计算公式如式(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))内,则dk+1ij=[mil(k+1)−mj(k+1)]2+[nil(k+1)−nj(k+1)]2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√dijk+1=[mil(k+1)-mj(k+1)]2+[nil(k+1)-nj(k+1)]2。当dk+1ijijk+1>1时,不会发生碰撞,则适应度函数Fil为待评价个体代表路径的报酬ρ,见式(4);当0≤dk+1ijijk+1<1时,UAVi与UAVj在k+1时刻可能发生碰撞,如果存在一个j(j=1,2,…,Nv,且j≠i),使得dk+1ijijk+1=0,则令适应度为零,见式(5),若dk+1ijijk+1≠0,则增加惩罚项,见式(6)。ρ=∑c=1q(ω1×ρf+ω2×ρu−ω3×Rc−1,c)ρ=∑c=1q(ω1×ρf+ω2×ρu-ω3×Rc-1,c)(4)Fil=ρFil=0(5)Fil=ρ−ω×∑NVj=1j≠idk+1ijFil=ρ-ω×∑ΝVj=1j≠idijk+1(6)式中:ω1,ω2,ω3为加权系数,且ω1+ω2+ω3=1,ω为惩罚因子。Rc-1,c为沿规划路径,UAV在相邻两步之间移动的距离。ρf为发现目标报酬,计算式为ρf=(Pd-Pf)Pmn(k)+Pf(7)ρu为不确定度降低报酬,计算式为ρu=∑c=1q[χmn(k)−χmn(k+1)]ρu=∑c=1q[χmn(k)-χmn(k+1)](8)2.2.3交叉操作中的操作子种群的进化操作选取如下:采用轮盘赌方法进行选择操作;交叉操作中,对任意两个父代染色体,当产生的随机数小于交叉概率Pc时,随机选择交叉点,进行单点交叉;变异操作中,当产生的随机数小于变异概率Pm时,随机选择一点进行变异。2.2.4对uavi的达到本文提出的用于多UAV协同区域搜索路径规划的协同进化遗传算法的步骤如下所述。Step1确定算法的控制参数,包括进化子种群的规模Psize,基因的交叉概率Pc,变异概率Pm,协同进化的代数T,算法的终止条件Tstop。Step2令k=0,对UAVi,产生k时刻的q步最优路径。1)令t=0,随机生成Psize个染色体长度为q的个体。2)利用其他进化子种群的代表个体,根据式(4)～式(5)计算每个待评价个体的适应值,并进行选择、交叉和变异操作。3)选择最优个体作为代表个体。4)判断是否满足进化停止条件t=T,若满足,则停止进化,并输出优化的q步路径;否则,令t=t+1,转Step2中第2)步。Step3执行最优路径的第一项,移动UAVi,并更新单元格和UAVi的状态。Step4判断是否满足算法终止条件k=Tstop,若满足,则算法停止;否则,令k=k+1,转Step2中第1)步。3uav目标的近自然实现设定仿真环境为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为由先验信息得知的区域单元格目标存在概率。图5和图6分别为使用协同进化算法和使用遗传算法进行路径规划的结果。当目标被发现后,由黑色的小方块表示,从图中可以清楚地看出找到了多少目标,漏掉了多少目标。图7给出了在相同时间内,分别使用协同进化算法和遗传算法发现目标的数量和时刻。图8为分别使用两种算法,在相同时间内,对环境不确定度的影响。从图中可以看出:两种算法中,无人机在进入任务区域后都是对目标概率较高的区域优先进行搜索,避免了对目标概率为0的区域的无效搜索。在相同的时间内,由于协同进化算法考虑了协同因素,使多架UAV之间较好地进行协调,避免