智能系统：人工蜂群算法的无人机航路规划与平滑

第6卷第4期 智能系统学报 Vol.6 No.4 2011年8月 CAAI Transactions on Intelligent Systems Aug.2011 doi:10.3969/i.i88n.1673-4785.2011.04.011 人工蜂群算法的无人机航路规划与平滑 刘敏12，邹杰12，冯星2，赵振字12 (1.光电控制技术重点实验室，河南洛阳471009；2.中航工业洛阳光电设备研究所，河南洛阳471009) 摘要：航路规划是无人机(UAV)作战任务规划系统的关键组成部分，目标是在适当的时间内为UAV计算出最优 或次最优的飞行航路.人工蜂群(ABC)算法是一种最新发展的模拟昆虫王国中蜜蜂群体寻找优良蛮源的群体智能 优化算法.采用人工蜂群算法完成无人机的平滑航路规划，首先闸述了人工蜂群算法的基本原理，然后将无人机航 路规划问题通过建模转换成为一个多维函数优化问题，利用人工蜂群算法的优势，找到多维函数的最优解，最后对 优化后的航路进行了平滑，使UAV对规划后的航路可飞.仿真实验结果表明，此方法可有效规划出航路，且所规划的 航路可飞. 关键词：无人机；航路规划；人工蜂群算法；平滑 中图分类号：TP18;V19文献标识码：A文章编号：16734785(2011)04034406 Smooth trajectory planning of an unmanned aerial vehicle using an artificial bee colony algorithm LIU Min'2,ZOU Jie2,FENG Xing2,ZHAO Zhenyu'2 (1.Science and Technology on Electro-optic Control Laboratory,Luoyang 471009,China;2.Luoyang Institute of Electro-Optical E- quipment,AVIC,Luoyang 471009,China Abstract:Trajectory is a key issue for an unmanned aerial vehicle(UAV),which aims to obtain an optimal or sub- optimal trajectory within proper time.The artificial bee colony (ABC)is a new algorithm based on how a bee colo- ny finds food.On the basis of introducing the basic principle of the ABC,and the description of threatening models of a UAV,the UAV trajectory planning was transformed into an optimization problem through modeling.Then the optimal solution of the multi-dimensional function was given by taking advantage of the artificial bee colony algo- rithm.Finally,the smoothing strategy was adopted to obtain a feasible path.The feasibility and effectiveness of the proposed approach was verified by experimental results. Keywords:unmanned aerial vehicle (UAV);trajectory planning;artificial bee colony (ABC)algorithm;smoot- hing 航路规划是无人机(unmanned aerial vehicle, 巡航导弹上的成功应用，航路规划方法研究日益受 UAV)作战任务规划系统的关键组成部分，目标 到世界各国的重视. 是在适当的时间内为UAV计算出最优或次优的飞 人工蜂群算法(artificial bee colony,ABC)是一 行航路，这个航路能使UAV突破敌方威胁环境，并 种最新发展的模拟昆虫王国中蜜蜂群体寻找优良蜜 且在完成任务目标的同时自我生存.航路规划时需 源的仿生优化算法2].它是建立在蜜蜂自组织模型 要考虑地形、数据、威胁信息、燃油和时间约束等. 和群体智能基础上的一种计算方法，主要从蜜蜂实 “运筹帷幄之中，决胜千里之外”自古就是军事家们 现采蜜的群体智能行为中得到启发.尽管人工蜂群 追求的目标，航路规划的出现为实现这一目标提供 算法的研究和应用还处于初级阶段，但由于算法的 了有力的技术支持.随着航路规划技术在“战斧”等 控制参数少、易于实现、计算方便等优点1，已经被 越来越多的学者所关注；相对于蚁群算法、遗传算 收稿日期：201101-28. 基金项目：总装重点实验室基金资助项目(9140C460104091301) 法、微粒群算法等其他仿生智能算法，人工蜂群具有 通信作者：刘敏.E-mail:chenshuizhong@gmail..com 很好的全局搜索能力和局部搜索能力，不易陷入局

