免疫算法在多无人机任务最优规划中的应用

王永成，蔡晨晓

（1.郑州航空工业管理学院管理工程学院，河南郑州 450046；2.南京理工大学自动化学院，江苏南京 210094）

1 引言

无人机因体积小、安全性高、制造成本低等优势被广泛应用在军事、科研和民用等领域，主要分为直升机、飞艇、伞翼机等类型。无人机执行任务不受飞行人员身体机能限制，当执行危险任务时可避免飞行人员伤亡。从某种意义上来说，无人机可被看作是空中机器人，随着研究的不断深入，其应用类型逐渐扩展，完成任务的难度也在增强，有时需要多个无人机共同协作执行某项任务，这对其控制和规划能力要求极为严格。通常情况下，无人机任务规划可表示为：在符合所有作战指标情况下，以实现任务为目标，为所有参与工作的无人机分配任务，以保证无人机以最小的代价高效完成任务，无人机的任务规划效率可影响其任务的完成效率。

目前，越来越多的学者投入到任务规划等研究中，文献［1］中将粒子群优化与模拟退火算法相结合，综合分析无人机物理约束条件，将航迹长度和威胁代价最小为目标函数，利用Voronoi图规划航迹，再通过模拟退火粒子群算法求解任务规划的最优解。文献［2］中研究一种人工蜂群无人机任务规划算法。构建目标价值随时间参数变化的任务规划模型，结合决策示意图合理规划任务；通过整数编码方式优化人工蜂群算法，利用该方法求解无人机最佳任务执行路径，实现任务规划。

通常情况下上述方法都能获得理想的任务规划效果，但是，无人机的工作环境动态性较强，当无人机发生意外或出现新增任务时，这些方法难以重新规划任务。基于此，将免疫算法用到无人机任务规划中。免疫算法模仿生物免疫系统［3］，其中，包括抗原、抗体等主要结构。抗原即为规划问题，抗体就是产生的可行解，利用亲和度描述可行解质量。结合飞机动力学约束与任务约束［4］，构建算法数学模型，设计编码方式，引入禁忌准则，设定算法终止条件，将免疫算法有效应用在任务规划中，提高无人机任务执行效率。

2 免疫算法在多无人机任务最优规划中的应用研究

2.1 无人机自身动力学约束条件分析

为安全起见，无人机在任务执行过程中必须满足自身动力学系统约束。在三维空间内，无人机除了要考虑垂直方向的约束条件外，还需满足如下几点约束。

2.1.1 俯仰角度

规划无人机任务时，受机动性能、气候环境和飞行高度等方面影响［5］，需要着重考虑机身所能承受的大爬升角。如果将最大俯仰角度设置为θmax，则由某点(x，y，z)爬升到某点(x′，y′，z′) 时爬升角度必须符合如下条件：

式中：a—一个向量。式（1）还可以描述为：

2.1.2 偏航角度

在水平空间内无人机满足的最大角度变化要求，即为偏航角度约束，表示为ηmax。

假设无人机从点O开始起飞，经过O′点，最终到达O′′。向量=(x−x′，y−y′)，则偏航角度有：

2.1.3 飞行高度

无人机在执行任务过程中，受到自身物理性能限制，飞行高度上限记做hmax。此外，为避免无人机撞击到建筑物，设定飞行的最低限制为hmin。无人机的最佳飞行高度应在二者之间，表示为：

2.2 基于免疫算法的无人机任务最优规划模型

免疫算法包括抗原、抗体、亲和力计算、免疫记忆和种群更新等方面组成。要想将免疫算法合理的应用在无人机任务规划中，必须分别对这些模块进行详细分析。

2.2.1 抗原生成

抗原即为待解决问题的数学模型［6］，通过构造任务规划问题的各类约束条件和目标函数，初始化部分参数，构建任务最优规划的数学模型。

假设利用描述多无人机任务规划问题，E表示任务所处环境，V代表所有无人机集合，无人机从起点起飞完成任务后返回到指定地点。假设起点总数量为m，其中第a个起点的无人机集合为Va={，，...，}。T={T1，T2，...，TN}描述Nv个目标任务集合，且每个目标的价值γj也不同，C是全部约束条件的集合。将这些任务规划给无人机时，必须确保整体效益最大。则构建的目标函数如下：

式中：A—属于权重系数；B—属于权重系数；f1—整体利益；f2—路径；f3—威胁代价；α—调节因子。f1、f2和f3的表达式如下：

