收稿日期： ２００８唱１０唱１６； 修回日期： ２００８唱１２唱０７
作者简介：王振华（１９８３唱） ，男，河南林州 人，博士研究生，主要研究方向为群智能优化、路径规划（ ｗｚｈｕａ＿ｒａｎｄｙ＠１６３．ｃｏｍ） ；章 卫 国 （ １９５６唱） ，
男，安徽南陵人，博导，博士，主要研究方向为飞行器控制、先进控制理论；李广文（１９７８唱），男，河北献县人，讲师，博士，主要研 究方向为 进 化算法、
飞行控制技术．
基 于 改 进 多 目 标 蚁 群 算 法 的 无 人 机 路 径 规 划
王振华， 章卫国， 李广文
（西北工业大学 自动化学院， 西安 ７１００７２）
摘 要： 针对无人机 ＳＥＡＤ 任务的路径规划问题，利用 ＶＯＲＯＮＯＩ 图构建初始路径，分析了路径代价计算方法，
并使用改进的多目标蚁群算法对路径进行优化选择。 针对该特殊应用场景，引入了各路径段与起始点—目标点
连线的夹角信息作为新的启发信息，加快了算法的搜索速度，同时改进启发信息的计算公式，适当缩小各可选路
径段启发信息量的差异，加强了蚁群算法的全局搜索能力。 仿真结果显示，与基本多目标蚁群算法相比，改进后
的算法有效提高了路径搜索的效率和质量。
关键词： 无人机； 路径规划； ＶＯＲＯＮＯＩ 图； 多目标蚁群算法
中图分类号： ＴＰ３９１ 文献标志码： Ａ 文章编号： １００１唱３６９５（２００９）０６唱２１０４唱０３
ｄｏｉ：１０．３９６９ ／ｊ．ｉｓｓｎ．１００１唱３６９５．２００９．０６．０３１
ＵＡＶ ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ
ＷＡＮＧ Ｚｈｅｎ唱ｈｕａ， ＺＨＡＮＧ Ｗｅｉ唱ｇｕｏ， ＬＩ Ｇｕａｎｇ唱ｗｅｎ
（ Ｓｃｈｏｏｌ ｏｆ Ａｕｔｏｍａｔｉｏｎ， Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｘｉ’ ａｎ ７１００７２， Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ｂａｓｅｄ ｏｎ ｔｈｅ ＶＯＲＯＮＯＩ ｄｉａｇｒａｍ，ｔｈｉｓ ｐａｐｅｒ ｃａｌｃｕｌａｔｅｄ ｔｈｅ ｐａｔｈ ｃｏｓｔｓ， ａｎｄ ｔｈｅｎ ｕｓｅｄ ｔｈｅ ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ａｎｔ ｃｏｌｏｎｙ
ｓｙｓｔｅｍ（ＭＡＣＳ） ａｌｇｏｒｉｔｈｍ ｔｏ ｓｏｌｖｅ ｔｈｅ ｒｏｕｔｅ ｐｌａｎｎｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ｔｈｅ ＵＡＶｓ ｔａｋｉｎｇ ｔｈｅ ＳＥＡＤ ｍｉｓｓｉｏｎ．Ｃａｌｃｕｌａｔｅｄ ａｎｄ ｉｎｔｒｏ唱
ｄｕｃｅｄ ｔｈｅ ａｎｇｌｅｓ ｂｅｔｗｅｅｎ ｐａｔｈ ｓｅｇｍｅｎｔｓ ａｎｄ ｔｈｅ ｌｉｎｅ ｓｅｇｍｅｎｔ ｊｏｉｎｉｎｇ ｔｈｅ ｓｔａｒｔ ｐｏｉｎｔ ａｎｄ ｔｈｅ ｔａｒｇｅｔ ｐｏｉｎｔ， ａｓ ｈｅｕｒｉｓｔｉｃ ｉｎｆｏｒｍａ唱
ｔｉｏｎ， ｉｎｔｏ ｔｈｅ ＭＡＣＳ ａｌｇｏｒｉｔｈｍ ｔｏ ａｃｃｅｌｅｒａｔｅ ｔｈｅ ｓｅａｒｃｈｉｎｇ ｓｐｅｅｄ．Ａｎｄ ａｌｓｏ，ｔｈｉｓ ｐａｐｅｒ ｉｍｐｒｏｖｅｄ ｔｈｅ ｅｘｐｒｅｓｓｉｏｎ ｏｆ ｔｈｅ ｈｅｕｒｉｓｔｉｃ
ｉｎｆｏｒｍａｔｉｏｎ， ｗｈｉｃｈ ｒｅｄｕｃｅｄ ｔｈｅ ｄｉｆｆｅｒｅｎｃｅｓ ａｍｏｎｇ ｔｈｅ ｐａｔｈ ｓｅｇｍｅｎｔｓ， ａｎｄ ｅｎｈａｎｃｅｄ ｔｈｅ ｇｌｏｂａｌ ｓｅａｒｃｈｉｎｇ ａｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｌｇｏ唱
ｒｉｔｈｍ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ：ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｏｒｉｇｉｎａｌ ＭＡＣＳ，ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｆｉｎｄ ａ ｂｅｔｔｅｒ ｒｅｓｕｌｔ ｍｏｒｅ
ｅｆｆｉｃｉｅｎｔｌｙ．
Ｋｅｙ ｗｏｒｄｓ： ＵＡＶ； ｐａｔｈ ｐｌａｎｎｉｎｇ； ＶＯＲＯＮＯＩ ｄｉａｇｒａｍ； ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ
０ 引言
无人机最重要的特点是无须考虑人机系统，因而具有高机
动性、零伤亡、费用低等一系列优点，在军用、民用领域受到越
来越广泛的关注
［１］
。 尤其在军事领域，无人机被用于执行侦
察、电子干扰、充当诱饵、目标攻击等任务。 由于无人驾驶，无
人机的任务规划就显得尤其重要。 路径规划是任务规划中最
为基础，也是最重要的部分。 合理的航路规划将有助于无人机
有效地规避威胁、减小飞行路径长度，提高其生存概率和作战
效率。
无人机路径规划方法主要有 ＶＯＲＯＮＯＩ 图搜索法、格栅搜
索法、人工势场法、基于生物激励神经网络的算法和基于模糊
逻辑的路径规划算法等。 文献［２，３］中均以 ＳＥＡＤ（ ｓｕｐｐｒｅｓｓｉｏｎ
ｏｆ ｅｎｅｍｙ ａｉｒ ｄｅｆｅｎｓｅ）作战任务为背景，利用 ＶＯＲＯＮＯＩ 图构建
初始路径，以最小化路径长度和威胁强度为目标进行路径的构
建。 对于该多目标优化问题，文献［２］中采用满意剪枝策略对
搜索过程中的不满足航路代价指标的航路直接进行剪枝，以搜
索无人机初始航路集合；文献［３］ 中使用了 Ｄｉｊｋｓｔｒａ 算法对路
径进行优化选择。 上述文章中均是通过线性加权和法将多目
标优换问题转换为单目标问题进行求解。 这样便面临着权重
系数如何选取的问题，同时，一旦任务决策者对各个目标的偏
好程度发生变化，便需要更改权重系数，重新进行优化选择。
为了克服上述算法的缺点，本文通过引入新的启发信息，同时
修改启发信息计算公式对基本多目标蚁群算法进行改进，利用
改进的蚁群算法进行路径选择和优化，找出问题的 Ｐａｒｅｔｏ 最优
解集提交给决策者，为决策者更好地作出决定提供了帮助。
１ 问题描述及环境模型的建立
无人机的 ＳＥＡＤ 任务路径规划可以简单描述为：给定起始
点和目标点，规划一条路径使得从起始点出发的无人机能够绕
开障碍物和敌防空火力威胁顺利到达目的地，从而执行其攻击
或监视任务。 为了讨论方便，本文将障碍物、威胁均简化为点
状威胁，假设所有威胁点位置是已知且固定不变的，并且各个
威胁对无人机的威胁强度是相同的。 在该假设前提下，以各个
威胁点为基础构建 ＶＯＲＯＮＯＩ 图，如图 １ 所示。 ＶＯＲＯＮＯＩ 图
的边构造出了所有的可行路径，这些边的交点即为所有可行路
径点。
无人机路径规划是一个多目标的优化问题，本文以最小化
路径长度和最小化威胁代价为目标进行路径的选择优化。 在
已构建的初始路径的基础上，一条可行路径由包括起始点和目
第 ２６ 卷第 ６ 期
２００９ 年 ６ 月
计 算 机 应 用 研 究
Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ
Ｖｏｌ．２６ Ｎｏ．６
Ｊｕｎ．２００９
评论0