第4期 刘敏，等：人工蜂群算法的无人机航路规划与平滑 ·345· 部最优，易收敛等优点4]，已被广泛地应用于函数 在多峰函数求极值中，与函数值有关，用数字量“收 优化、图像处理、神经网络训练等领域中，并取得了 益度”衡量蜜源. 很多不错的研究成果。 2)采蜜蜂(employed foragers) 采用人工蜂群算法完成无人机的平滑航路规 采蜜蜂同具体的蜜源联系在一起，采蜜蜂通过 划，首先将无人机航路规划问题通过建模转换成为 摇摆舞与其他蜜蜂分享这些信息，并按照收益度等 一个多维函数优化问题，然后利用人工蜂群算法的 因素，一部分成为引领蜂 优势，找到多维函数的最优解，最后对优化后的航路 3)待工蜂(unemployed foragers) 进行了平滑，使UAV对规划后的航路可飞.仿真实 正在寻找蜜源采集，可以分为侦查蜂和跟随蜂 验结果表明，所研究的方法可有效规划出航路，且所 2种：侦查蜂搜索新蜜源，跟随蜂在巢内等待，通过 规划的航路可飞 分享EF的信息来找到蜜源. 此外，引入3种基本的行为模式：搜索蜜源 1人工蜂群算法基本原理 (search)、为蜜源招募(recruit)、放弃蜜源(aban- 1.1算法起源 don).如图2所示，假设有2个已经发现的蜜源：A、 诺贝尔奖得主奥地利人K,Von Frisch发现，在 B,刚开始时，待工蜂没有关于蜜源的任何信息，有2 自然界中，虽然各社会阶层的蜜蜂只能完成单一的 种选择： 任务，但是蜜蜂通过摇摆舞、气味等多种信息交流方 1)待工蜂作为侦查蜂，自发寻找蜂巢附近的蜜 式，使得整个蜂群总是能很自如地发现优良蜜源 源(S线)； (或花粉)，实现自组织行为（如图1所示） 2)在观察到其他蜜蜂的摇摆舞之后（分享信息）可 以被招募，并按照获得的信息寻找蜜源(‘R'线)， 待工蜂发现新的蜜源之后，蜜蜂记住蜜源的位 置，并迅速采蜜，因此待工蜂变成了采蜜蜂.蜜蜂采 完蜜之后回到蜂箱，有以下3种选择： 1)放弃蜜源（收益度不高），成为待工的跟随蜂 (UF): 2)跳摇摆舞招募蜂巢其他伙伴(EF1); 图1蜜峰跳摇摆舞 3)不招募蜜蜂，继续采蜜(EF2) Fig.1 Sketch map of swing dancing bees 非蜜源 蜜源A 在自然界中，蜜蜂沿直线爬行，然后再向左这样 EP2 EF1 一种舞蹈，其动线呈8字型，并摇摆其腹部，舞蹈的 EP2 中轴线与地心引力的夹角正好表示蜜源方向和太 特工蜂 U蜂房A 摇摆舞区A 阳方向的夹角α；蜜蜂跳舞摆尾的时间表示蜂巢距 EFI 摇摆舞XA 离蜜源的远近；在蜂巢内的蜜蜂根据摇摆舞得到的 摇摆舞风B 信息，选择蜜源去采蜜或者在附近重新寻找新的蜜 蜂箱 U 卸 源.蜜蜂之间通过这种相互之间的信息交流、学习， 蜂房B EP2 使得整个蜂群总能找到较优的蜜源进行采蜜.土耳 EP 其Erciyes大学的D.Karaboga于2005年提出了人 非蜜源 EFI 蜜源B 工蜂群算法]，该算法最初应用于多峰值函数. 图2人工蜂群算法原理 1.2算法基本原理 Fig.2 Sketch map of principles of the ABC 蜂群实现采蛮的集体智能行为包含3个基本部 初始时刻，所有蜜蜂没有任何先验知识，其角色 分：蜜源、采蜜蜂EF、待工蜂UF,此外引入3种基本 都是侦查蜂.随机搜索到蛮源后，根据蛮源收益度相 的行为模式：搜索蜜源、为蜜源招募和放弃蜜源4」 对大小，侦查蜂可以转换为上述任何一种蛮蜂，其转 1)蜜源(food sources). 变原则如下：当所采集食物源收益度排名高于临界 蜜源代表解空间范围内各种可能的解，蜜源值 时，成为引领蜂，继续采蜜，并招募更多蜜蜂采蜜 取决于多种因素，诸如蜜源与蜂巢的接近程度、蜜源 (EF1):食物源收益度相对很低时，放弃该食物源， 内的大小和集中程度以及提取该能量的容易程度. 再次成为侦查蜂搜寻食物源(UF):所采集食物源收

·346 智能系统学报 第6卷 益度排名小于临界值时，可以成为跟随蜂，前往相应 然后将X'轴D等分，对每个节点垂线上相应的 的食物源采蜜；当在蜜源周围搜索次数超过极限，但 Y坐标进行优化，得到一组由D个点的纵向坐标组 仍未找到较优的蜜源时，放弃该蜜源，并去寻找新的 成的点列，显然，这些点的横坐标很容易得到.将这 蜜源. 些点按顺序连接在一起，就组成了一条路径，这样就 在整个群体智慧的形成过程中，蜜蜂间交换信 把航路规划问题转换成了一个D维函数优化问题 息是最为重要的一环.引领蜂通过摇摆舞的持续时 2.2航路优化性能指标 间等来表现食物源的收益率，收益率与食物源被选 无人机航路规划是根据任务目标规划出满足某 择的可能性成正比.因而，蜜蜂被招募到某一个食物 种性能指标最优的飞行航路，其性能指标主要包括完 源的概率与食物源的收益率成正比.在整个寻找最 成规定任务的安全性能指标和燃油性能指标8]，即威 优解的过程中，引领蜂有保持优良花蜜源的作用：跟 胁代价最小性能指标和燃油代价最小性能指标 随蜂增加优良花蜜源对应的蜜蜂数目，起到提高算 威胁代价最小性能指标为 法收敛速度的作用；侦察蜂随机搜索新花蜜源，能帮 助算法跳出局部最优.正是通过这种信息交流方式， min J.wdl, 蜜蜂发挥群体智能，总能找到较优的蜜源位置.相对 油耗代价最小性能指标为 于其他诸如遗传算法、粒子群算法，人工蜂群算法最 大的优点是它在每次迭代都进行局部搜索，因此找 咖- 则UAV航路的总性能指标为 到最优参数的概率也大大增加： min J=kJ:+(1-k)J 2 UAV航路规划建模 式中：0，表示航路上各点的威胁代价；w表示航路上 各点的油耗代价，是航路长度的函数（仿真中，0=1） 航路规划是无人机作战任务规划系统的关键组 L为航路的长度；k∈[0,1]，表示安全性能与燃油性 成部分，目标是在适当的时间内为无人机计算出最 能的权衡系数，其值可根据UAV所执行的任务而定， 优或次最优的飞行航路，这个航路能使无人机突破 如果任务重视飞行时的安全性，则飞选择较大的值； 敌方威胁环境，并且在完成任务目标的同时自我生 如果任务需要飞机的快速性，则斥选择较小的值.总 存.航路规划时需要考虑地形、数据、威胁信息、燃油 之，加权的大小取决于权项的重要性和可行性的综合 和时间约束等6] 指标 2.1航路规划问题建模 2.3威胁代价的计算 如图3，将原坐标系转换为以起始点到目标点 当无人机沿路径L飞行时，N,个威胁源对其 连线为横轴的新的坐标轴系[]，坐标转化公式如式 产生的总的威胁代价为 (1)所示，其中(x,y)为点在原地面坐标系OXY下 的坐标，(x',y)为该点在旋转坐标系OXY下的坐 4-。名(x-)+(y-' 标值，0为坐标系的旋转角度， 为了简化计算，如图4所示1，把每条边等分 0=arcsin Y2-Y1 为5段，取其中的5个点来计算这条边所受到的威 I ABI 胁代价，若威胁点到该边的距离在威胁半径之内，则 按下列公式计算它的威胁代价： sin0cos0八y' 日标总 0=5台 1+ 1 1 1 (2) 式中：Lg为连接节点i,J边的长度；d.L,k表示Lg边上 的1/I0分点距第k个威胁源中心的距离；为威胁 起始点 源的威胁等级， (Xova) 另外，由于燃油代价与航程有关，故可以简单认 图3航路规划原理 为0=L,则对每一条边的燃油代价有0私=L, Fig.3 Schematic diagram of trajectory planning

第4期 刘敏，等：人工蜂群算法的无人机航路规划与平滑 ·347· 威胁点k 续，这种航路较为光滑； 5/10 ▣J 4)第4类曲线是最为光滑的航路，航路曲线的 威胁点+1 19/10 曲率也是连续的，性能非常好，但这类曲线的算法比 ●了 7/10 较复杂，在实际系统中一般不予以采用. 1/10 利用人工蜂群算法规划出的无人机飞行航路属 威胁点k-1 于第2类曲线，曲线本身是连续的，但是在节点处不 L0 可微，实际中对UAV而言不是一条可飞的航路，因 图4威胁代价的计算 此对已经规划出的航路还要经平滑处理使之成为连 Fig.4 Calculation of threat costs 续可微的航线： 航路平滑的主要目的是：应用数学的方法，去掉 3 UAV航路规划与平滑 凹凸点，使得搜索出的最优航路不仅连续，并且它的 利用人工蜂群算法进行无人机平滑航路规划的 一阶导数也连续，使搜索出来的曲线成为第3类曲 具体实现步骤如下： 线 1)初始化算法参数，并根据所给的任务和威胁 考虑如图5所示的航路1o,该航路由0：-1、w: 信息，建立旋转坐标系，将战场威胁信息转化到旋转 和0：+1组成.很明显，航路在节点0：处存在切向突 坐标系上，转换公式如式(1)所示，将旋转坐标系的 变，对UAV而言是不可飞路段，必须对其进行平滑. 横轴D等分，每一个可行解都由D个由浮点数表示 的坐标组成的数列，可记为P={p1,P2,·,P; 2)在战场范围允许的条件下，随机产生M条初 始路径作为初始蜜源，根据战场上各个威胁的信息， 计算每一条可行路径的代价值，如式(2)； 3)采蜜蜂在初始蜜源周围进行搜索更优的路 径，若找到路径更优，直接替换原路径； 4)跟随蜂根据采蜜蜂搜索到的路径的威胁值 w. 大小，按概率选择威胁值较小的蜜源（路径），在其 图5UAV航路点平滑 周围进行搜索路径，若找到路径更优，则直接替换原 Fig.5 Smoothing to UAV trajectory point 路径； 可令q:表示从0：-1到0：的单位向量，4：+1为从 5)找出所有路径中威胁值最小的路径进行标记； 0:到0：+1的单位向量，则有 6)若某一蜜源附近的搜索次数已经达到上限， 9:=（0:-0:-1）/‖0：-0-1‖， 仍没找到更优的路径，则放弃该蜜源，重新随机初始 q+1=(0+1-0:)/‖0+l-0:‖. 化一条新的路径； 令B表示向量9：与9+1的夹角，则B= 7)若迭代次数大于最大迭代次数，则退出循 arccos(-9:+1·q:).C表示内切圆，其半径可表示为 环，否则转人3)，进人下一迭代； R=0.5min‖0：-w-t‖， 8)将最终得到的最优路径坐标进行坐标反变 换，并输出； 【画Iam号 (3) 显然，内切圆C的圆心在2条折线夹角的平分 9)对路径进行平滑操作，平滑半径和圆心的设 线上，因此，圆心C:的坐标可表示为 置见式(3)和(4)，选取圆弧上的点作为平滑航路， 并在图中显示所得路径. C=+(R/sm)(g-g,)/1g1-9.. 不同的航路规划算法所产生的各种航路分成以 (4) 下4类： 那么，经过平滑处理后，原先的航路0：-10：→ 1)第1类航路是不连续的，平滑程度最低，存在 0:+1可由0：-1A→ACB→B0:+1代替，显然，平滑处 位置的突变奇异点，这类型曲线显然是不可飞航路； 理后的航路对UAV而言是可行的. 2)第2类曲线是连续的曲线，但是曲线中存在 利用人工蜂群算法进行无人机航路规划的基本 切线方向的突变； 流程如图6所示. 3)第3类曲线不仅连续，而且切线方向角也连

