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

陈礼琪

（上海理工大学光电信息与计算机工程学院 上海 200093）

1 引言

随着科学技术的发展，无人机因其可飞行，可探索未知领域等优点被广泛地应用。在各个行业中。但是无人机在飞行过程中也会遇到障碍物，在目标搜寻中，需要避开所在的障碍物，同时需要最短的距离。

目前有很多对于无人机路径规划的智能算法，比如：遗传算法［1］，粒子群算法［2］，人工势场算法［3］，蚁群算法［7~16］，免疫算法［4］，混合组搜索优化器算法［5］，以及A*算法［6］等。蚁群算法是一种用来寻找优化路径的概率型算法，模拟了一种基于蚁群间协作的仿生智能优化算法。最初是应用在TSP 旅行商最优路线的规划。后来逐渐应用在路径规划，可以实现二维以及三维的路径规划。文献［7］借鉴了狼群分配的原则对蚁群算法进行了优化，通过柔和路径曲线达到减小路径的目的。文献［8］在蚁群算法的基础上增加了智能增益算法，可以有效地跳出局部最优，收敛速度明显加快，但是对于路径的优化并不是很明显。文献［9］是在蚁群算法的基础上提出了一种新型的算法，增加了惩罚策略，改变了蚁群算法的模型。文献［10］提出双蚁群算法，同时增加了遗传算法，定期进行信息交换。文献［11］提出基于A*算法和蚁群算法结合的算法。文献［12］通过路径代价计算方法，并使用改进的多目标蚁群算法对路径进行优化选择。文献［13］是通过一种改进信息素更新规则的蚁群算法。文献［14］传统蚁群算法的局部收敛问题采用全局与局部信息素互补衰减法，来高效完成蚁群算法寻优问题。文献［15］在路径搜索时引入了一种双向搜索机制，对选择方法进行改进。文献［16］通过调整信息素挥发因子大小，提出了一种适用于路径规划的自适应蚁群算法。

本文提出一种改进的蚁群算法，在借鉴了文献［8］的基础上，增加了转移概率，并对最优路径的信息素增强。最后通过实验表明，算法能够搜寻到更短的路径，而且加快了收敛速度，减少了迭代次数。

2 基本算法

2.1 栅格法

本文采用栅格法模拟静态环境，作为移动空间模型。在静态环境中，假设障碍物的大小和位置都是已知的。

在栅格网中，随机生成一个环境，其中白色表示可行区域，黑色表示障碍物。在栅格网规划一个起点和终点，然后随机分布障碍物，无人机运行轨迹必须避开障碍物到达终点，并且寻找出最佳路径。同时，对栅格网进行坐标点的建立，每一格网格都对应一个坐标点。网格的编号从左往右，从下往上都是逐渐增大。假设小方格的边长为a，横坐标一共有X 个方格，纵坐标一共有Y 个方格，i 为方格的编号，我们可以通过下列式子求得每个编号所对应的坐标点：

图1 是无人机可以飞行的八个方向，它的每一步都是从一个网格的中心到另一个相邻网格的中心，所以无人机飞行时运动的步长为a或者 2a。

图1 无人机飞行方向

2.2 传统蚁群算法

蚁群算法一直被用来解决路径规划问题，然而蚁群算法的关键部分是在信息素矩阵的更新。更新的结果直接导致蚁群算法的最优路线。每一代蚂蚁行走的路线表示待优化的可行解，蚁群行走的所有路径就构成了解空间，在每一代每一只蚂蚁行走的时候都会释放一种信息素。随着时间的推进，每一代蚂蚁走过的相同路径的信息素就会越来越高，那么就有更大的可能性选择信息素较高的路径，从而能找出更优路线。

2.3 转移概率

传统的蚁群算法的转移概率为

上式α表示的是信息素重要程度因子，β表示启发函数重要程度因子，Jk(i)表示第k 只蚂蚁从位置i到可行路径点的集合，τij(t)表示在t 时刻从位置i到j的信息素，ηij(t)是在t时刻启发因子，它的值为t时刻位置i到j的距离的倒数：

在现实世界中，随着时间的推移，蚂蚁释放的信息素会逐渐蒸发。它有助于蚂蚁在选择的时候能找到更好的路径。对下一代的蚂蚁寻找路径的时候有着很好的指导作用。信息素的更新公式如下：

式中ρ是信息素挥发因子，范围在0~1之间。

Lk表示的是第k 只蚂蚁走过的总路程。Q 表示信息素释放总量。

3 算法改进

3.1 转移概率改进

考虑到为了增加有效蚂蚁，尽可能减少蚂蚁陷入死区间，在转移概率上进行了改进，添加了选择下一个节点的可行点的分析，可将转移概率公式改进为下列公式：

