固定翼巡线无人机实时蚁群算法路径规划

郑武略+尚涛+金钊

摘 要：本文针对传统蚁群算法局部早熟等问题对算法进行了改进，并对无人机路径规划及重规划多条件约束问题进行了研究，提高蚁群算法航迹规划计算速度及全局性来满足实时蚁群算法航迹规划要求。文章针对传统蚁群算法的早熟问题采用全局與局部信息素互补衰减法，来高效完成蚁群算法寻优问题，并当无人机偏离航线时能及时根据无人机所在位置重新规划。通过实验结果得出蚁群算法具有快速的计算能力，能在短时间内对更改的路径进行响应，完成无人机自校正航迹规划。

关键词：无人机；实时路径规划；蚁群算法

中图分类号：TP242 文献标识码：A

Abstract：Because of premature in traditional ACO（Ant Colony Optimal）， this article comes up with a improved algorithm and use this algorithm to realize the multifactor control in UAV online path planning to improve the speed and global search. By combing local evaporation with global pheromone update， the ACO has a higher speed in finding optimal planning path. Whats more， its suit for the self adjust UAV path planning. Through the improving ACO， a more precise and efficiency path can be found.

Keywords： unmanned aerial vehicle（UAV）； path planning online； ant colony optimal（ACO）

1 引言

近年来，作为新兴航空机器人的无人机，由于体积小、质量轻及高机动性等因素让其在各行各业都得到了广泛的应用于认可[1]。其在电力巡线、区域勘测、无损检测等作业中优秀的性能及灵活的操纵性使其收到电力行业广泛认可，并且由于无人机可搭载多样传感器，使无人机的功能拓展与应用得到广泛的拓展与关注。而在固定翼无人机自主巡线作业中，由于电力巡检部分输电走廊处于地势危险地区，这给无人机自主巡线造成很大的困难，同时对无人机航迹规划精确性有了更高的要求，使无人机自校正重新路径重规划算法成为无人机航迹规划的研究者争相探讨研究的技术难点。

目前航迹规划方向已经涌现出大量的研究性成果，其中‘The Visibility Graph 法针对卫星地图序列，通过鸟瞰视角针对无人机作业区域利用直线段标定规划路径[2]。四叉树路径规划法通过将无人机巡航环境分解成四叉树结构，通过四叉树结构分叉来遍历整个巡航环境来生成无人机航行最优航迹[3]。Jitin Kumar Goyal等人针对A*算法计算搜索细胞尺寸进行改进，并利用启发因子来提高搜索最优航迹的效率，对无人机与搜索环境之间的比例进行考虑来提高航迹规划算法的安全性[4]。

蚁群算法最早由Dorigo 等[5]作为一种多条件约束优化的计算方法展开研究，因为其可以全局的并行计算并且具有良好的动态性及鲁棒性，因此在复杂的组合优化问题十分适用。由于在收敛后期基本蚁群算法早熟局的缺点，有大量研究人员将蚁群算法与其他算法相结合来提高蚁群算法搜索能力，但同时大大增加了算法的复杂性与计算速度[6-8]。本文以信息素更新等方面作为改进点，来提高蚁群算法全局搜索能力，与计算速度，进而实现无人机自校正航迹规划。

2 改进蚁群算法

2.1 蚁群优化算法

蚁群算法基于是蚂蚁从出发点沿地形寻找食物，找到食物后原路折返，并在走过的路径上留下信息素。因此，所走路径越短的蚂蚁，其所走路径上包含有较高的信息素含量，而后寻找食物的蚂蚁会有较大的可能选择这条路线，由此组成一个逐渐逼近最优解的正反馈寻优过程。

1） 蚁群算法转移策略

