基于改进蚁群算法的无人机路径规划

李喜刚, 蔡远利

(西安交通大学 电子与信息工程学院, 陕西 西安 710049)

基于改进蚁群算法的无人机路径规划

李喜刚, 蔡远利

(西安交通大学 电子与信息工程学院, 陕西 西安 710049)

针对传统无人机路径规划算法存在规划效率低以及无法满足特定任务需求的缺点,提出了基于改进蚁群优化算法的无人机路径规划算法。首先,将待规划区域栅格化,给每一个网格按顺序编号;其次,在路径搜索时引入了一种双向搜索机制,对信息素的更新规则和下一步节点的选择方法做出改进;最后,提出了一种新的方法来整合两组蚂蚁生成的路径,并给出了若干仿真试验结果。结果表明,所提算法相比传统算法更能有效避免过早陷入局部最优,收敛速度加快,生成满足任务约束的最短路径。

蚁群优化算法; 无人机路径规划; 双向搜索

0 引言

无人机在整个航空领域扮演着越来越重要的角色。为了完成各种民用和军事任务,无人机控制系统面临许多难题,比如多机任务协同、路径规划、路径跟踪等,其中路径规划是无人机导航和控制的核心技术。

对路径规划的研究始于20世纪60年代,国内外学者提出了大量的路径规划算法,包括A*算法[1]、Voronoi图算法[2]、动态规划方法[3]、仿生学算法[4]等。由于路径规划问题具有高时间复杂度,所以,问题的求解时间会随着问题的规模呈指数型增长,尤其在复杂环境或者搜索空间比较大的情况下,上述所有算法的计算成本会急剧增加。由此,提出了新的启发式算法和混合式算法用于无人机路径规划,典型代表有模糊控制[5]、神经网络[6]、蚁群优化算法[7]、模拟退火-人工势场法[8]和粒子群算法[9]。

蚁群优化算法(Ant Colony Optimization,ACO)是基于生物界蚂蚁的群体行为习性提出的一种仿生学搜索算法。为了使规划出来的路径能够满足特定的任务要求,需要对传统蚁群算法进行一定的改进。其中一种方法是改变蚁群的搜索机制,比如文献[10-11]提出的双向搜索。然而,文献[10]没有对路径的转弯角度作限制,也没有无人机的飞行性能约束,而文献[11]的搜索效率也不高。一般来讲,无人机从机场起飞后要经过一系列转弯过程才能加入航线,因此无人机离开出发点空域时有角度约束,同时,无人机可能要以特定的角度进入目标空域执行任务,显然传统的ACO算法不能满足任务需要。

本文针对无人机路径规划问题的特殊性,对传统ACO算法进行了改进。首先,将无人机的工作区域划分为一系列具有二值信息的网格单元,在栅格图中进行路径规划时考虑无人机的最大转弯角度限制,以及起始区域和终点区域的角度约束;然后改进了蚂蚁信息素的更新规则,根据每只蚂蚁所求解的质量不同,对蚂蚁经过路径上的信息素增量自适应地更新,信息素挥发系数ρ也随着迭代次数的增加而相应地改变,使得算法在一定程度上避免陷入局部最优;最后,提出了一种双向搜索机制,在任务起点和终点同时放出两组蚂蚁进行路径搜索,并分别讨论了搜索过程中蚂蚁的相遇问题,提出了一种路径整合方法,充分利用了搜索方向相对的两只蚂蚁各自的信息,加快了路径生成的速度。

1 搜索空间建模

本文无人机的搜索空间为一张32×32的栅格地图,每一个网格都被赋予从1到1024的一个编号。由蚁群优化算法最终生成的无人机路径是一个数集,如{1,2,13,25,…, 991},其中1为栅格地图上的起点编号,991为栅格地图上的终点编号。

栅格地图从左到右、自上而下的编号为:第一行从左至右依次为1,2,3,…,32,第二行从左至右依次为33,34,…,64,依此类推。栅格地图的网格编号和任务区域的坐标对应关系为:

(1)

式中:(xm,ym)为栅格地图中节点的坐标;(xr,yr)为真实任务区域的相对坐标;δ为无人机在单位时间内实际飞行的距离;f(x,δ)为x除以δ;H为栅格地图的高度;I为网格的编号。

在栅格地图中,障碍物占一个或多个栅格,当不满一个栅格时,算一个栅格。值为1代表该网格是障碍物,可能是雷达威胁或地形威胁,值为0代表无人机可以通过该区域,如图1所示。

在实际场景中,无人机的飞行路径还受到最大转弯角度和任务区域角度的约束。

图1 栅格地图(黑色方块代表禁飞区)Fig.1 Grid map(black squares indicating no-fly zones)

1.1 最大转弯角度

无人机在转弯机动时,由于性能限制转弯角度不能超过最大转弯角θm。也就是说,无人机在转弯时其角度变化范围不能超过[θ0-θm,θ0+θm],θ0为无人机当前的飞行角度,如图2所示。