式中：Nv—目标任务个数；γj—目标j的价值；—第a个起点中无人机i完成任务Tj之后是否继续执行目标任务Tk；—第a个起点处，无人机i完成任务Tj后是否返回到起点。

rmax—最大风险。

—目标Tj和起始点之间的距离。

任务规划除了将上述函数作为目标外，还需要满足如下几个要求：

（1）某架无人机在完成目标j后，后续目标仅能有一个，通过下述公式表示：

（2）无人机不能执行已经执行完的任务：

（3）所有无人机的飞行距离必须小于或等于工作半径：

式中：R—无人机工作半径。

（4）必须确保全部任务都被规划到：

2.2.2 抗体群生成

抗体即为通过合理的编码方式，结合先验知识生成初始抗体群。无人机在工作过程中，需要分析运动状况。为方便分析，通过栅格法将三维空间分割为若干个层次［7］，每一次仅分析单个层次内的运动状况。主要目的是在符合无人机动力学约束条件下，确保航程最小。

编码是否合理直接关系到操作算子性能，根据无人机航线规划特征，利用数字符串编码方法。算法的主要思想是利用字符串表示抗体，保证其中所有元素都与某坐标点(L，H)相对应，L与H分别代表维度和高度。通过构建数字高程地图，确定编码长度是42，并使用（2×42）矩阵构成的基因描述无人机航线。矩阵首列是[1，42 ]区间内的整数Lat= 29 + 0.01(L−1)，利用公式将具体数值变换为维度。同理，也可解码高度，达到地理信息与基因编码相互转换的目的［8］。

通过随机数生成原始种群，网格数量决定了编码长度，因少数网格节点在地形下方，所以建立失效节点列表来存放无效网格点。当有种群生成时，基因节点必须为有效节点才能加入，基因编码方式如下：

式（13）所示的矩阵能够表示出完整的飞行轨迹。

抗体生成后，需计算抗体之间的亲和度，也就是空间距离，距离越近表示抗体间相似程度越高，种群多样性特征不明显，容易陷入局部最优。例如抗体p和q的亲密度公式如下：

式中：Qp—抗体p在解集空间中的点解；

Qq—抗体q在解集空间中的点解。

2.2.3 免疫记忆种群更新

免疫记忆即为将现阶段种群内亲和力较高的抗体添加到记忆种群中［9］。在迭代过程中，将亲和力最佳的抗体与记忆种群对比，若适应值高于记忆种群的适应度，则进行替换，反之不变。具体方法如下：（1）选取抗体适应度最佳的o个抗体，将其保存到外部抗体群Mbest中，若种群规模没有达到标准，则继续接受更新。（2）将网格内适应度最佳的o个抗体加入到记忆种群内，当种群规模高于设定规模Ko时，将超出部分中适应度较低的抗体删除，始终保持|Mbest|=Ko。

2.2.4 高频变异

在免疫算法中，要想保证抗体的成熟与多样性等特征，需通过高频变异的形式实现。此种操作的实质是结合抗体间亲和度的大小，克隆抗体细胞［10］。该过程可利用下述公式描述：

式中：Gc—经过克隆的抗体种群规模；

Int( )—取整函数；

f(Xu)—第u个个体亲和度。

经高频变异后，亲和度高的抗体产生多个镜像，保持原有抗体良好的特征，改善了规划空间的搜索性能。

2.2.5 禁忌准则与终止条件确定

为改善算法收敛速度，设置禁忌准则，核心思想就是标记局部最优解，在下一轮迭代时避开这些最优解，将亲和度没有变化的个体加入到禁忌项中。如果项中的个体禁忌数量高于设定阈值，则特赦个体，扩大搜索空间，保证持续的搜索能力，避免迂回搜索。

算法停止条件通常为满足设定的迭代次数。此外，在某迭代周期内，如果没有寻找到适应度更好的抗体，算法也会停止。停止算法后，当前模型输出的结果即为最终规划方案。

3 实验分析

3.1 实验环境设置

为验证所提方法在无人机多任务规划中的应用性能，选取根据无人机具体结构建立数据模型，进行多任务规划模拟，掌握无人机的位置与姿态。本次实验在一台运行内存为8GB 的Win⁃dows 10 系统中实施，利用matlab软件中的simunik动态仿真组件完成控制模型的建立及仿真，通过传输指令控制无人机运动。

无人机相关参数，如表1所示。

表1 无人机参数指标Tab.1 Parameter Index of UAV

免疫算法参数设置，如表2所示。

