基于自适应多态融合蚁群算法的无人机航迹规划

甄然 张春悦 矫阳 吴学礼

摘 要：为解决传统航迹规划最短路径算法易陷入局部最优及复杂地形情况下的无人机航迹规划问题，提出了一种基于自适应多态融合蚁群算法的航迹规划方法。通过对航迹规划问题进行描述， 建立数学模型， 将自适应和蚁群算法相结合，与多态蚁群形成了全局、局部并行搜索模式，以提高算法寻找全局最优值的能力;提出自适应并行策略和自适应信息更新策略，以提升其全局搜寻能力。仿真结果表明，自适应多态融合蚁群算法较传统蚁群算法和多态蚁群算法具备更好的性能，能有效地提高搜索路径的长度和收敛速度，从而避免在求解过程中陷入局部最优，因此在求解最优航迹规划问题上有很好的应用前景。

关键词：计算机仿真;无人机;航迹规划;多态蚁群;自适应并行策略

中图分类号：TP273;V279+.2   文献标志码：A   doi：10.7535/hbkd.2019yx06010

Abstract：Aiming at the problem of traditional UAV trajectory planning which falls into local optimum easily， and the problem of UAV trajectory planning in complex terrain， a trajectory planning method based on adaptive polymorphic fusion ant colony algorithm is proposed. This study describes the problem of route planning， establishes a mathematical model， and combines the adaptive ant colony algorithm with the polymorphic ant colony algorithm to form a global and local parallel search mode， which improves the ability of the algorithm to find the global optimal value. An adaptive parallel strategy and an adaptive information update strategy are proposed to improve the global search ability. Simulation results show that this method has better performance than the other two traditional ant colony algorithm and polymorphic ant colony algorithms. It can effectively improve the length and convergence speed of the search path and avoid falling into local optimum in the solution process. Therefore， the adaptive polymorphic fusion ant colony algorithm has a good application prospect in solving the optimal track planning problem.

Keywords：computer simulation; UAV; track planning; polymorphic ant colony; adaptive parallel strategy

隨着现代科学技术的不断进步，无人机技术飞速发展。无人机的航迹规划在军事、民用等领域具有十分重要的研究意义和价值。随着作战环境与作战任务的日益复杂，无人机自主作战、集群协同作战等将逐步成为现代战争重要的作战样式[1]，路径规划算法的性能直接影响规划路径的质量，甚至影响后续作战任务的顺利进行。航迹规划的实质是为执行任务的飞行器规划出一条最安全的飞行航迹[2]。

传统的航迹规划最短路径算法主要包括Dijkstra算法[3]、Floyd算法和A*算法[4]。常用的随机搜索算法包括遗传算法、粒子群算法[5]、蚁群算法等智能优化算法。本文根据文献把路径规划算法分为网格图法、路线图法和人工势场法[6-8]。基于各类智能算法，研究人员在路径规划方面已经做了大量工作[9-12]。其中，文献＼[9＼]动态地提出了一种多信息素更新的蚁群算法。文献＼[10＼]提出了基于混合动力车辆路径问题的局部搜索问题与传统蚁群相结合的蚁群算法。文献＼[11＼]针对路径对准问题，提出了一种自适应蚁群优化算法。蚁群算法是一种用来寻找最优路径的智能优化算法，具有强大的鲁棒性和搜索更好解决方案的能力，但易陷入局部最优，搜索时间长，文献＼[12＼]提出了自适应并行蚁群算法来解决这一问题。

1 蚁群算法基本原理

