人工蜂群算法的无人机航路规划与平滑

刘敏，邹杰，冯星，赵振宇

(1.光电控制技术重点实验室，河南洛阳 471009;2.中航工业洛阳光电设备研究所，河南洛阳 471009)

人工蜂群算法的无人机航路规划与平滑

刘敏1，2，邹杰1，2，冯星1，2，赵振宇1，2

(1.光电控制技术重点实验室，河南洛阳 471009;2.中航工业洛阳光电设备研究所，河南洛阳 471009)

航路规划是无人机(UAV)作战任务规划系统的关键组成部分，目标是在适当的时间内为UAV计算出最优或次最优的飞行航路.人工蜂群(ABC)算法是一种最新发展的模拟昆虫王国中蜜蜂群体寻找优良蜜源的群体智能优化算法.采用人工蜂群算法完成无人机的平滑航路规划，首先阐述了人工蜂群算法的基本原理，然后将无人机航路规划问题通过建模转换成为一个多维函数优化问题，利用人工蜂群算法的优势，找到多维函数的最优解，最后对优化后的航路进行了平滑，使UAV对规划后的航路可飞.仿真实验结果表明，此方法可有效规划出航路，且所规划的航路可飞.

无人机;航路规划;人工蜂群算法;平滑

航路规划是无人机(unmanned aerial vehicle，UAV)作战任务规划系统的关键组成部分［1］，目标是在适当的时间内为UAV计算出最优或次优的飞行航路，这个航路能使UAV突破敌方威胁环境，并且在完成任务目标的同时自我生存.航路规划时需要考虑地形、数据、威胁信息、燃油和时间约束等.“运筹帷幄之中，决胜千里之外”自古就是军事家们追求的目标，航路规划的出现为实现这一目标提供了有力的技术支持.随着航路规划技术在“战斧”等巡航导弹上的成功应用，航路规划方法研究日益受到世界各国的重视.

人工蜂群算法(artificial bee colony，ABC)是一种最新发展的模拟昆虫王国中蜜蜂群体寻找优良蜜源的仿生优化算法［2］.它是建立在蜜蜂自组织模型和群体智能基础上的一种计算方法，主要从蜜蜂实现采蜜的群体智能行为中得到启发.尽管人工蜂群算法的研究和应用还处于初级阶段，但由于算法的控制参数少、易于实现、计算方便等优点［3］，已经被越来越多的学者所关注;相对于蚁群算法、遗传算法、微粒群算法等其他仿生智能算法，人工蜂群具有很好的全局搜索能力和局部搜索能力，不易陷入局部最优，易收敛等优点［4］，已被广泛地应用于函数优化、图像处理、神经网络训练等领域中，并取得了很多不错的研究成果.

采用人工蜂群算法完成无人机的平滑航路规划，首先将无人机航路规划问题通过建模转换成为一个多维函数优化问题，然后利用人工蜂群算法的优势，找到多维函数的最优解，最后对优化后的航路进行了平滑，使UAV对规划后的航路可飞.仿真实验结果表明，所研究的方法可有效规划出航路，且所规划的航路可飞.

1 人工蜂群算法基本原理

1.1 算法起源

诺贝尔奖得主奥地利人K.Von Frisch发现，在自然界中，虽然各社会阶层的蜜蜂只能完成单一的任务，但是蜜蜂通过摇摆舞、气味等多种信息交流方式，使得整个蜂群总是能很自如地发现优良蜜源(或花粉)，实现自组织行为(如图1所示).

图1 蜜蜂跳摇摆舞Fig.1 Sketch map of swing dancing bees

在自然界中，蜜蜂沿直线爬行，然后再向左这样一种舞蹈，其动线呈8字型，并摇摆其腹部，舞蹈的中轴线与地心引力的夹角 正好表示蜜源方向和太阳方向的夹角α;蜜蜂跳舞摆尾的时间表示蜂巢距离蜜源的远近;在蜂巢内的蜜蜂根据摇摆舞得到的信息，选择蜜源去采蜜或者在附近重新寻找新的蜜源.蜜蜂之间通过这种相互之间的信息交流、学习，使得整个蜂群总能找到较优的蜜源进行采蜜.土耳其Erciyes大学的D.Karaboga于2005年提出了人工蜂群算法［5］，该算法最初应用于多峰值函数.

1.2 算法基本原理

蜂群实现采蜜的集体智能行为包含3个基本部分:蜜源、采蜜蜂EF、待工蜂UF，此外引入3种基本的行为模式:搜索蜜源、为蜜源招募和放弃蜜源［4］.

1)蜜源(food sources).