表2 免疫算法参数指标Tab.2 Parameters of Immune Algorithm

除对无人机参数及免疫算法参数进行设置，还需要对其环境参数、任务数目及任务地点进行设置。本次设置当天温度在（20~22）℃之间，其风速达到（5.5~6.1）m/s，待执行的任务总数为10个，1~10 的坐标依次为（29.4，103.1，345.5）、（29.35，103.2，150.7）、（29.35，103.3，220.8）、（29.25，103.1，250.3）、（29.25，103.3，280.9）、（29.2，103.35，205.2）、（29.15，103.1，189.2）、（29.15，103.15，170.9）、（29.15，103.2，220.7）、（29.1，103.3，160.5），本次共派出三架无人机执行任务，无人机（1~3）号起始点坐标依次为（29.15，103.0，0）、（29.25，103.0，0）、（29.30，103.0，0）。

3.2 可行性实验验证

在无意外发生情况下，利用所提方法进行任务规划得到规划结果，如图1所示，图中星型表示任务。

图1 无意外发生情况下任务规划结果图Fig.1 Task Planning Results Without Accidents

由图1可以看出，无人机1执行任务1、2和3，无人机2则执行任务4、5和6，无人机3执行的任务相对较多，这是因为这些任务之间距离较短。从规划的航线上来看，无人机飞行的总距离最短，基本按照最近原则分配任务，减少路径代价。

但是任务环境具有较强的动态性，在任务执行期间，无人机很有可能出现失联等突发状况。另外，威胁源的信息也会发生突变。分别在上述情况下进行任务规划。

情况1：无人机失联

假设无人机2在执行完任务5后出现失联情况，则此时的任务规划结果，如图2所示。

图2 无人机失联情况下任务规划结果Fig.2 Mission Planning Results in Case of UAV Loss of Contact

由图2可知，当无人机2失去信号后，无人机1在执行完任务2后到达任务5所在地点执行任务。这是因为免疫算法在执行过程中可以通过反复迭代重新整理任务航线，通过合理的编码设计确保无人机航程最短。

情况2：任务信息改变

传感器可能会造成信息滞后，无人机任务初始分配时的环境信息与实际信息可能会有误差。在任务执行过程中，会增加任务点，此时需重新规划任务。假设新增任务点为X，获取免疫算法的规划结果，如图3所示。

图3 威胁源信息变化时任务规划结果Fig.3 Mission Planning Results When Threat Source Information Changes

由图3看出，即便无人机在执行任务过程中出现新增任务，所提方法也能合理的将新任务分配给对应的无人机，确保无人机顺利完成所有任务的同时，还能满足设定的目标函数要求。

3.3 对比实验分析

在规划合理性方面所提方法表现出优越的性能，为测试算法目标函数的收敛能力，将收敛曲线和模拟退火粒子群算法、人工蜂群算法进行对比，得出比较结果，如图4所示。

图4 不同算法收敛曲线对比图Fig.4 Comparison of Convergence Curves of Different Algorithms

测试结果表明，与其他两种算法相比，免疫算法的收敛速度较快，当迭代次数为40次时即可达到最优目标值。这是因为该方法运用了高频变异操作，可避免算法陷入局部最优，而编码过程则是对最优解的记忆过程，加快了全局最优解的搜索速度。

三种方法规划3次运行结果，如表3所示。

表3 不同方法的规划航程及耗时对比Tab.3 Planning Voyages and Time-Consuming Comparison of Different Methods

经过对比可知，所提方法三次规划以来，其航程最优缩减为62.1km，规划耗时小于30s，而对比方法的航程全部大于85km，且规划耗时大于100s，所提方法具有更好的规划效果，其规划速率更优。

4 结论

为提升无人机任务规划的准确率和规划速率，这里将免疫算法应用在多无人机任务最优规划中。结合任务规划的各类约束条件，构建规划数学模型，经过编码设计、高频变异等过程输出最优的任务规划方案，经过仿真实验证明所提方法的可行性和先进性。（1）可行性实验结果如下：在无意外发生情况下，可按照最近原则分配任务，以减少路径代价；在某一无人机出现信号失联时，可通过反复迭代重新整理任务航线，遵循无人机航程最短原则，就近安排其余无人机完成任务；可在任务点新增时，将新任务分配给对应无人机，就近完成任务，实现规划目标。（2）对比实验结果如下：所提方法可在迭代40次后完成达到最优目标值，且可在规划3次后将航程缩减到62.1km，整体规划耗时小于30s，优于对比方法。