20世纪90年代初，意大利学者DORIGO等通过模拟蚂蚁对自然界食物的集体搜索，提出了蚁群算法（ACA）。蚂蚁觅食是一种基于群体的启发式仿生算法，不是单一的蚂蚁自主寻找食物来源。蚂蚁在觅食时会利用特殊的感官能力，这些能力使它们始终能够找到巢穴和食物来源之间的最短路径。觅食行为取决于蚂蚁和蚂蚁之间或蚂蚁个体与环境之间的交流，这是基于蚂蚁产生的化学物质（称为信息素）的使用。蚂蚁在走路时将信息素存放在地面上，并倾向于沿着信息素含量高的路径行进，孤立的蚂蚁随意移动。然而，当它遇到信息素的踪迹时，遵循这条踪迹的概率会增加。蚂蚁的工作原理如下：首先，当蚂蚁到达它们必须决定向左或向右转的决定点时，蚂蚁会随机选择下一条路径并将信息素存放在地面上，因为它们不知道哪个是最佳选择。在短暂停顿选择之后，两条路径上信息量的差异足以影响新的蚂蚁进入系统的决定，从此刻开始，新的蚂蚁将更有可能选择信息量较多的路径。因此，蚂蚁可以闻到信息素的味道，并且很可能选择强信息素浓度为标志的路径。蚁群算法具有正反馈、分布式计算和用于贪婪搜索的特点，因而具有较强的鲁棒性和搜索性，目前已应用于多个领域，例如：旅行商问题（traveling salesman problem）[13]、工作流转分配问题、工作车间模式调度问题[3]等。传统蚁群算法和大部分改进算法都是基于单种蚁群、单种信息素的算法，主要模拟了实际蚁群系统的一部分。在自然界当中，真实蚂蚁社会中的蚁群是有计划、有组织的，类似于人类，不同种类的蚂蚁群体具有不同的信息素控制机制，不同的控制机制对不同群体完成繁杂任务具有非常重要的作用。除此以外，蚁群算法还存在搜索时间长、收敛速度慢、容易陷入局部最优等缺点[14]。

2 自适应多态融合蚁群算法路径规划

2.1 多态蚁群算法

根据传统蚁群算法进行具体分化的多态蚁群算法，这里面的“多态性”是指蚁群社会中各种形态的蚁群和信息素。蚂蚁根据任务及分工的不同，分为侦察蚁、搜索蚁和工蚁，各种蚂蚁各司其职[15]。其中，工蚁蚁群与路径寻优无关，所以就只需针对侦察蚁群和搜索蚁群，设计各自的信息素调节机制[15]，侦察蚁群负责局部侦察，搜索蚁群负责全局搜索。这种利用蚂蚁种群的分工机制大大提高了蚂蚁群体之间的合作效果，增强了算法的有效性[15]。

为了解决死锁问题，科学家采用早期死亡这种方法，该方法的主要思想是使陷入死锁中的蚂蚁死亡，从而停止更新已经走过的路径上的信息素。当大量蚂蚁处于死锁状态时，该方法不仅不利于全局寻优，而且降低了路径解的多样性。文献＼[18＼]用回退法解决这个问题，当蚂蚁陷入死锁时，不要让它死去，而是允许它后退一步，继续搜索。

本文研究的方向确定法是一种解决死锁问题的工具，当蚂蚁处于死锁状态时，对禁忌表进行更新[19]，对死锁边缘的信息素进行惩罚，使得蚂蚁可以在原有位置上调整前进方向，找到无障碍方向[20]，然后继续前进，这个方向如图2中的箭头所示。

该方法在解决死锁问题中的应用目的是提高算法的全局搜索能力，有效地減少其他蚂蚁在同一个位置陷入死锁的可能性，它的信息素惩罚公式为τrs=（1-λ）τrs，（9）式中1-λ是相应的惩罚系数。

自适应多态融合蚁群算法无人机路径规划的具体步骤方法如下。

步骤1：采用网格法对初始环境进行建模，设置常量q，c，n。

步骤2：将m侦察蚁分别放置在n路径节点上，每个侦察蚁调查以其路径节点为中心的其他（n-1）路径节点，根据式（1）计算侦察要素，并将结果放置到sij中。

步骤3：根据式（2）设定初始时刻各路径上的初始信息量。

步骤4：随机选择每个搜索蚂蚁的初始位置，并将其放入相应的禁忌表中。

步骤5：根据式（6）计算每只搜索蚂蚁k下一步转移的位置，将其设置为j;将前一位置设置为i，并将j放入搜索蚂蚁k的相应禁忌表中，直到每个搜索蚂蚁完成一个周期以获得解;如果蚂蚁k在路径搜索中陷入死锁，那么采用方向确定法解决死锁问题。

