蚁群算法在无人机物流路径规划中的应用

何光勤，黄鑫

（中国民用航空飞行学院，广汉 618307）

0 引言

相对于传统的地面交通运输，航空运输更加快捷；而在航空运输中无人机又拥有不可代替的优点。无人机运输相对于传统的航空运输，其所需要的地面基础设施少，并能在一些偏远区域用较少时间进行运输。无人机的操作也更加简单智能，能够自由调度，且运行成本低。在短距离运输，特别是特大型城市的区间物流或基础设施落后的山区，无人机运输方式能使物品运输更加高效便捷，这是其它的运输方式不能做到的［1］。

最近几年国内外对无人机物流问题已经进行了大量的研究，研究较多的还是无人机避障飞行路径研究。无人机避障研究主要是周围地形环境危险源研究与最优飞行路线研究两方面。赵嶷飞等人［2］通过对无人机的起降、巡航等状态的研究，建立了参数化的垂直速度剖面的模型，然后将退火顺发与粒子群算法用于任务剖面优化。李宪强等人［3］为避免无人机三维航迹规划过程中，蚁群算法陷入局部最优解，引入了人工势场算法对蚁群算法的状态转移函数进行优化。仇钧正［4］提出一中在有雷达与武器威胁的环境下，将预测控制模型与社群蜘蛛算法相结合的无人机动态路径规划方案。黄龙杨等人［5］通过对蚁群算法原理和模型的分析，对算法状态转移函数更新规则进行改进，引入调节信息素的因子，最后使用改进后的蚁群算法对二维栅格环境模型进行航迹仿真［5］。沈培志等人［6］通过无人机路径规划的研究分析，提出了多不同价值目标与多危险源下的无人机飞行决策模型。张宏宏等人［7］针对无人机运行环境安全系数低的情况，对环境模型进行风险评估，再将安全系数作为综合代价，最后改进一群算法对三维空间进行路径规划［7］。揭东等人［8］在无人机冲突模型中加入角度与速度改变的调度策略，使用改进一起拿算法对多机解脱进行路径规划。吴成振等人［9］通过构造无人机定位误差模型，利用贪心算法对无人机二维路径快速规划。

本文将在蚁群算法基础上，对模型中的信息素挥发进行自适应调整，通过多次迭代使信息素挥发系数降低，直至其保持在合理范围内。然后将改进后的算法应用到无人机物流航迹规划中，并通过MATLAB软件完成仿真实验，最后输出无人机二维航迹的优化解。

1 问题描述

2019年杭州已经有物流科技公司开展关于无人机物流运行场景的测试飞行。2020年，民航局召开无人机在低空运行的相关的规则标准与法规的立项开题评审会。伴随着社会快速的发展，低空空域的开放以及相关制度规则的完善，无人机路径规划将在实际生活中的运用越来越多。

在实际应用中无人机物流路径规划问题就是怎样在高楼大厦密集的城市给无人机规划一条安全飞行路线，在起始地与目的地之间找到最优路径。在模型中无人机路径规划就是在已经建立的二维避障环境中，通过算法找到一条不与任何障碍物相交的最优路径。

本文的无人机路径规划主要由两步构成：第一步构建包含有障碍物区的区域和自由移动的环境模型；第二步在建立的环境地图模型上采用改进蚁群算法进行路径搜索，找到最优路径。关于环境模型，本文采用了栅格法。栅格法通过自由栅格与障碍物栅格能够描绘无人机的工作环境。同时栅格法还能够实现空间与时间的消耗最优。关于路径搜索，本文采用了改进蚁群算法。

2 改进蚁群算法

2.1 算法描述

近几十年，学者对生物在自然界生存时所表现出来的智能行为进行了研究与模拟，提出了各种智能算法，例如粒子群算法、蚁群算法、鱼群算法、菌群优化算法、人工蜂群算法等。其中蚁群算法就是科学家对自然界蚂蚁的种群生物习性进行观察研究，提出的一种自启发式算法。蚁群算法具有自然界蚂蚁选择路径时的随机性和路径上信息素的挥发机制。蚂蚁通过路径上的信息素进行正反馈信息交流，从无序状态转换到有序状态。路径规划就是人工蚁群对自然界蚁群寻找食物源的活动进行的模仿。

