第3 9卷第 4 期 2 0 0 9年 7月 航 空 计 算 技 术 Ae r o n a u t i c a l Co mp u t i n g Te c h n i q u e Vo J 3 9 No 4 J u 2 0 0 9 基于改进遗传算法的多无人机路径规划 徐剑 ， 周德 云 ， 黄鹤 ( 西北工业大学， 陕西 西安 7 1 0 0 7 2 ) 囵 茎篓 专 。 警 ： 壹 皇 警 孥 竺 耋 法 贝 ，堡 -于 尊 ( 1 ) 操 作，使 所 求 解 的 问 题 逐 步 逼 近 最 优 解 。 与 其 他 方 法 相 【 = 1 一 n( 1 一 ) 收稿 日期 ： 2 0 0 9 0 2 1 8 修订 日期 ： 2 0 0 9 0 6 - 2 3 作者简介： 徐剑( 1 9 7 3 一) ， 男， 湖北襄樊人， 高级工程师， 博士， 研究方向为翼伞回归， 无人机路径规划。 4 4 航 空 计 算 技 术 第3 9 卷 第4期 渡处理。通常这个圆弧的半径选择为无人机的最小转 弯半径 ， 满足无人机的机动性能约束 ， 并且保证构成 该 圆弧与相连的两条线之间相切才能够平 滑过渡， 用 得到的两个切点代替原来的拐角点。 1 3 无人机的状态 本文按照无人机的实际运行情况 ， 将无人机区分 为 ： 就绪、 工作、 返航 、 失控 4个状态。处于就绪状态的 无人机等候在指定基地 ， 随时可以投入战斗。处于工 作状态的无人机正在进行侦查或压制任务。返航状态 指无人机已经完成属于它的侦查或压制任务 ， 准备或 正在返 回基地的状态。失控状态指无人机被敌人火力 或意外事故等 因素破坏 ， 而处于无法控制的状态。在 无人机任务调度 中， 需要对实时地根据环境的变化作 出正确的响应。 1 4 路径 规划 问题 描述 为了有效地解决多无人机动态环境下的路径规划 问题， 本文作如下假设 ： 1 ) 无人机处于高度为 的水平面 ； 2 ) 无人机起飞与降落速度恒定 ， 等于其平均速度。 给定条件 ： 1 ) 无人机位置 ( U X ， u Y , ) ， 即无人 机在 2维坐标 系中的坐标值 ； 2 ) 无人机状态 S 就绪 ， 工作 ， 返航， 失控 ； 3 ) 无人机的油量 P ， 用可以飞行的路程表示 ； 4 ) 无人机的平均航速 ； 5 ) 目标点位置( j ， ) ； 即目标点在 2维坐标系 中的坐标值 ； 6 ) 威胁描述 F =( F X ， F ， ) ， 各个分量表示威 胁的中心位置 ， 威胁的杀伤概率函数。 多无人机路径规划就是在上述条件下， 对于非失 控状态的无人机进行调度 ， 并确定相关无人机的工作 路径， 以便快速完成预定的或实时指定的任务 ， 并使得 无人机整体所受到的威胁最小。 1 基于改进遗传算法的多无人机路径规划 由前面的关于多无人机动态环境下 的路径规划问 题的描述可知 ， 该问题的求解主要分为 2部分 ， 一方面 是要求解任务由哪些无人机去完成； 另一方面是要为 这些工作的无人机分配任务序列。这两个方面是相互 联系的相互影响的， 将它们分解为 2个 问题是不合理 的。同时实验数据表 明， 应用通用的遗传算法对该 问 题求解时有很大的缺陷 ， 主要表现在容易陷入局部最 优且收敛缓慢 。分析其原 因， 主要是 由于将统一的编 码方法和统一的遗传算子应用于上述 2个性质不同的 子问题的解的表示和进化时 ， 没有充分利用子问题的 特点和性质。另外， 用通用的遗传算法对该问题求解 时， 对环境的变化( 比如任务的插入或删除、 无人机的 失控等) 反应缓慢。为此， 本文提出一种新的遗传算 法 ， 其主要特点是 ： 采用不同的编码和解码方法， 用 于表示和处理不同的子问题的解， 使得算法能适应可 变的条件和问题规模； 根据子问题的特点对基因采 用不同的遗传算子 。 2 1 染色体的编码 由于实际需求 ， 本文在 问题的模型中引人 了可变 的无人机数量和可变 的任务数量， 这样无疑加大了该 问题染色体编码的难度。根据问题的特殊性， 本文将 编码 划分 为 2部分 ： 1部分用 于表示调度 的无人 机 ； X 2部分表示各无人机的任务序列。即： X： l ， ( 2 ) 其 中， 编码 1为各个无人 机代 号的一个排列 ， 比如 ： B G E F A C D依次表示 7架无人机， 考虑到可能在作战中 得到补充 ， 本文在 1中设计了一些冗余的无人机编码； 部分表示任务序列 ， 同理， 由于无人机可能有临时的 任务， 本文在 中设计了一些冗余的任务编码。另外 ， 无人机要与分配给它的任务相关联 ， 这对于整个算法的 合理运行非常重要， 同时其设计也是较为困难的。本文 用下面的方法巧妙地解决了这个问题： 假设总任务数 目 为 t ( 其中包括未知临时任务) ， 而无人机总数为 ( 其中 包括等待扩充的无人机) ， 本文设置 一 1个“ 分隔标志” 编码， 与 t 个任务编码混合在一起， 作为表示任务的编码 X2。 2 2 染色体的解码 本文设计 了2个描述表用于染色体的解码 ： 任务 描述表和无人机描述表。 在染色体编码 中， 1 含有 总数为 u的无人机 ( 其中包括等待扩充的无人机 ) ， 而 中 u一1个“ 分 隔标志” 将编码分割成 “段( 各段长度可能为 0 ) ， 则无 人机和任务编码可按顺序一一对应。下面将解码的算 法描述如下 ： 步骤 1 设置累计任务序列 T _ T E MP为空 ； 步骤 2 如果 x l 读取完毕 ， 转步骤 7 。否则， 从 1 按顺序读取无人机代码， 得到 U jD； 步骤 3 查 u _ l D对应的任务段序列 T I D； 步骤 4 将 T T E MP与 T - I D合并， 得到新 的 T TEMP； 步骤 5 在无人机描述表 中查 U jD的状态 ， 如果 是工作、 就绪、 返航状态 ， 拷贝任务序列 ： T I D JIA s K + - T _T E MP ， 并将 T - T E M P置空 ； 否则 ， 转步骤 2 ； 步骤 6 在 T _ I D _ T A S K中过滤除去“ 分隔标志” 、 “ 已 完成” 任务， 得到该无人机分配的任务序列。转步骤2 ； 2 0 0 9年 7月 徐剑 等： 基于改进遗传算法的多无人机路径规划 步骤 7 结束。 表 1 任 务描 述表 已知任务 未知临时任务 任 务代 号 1 2 3 4 5 6 7 位 置( k m)( 2 4 ， 3 3 )( 5 6 ， 4 4 )( 3 8 ， 5 6 )( 4 0 ， 9 8 )( 1 2 0 ， 9 0 ) ( 0， 0 ) ( 0 ， 0 ) 任务状 态 已完成 已完成 未完成 未 完成 未完成 未完成 未完成 无人机描述表 已知的无人机 待补充 的无人机 代 号 A B C D E 位置( k m)( 1 0 ， 2 2 )( 5 0 ， 6 8 )( 5 ， 8 )( 0 ， 0 )( 0 ， 0 ) 时速 ( k m) 5 8 0 5 8 0 3 2 0 3 2 0 3 2 0 状 态 工作 失控 返航就绪就绪 油量( k m) 1 6 3 2 0 1 6 8 9 3 4 0 0 3 4 0 0 F ( 0 ， 0 ) 0 失控 0 G ( 0 ， 0 ) 0 失控 0 2 3 遗传算子的选择 本文对染色体 的不 同部分采用 了不 同的算子 ： 对 于 1 部分采用了普通的单点交叉的方法进行杂交 ； 对 于 X 2部分 ， 采用了 I n v e r O v e r 算子_ 4 J ， 该算子被证 明 在 T S P问题的求解 中非常有效 。 2 4评 价 有效 、 迅速 的评价方 法对于遗传算 法非 常重要。 多无人机的路径规划问题可以看成一个多 目标优化 的 问题 ， 既要迅 速完成任务 ， 又要机群受到 的威胁最小 化 。本文将该问题转化为一个单 目标优化 问题 ， 将威 胁代价与时间代价合并 ， 得到总代价计算公式 ( 3 ) ， 以 便于评价的实施。 Mi n = 1 W+ 2 t ( 3 ) 其 中， 1 ， 2是经验值 ， 本文 中 k l=1 0 ， k 2=5 0 。总 威胁代价计算见公式( 1 ) ， 总时间代价计算如下 ： f t =m a x ( t I ， t 2 ， ， t ) J f 4、 l S v 一 2 5 多无人机路径规划算法 用于动态环境下 的多无人机路径规划的改进遗传 算法描述如下 ： 步骤 1 初始化 ： 无人机描述表 、 初始化任务描述 表、 威胁描述表 ； 步骤 2 初始化群体 ； 步骤 3 如果任务完成 ， 转步骤 9 ； 步骤 4 对于每个个体 ： 步骤 4 1评价 ； 步骤 4 2如果该个体优于全局最优解 ， 则更新全 局最优解 ； 步骤 4 3按照全局最优解调度执行 ； 步骤 4 4杂交与变异 ； 步骤 5 更新无人机描述表( 更新位置、 状态等) ； 步骤 6 如果需要 ， 更新任务描述表 ； 步骤 7 如果需要 ， 更新威胁描述表 ； 步骤 8 转步骤 4 步骤 9 结束 从算法中可 以看出 ， 该算法对于实际问题 的部分 条件变化和部分任务变化是兼容的， 即： 在算法 的执行 过程中， 无人机、 任务 以及威胁都是可以重新指定 的。 3 仿真实验 本文在仿真环境下对该算法进行 了实验。在实验 中， 随机生成 2 0个任务 ， 分别指定 2架 、 3架、 4架可用 的无人机及其运行参数 ， 并指定了 2个威胁 ， 下 图是实 验中的一个输出图片 ， 图中的点表示任务 ， 圆圈表示概 率大于 0 9 0的威胁 ， 线表示规划的路径 。 O 一 f 。 O 仿真实验输出图 4 结论 本文将多无人机在动态环境下的路径规划问题进 行了建模 ， 考虑了无人机分布、 飞行特性、燃料限制等 条件 ， 采用了新 的编码方法对 求解 方案进行编码 、 解 码、 交叉以及变异， 设计了改进的遗传算法用于该问题 的求解 。仿真实验证明， 新的算法效率高、 鲁棒性好， 能 对无人机和任务的实时变化很快地作 出正确的响应。 4 6 航 空 计 算 技 术 第3 9卷 第4期 参考文献： 高晖， 陈欣， 夏云程 无人机航路规划研究 J 南京航空 航天大学学报， 2 0 0 1 ， 3 3 ( 2 ) ： 1 3 51 3 8 符小卫， 高晓光 一种无人机路径规划算法研究 J 系统 仿真学报 ， 2 0 0 4， 1 8 ( 1 ) ： 2 0 2 3 B e l l i n g h a m J ， R i c h a r d s A， Ho w J P Re c e d i n g Ho ri z o n C o n - t r o l o f A u t o n o mo u s A e r i a l V e h i c l e s A P r o c e e d i n g s o f A m e ri c a n C o n t r o l C o n f e r e n c e c A n c h o r a g e ， A K， 2 0 0 2 ， 5 ： 3 7 413 74 6 谢大同， 李程