步骤6：计算每个搜索蚂蚁的路径长度Lk（k=1，2，…，m），并记录当前最优解。

步骤7：如果已经达到指定的迭代次数，或者所求的解在最近迭代中没有明显改善，则跳转到步骤9;否则，根据式（8）修改每条路径的信息素浓度。

步骤8：将i，j设置为0，清除禁忌表，将NC+1更新为NC，并返回步骤4。

步骤9：输出最优解。

3 实验结果和分析

为了验证基于自适应多态融合蚁群算法的有效性，利用栅格法进行仿真。在设置的栅格环境下，对传统蚁群算法、多态蚁群算法和自适应多态融合蚁群算法进行仿真验证。无人机可移动方向如图3所示。

实验参数设置如下。

蚂蚁数m=150，迭代次数n=210，信息素重要程度因子α=1，启发函数重要程度因子β=5，信息素蒸发系数ρ=0.9，常数Q=100，初始时间c=3时每条路径上的信息量，初始建模设置为22×22的栅格地形图。

在图4—图6中获得3个路径中的最优路径长度，从图中可以发现，自适应多态融合蚁群算法的路径长度要优于传统蚁群算法和多态蚁群算法。

根据表1的3种算法的数据对比可知，传统蚁群算法和多态蚁群算法的最优路径长度比改进的自适应多态融合蚁群算法路径长得多。在进行的20次运算中，前两种算法分别小于或等于35 m的次数为7次和9次，第3种算法分别小于或等于35 m的次数有20次，结果都小于35 m，最优路径长度为33.56 m。图7—图9为3种算法的迭代曲线。改进后的算法在全局航迹计划中实现了快速收敛，所找寻到的航迹长度较短，航迹较为平滑。实验结果表明，在最优航迹、收敛性和迭代效果方面，本文采用自适应多态融合蚁群算法得到的路径规划效果要好于另外两种算法。

4 结 语

为了在无人机有障碍的情况下寻找出最优航迹，提出了一种自适应多态融合蚁群算法。在多态蚁群算法的基础上，引入了自适应并行规则和伪随机规则，避免了搜索过程中容易陷入局部最优问题。搜索蚂蚁在搜索阶段根据伪随机规则进行状态转移，同时采用自适应并行策略确定状态转移函数中的最优组合参数。用方向确定法来解决蚂蚁在搜索过程中陷入死锁问题，提高了算法的全局搜索能力，有效地减少其他蚂蚁在同一个位置陷入死锁的可能性。对于不同分工的蚁群，分别进行局部搜索和全局搜索，增强了算法的全局搜索能力，能有效避免陷入局部最优，而且明显提升了最优路径的长度。本文只考虑了静态障碍物的航迹规划，在未来的研究中应考虑动态障碍物的航迹规划，并在此算法的基础上改进动态障碍物航迹规划。

参考文献/References：

[1] 黄克明，王涛，胡军.无人机作战仿真平台设计及其关键技术研究[J].兵工自动化，2016，35（1）：90-95.

HUANG Keming， WANG Tao， HU Jun. Study on design of UAV combat simulation platform and its key techniques[J].Ordnance Industry Automation，2016，35（1）：90-95.

[2] 王俊，周树道，朱国涛，等.无人机航迹规划常用算法[J].火力与指挥控制，2012，37（8）：5-8.

WANG Jun， ZHOU Shudao， ZHU Guotao，et al. Research of common route planning algorithms for unmanned air vehicle[J].Fire Control & Command Control，2012，37（8）：5-8.

[3] GAN Rongwei，GUO Qingshun，CHANG Huiyou，et al.Improved ant colony optimization algorithm for the traveling salesman problems[J].Journal of Systems Engineering and Electronics，2010，21（2）： 329-333.

[4] 劉学芳，曾国辉，黄勃，等.基于改进蚁群算法的移动机器人路径规划研究[J].电子科技，2019，32（9）：5-9.

LIU Xuefang，ZENG Guohui，HUANG Bo，et al. Research on path planning of mobile robot based on improved ant colony algorithm[J].Electronic Science and Technology， 2019，32（9）：5-9.

[5] 陈冬，周德云，冯琦.基于粒子群优化算法的无人机航迹规划[J].弹箭与制导学报，2007，27（4）：340-342.