348 智能系统学报 第6卷 100 日标点 开始 0威胁中心 80 ·起始点 坐标系转换 60 随机初始化N条路径作 高地 子弹 为蜜源，并计算母条路 40 径的威胁值 20 采蜜峰在蛮源附近搜索新路径 106 10 30 50 若找到更优路径，对原路径 7090 X (蜜源)进行矿替代 图7航路规划结果（平滑前） 根据路径代价计算 Fig.7 Trajectory planning results(before smoothing) 每条的被跟随做 100r口目标点 按概率选择蜜源，在其周围 。威胁中心 寻找新的路径，若比原路径 80叶·起始点 史优，则替代原路径 60 0 、 计算最小路径代价 T-T+1 重达 以及最小路径坐标点 40 高幽 若某条路径的搜索次数超过 20 导弹 Limit,仍没有找到史优路径， 重新初始化一条新的路径 10%10 30 50 70 90 T>T? 图8航路规划结果（平滑后】 Fig.8 Trajectory planning results(after smoothing) Y 75 进行坐标新反变换 并输出最优路径 70 航路平滑 60 (结束 55 图6UAV航路规划算法流程 50/ Fig.6 Trajectory planning algorithm process of UAV 450 20 40 60 80100 4仿真算例分析 迭代次数 设定UAV飞行任务的战场环境如表1所示，仿 图9人工蜂群算法收敛曲线 真软件的运行环境为Windows XP,使用Mat Fig.9 Convergence curve of ABC algorithm lab2009b进行仿真分析. 图7为基于人工蜂群算法的航路规划结果，可 表1任务设置 以看出，航路段与段之间存在不可微的情况，即不可 Table 1 Task setting 飞点，不能满足无人机的飞行性能约束，经过本文的 起始点坐标[21,21]输入终点[80,80]代价权值0.5 平滑策略处理后，见图8，航路变得较为光滑，可以 威胁中心[52,52][32,40][12,48][36,26][80,6] 满足无人机的飞行要求.通过图9可以看出，基于人 工蜂群的算法在第9次迭代时出现了快速收敛的现 威胁半径 10 10 8 12 9 象，第16代的规划结果已经达到了可飞解的效果， 威胁等级 2 10 1 2 3 表明改算法具有比较快的收敛速度.由以上结果表 设置采蜜蜂数量为30，跟随蜂数量为30，最大 明，人工蜂群算法在解决无人机平滑航路规划问题 搜索极限30，函数优化维数为12，最大迭代次数为 时具有可靠性和有效性.下一步，将进一步开展基于 100,威胁类型包括高炮、导弹、雷达、禁飞区，仿真结 动态威胁的人工蜂群航路规划研究，满足机载实时 果如图7~9所示. 重规划的要求

第4期 刘敏，等：人工蜂群算法的无人机航路规划与平滑 ·349· [6]柳长安，李为吉，王和平.基于蚁群算法的无人机航路 5结束语 规划[J].空军工程大学学报：自然科学版，2004,2 采用人工蜂群算法完成无人机的平滑航路规 (5):9-12. 划，首先将无人机航路规划问题通过建模转换成为 LIU Chang'an,LI Weiji,WANG Heping.Path planning for reconnaissance UAV based on ant algorithm[J].Journal 一个多维函数优化问题，然后利用人工蜂群算法的 of Air Force Engineering University:Natural Science Edi- 优势，找到多维函数的最优解，最后对优化后的航路 tion,2004,2(5):9-12 进行了平滑，使UAV对规划后的航路可飞.仿真实 [7]王斌，陈知秋，林栋。基于遗传算法的无人机航路规划 验结果表明，所研究的方法可有效规划出航路，且所 与建模仿真[J].吉林工程技术师范学院学报，2010， 规划的航路可飞， (03):8-11. WANG Bin,CHEN Zhigiu,LIN Dong.Based on genetic 参考文献： algorithm for UAV route planning and modeling and simula- [1]田伟.无人作战飞机航路规划研究[D].西安：西北工 tion[J].Joumal of Jilin Teachers Institute of Engineering 业大学，2007：10-13. and Technology,2010(3):8-11. TIAN Wei.Research on the path planning for unmanned [8]XU Chunfang,DUAN Haibin,LIU Fang.Chaotic artificial combat air vehicle[D].Xi'an:Northwestern Polytechnical bee colony approach to uninhabited combat air vehicle University,2007:10-13. (UCAV)[J].Aerospace Science and Technology,2010, [2]KARABOGA D,BASTURK B.A powerful and efficient al- 14(8):535-541. gorithm for numerical function optimization:artificial bee [9]ANDERSON E P.BEARD R W,MCLAIN T W.Real-time colony (ABC)algorithm[J].Joural of Global Optimiza- dynamic trajectory smoothing for unmanned air vehicles[J]. ion,2007,39(3):459471. IEEE Transactions on Control Systems Technology,2005, [3]KARABOGA D,BASTURK B.On the performance of arti- 13(3):471477. ficial bee colony (ABC)algorithm[J].Applied Soft Com- 作者简介： puting,2008,8(1):687697. 刘敏，女，1980年生，工程师，主要 [4]HU C L,SUN T Y.Reliable multi-goal route planning for 研究方向为仿生智能计算、无人机航路 vehicle using skeletonization and genetic algorithms[C] 规划. Proc 2008 CACS International Automatic Control Confer ence.[S.l.],2008:159-263. [5]KARABOGA D.An idea based on honey bee swarm for nu- merical optimization technical report 06[R].Erciyes Uni- versity,2005