蜜源代表解空间范围内各种可能的解，蜜源值取决于多种因素，诸如蜜源与蜂巢的接近程度、蜜源内的大小和集中程度以及提取该能量的容易程度.在多峰函数求极值中，与函数值有关，用数字量“收益度”衡量蜜源.

2)采蜜蜂(employed foragers).

采蜜蜂同具体的蜜源联系在一起，采蜜蜂通过摇摆舞与其他蜜蜂分享这些信息，并按照收益度等因素，一部分成为引领蜂.

3)待工蜂(unemployed foragers).

正在寻找蜜源采集，可以分为侦查蜂和跟随蜂2种;侦查蜂搜索新蜜源，跟随蜂在巢内等待，通过分享EF的信息来找到蜜源.

此外，引入3种基本的行为模式:搜索蜜源(search)、为蜜源招募(recruit)、放弃蜜源(abandon).如图2所示，假设有2个已经发现的蜜源:A、B，刚开始时，待工蜂没有关于蜜源的任何信息，有2种选择:

1)待工蜂作为侦查蜂，自发寻找蜂巢附近的蜜源(‘S’线);

2)在观察到其他蜜蜂的摇摆舞之后(分享信息)可以被招募，并按照获得的信息寻找蜜源(‘R’线).

待工蜂发现新的蜜源之后，蜜蜂记住蜜源的位置，并迅速采蜜，因此待工蜂变成了采蜜蜂.蜜蜂采完蜜之后回到蜂箱，有以下3种选择:

1)放弃蜜源(收益度不高)，成为待工的跟随蜂(UF);

2)跳摇摆舞招募蜂巢其他伙伴(EF1);

3)不招募蜜蜂，继续采蜜(EF2).

图2 人工蜂群算法原理Fig.2 Sketch map of principles of the ABC

初始时刻，所有蜜蜂没有任何先验知识，其角色都是侦查蜂.随机搜索到蜜源后，根据蜜源收益度相对大小，侦查蜂可以转换为上述任何一种蜜蜂，其转变原则如下:当所采集食物源收益度排名高于临界时，成为引领蜂，继续采蜜，并招募更多蜜蜂采蜜(EF1);食物源收益度相对很低时，放弃该食物源，再次成为侦查蜂搜寻食物源(UF);所采集食物源收益度排名小于临界值时，可以成为跟随蜂，前往相应的食物源采蜜;当在蜜源周围搜索次数超过极限，但仍未找到较优的蜜源时，放弃该蜜源，并去寻找新的蜜源.

在整个群体智慧的形成过程中，蜜蜂间交换信息是最为重要的一环.引领蜂通过摇摆舞的持续时间等来表现食物源的收益率，收益率与食物源被选择的可能性成正比.因而，蜜蜂被招募到某一个食物源的概率与食物源的收益率成正比.在整个寻找最优解的过程中，引领蜂有保持优良花蜜源的作用;跟随蜂增加优良花蜜源对应的蜜蜂数目，起到提高算法收敛速度的作用;侦察蜂随机搜索新花蜜源，能帮助算法跳出局部最优.正是通过这种信息交流方式，蜜蜂发挥群体智能，总能找到较优的蜜源位置.相对于其他诸如遗传算法、粒子群算法，人工蜂群算法最大的优点是它在每次迭代都进行局部搜索，因此找到最优参数的概率也大大增加.

2 UAV航路规划建模

航路规划是无人机作战任务规划系统的关键组成部分，目标是在适当的时间内为无人机计算出最优或次最优的飞行航路，这个航路能使无人机突破敌方威胁环境，并且在完成任务目标的同时自我生存.航路规划时需要考虑地形、数据、威胁信息、燃油和时间约束等［6］.

2.1 航路规划问题建模

如图3，将原坐标系转换为以起始点到目标点连线为横轴的新的坐标轴系［7］，坐标转化公式如式(1)所示，其中(x，y)为点在原地面坐标系OXY下的坐标，(x'，y')为该点在旋转坐标系OX'Y'下的坐标值，θ为坐标系的旋转角度.

图3 航路规划原理Fig.3 Schematic diagram of trajectory planning

然后将X'轴D等分，对每个节点垂线上相应的Y'坐标进行优化，得到一组由D个点的纵向坐标组成的点列，显然，这些点的横坐标很容易得到.将这些点按顺序连接在一起，就组成了一条路径，这样就把航路规划问题转换成了一个D维函数优化问题.

2.2 航路优化性能指标

无人机航路规划是根据任务目标规划出满足某种性能指标最优的飞行航路，其性能指标主要包括完成规定任务的安全性能指标和燃油性能指标［8］，即威胁代价最小性能指标和燃油代价最小性能指标.