CHEN Dong， ZHOU Deyun， FENG Qi. Route planning for unmanned aerial vehicles based on particle swarm optimization[J].Journal of Projectiles Rockets，Missiles and Guidance，2007，27（4）：340-342.

[6] 王志中.基于改进蚁群算法的移动机器人路径规划研究[J].机械设计与制造，2018（1）：242-244.

WANG Zhizhong. Path planning for molile robot based on improved ant colony algorithm[J].Machinery Design & Manufacture，2018（1）：242-244.

[7] 赵文婷，彭俊毅.基于 VORONOI图的无人机航迹规划[J].系统仿真学报，2006，18（sup2）：159-162.

ZHAO Wenting，PENG Junyi.VORONOI diagram-based path planning for UAVs[J].Journal of System Simulation，2006，18（sup2）：159-162.

[8] 韩攀，陈谋，陈哨东，等.基于改进蚁群算法的无人机航迹规划[J].吉林大学学报（信息科学版），2013，31（1）：66-72.

HAN Pan，CHEN Mou，CHEN Shaodong，et al.Path planning for UAVs based on improved ant colony algorithm[J].Journal of Jilin University （Information Science Edition），2013，31（1）：66-72.

[9] 夏亚梅，程渤，陈俊亮，等.基于改进蚁群算法的服务组合优化[J].计算机学报，2012，35（2）：270-281.

XIA Yamei，CHENG Bo，CHEN Junliang，et al.Optimizing services composition based on improved ant colony algorithm[J].Chinese Journal of Computers，2012，35（2）：270-281.

[10] CHENG C T， FALLAHI K， LEUNG H，et al. An AUVs path planner using genetic algorithms with a deterministic crossover operator[C]//2010 IEEE International Conference on Robotics and Automation.Anchorage：IEEE，2010：5509335.

[11]  Al-TAHARWA I， SHETA A，Al-WESHAH M. A mobile robot path planning using genetic algorithm in static environment[J].Journal of Computer Science，2008，4（4）：341-344.

[12] 王楠，张军，解鹏.基于改进AG算法的机器人动态路径规划方法[J].河北工业科技，2018，35（3）：178-184.

WANG Nan， ZHANG Jun， XIE Peng. Robot dynamic path planning method based on improved AG algorithm[J]. Hebei Journal of Industrial Science and Technology，2018，35（3）：178-184.

[13] KOREN Y， BORENSTEIN J. Potential field methods and their inherent limitations for mobile robot navigation[C]//1991 IEEE International Conference on Robotics and Automation.Sacramento：IEEE，1991：131810.

[14] 楊雅宁，蔺勇.基于蚁群算法的一种无人机二维航迹规划方法研究[J].电脑知识与技术，2016，12（28）：188-191.

[15] MAVROVOUNIOTIS M， MLLER F M，YANG Shengxiang. Ant colony optimization with local search for dynamic traveling salesman problems[J].IEEE Transactions on Cybernetics，2017，47（7）：1743-1756.

[16] ZHAI Yahong，XU Longyan，YANG Yanxia. Ant colony algorithm research based on pheromone update strategy[C]//Proceedings of the 2015 7th International Conference on Intelligent Human-Machine Systems and Cybernetics. Washington DC： IEEE，2015：38-41.

[17] 何燕.基于动态加权A*算法的无人机航迹规划[J].河北科技大学学报，2018，39（4）：349-355.

HE Yan.UAV route planning based on improved dynamic weighted A* algorithm[J].Journal of Hebei University of Science and Tech-nology， 2018，39（4）：349-355.

[18] WEN Naifeng，ZHAO Lingling，SU Xiaohong，et al.UAV online path planning algorithm in a low altitude dangerous environment[J].IEEE/CAA Journal of Automatica Sinica，2015， 2（2）：173-185.

[19] PHUNG M D，QUACH C H，DINH T H，et al.Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection[J].Automation in Construction，2017，81（6）：25-33.

[20] QI Huang， ZHENG Guilin. Route optimization for autonomous container truck based on rolling window[J].International Journal of Advanced Robotic System，2016，13（3）：112-121.