在算法中的人工蚂蚁都是独立个体，可以通过信息素进行信息交流与协作。在刚开始时每只人工蚂蚁带着相同的任务目标，以局部移动的方式独立地随机地朝各方向出发寻找食物。过一段时间之后，人工蚂蚁会在走过的路径上留下信息素，信息素会随着时间的推移而挥发。之后的人工蚂蚁会根据通过路径节点上的信息素的状态来进行信息交流与协作，以便从一种离散状态转移到另一种离散状态量。当人工蚂蚁的数量足够多的时候，相互协作的蚁群就能构造出路径规划的最优解。

蚁群算法设计中，将m只人工蚂蚁投放到起点，进行路径探索。刚开始时节点i到节点j的路径上信息素τij(0)=c（c为常数）。随着人工蚂蚁的路过，路径上的信息素将会发生改变。第k只人工蚂蚁将根据路径上的信息素τij()t与启发式信息（从节点i到节点j路径距离倒数）ηij()t，在下一步可以选择的点集合J k()t中，独立地选择下一个节点。其中，α、β分别表示信息素和启发信息的相对重要程度。综上，人工蚂蚁选择先下一个节点的概率pkij(t)为：

随着时间的推移，算法中信息素将会像自然界的信息素一样，挥发掉一部分。算法将通过对路径上信息素的更新来实现这一点。路径上信息素的状态信息，将由路径上的信息素蒸发系数与本次迭代中路径节点中信息素增量△τij表示。

当求解的问题规模比较大时，蚁群算法在进行计算的过程中存在搜索时间较长和在路径的搜索过程中易于陷入停滞的现象。原因是蚁群算法在模仿信息素的挥发系数时，设置的是固定的数值。当信息素挥发系数设置过大时，算法的全局搜索能力会降低；当信息素挥发系数设置过小时，算法的收敛速度将会降低。通过探寻算法的全局搜索能力与收敛速度之间的平衡点，本文提出了在蚁群算法信息素挥发机制的基础上进行改进的解决办法。在数学模型上对基础蚁群算法的信息素挥发系数进行自适应的调整，使信息素的挥发系数在每次迭代之后在一定范围内变化，而不是一个固定常数。通过对信息素挥发系数的自适应调整，可以提高算法在路径搜索的时间效率和求解精度。

一些从未被搜索到的路径由于信息素的挥发系数的存在，可能会使路径上的信息素将有保持为0，进而降低算法的全局搜索能力，且容易使蚁群算法限于停滞。当信息素的挥发值过大时，使得算法人工蚁群选择此条路径的概率会过大，此时算法的收敛速度将会降低。通过自适应的改变ρ值

将信息素挥发值ρ限制在一定的范围内，并随着时间的推移ρ值可以自适应的发生改变，以避免以固定不变的去更新路径上信息素的量和选择每条路径的概率，同时提高算法的收敛速度。ρmin可以保证信息素的挥发不会过小，而使算法在路径搜索过程中陷入停滞。

2.2 改进蚁群算法实现

将改进的蚁群算法运用于路径规划，主要分为4步：①用栅格法建立二维环境模型。②将参数初始化。③构建问题的解。④求解。改进蚁群算法流程如图1所示。

图1 改进群算法流程

3 仿真研究结果

为验证改进后蚁群算法在无人机路径规划上的求解性能，本节以MATLAB为仿真平台，进行两次仿真验证。仿真平台为MATLAB，设置20×20的二维栅格图，黑色区域设置为环境障碍物，人工蚁群起点为（0，20），目的地为（20，0）。图2（a）为传统蚁群算法的无人机路径仿真图，图2（b）为传统蚁群算法在搜索路径时的收敛曲线，在迭代了45次后蚁群找到了最短路径，路径长度为30。图3（a）为改进蚁群算法的无人机路径仿真图，图3（b）为改进蚁群算法在搜索路径时的收敛曲线，在迭代了16次之后蚁群找到最短路径，最短路径长度为30。

图2 传统蚁群算法的无人机路径仿真（续）

图2 传统蚁群算法的无人机路径仿真

图3 改进蚁群算法的无人机路径仿真

4 仿真研究结果

本文研究了改进后蚁群算法在无人机在物流配送中二维航迹中的规划。通过对传统的模仿自然界蚁群寻找食物时在路上留下一定量的信息素的蚁群算法进行改造，使路径上的信息素自适应的调整，每次迭代后信息素的挥发系数在规定的范围内进行调整，防止路径上的信息素过高或者过低。仿真结果表明运用改进后蚁群算法在对路径进行全局搜索时拥有更高的效率，在较少的时间内就能找到最短路径。无人机在实际运行中是在三维环境中运行，后续的研究将会着重于三维地形研究。