图2 最大转弯角度约束示意图Fig.2 Diagram of maximum turning angle constraint

1.2 任务区域角度约束

通常情况下,机场的飞机离场图规定飞机必须按照特定的路线离开机场空域,飞机从跑道起飞后需要进行一系列的转弯机动,经过规定的导航台后才能加入航线,离开机场空域。这就要求从机场开始进行路径规划时,必须考虑无人机离开机场空域的起始角度。图3展示的是机场的其中一条离场航线示意图。同样地,任务的终点区域可能由于地形或者威胁限制了无人机的进近角度和方向,如图4所示。这样在作路径规划时,必须考虑无人机离开起始区域的角度θs和进入终点区域的角度θe。

图3 机场某条离场航线示意图Fig.3 Diagram of an illustrative departure route in airport

图4 任务终点角度示意图Fig.4 Diagram of approaching angle

2 改进的ACO路径规划算法

尽管ACO算法有着诸多的优势,但是它的缺点仍然不容忽视,例如收敛速度慢、易陷入局部最优、不能满足特定任务的需求等。为了解决这些问题,同时满足特定的任务约束,本文提出了一种改进的ACO算法。

2.1 改进蚂蚁的移动规则

在传统ACO算法中,每只蚂蚁在走完一步后要在邻接的节点中选择下一步要走的节点,候选节点数量将直接影响到计算状态转移概率的时间和内存消耗。在1.2节中提到,无人机最大转弯角限制了蚂蚁在选择下一节点时,不能把当前时刻它周围的8个节点都看作是候选节点,只有3个节点(如果它们不在禁飞区的话)才能算作是候选节点,且这3个节点和当前节点的连线与蚂蚁的前进方向夹角为θm∈{45°,0°,-45°},如图5所示。图中,黑色实线为蚂蚁已经走过的路径。

图5 可供蚂蚁选择的候选节点示意图Fig.5 Diagram of potential nodes for ants to choose

2.2 改进全局信息素的更新策略

2.2.1 改进信息素挥发系数的更新方式

通常情况下,ACO算法信息素的正反馈机制能够得到路径规划问题的全局最优解,但有时ACO算法会过早陷入局部优化。为了解决这个问题,本文首先对信息素挥发系数ρ的更新规则作了改进,使其可以随着迭代次数的增加自适应地改变。

(2)

式中:n为当前迭代的次数;N为设定迭代的总次数。

2.2.2 改进信息素增量的更新方式

通过引入信息素增量调节因子λ,根据每只蚂蚁所求解的优劣程度调节信息素的增量为：

(3)

(4)

通过引入信息素增量调节因子λ,使得在短时间内可以通过信息素增量来判断路径的优劣程度,可以将次优路径和其他路径分开,在较大程度上加快了算法的收敛速度,提高了算法的全局搜索能力。

综上所述,t+n时刻在蚂蚁的路径点(i,j)上的信息素更新法则如下:

(5)

(6)

2.3 双向搜索机制

在传统ACO算法中,一条路径的生成通常是从起点开始,到终点结束,没有充分发挥蚂蚁群体协作的特性,因此影响了算法的效率和收敛速度,而且不一定满足任务的角度约束,双向搜索机制能够有效解决这个问题。将两组蚂蚁(A组和B组)分别放在起点和终点区域,然后两组蚂蚁同时以对方的出发点为目的地寻找最短路径。A组的蚂蚁出发角为θs,终止角为θe,而B组的蚂蚁正好相反。

蚂蚁在寻找路径的过程中,寻路方向不同的两只蚂蚁可能会在途中相遇。这两只蚂蚁分别携带了它们各自的路径信息,通过整合它们的信息,可以快速得到一条新的可行路径,从而加快了算法的收敛速度。当蚂蚁移动到下一个节点后,就开始检测当前节点是否在对向蚂蚁的路径上,如果是,则通过整合机制将两条路径整合为一条新的可行路径;如果不是,则检测是否与对向来的蚂蚁相遇,当两只蚂蚁相遇时,也可以通过路径整合得到一条新的路径。

图6中可能出现两种情况。情况一:蚂蚁k1的当前位置为p3,蚂蚁k2的当前位置为p4,则两只蚂蚁不会相遇,但此时程序检测到p3已经被蚂蚁k2访问过,所以直接联合蚂蚁k1的路径path1={1,12,23,24,25,36,46,56}和蚂蚁k2的路径path2={98,89,79,69,58,57,56,55,54,53}生成新的路径path={1,12,23,24,25,36,46,56,57,58,69,79,89,98},考虑到无人机的最大转弯角限制,在路径结合处做平滑处理,最终得到新路径path—new={1,12,23,24,25,36,46,57,58,69,79,89,98}。情况二:蚂蚁k1的当前位置为p1,蚂蚁k2的当前位置为p2或者p3,根据相遇检测算法,两只蚂蚁在途中相遇了。此时,根据蚂蚁k1和k2的已有路径,考虑到路径结合处的最大转弯角度限制,直接生成一条满足约束条件的可行路径path—meet={1,12,23,24,25,36,46,57,58,69,79,89,98}。