allowij(t)是蚂蚁选择的下一节点可行节点的个数。具体情况如图2所示。

图2 路径选择分析

从图2 中，无人机当面对有死区的时候，通过下一个节点的可行节点的个数，优先选择可行节点多的方向。这样可以避免产生过多的无效蚂蚁。

3.2 信息素改进

传统的蚁群算法在每一代搜索路径的时候可能会丢失最佳路径。改进的蚁群算法将每一代的蚂蚁最佳路径与历史的最佳路径进行比较，如果当代的最佳路径比历史最佳路径长度更短。则保持当代蚂蚁的路径。否则，将历史最优路径替换到当代最远路径。每条路径上的信息素可以更改为如下公式：

在第二方面所提出的基于增益算法中，通过消除需要穿越障碍物周围所有的路径来获得能量减少。通过这一原理，可以将信息素更新公式改写为

在迄今为止找到的最佳路径上添加新的信息素，通过减少障碍物周围所有路径的能量计算，实现更快的寻路。本文利用了标准正态分布函数作为信息素的增益，通过下列公式可以得到信息素增益：

其中Xcurrent表示无人机当前的位置，Xdestination表示无人机的终点，Xinitial表示无人机的起点。

增益值呈标准正态分布函数，增益可以是正的，也可以是负的，如果增益为正，蚂蚁将往目标点的方向移动，如果增益是负的，那么蚂蚁将会远离目标点。当蚂蚁到达当前节点的时候，搜索下一个要访问的节点，那么会优先选择离目标点近的节点作为下一个要访问的节点。

图3 中，A 表示无人机起点，B 为目标点，X1 表示前一个位置节点，X2 表示无人机当前的节点。如果X2到B点的欧式距离小于X1到B点的欧式距离，则增益，将与当前信息素数量增加，否则按照等式中给出的方法减去。

图3 增益分析图

3.3 算法流程

1）环境建模，设立初始化参数，设立初始点和目标点。

2）初始化蚂蚁种群。

3）蚂蚁从初始点转移，通过生成的转移概率以及轮盘赌法选择转移的点，同时将上一节点接入禁忌表中。

4）保存这一代每只蚂蚁走的路径以及总长度。并与历史最短路径进行比较，如果当前最短路径长度大于历史最短路径，将历史最短路径替换到当代最远路径。

5）利用提出改进方法更新信息素。

6）判断是否达到最大迭代次数，若达到最大迭代次数，停止循环，否则，继续循环。

7）输出结果。

4 实验仿真

4.1 参数设定

本实验在Windows10 系统的Matlab 软件下不同的环境进行仿真。设每条路径的初始浓度为8，小方格的边长为1m。迭代次数为100，种群大小M为50。表1列出了算法的内部初始值参数设置。

表1 初始参数设定

4.2 仿真结果

本次20*20的简单环境和30*30的复杂环境是随机生成的。

4.2.1 测试一

从图4~图6可以看出，改进后的算法收敛速度明显加快，更能寻到更短的路径，有较好的稳定性。

图4 20*20传统蚁群算法路径规划图

图6 20*20收敛比较

4.2.2 测试二

从图7~图9 可以看出，在更为复杂的环境下，传统蚁群算法明显出现了大量的折回路线，相比之下，改进后的算法能寻到更短的路径，收敛速度也明显加快。

图5 20*20改进蚁群算法路径规划图

图7 30*30传统蚁群算法路径规划图

图8 30*30改进蚁群算法路径规划图

图9 30*30收敛比较

4.3 数据分析

本实验在随机选择转移点时采用的是轮盘赌法，根据Matlab随机生成的数值决定了选择下一个节点。因此具有一定的随机性，为了避免路径规划中存在一定的偶然性，本实验进行多次实验，对数据取平均值。得到表2和表3。

从表2 和表3 可以看出，本文算法不管在20*20的环境还是30*30的环境下，得到的路径长度都是小于传统的蚁群算法，而且收敛速度快。本文通过改变转移概率及朝着最优方向不断优化信息素的方法，通过仿真实验可以看出有着明显的优越性。也更能找到最优路径。收敛也更加稳定。算法有着一定的提升。

表2 20*20改进算法和传统算法性能评估

表3 30*30改进算法和传统算法性能评估

5 结语

蚁群算法是一种具有正反馈机制的智能算法，主要内容包括路径的构建和信息素的更新。本文主要以传统蚁群算法所存在的缺点提出一种改进的算法。对于转移概率的改进，可以有效避免蚂蚁陷入死区间。再利用增益函数，对节点进行距离判断，来增加或减少当前路径的信息素。算法再Matlab 中实现，实验结果表明改进的算法在路径收敛速度以及寻找最佳路径方面表现较好。

但是本文只考虑了静态环境，动态障碍物并没有涉及，有着一定的局限性。