威胁代价最小性能指标为

油耗代价最小性能指标为

则UAV航路的总性能指标为

式中:wt表示航路上各点的威胁代价;wf表示航路上各点的油耗代价，是航路长度的函数(仿真中，wf≡1)L为航路的长度;k∈［0，1］，表示安全性能与燃油性能的权衡系数，其值可根据UAV所执行的任务而定，如果任务重视飞行时的安全性，则k选择较大的值;如果任务需要飞机的快速性，则k选择较小的值.总之，加权的大小取决于权项的重要性和可行性的综合指标.

2.3 威胁代价的计算

当无人机沿路径Li，j飞行时，Nt个威胁源对其产生的总的威胁代价为

为了简化计算，如图4所示［9］，把每条边等分为5段，取其中的5个点来计算这条边所受到的威胁代价，若威胁点到该边的距离在威胁半径之内，则按下列公式计算它的威胁代价:

式中:Lij为连接节点i，j边的长度;d0.1，k表示Lij边上的1/10分点距第k个威胁源中心的距离;tk为威胁源的威胁等级.

另外，由于燃油代价与航程有关，故可以简单认为wf=L，则对每一条边的燃油代价有=Lij.

图4 威胁代价的计算Fig.4 Calculation of threat costs

3 UAV航路规划与平滑

利用人工蜂群算法进行无人机平滑航路规划的具体实现步骤如下:

1)初始化算法参数，并根据所给的任务和威胁信息，建立旋转坐标系，将战场威胁信息转化到旋转坐标系上，转换公式如式(1)所示，将旋转坐标系的横轴D等分，每一个可行解都由D个由浮点数表示的坐标组成的数列，可记为P={p1，p2，…，pD};

2)在战场范围允许的条件下，随机产生M条初始路径作为初始蜜源，根据战场上各个威胁的信息，计算每一条可行路径的代价值，如式(2);

3)采蜜蜂在初始蜜源周围进行搜索更优的路径，若找到路径更优，直接替换原路径;

4)跟随蜂根据采蜜蜂搜索到的路径的威胁值大小，按概率选择威胁值较小的蜜源(路径)，在其周围进行搜索路径，若找到路径更优，则直接替换原路径;

5)找出所有路径中威胁值最小的路径进行标记;

6)若某一蜜源附近的搜索次数已经达到上限，仍没找到更优的路径，则放弃该蜜源，重新随机初始化一条新的路径;

7)若迭代次数大于最大迭代次数，则退出循环，否则转入3)，进入下一迭代;

8)将最终得到的最优路径坐标进行坐标反变换，并输出;

9)对路径进行平滑操作，平滑半径和圆心的设置见式(3)和(4)，选取圆弧上的点作为平滑航路，并在图中显示所得路径.

不同的航路规划算法所产生的各种航路分成以下4类:

1)第1类航路是不连续的，平滑程度最低，存在位置的突变奇异点，这类型曲线显然是不可飞航路;

2)第2类曲线是连续的曲线，但是曲线中存在切线方向的突变;

3)第3类曲线不仅连续，而且切线方向角也连续，这种航路较为光滑;

4)第4类曲线是最为光滑的航路，航路曲线的曲率也是连续的，性能非常好，但这类曲线的算法比较复杂，在实际系统中一般不予以采用.

利用人工蜂群算法规划出的无人机飞行航路属于第2类曲线，曲线本身是连续的，但是在节点处不可微，实际中对UAV而言不是一条可飞的航路，因此对已经规划出的航路还要经平滑处理使之成为连续可微的航线.

航路平滑的主要目的是:应用数学的方法，去掉凹凸点，使得搜索出的最优航路不仅连续，并且它的一阶导数也连续，使搜索出来的曲线成为第3类曲线.

考虑如图 5 所示的航路［10］，该航路由wi－1、wi和wi+1组成.很明显，航路在节点wi处存在切向突变，对UAV而言是不可飞路段，必须对其进行平滑.

图5 UAV航路点平滑Fig.5 Smoothing to UAV trajectory point

可令 qi表示从wi－1到wi的单位向量，qi+1为从wi到wi+1的单位向量，则有

令 β 表示向量 qi与 qi+1的夹角，则 β=arccos(－qi+1·qi).C表示内切圆，其半径可表示为

显然，内切圆C的圆心在2条折线夹角的平分线上，因此，圆心Ci的坐标可表示为

利用人工蜂群算法进行无人机航路规划的基本流程如图6所示.