蚁群算法迭代初始，置 （h为常数）并设定蚁群规模为m （1，2，…，M）。其中，第t次迭代i点到j点间所含的信息浓度用 来表示。在蚁群寻优过程中，蚂蚁通过可行路径上的信息素作为下一方向搜索依据，并将转移概率与轮盘赌注法相结合来对下一节点进行搜索。 为第k只蚂蚁在第t次的迭代时从点i转移到j的概率，其计算公式如（1）所示：

其中， 为蚁群算法中蚂蚁的可到达点， 为禁止清单，记录蚂蚁k代所走过的节点及蚂蚁禁止通行的节点，并针对当前路径及时动态调整。 表示尚未搜索节点，此外式（1）中的 代表信息素浓度因子， 代表启发因子， 表示引导因子端的重要性权重，且 与 的取值大小酸谷算法收敛速度。

2）启发因子设计

通过对启发因子进行设计，可以影响蚁群算法转移概率，进而引导蚂蚁搜索方向，对蚂蚁寻优进行引导。其计算公式如式（2）所示。

其中， 为点i与点j之间的距离。且当下一搜索节点距当前位置越近，导引因子则越大。此外，无人机巡线飞行过程由于姿态控制会对无人机自身机能造成一定的损耗，因此无人机在巡线过程中具有能量消耗上限即 ，因此每一航程段距离 应满足：

2.2 基于蚁群算法的航迹规划

本文基于固定翼无人机作业路径情况考虑，一般而言无人机巡线作业飞行轨迹都是从起点出发遍历各个作业目标点完成任务后折返的过程。本文通过考虑在无时间条件约束时给定无人机飞行起点和所需遍历的各个目标点，并设定无人机巡线环境限制来将路径规划问题视为 TSP（Traveling Salesman Problem） 问题求解[12，13]。其伪代码如下所示：

Step1 设定蚁群规模，并将蚁群随机分配到各个目标点中，并将目标点置于禁忌表中。

Step2 对蚁群算法迭代次数进行设定，当达到最大迭代次数时结束循环，否则循环执行步骤3、4，并在迭代结束后进行全局信息素更新。

Step3 对蚂蚁 k（1≤k≤M），进行如下指示：

if （查找可达目标点i）

若找到，则记录i为下一目标点；

else

记录本次循环路径。

Step4 更新路径上的信息素。

Step5 输出结果。

Step6 程序结束。

2.3 无人机自校正航迹规划

在无人机航迹规划历程中，系统会根据用户给定的目标点自动生成最优航迹，可以控制无人机根据蚁群算法所给出的目标点来遍历其他作业点。但是当需要临时更改重新生成路径时，需要用户手动更改新目标点，然后利用蚁群算法对无人机航迹路线进行校正。

无人机路径规划系统主要包括两类规划策略，一种是基于蚁群算法的静态无人机路径规划，另一种是根据无人机真实环境而重新设定无人机航迹的动态无人机航迹规划。如果无人机由于环境威胁及作业目标变更时，固定翼无人机会偏移原航迹。因此，系统需要以当前无人机坐标位置为起点，对原航迹规划路线进行校正，然后令无人机按新生成的路径来对作业点进行遍历。 自动控制系统是无人机自主飞行系统中的关键环节，因此无人机需要跟随蚁群算法所生成的航迹来执行飞行命令。当无人机规划航迹变更后，无人机飞行控制将会收到来自地面站的目标点变更指令及导入校正后的规划路径，并通过PWM信号对无人机姿态进行控制[14，15]。

3 仿真实例

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

设定无人机起点为（0，10，4），并设定目标点为（20，8，5）， 设 =1.5， =2， =0.1， =0.01， =0.1，M=30，K=100，其中M为蚁群规模，K为迭循环次数。仿真得到的路径曲线分别如图1所示。

由于将起始点、终止点及地图信息输入到蚁群算法搜索中，算法时长301毫秒，并且从算法生成路径中可以看出算法在避开障碍物的同时可以沿着地形走势飞行，切实提高无人机巡线效率。

3.2 无人机蚁群算法的路径重规划

