基于DEPSO算法的多无人机绕检机队规模优化方法

高庆吉 谈 政 管若乔

(中国民航大学机器人研究所 天津 300300)

0 引 言

民航飞机进行绕机检查是保证飞机安全的必要作业[1]。客机的常规检查依飞行状态，可以分为航前、过站和航后三种。航前绕机检查是为了保证飞机的整体状态，确保飞行安全；航后则需要对飞机外灯、蒙皮、天线、起落架、机轮、发动机等20余个部位的异常及磨损状况进行判断。目前每次航前航后都需要机务人员以及飞行机组人员进行目视绕检，而且对于飞机顶部等某些人眼观测不到的区域难以检查。无人机通过近距航拍，能够在较短的时间内完成高分辨率的图像采集，实时自动识别异常点状态并定位。这些信息可实时传送给接收平台深度处理，工作人员也可在平台上观察机身的实际状况。无人机绕检可大幅度提升航前航后检查效率和效果。因此采用无人机绕检代替人工作业成为关注热点[2]。而多无人机协同绕检将更有利于提高效率。在多无人机绕机检查时，将面临两个问题，一是无人机协同完成任务时航迹的规划，二是无人机最优数量的确定。

多无人机路径规划的效果决定了多无人机执行任务的成功率和效率[3]。而在路径规划算法的设计时，算法的优劣决定了规划路径的质量[4]。目前无人机航迹规划中主要包括A*算法[5]、D*算法[6]、遗传算法[7]、蚁群算法[8]和粒子群算法[9]等。A*算法是一种较为普遍的启发式搜索算法，在路径规划方面使用广泛，但由于计算时存储量大，非常耗时，不适用于过于复杂环境的路径规划；D*算法同样普遍用于路径规划领域，但不适用于远距离的最短路径上发生变化时的计算；遗传算法是一种类生物算法，但算法存在适应值标定方法多样、早熟收敛、最优解附近摆动等方面的问题，导致在迭代后期收敛速度慢，甚至无法收敛于最优值；蚁群算法模拟蚂蚁觅食行为，采用概率式搜寻最优解，不易陷入局部最优，但算法一般需要较长的搜索时间，且法容易出现停滞现象，不利于发现更好的解；粒子群算法在三维路径规划领域应用广泛，由于算法操作简单且易于实现，其个体充分利用自身经验和群体经验调整自身的状态，对于求解一些连续函数的优化问题优势明显。

粒子群算法在求解三维空间路径规划问题应用广泛，但现有粒子群算法在迭代过程中容易出现种群早熟的情况，导致局部极值，且算法过于简单，规划出的路径并非最优。为避免上述情况，国内外学者提出了诸多方法进行算法优化，如文献[10]和文献[11]在速度更新公式的基础上分别添加了有界随机扰动和临近粒子信息，引入变异机制，防止粒子过早收敛，但是粒子的多样性一定程度上影响了算法的收敛速度，且研究不能在满足多种约束的情况下很好地解决多无人机飞行时导致的时空协同问题；文献[12]先将最小威胁曲面的概念引入了论文，随后通过对粒子群位置进行编码的方式将多约束条件以及智能搜索算法相结合。这虽然缩小了搜索空间，但该算法考虑的目标过于单一、对航迹规划的约束分析尚不全面，对算法的整体寻优效率仍然没有提升。

综上所述，本文研究了一种应用于多无人机航迹规划的改进粒子群算法，将基本粒子群算法有机地与差分进化算法进行了结合，并对航迹空间建模，建立航迹规划代价函数，在航迹规划空间设计多个航点并进行任务分配，以实现多无人机航迹规划和机队规模优化。

1 绕检目标模型及路径规划模型建立

无人机绕检时多机协作及机队规模优化，将在一个障碍物已知(被绕检飞机)的环境空间中，寻找一条到达目标点且满足各约束条件的最优路径，同时机队规模最优。

将问题转化为在已知环境的全局地图中搜寻无碰撞点序列所构成的路径。一般在路径规划的数学模型建立时，分为两部分进行，结合文献[10]中的方法，首先，确定路径规划的起始位置和目标位置，如图1所示。

图1 绕检目标模型

其次，对绕检作业空间离散化，如图2所示，建立坐标系O-XYZ，其中，以点S为坐标原点、SG为Z轴正方向。

图2 作业空间离散化

将SG进行d+1等分，再过每个等分点作平行于OXZ面的d个平面L1,L2,…,Ld。

为方便计算，将AB进行2m等分，AD进行n等分，从而将平面Li(i=1,2,…,d)分割成2m×n个栅格，作为离散化的作业空间。待规划空间内任一离散点的序号坐标为P(i,j,k)(其中i=-m,…,0,1,2,…,m，j=0,1,2,…,d，k=0,1,2,…,n)。