图6 UAV航路规划算法流程Fig.6 Trajectory planning algorithm process of UAV

4 仿真算例分析

设定UAV飞行任务的战场环境如表1所示，仿真软件的运行环境为 Windows XP，使用 Matlab2009b进行仿真分析.

表1 任务设置Table 1 Task setting

设置采蜜蜂数量为30，跟随蜂数量为30，最大搜索极限30，函数优化维数为12，最大迭代次数为100，威胁类型包括高炮、导弹、雷达、禁飞区，仿真结果如图7～9所示.

图7 航路规划结果(平滑前)Fig.7 Trajectory planning results(before smoothing)

图8 航路规划结果(平滑后)Fig.8 Trajectory planning results(after smoothing)

图9 人工蜂群算法收敛曲线Fig.9 Convergence curve of ABC algorithm

图7为基于人工蜂群算法的航路规划结果，可以看出，航路段与段之间存在不可微的情况，即不可飞点，不能满足无人机的飞行性能约束，经过本文的平滑策略处理后，见图8，航路变得较为光滑，可以满足无人机的飞行要求.通过图9可以看出，基于人工蜂群的算法在第9次迭代时出现了快速收敛的现象，第16代的规划结果已经达到了可飞解的效果，表明改算法具有比较快的收敛速度.由以上结果表明，人工蜂群算法在解决无人机平滑航路规划问题时具有可靠性和有效性.下一步，将进一步开展基于动态威胁的人工蜂群航路规划研究，满足机载实时重规划的要求.

5 结束语

采用人工蜂群算法完成无人机的平滑航路规划，首先将无人机航路规划问题通过建模转换成为一个多维函数优化问题，然后利用人工蜂群算法的优势，找到多维函数的最优解，最后对优化后的航路进行了平滑，使UAV对规划后的航路可飞.仿真实验结果表明，所研究的方法可有效规划出航路，且所规划的航路可飞.

［1］田伟.无人作战飞机航路规划研究［D］.西安:西北工业大学，2007:10－13.

TIAN Wei.Research on the path planning for unmanned combat air vehicle［D］.Xi’an:Northwestern Polytechnical University，2007:10－13.

［2］KARABOGA D，BASTURK B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm［J］.Journal of Global Optimization，2007，39(3):459－471.

［3］KARABOGA D，BASTURK B.On the performance of artificial bee colony(ABC)algorithm［J］.Applied Soft Computing，2008，8(1):687－697.

［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 Conference.［S.l.］，2008:159－263.

［5］KARABOGA D.An idea based on honey bee swarm for numerical optimization technical report 06［R］.Erciyes University，2005.

［6］柳长安，李为吉，王和平.基于蚁群算法的无人机航路规划［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 Edition，2004，2(5):9－12.

［7］王斌，陈知秋，林栋.基于遗传算法的无人机航路规划与建模仿真［J］.吉林工程技术师范学院学报，2010，(03):8－11.

WANG Bin，CHEN Zhiqiu，LIN Dong.Based on genetic algorithm for UAV route planning and modeling and simulation［J］.Journal of Jilin Teachers Institute of Engineering and Technology，2010(3):8－11.

［8］XU Chunfang，DUAN Haibin，LIU Fang.Chaotic artificial bee colony approach to uninhabited combat air vehicle(UCAV)［J］.Aerospace Science and Technology，2010，14(8):535－541.

［9］ANDERSON E P，BEARD R W，MCLAIN T W.Real－time dynamic trajectory smoothing for unmanned air vehicles［J］.IEEE Transactions on Control Systems Technology，2005，13(3):471－477.

刘敏 ，女，1980年生，工程师，主要研究方向为仿生智能计算、无人机航路规划.

Smooth trajectory planning of an unmanned aerial vehicle using an artificial bee colony algorithm

LIU Min1，2，ZOU Jie1，2，FENG Xing1，2，ZHAO Zhenyu1，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)

Trajectory is a key issue for an unmanned aerial vehicle(UAV)，which aims to obtain an optimal or suboptimal trajectory within proper time.The artificial bee colony(ABC)is a new algorithm based on how a bee colony 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 algorithm.Finally，the smoothing strategy was adopted to obtain a feasible path.The feasibility and effectiveness of the proposed approach was verified by experimental results.

unmanned aerial vehicle(UAV);trajectory planning;artificial bee colony(ABC)algorithm;smoothing

TP18;V19

A

1673－4785(2011)04－0344－06

10.3969/j.issn.1673－4785.2011.04.011

2011－01－28.

总装重点实验室基金资助项目(9140C460104091301).

刘敏.E－mail:chenshuizhong@gmail.com.