设定无人机巡线作业目标点分别为{10，50，20}，{25，44，25}，{34，38，36}，{48，47，31}，{62，37，41}，{75，48，34}，{64，60，39}，{45，68，37}，{34，59，30}，{22，52，28}，其蚁群算法参数与上文航迹规划所设参数保持一直，得到无人机遍历目标点的路径如图4红线所示航迹，其算法运行时间为353毫秒，最短路径长为170.209。当无人机航迹遍历目标更改时，生成路径如图2蓝线航迹所示，最短路径长度为162.641，航迹校正用时261ms。

4 结论

本文主要针对巡线无人机基于蚁群算法无人机实时航迹规划方法进行研究。根据实验结果可以看出，改进蚁群算法高效的迭代能力和快速的计算速度可以在目标点更改后快速做出相应，并计算出改变后的无人机航迹目标点后无人机新的航迹路线，满足无人机实时航迹规划准确性和实时性的要求，让无人机实时做出反应。

参考文献

[1]. 王连波. 浅谈无人机的发展现状及发展趋势研究[J]. 科技与企业. 2013（14）：349

[2]. Christos Alexopoulos and Paul M. Griffin. Path Planning for a Mobile Robot. IEEE transactions on Systems[J]. Man and Cybernetics. 1992， 22（2）： 318 – 322

[3]. Kambhampati S. and Davis L.Multiresolution path planning for mobile robots[J]. IEEE Journal of Robotics and Automation. 1986， 2（3） ： 135-145

[4]. Jitin Kumar Goya， K.S. Nagla. A New Approach of Path Planning for Mobile Robots[J]. IEEE. 2014：863-867

[5]. Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agent [J]. IEEE Transactions on Systems ，Man ， and Cybernetics ， 1996， 26（1）： 29- 41

[6]. 左洪浩.蟻群优化算法及其应用研究 [D].合肥： 中国科学技术大学合肥智能机械研究所，2006.

ZUO Hong Hao. Research on the Ant Colony Optimization Algorithm and Its Applications[D]. Hefei： Institute of Intelligent Machines，University of Science and Technology of China，2006

[7]. Yang Yu .Research on Path Planning for Mobile Robot Based on Ant Colony Algorithm in Dynamic Environment[J].IEEE，2008：497-499

[8]. TANG L.，FANG T .J .，”Path Planning Method based on Improved Ant Colony Algorithm”， Journal of university of science and technology of china. China，Vol.39（9）， pp. 77-79， 2009.

[9]. Gu Ping， Xiu Chunbo， Cheng Yi， Luo Jing， Li Yanqing. Adaptive Ant Colony Optimization Algorithm[J]. IEEE. 2014：95-98.

[10]. 王緒芝.基于蚁群算法的无人机航迹规划及其动态仿真[D].南京航空航天大学自动化学院，2012

WANG Xu-zhi. Path Planning for UAV Based on Ant Colony Algorithm and Dynamic Simulation[D].Nanjing University of Aeroautics and Astronautics，2012

[11]. Ruey-Maw Chen. Heuristics Based Ant Colony Optimization for Vehicle Routing Problem[J] .IEEE Conference on Industrial Electronics and Applications，2011：1039-1043

[12]. Wen zhi-qiang， Cai zi-xing. Global path planning approach based on ant colony optimization algorithm. J. cent. South univ. technol， 2006， 13（6）：707-712

[13]. Wu Bin， Shi Zhong-zhi， An Ant Colony Algorithm Based Partition Algorithm for TSP， Chinese J. Computers， Vol. 24， No. 12， 1328-1333，2001

[14]. Path Planning and Obstacle Avoidance for Vision Guided quadrotor UAV Navigation[J].12th IEEE International Conference on control & Automation（ICCA），2016：984-989

[15]. S. S. Ge and Y. J. Cui， ”Dynamic motion planning for mobile robots using potential field method”， Autonomous Robots， Vol. 13， pp. 207-222， 2002