航迹规划是为了设计出无人机安全可靠的航迹。在多无人机航迹规划中，需要设置航迹节点。一般民航客机绕机检查关键点包括机头、前起落架、左侧前部机身等，将这些关键点作为目标节点，结合绕检目标连接作业空间中的离散点，构成绕检路径。在工作空间O-XYZ坐标系中，无人机从O点出发，首先到达平面L1上的某一点P1(i1,j1,k1)，形成航迹r(OP1)，然后从P1(i1,j1,k1)出发到平面L2上的某点P2(i2,j2,k2)，形成航迹r(P1P2)，依次最后到达平面Ld上G(Pd)，则无人机从起点S(P0)飞往终点G(Pd)，由多条航迹构成一条从源点S(P0)到目标点G(Pd)的路径，表达式如下：

(1)

将式(1)扩展到N架无人机，无人机k的起点和终点通过路径rk(P1kP2k)连接，形成无人机k飞行中经过的航迹。则多无人机总航迹可表示为：

(2)

2 航迹规划约束分析及代价函数

粒子适应度函数是生成路径质量的唯一依据，因此，为了更好地对路径质量进行判断，考虑到无人机在对民航飞机绕检时的实际问题，提出以下约束条件。

2.1 单无人机绕检航迹约束分析

分析无人机生成路径约束条件，考虑到航迹距离、障碍物因素和路径平滑度三个约束条件。

1) 航迹距离约束：平面Lj上的任意一点P(ia,ja,ka)，以及平面Lj+1上点P(ib,jb,kb)相连，如果线段P(ia,ja,ka)P(ib,jb,kb)不与任何障碍相交，则是一条可行航迹。计算相邻两平面点P(ia,ja,ka)和点P(ib,jb,kb)的连线距离，则有路径长度评价函数：

(3)

式中：DSG表示生成航迹在三维空间中欧氏距离;h表示ABCD-EFHM的长度。

(4)

(5)

3) 路径平滑度约束：避免规划出的路径多为折线。路径平滑度计算方法为：对一条路径中所有连接三个相邻节点的两条线段之间的偏转角β求和来近似评估路径的平滑度。路径平滑度评价函数如下：

(6)

(7)

2.2 多无人机绕检航迹约束分析

1) 机队规模约束。为保证每台无人机的合理分配，避免资源冗余，优化最佳机队规模，同时也不超过无人机数量的最大值，即:

N

(8)

2) 总任务时间约束。为能够高效地完成绕检任务，需要对总任务完成时间进行约束。设Ts表示绕检任务开始时间，Te表示完成任务时间，即最后一架无人机完成任务到达终点的时刻，则Te-Ts必须满足：

Te-Ts

(9)

3) 航迹节点约束。无人机在绕检作业过程中，作业空间是一个已知的范围，为提高多无人机协同绕检时工作效率，避免绕检节点冗余的情况，当两个航迹节点过近时，删除其中一个航迹节点，对航迹节点约束如下：

(10)

2.3 航迹规划代价函数

航迹代价函数的确定是根据航迹距离、障碍物危险程度、无人机飞行最大时间等因素评价的，同时也考虑了机队规模的约束，最终确定飞行航迹及无人机数量。

综上所述，可构造无人机k航迹节点分配后的代价函数为：

(11)

3 基于DEPSO算法的航迹规划

为解决多无人机航迹规划，可以分为航迹节点分配和全局航迹规划两个部分[13-15]，航迹节点分配就是根据任务要求设定各无人机的航迹，离线规划出多条飞行航迹；在此基础上，研究了一种改进粒子群算法，将差分进化引入粒子群算法中，对算法过早收敛的粒子进行差分进化操作，改善收敛状态，同时加入自适应调整惯性权重策略进行改进。算法流程如图3所示。

图3 算法流程

3.1 航迹节点规划方法

航机节点代表无人机在完成绕检任务时要遍历的关键点。设定初始点Ps与终止点Pe。其中应有P-2个航迹节点，由此计算P-2+N维的数列的解，可表示为:

Pi=(Pi1,Pi2,…,Pi(B-2),Pi(B-1),…,Pi(B-3+N))

(12)

式中：Pi1,…,Pi(B-2)代表航迹节点的编号，Pi(B-1),…,Pi(B-3+N)为分割无人机航迹的点。当计算出一个解时，将N-1个点Pi(B-1),…,Pi(B-3+N)插入Pi1,…,Pi(B-2)中，划分出N个航迹。进而通过点Pi(B-1),…,Pi(B-3+N)插入的位置的改变，使无人机遍历不同的航迹节点，简化了多无人机航迹规划的难度，过程如图4所示。

图4 航迹节点分配示意图

3.2 粒子群算法

(13)

式中：ω为惯性权重因子；r1和r2服从均匀分布U(0,1)；c1和c2是加速系数。由于粒子群算法存在粒子陷入局部最优的问题，引入方差来观察种群的多样性。适应度方差σ2代表粒子在迭代时的离散程度，可以表示为:

(14)

(15)

3.3 差分进化操作

为解决粒子陷入局部极值问题，保证种群的多样性，采用差分进化，在保留种群全局搜索的同时，对种群个体变异操作，即:

ui=xr1(t)+F[xr2(t)-xr3(t)]

(16)

式中：t为当前迭代次数；xr1、xr2、xr3为种群中的个体；F为比例因子。

新一代种群Ni由Ui和Ti组成。

(17)

