蚁群优化算法的无人机室内航迹规划
2022-05-06马肇祥朱庆伟张俊屈乾龙
马肇祥 朱庆伟 张俊 屈乾龙
摘要：由于室内无人机导航较为复杂，针对现有的传统（基本）蚁群算法存在早期盲目搜索、易陷入局部最优和收敛速度慢等问题，探索一种高效、准确的航迹规划方法意義重大。为提高收敛速度使其避免陷入局部最优等算法缺陷，提出一种改进蚁群算法的室内无人机三维航迹规划方法，该方法设计初始信息素的调节因子，增强蚁群搜索的方向性;设计启发概率函数，改进状态转移规则，有效提高蚁群可见性精度;改进算法的信息素更新方式，增加信息素挥发率的动态调整策略，提高算法的收敛速度，扩大搜索空间，有效避免其陷入局部最优。通过仿真实验进行算法适应性验证，结果表明：改进蚁群算法有效提高全局搜索能力，减少收敛迭代次数，得到的最优路径长度比传统蚁群算法平均缩短38.6%，平均用时减少3.8%，显著提高蚁群优化算法的适应性，体现出在特定应用场景下的优越性。
关键词：无人机;蚁群算法;室内环境;三维航迹规划;较优路径
中图分类号：TP 24文献标志码：A
文章编号：1672-9315（2022）02-0307-10
DOI：10.13800/j.cnki.xakjdxxb.2022.0215开放科学（资源服务）标识码（OSID）：
Ant colony optimization algorithm for UAV
indoor trajectory planningMA Zhaoxiang，ZHU Qingwei，ZHANG Jun，QU Qianlong
（College of Geomatics，Xian University of Science and Technology，Xian 710054，China）
Abstract：Due to the complicated indoor drone navigation，there is an early blind search for the existing traditional（basic）ant colony algorithm，which is easy to fall into a problem such as local optimization and slow convergence speed.Explore an efficient and accurate track planning method significance. In order to improve the convergence speed，it is proposed to improve the three-dimensional airline planning method for improving the ant colony algorithm.The method designs the adjustment factor of the initial pheromone，enhances the directionality of the ant colony search.The design inspiration probability function，improve the state transfer rules，effectively improve the visibility of ant colony.The updated methods of the algorithm pheromones are improved，with their dynamic adjustment strategies promoted，thus increasing the convergence speed of the algorithm，expanding search space，and effectively avoiding its topical optimal.The algorithm adaptation verification is performed by simulation experiments， and the results show that the improved ant colony algorithm effectively improves global search capabilities，reducing the number of convergence iterations，the optimal path length is less than 38.6% more than the traditional ant colony algorithm， nd the average time reduces by 3.8%.Significantly improve the adaptability of the ant colony optimization algorithm，indicating the superiority of a particular application scenario.
Key words：unmanned aerial vehicle（UAV）;ant colony algorithm;indoor environment;three-dimensional trajectory planning;better path
0引言
无人机因其操作简便、机动性能好等特点，已经被广泛应用于各个领域。将无人机用于执行室内灾害救援任务时，可以减少救援人员的安全风险，提高救援工作效率。航迹规划是无人机完成自主飞行的关键技术之一，在室内救援时，寻找一条安全、可靠的飞行航迹是保证救援任务能否完成的关键。无人机室内飞行面临的挑战是室内空间狭小、障碍物较多，高度有限，使无人机飞行受到一定条件的限制。在室内，由于环境信息是未知的，航迹规划要满足避障要求，规划一条合理路径。
目前，各国学者已提出许多种无人机航迹规划算法。常用到的算法有：可视图法、D*算法[1]、A*算法[2]、人工势场法[3]、神经网络算法[4]、快速搜索随机树（RRT）算法[5]、遗传算法[6]、粒子群算法[7]、蚁群算法[8-10]、模拟退火算法[11]、强化学习算法[12]等。其中，蚁群算法在求解较优航迹方面较其他算法具有显著优势。对蚁群算法进行改进应用于航迹规划的研究，国内外学者作了大量的研究工作。陈侠等提出的算法为使蚁群算法能更好适用于无人机三维航迹规划，对算法存在的收敛速度慢、易陷入局部最优的问题，进行了相应改进，将三维航迹规划分解成二维平面规划和高度规划2部分，运用几何优化法增强蚁群的引导方向性，根据无人机航迹点与障碍物之间的距离，对飞行高度进调整，利用自适应变化阈值参数法提高了蚁群在全局中的搜索能力，从而达到求解多样性的效果[13]。针对蚁群算法所含有的空间复杂性高、收敛速度慢的缺陷，魏江等提出的算法改进部分对局部搜索策略和初始信息素调节因子进行优化，在启发函数中加入路径偏移因子，有效降低空间搜索复杂性，提高了路径规划效率[14]。徐玉琼等针对传统蚁群算法在路径规划中对鲁棒性缺乏的问题，提出改进自适应蚁群算法，在概率转移规则中引入加权因子，以提高算法收敛速度，并按解的分布状况适应性地对信息素进行更新，同时在步长选择策略中选择最优步长，增强算法全局搜寻能力，从而提高机器人路径规划效率[15]。李宪强等将人工势场法与蚁群算法融合组成新的融合算法。由于蚁群算法易陷入局部最优，引入人工势场法对初始信息素进行分配。并且引入势场引导函数对蚁群算法的状态转移函数进行相应改进，从而避免算法因忽视周围障碍物信息而陷入长时间进行路径选择的问题[16]。这些研究都将蚁群算法用到具体的环境[17-22]，取得良好的效果，然而，对于文中研究的室内无人机航迹规划，并不适用。因为这些算法应用于室外环境，且算法规划速度较慢，搜索时间较长，难以滿足室内灾害救援及其他室内飞行任务的要求。
由于室内环境分布着大量障碍物，且障碍物分布不均以及其高度、形状、大小都各不相同[23-25]。而无人机在室内进行搜救或者自主导航时，室内环境信息并不能保证都了解。笔者结合室内环境特点及蚁群算法存在的缺陷，对空间做离散化处理，降低其空间复杂度。针对搜索初期，因信息素的缺乏，会导致搜索的盲目性，采用信息素调节因子，同时根据算法存在收敛速度慢和易陷入局部最优的缺点，设计启发概率，并改进信息素更新规则和采用动态信息素挥发策略。最后，通过实验测试对改进后的算法性能进行验证和分析。
1空间离散化
室内环境中随机分布着很多障碍物，且空间环境处于连续状态。当发生灾害时，室内障碍物和突发的各种不确定因素给航迹规划带来巨大挑战。因此，对室内三维空间环境进行离散化处理，则在航迹规划时可以直接获得空间节点集。即在空间节点集中找到组成路径规划的总成本代价最小的节点。
2改进的蚁群算法
在基本蚁群算法中，概率选择并不能总是保证最优解，有时在优化的早期，算法会进行盲目搜索、易陷入局部最优，而且由于启发式搜索的局限性，导致算法收敛速度很慢，为提高基本蚁群算法的性能并克服其缺点，做出以下改进：改进初始信息素调节因子，有效增强蚁群算法的搜索方向性;设计启发概率并改进状态转移概率函数，从而扩展蚁群搜索视野和提高可见性精度;对信息素更新规则进行改进和增加信息素挥发率的动态调整策略，有效提升算法的收敛速度、扩大搜索空间。
2.1初始信息素的改进
由于基本蚁群算法的初始信息素均匀分布于空间中，因此在算法搜索初期，蚂蚁选择任意节点位置的概率都相同，从而出现蚁群盲目搜索的现象，同时也耗费大量的时间。
为避免蚂蚁在算法搜索初期的盲目性，在起始点和目标点连线的区域中，通过起始点到当前节点的距离和待选节点到目标点距离的变化量来影响初始信息素。基本蚁群算法的初始信息素是一个固定常数值，改进蚁群算法通过确定起始点、当前节点、待选节点以及且标点之间的距离，使蚁群尽可能沿着起始点和目标点连线的附近进行路径搜索，从而缩小路径搜索范围，因此对初始信息素调节因子进行了如下设计。
式中D为室内空间中起始点与目标点连线的欧式距离;τ′0为固定的信息素常数;dsi为蚁群所走路径的起始点与当前节点的距离（因为蚁群算法搜索具有随机性，这里的dsi为蚁群所搜索的路径，这一距离大于起始点到当前节点的直线距离），dij为蚁群所走路径的当前节点与下一待选节点的距离，dje为待选节点与目标点的距离。由公式（4）可知，dsi+dij+dje的值越大，则路径（i，j）间的初始信息素越大;反之，初始信息素的值越小。
通过对上述信息素调节因子的设计使改进算法达到增强蚁群搜索方向性的效果。
2.2启发概率
ST是组合运算，启发概率设计了让蚂蚁更容易选择最好的下一个空间网格（将室内空间按单位长度等分为大小相等的多个空间网格），所选网格必须是一个可行的网格，有多个可行通道抵达目标。这个概率取决于网格周围障碍物的数量。因此，空间网格周围的障碍物越少，概率就越大，网格就越有吸引力。需要做以下组合。
在三维空间中，无人机在搜索时，有27个搜索方向，去掉无人机本身的所占据的位置，因此剩于26个方向，即N（26，Mobs），它表示围绕一个确定的网格j，其周围障碍物可能分布的数量，即表征一个可行网格节点周围有多少障碍物，且障碍物数量为[0，26]，如图1所示。
2.3改进信息素更新规则
信息素的数量是选择经过最短路径上的最佳空间网格的必要因素之一，然而，它含有一定强度的劣质信息素，这是由最差的蚂蚁所产生的，它会使其他蚂蚁移动到难以接近目标点的位置上，或者会导致算法过早求解，为了获得良好的寻优性能，在每次迭代中，可使用以下更新规则增加最佳局部路径上的信息素浓度并降低最差局部路径上的信息素浓度。因此，对信息素更新规则公式改进为
2.4设置动态信息素挥发策略
在基本蚁群算法中，信息素挥发率ρ是（0，1）范围内的常数，直接影响着算法全局搜素能力和收敛速度，如果ρ太小，信息素挥发的较慢，会降低全局搜索能力，使算法陷入局部收敛。如果ρ过大，全局搜索能力会得到一定程度的提高，但收敛速度会降低。
为确保能在扩大搜索空间和加快收敛速度两者间取得良好的平衡，对信息素挥发率进行动态调整。其中，在算法开始时，将挥发率设置为较大的值，来改善全局搜索能力，然后挥发率将按如下公式进行改变
3算法改进与实现
3.1改进蚁群算法的步骤
具体改进蚁群算法流程如图2所示。
3.2仿真实验环境构建与有效性分析
3.2.1仿真实验环境的构建
为验证改进的蚁群算法在室内三维航迹规划的有效性，在三维栅格地图中对改进蚁群算法进行实验。实验仿真平台为MATLAB2018a，考虑到一架无人机和室内环境模型特点，且无人机可以向环境中任意方向运动飞行。该实验的规划空间分为10 m×10 m×10 m栅格，20 m×20 m×20 m栅格和30 m×20 m×15 m栅格，实验搭建的三维模型如图3所示，为更真实的接近室内场景，空间中随机设置障碍物。规定没有障碍物的空间栅格可以通过，有障碍物的空间栅格不可通过。
在室内航迹规划中，算法参数设置如下：蚂蚁数量m=100，信息素浓度启发因子α=1，能见度启发因子β=2，挥发系数ρ=0.7，信息素强度Q=10，迭代次数n=50。
3.2.2改进算法的实现及有效性验证
在不同空间规模的条件下，采用改进算法和基本算法在室内环境1（规模为10 m×10 m×10 m）、室内环境2（规模为20 m×20 m×20 m）和室内环境3（规模为20 m×30 m×15 m）中各进行20次重复航迹规划，然后从路径长度，收敛时间等角度来比较2种算法的实验效果，并对得到的结果进行对比和分析。为便于统计計算，对实验的相关结果保留至小数点后3位。3种室内空间规模中基本算法和改进算法所规划的路径以及最佳个体适应度变化情况分别如图4～图6所示。
图4～图6的实验结果表明，改进蚁群算法在3种不同的室内环境中经过计算迭代后，均能搜索到一条较优路径，并且搜索到的较优路径比基本蚁群算法的路径长度更短，如图4（b）、图5（b）、图6（b）中的蓝色路径相较于红色路径更短。这是因为在算法搜索初期，基本蚁群算法因缺乏初始信息素，对空间进行盲目搜索，使得所找寻到的路径较长。而改进算法对初始信息素调节因子进行改进，增强朝目标点方向的信息素浓度，避免算法出现盲目搜索的状况，从而找寻到一条较短路径，有效节约搜索时间。同时，在环境1中，障碍物的高度不一，分布也不均匀，改进算法所规划的路径选择离目标点距离近且周围障碍物少的路径通道，基本蚁群算法按传统的启发式规则随机选择可行通道，有时选择的可行通道节点离目标点较远。产生这2种结果的原因是改进算法中新设计的启发式概率有效扩展蚁群搜索视野并提高了蚁群可见性精度。
如图4（c）、图5（c）、图6（c）为3组实验的侧视图。图4（d）、图5（d）、图6（d）所反映的是最佳个体适应度值变化趋势，可以得出改进算法（蓝色曲线）比基本算法（红色曲线）的收敛迭代速度快，且当适应度值达到稳定后，改进算法所得到的适应度值比基本算法的小，并且改进算法的适应度值在算法前期搜索阶段，快速下降，出现这种结果是由于算法改进了信息素更新规则并采用信息素挥发率动态调整策略，从而加快算法的收敛速度，同时也扩大蚁群搜索范围，有效解决基本蚁群算法易陷入局部最优极值的问题。在环境1中，基本算法经过33次迭代后，其最佳个体的适应度值趋于稳定，且达到最优，而改进算法在迭代15次后，最佳个体的适应度值达到最优，如图4（d）所示。并且基本算法经过后续的多次迭代后，其最佳个体的适应度值仍高于改进算法相对应的值。从图5（d）可以看出，改进算法和基本算法分别经过19次、43次迭代后，适应度值达到最小。图6（d）中，改进算法和基本算法分别经过6次、8次迭代后，适应度值达到最小。图4室内环境1中2种算法仿真对比
对2种蚁群算法在3种不同室内环境中重复实验得到的20条路径长度和算法所用时长进行统计比较，见表1。由表1可知，改进蚁群算法搜索的20条最优路径长度效率分别提高：11.8%，46.9%，57.2%，路径长度平均值效率分别提高17.7%，54.9%，62.7%。改进蚁群算法平均用时相较基本蚁群算法而言，提升较小。具体来说，在室内空间规模较小的环境1中，2种算法都能较快搜索到最优解，搜索到的路径长度平均值和算法用时两方面的效率百分比相差不大。
伴随着室内空间范围扩大，改进算法的各项性能逐渐显现，同时路径长度效率提升趋势与算法用时效率提升趋势呈一升一降2种相反的变化结果。分析可知，这是由于改进算法在寻找较优路径时，随着空间范围的增大，相应地空间搜索计算量也增大，从而导致所用时间增大，算法用时的提升效率也随之降低。
3.2.3算法适应性验证
为验证所提出的改进算法在不同场景下的适应性，在不同障碍物和目标位置点中分别进行3组实验，每次实验运行多次并使结果保留至小数点后3位。图7～图9显示3组实验的路径规划图。其中图7（b）在图7（a）基础上改变目标点位置，图8（b）与图8（a）为相同起始点和目标点条件下的室内不同障碍物环境，图9（a）和图9（b）为完全不同的室内环境和目标点。
从图7可以看出，实验更改无人机所要到达的目标位置，规划的路径仍能够安全避开障碍物并准确到达目标点，由于图7（a）和图7（b）起始点坐标都为（1，1，1），图7（a）目标点坐标是（9，10，7），图7（b）目标点坐标是（10，9，8），所以图7（b）实验得到的路径规划长度、算法计算用时、迭代次数都大于图7（a）的值。图8（a）与图8（b）因障碍物差异较大，且图8（a）中的无人机直接通过第2、第3个障碍物下方的通道到达目标点，但在图8（b）中，由于第2个障碍物是一个类似U型的障碍物，则无人机需要先不断沿y轴方向搜索，再转向x轴方向搜索到达目标点，最终导致改进算法搜索到的最优路径长度、算法用时、收敛迭代次数不同。在第3组实验中，由于室内空间范围由图9（a）的20 m×20 m×12 m扩展为图9（b）的20 m×20 m×14 m，使得图9（b）中采用改进算法所规划的路径长度比图9（a）的路径长度更长。表2为图7～图9这3组实验得到的数据结果。
表2结果说明，改变不同的条件，所提出的改进算法在不同的场景下有着很好的适应性，同时通过实验验证改进算法的路径规划性能指标与无人机起始点和目标点的距离大小、空间复杂度大小、空间范围大小这3种因素有关。
4结论
1）针对传统蚁群算法存在初期盲目搜索、易陷入局部最优、收敛速度慢等问题，提出一种优化蚁群算法，通过改进初始信息素调节因子，进而增强蚁群搜索的方向性。
2）设计一种启发概率函数，扩展蚁群搜索视野并提高可见性，使得最优路径长度比基本蚁群算法缩短38.6%，平均用时减少3.8%。
3）对信息素更新规则进行改进，增添信息素挥发动态调整策略，从而加快算法收敛迭代速度，有效验证改进算法在复杂环境中的良好适应性。
参考文献（References）：
[1]张飞，白伟，乔耀华，等.基于改进D*算法的无人机室内路径规划[J].智能系统学报，2019，14（4）：662-669.ZHANG Fei，BAI Wei，QIAO Yaohua，et al.UAV indoor path planning based on improved D* algorithm[J].CAAI Transactions on Intelligent Systems，2019，14（4）：662-669.
[2]MANDLOI D，ARYA R，VERMA A K.Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3D environment[J].International Journal of System Assurance Engineering and Management，2021，12（5）：990-1000.
[3]谌海云，陈华胄，刘强.基于改进人工势场法的多无人机三维编队路径规划[J].系统仿真学报，2020，32（3）：414-420.CHEN Haiyun，CHEN Huazhou，LIU Qiang.Multi-UAV 3D formation path planning based on improved artificial potential field[J].Journal of System Simulation，2020，32（3）：414-420.
[4]朱大奇，刘雨，孙兵，等.自治水下机器人的自主启发式生物启发神经网络路径规划算法[J].控制理论与应用，2019，36（2）：183-191.ZHU Daqi，LIU Yu，SUN Bing，et al.Autonomous underwater vehicles path planning based on autonomous inspired Glasius bio-inspired neural network algorithm[J].Control Theory & Applications，2019，36（2）：183-191.
[5]GAN Y，ZHANG B，KE C，et al.Research on robot motion planning based on RRT algorithm with nonholonomic constraints[J].Neural Processing Letters，2021，53（4）：3011-3029.
[6]XIN J，ZHONG J，YANG F，et al.An improved genetic algorithm for path-planning of unmanned surface vehicle[J].Sensors，2019，19（11）：1-23.
[7]SHAO S，PENG Y，HE C，et al.Efficient path planning for UAV formation via comprehensively improved particle swarm optimization[J].ISA Transactions，2020，97：415-430.
[8]韓鹏，张冰玉.基于改进蚁群算法的无人机安全航路规划研究[J].中国安全科学学报，2021，31（1）：24-29.HAN Peng，ZHANG Bingyu.Safety route planning of UAV based on improved ant colony algorithm[J].China Safety Science Journal，2021，31（1）：24-29.
[9]陈超，张莉.基于改进蚁群算法的三维路径规划[J].计算机工程与应用，2019，55（20）：192-196.CHEN Chao，ZHANG Li.Three-dimensional path planning based on improved ant colony algorithm[J].Computer Engineering and Applications，2019，55（20）：192-196.
[10]LUO Q，WANG H，ZHENG Y，et al.Research on path planning of mobile robot based on improved ant colony algorithm[J].Neural Computing and Applications，2020，32（6）：1555-1566.
[11]HUO L，ZHU J，WU G，et al.A novel simulated annealing based strategy for balanced UAV task assignment and path planning[J].Sensors，2020，20（17）：4769.
[12]BAE H，KIM G，KIM J，et al.Multi-robot path planning method using reinforcement learning[J].Applied Sciences，2019，9（15）：3057.
[13]陈侠，艾宇迪，梁红利.基于改进蚁群算法的无人机三维航迹规划研究[J].战术导弹技术，2019（2）：59-66，105.CHEN Xia，AI Yudi，LIANG Hongli，et al.Research on three-dimensional path planning of UAV based on improved ant colony algorithm[J].Tactical Missile Technology，2019（2）：59-66，105.
[14]魏江，王建軍，王健，等.基于改进蚁群算法的三维航迹规划[J].计算机工程与应用，2020，56（17）：217-223.WEI Jiang，WANG Jianjun，WANG Jian，et al.3D path planning based on improved ant colony algorithm[J].Computer Engineering and Applications，2020，56（17）：217-223.
[15]徐玉琼，娄柯，李婷婷，等.改进自适应蚁群算法的移动机器人路径规划[J].电子测量与仪器学报，2019，33（10）：89-95.XU Yuqiong，LOU Ke，LI Tingting，et al.Path planning of mobile robot based on improved adaptive ant colony algorithm[J].Journal of Electronic Measurement and Instrumentation，2019，33（10）：89-95.
[16]李宪强，马戎，张伸，等.蚁群算法的改进设计及在航迹规划中的应用[J].航空学报，2020，41（S2）：213-219.LI Xianqiang，MA Rong，ZHANG Shen，et al.Improved design of ant colony algorithm and its application in path planning[J].Acta Aeronautica et Astronautica Sinica，2020，41（S2）：213-219.
[17]唐立，郝鹏，张学军.基于改进蚁群算法的山区无人机路径规划方法[J].交通运输系统工程与信息，2019，19（1）：158-164.TANG Li，HAO Peng，ZHANG Xuejun.An UAV path planning method in mountainous area based on an improved ant colony algorithm[J].Journal of Transportation Systems Engineering and Information Technology，2019，19（1）：158-164.
[18]WANG H，GUO F，YAO H，et al.Collision avoidance planning method of USV based on improved ant colony optimization algorithm[J].IEEE Access，2019，7：52964-52975.
[19]LI B，QI X，YU B，et al.Trajectory planning for UAV based on improved ACO algorithm[J].IEEE Access，2019，8：2995-3006.
[20]LIU W，ZHENG X.Three-dimensional multi-mission planning of UAV using improved ant colony optimization algorithm based on the finite-time constraints[J].International Journal of Computational Intelligence Systems，2021，14（1）：79-87.
[21]YUE L，CHEN H.Unmanned vehicle path planning using a novel ant colony algorithm[J].Eurasip Journal on Wireless Communications and Networking，2019，2019（1）：1-9.
[22]SANGEETHA V，KRISHANKUMAR R，RAVICHANDRAN K S，et al.Energy-efficient green ant colony optimization for path planning in dynamic 3D environments[J].Soft Computing，2021，25（6）：4749-4769.
[23] MIAO C，CHEN G，YAN C，et al.Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J].Computers & Industrial Engineering，2021，156：107230.
[24]LI F，ZLATANOVA S，KOOPMAN M，et al.Universal path planning for an indoor drone[J].Automation in Construction，2018，95：275-283.
[25]ZHANG X，WANG J，FANG Y，et al.Multilevel humanlike motion planning for mobile robots in complex indoor environments[J].IEEE Transactions on Automation Science and Engineering，2018，16（3）：1244-1258.