图6 双向搜索算法示意图Fig.6 Diagram of bidirectional searching

3 仿真结果及分析

本文采用Matlab对改进的ACO算法进行两组仿真试验,除出发角为θs和终止角为θe不同外,其余参数完全一致。仿真参数为:蚂蚁数量M=50只;信息启发因子α=1;ρ=0.95;期望启发因子β=5;Q=1;θm=45°;搜索次数50次。仿真试验1的θs=0°,θe=180°,起始节点编号为65,目标节点编号为1021,仿真结果如图7所示。仿真试验2的θs=-90°,θe=135°,起始节点编号为65,目标节点编号为990,仿真结果如图8所示。

图7 仿真试验1路径规划结果Fig.7 Path planning in simulation 1

图8 仿真试验2路径规划结果Fig.8 Path planning in simulation 2

试验中,将传统的和改进的ACO算法的仿真结果进行了对比,结果如表1所示。图9和图10为两种算法最短路径收敛曲线对比图。

表1 仿真结果对比

图9 试验1最短路径收敛曲线Fig.9 Convergence curves of shortest path in simulation 1

图10 仿真试验2最短路径收敛曲线Fig.10 Convergence curves of shortest path in simulation 2

仿真结果表明,改进的ACO算法能够以更快的收敛速度规划出最短路径。图7和图8表明，传统ACO算法虽然能规划出一条从起点到终点的路径,但无法保证规划出来的路径满足任务的约束条件。图9和图10表明，改进的ACO算法的收敛速度和全局最优性都得到了较大提高。

4 结束语

本文提出了一种基于改进蚁群优化算法的无人机路径规划算法。该算法限制了蚂蚁在搜索路径时的“视野”,在一定程度上提高了算法的搜索效率。提出的蚂蚁相遇策略充分发挥了蚁群之间相互协作的群体特性,大大提升了生成路径的速度。

传统蚁群算法和改进蚁群算法收敛曲线对比结果表明,改进算法比传统算法具有更快的收敛速度,能够更快、更有效地获得可行路径。在接下来的工作中,可以将本优化算法拓展到三维空间和更复杂、更真实的应用场景中。

[1] 谭宝成,王培.A*路径规划算法的改进与实现[J].西安工业大学学报,2012,32(4):325-329.

[2] Pehilivanoglu Y V.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology,2012,16(1):47-55.

[3] Jennings A L,Ordonez R,Ceccarelli N.Dynamic programming applied to UAV way point path planning in wind[C]//IEEE Multi-conference on Systems and Control.San Antonio,Texas:IEEE,2008:215-220.

[4] 戴青.基于遗传和蚁群算法的机器人路径规划研究[D].武汉:武汉理工大学,2009.

[5] 付宜利,顾晓宇,王树国.基于模糊控制的自主机器人路径规划策略研究[J].机器人,2004,26(6):548-552.

[6] 樊长虹,陈卫东,席裕庚.未知环境下移动机器人安全路径规划的一种神经网络方法[J].自动化学报,2004,30(6):816-823.

[7] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.

[8] 王强,张安,吴忠杰.改进人工势场法与模拟退火算法的无人机航路规划[J].火力与指挥控制,2014,39(8):70-73.

[9] WU Xianxiang, MING Yan, WANG Juan. An improved path planning approach based on particle swarm optimization[C]//International Conference on Hybrid Intelligent Systems (HIS).Meacca:IEEE,2011:157-161.

[10] 曹文锋.基于改进蚁群算法的飞行器航迹规划研究[D].重庆:重庆大学,2011.

[11] 卢江松.基于改进蚁群算法的多机协同突防航迹规划方法研究[D].长沙:国防科学技术大学,2011.

(编辑：方春玲)

UAV path planning based on improved ant colony algorithm

LI Xi-gang, CAI Yuan-li

(School of Electronic and Information Engineering, Xi’an Jiaotong University,Xi’an 710049, China)

Traditional intelligent optimization algorithms have lots of disadvantages in UAV path planning, and they rarely take mission constraints into consideration. In order to obtain an optimal path that meets the mission constraints with higher efficiency, an improved ant colony optimal (ACO) algorithm is proposed in this paper. First of all, searching space was modeled as a grid map and each grid was labeled by sequential number. Secondly, a bidirectional searching method was used in the path searching, pheromone updating rules and the method to select next node were also improved. Finally, a new method was presented to combine and smooth the paths generated by those two group ants. Simulation results show that the improved ACO algorithm is capable to generate a feasible path that meets the mission constraints, and the improved ACO algorithm can help the solutions escape from their local optimization and find better path at higher convergence speed.

ant colony optimization algorithm; UAV path planning; bidirectional searching

2016-03-30;

2016-10-21;

时间:2016-11-01 16:48

国家自然科学基金资助(61308120)

李喜刚(1988-)，男，甘肃静宁人，硕士研究生，研究方向为无人机建模及路径规划。

V279

A

1002-0853(2017)01-0052-05