式中：j=1,2,…D，D表示空间维数；Pc∈[0,1]，为交叉概率；Ui为随机变量；Ti是目标矢量。选择操作时采用贪婪策略，即:

(18)

式中：fit为适应度函数，使用新的粒子继续迭代，增加了种群的多样性，避免了陷入局部极值。

3.4 自适应惯性权重调整

为提高基本粒子群算法的收敛性能以及避免陷入局部极值，Shi等[16]1998年提出了惯性权重这一概念。在初始迭代时，权重因子较大可以加快算法的寻优速度，而进入迭代后期时，权重因子减小可以增加局部寻优能力。动态调整惯性权重因子的大小，提高全局搜索与局部寻优的协调性，采用自适应调节策略，即：

(19)

式中：tmax为最大迭代次数；λ为控制因子。在迭代初期，t值较小，惯性权重ω较大，进入迭代后期，t值增大，惯性权重ω减小，所以提高全局搜索与局部寻优的协调性。

4 仿真实验与分析

本文在Windows 10环境下采用MATLAB 2014a与Solidworks 2018联合仿真，验证上述算法的有效性。实验对象空客A380是四发超大型远程宽体客机，投产时也是全球载客量最大的客机，有“空中巨无霸”之称[17]，由于A380外形庞大，绕检航迹线路长，环境复杂，相比于目前使用广泛的机型空客A320以及其他机型绕检点数量大，计算复杂程度高，具备绕检目标代表性，所以采用空客A380客机为绕检目标，建立绕检客机模型，进行实验仿真实验。根据A380出港前关键部位绕机检查规范，绕检时按照图5所示的路线逐项进行检查，严格按照所持工卡的要求执行。绕机检查路线为：机头→前起落架→左侧前部机身→左大翼内侧→左发动机→左大翼外侧→左主起落架→左侧后部机身→APU→左水平安定面→垂直尾翼→右水平安定面→右侧后部机身(含后货舱)→右主起落架→右大翼外侧→右发动机→右大翼内侧→右侧前部机身(含前货舱)→机上检查[18]。

图5 A380绕机航线检查标准路径

首先对单无人机航迹规划仿真实验，目标点P为20，采用Solidworks中Simmechanicslink插件与MATLAB仿真接口，获取节点坐标，如图6和图7所示。

图6 A380 Solidworks外观结构建模

图7 A380 MATLAB数学模型呈现

航迹空间内航迹节点信息如表1所示。

表1 目标节点分布情况

目标节点1设置为出发节点，目标节点22设置为终止节点，目标节点的信息代表在空间内的三维坐标，障碍物模型为A380客机。

单无人机航迹规划时，考虑到无人机安全和续航问题，设定最大飞行距离为200 m，最大飞行速度为0.5 m/s，设置起点坐标PS=(0,0,0)，终点坐标PG=(0,76,0)及各节点坐标代入式(12)，规划航迹结合单无人机绕检航迹约束分析函数式(11)，计算航迹代价，并与遗传算法及基本粒子群算法进行仿真对比,如图8所示。

图8 改进DEPSO算法与标准PSO算法对比

可以看出，遗传算法在迭代中期，收敛速度快于粒子群算法，但随着迭代次数增加，收敛速度减慢，最终收敛于2 159，效果欠佳。标准粒子群算法在迭代至500次，达到最大迭代次数限制时，仍未收敛，而DEPSO算法在第190次迭代时接近收敛，最终在第283次迭代后收敛于1 325。加入自适应惯性权重调整的DEPSO算法在迭代至46次时收敛于1 226，由此得出，加入自适应惯性权重调整的改进粒子群算法在收敛性能上更好，生成的航迹代价指标更优。

在上述绕检作业空间内进行单架无人机航迹规划，结合约束条件，得到的航迹最终如图9所示。

图9 单架无人机航迹规划图

基于单架无人机航迹仿真实验验证，现设定无人机架数并分别进行实验，结果如表2所示。

表2 不同数量无人机航迹规划对比

可以看出，随着无人机数量增加，总航迹长度递增，而平均航迹长度呈现递减状态。由于绕检作业空间中无人机需要避开客机机身，平均航迹代价逐渐趋于稳定且略大于起始节点和终止节点直接飞行的航迹代价。无人机数量由2架增加至3架时，平均航迹长度和平均航迹代价明显下降，而无人机数量为3、4、5架时，平均航迹代价没有明显下降，且基本趋于稳定。综上所述，基于A380客机绕检目标模型下，3架无人机为该绕检作业空间中的最优机队规模。

5 结 语

针对多架无人机绕检的数量优化问题，通过设定绕检关键点作为目标节点，插入分割点的方法来简化寻优过程。引入差分进化操作更新粒子群，并采用自适应方法调整粒子的惯性权重，改进粒子群算法，最终实现多无人机航迹规划并确定最合适的无人机架数。对比于传统粒子群算法，提高粒子群算法的寻优效率，能更有效地解决多无人机航迹规划问题，优化机队规模。下一步研究工作将放在复杂环境下多机协同作业时的规划问题及机队规模优化，DEPSO算法必将在其应用中发挥独特价值。