贵州民族大学数据科学与信息工程学院，贵州 贵阳

收稿日期：2020年10月8日；录用日期：2020年10月23日；发布日期：2020年10月30日

摘要

路径规划是无人机研究领域的重要课题之一。针对蚁群算法在优化路径规划问题出现算法运行效率较低，易陷入局部最优的问题。提出了基于对数正太分布函数改进蚁群算法的信息素蒸发因子，然后改进信息素强度和引入轮盘赌算法。并对其进行计算机仿真和结果分析。结果表明：该算法能够保证无人机在最短的距离到达终点，且减少了算法的迭代次数，验证了算法的可行性和高效性。

关键词

路径规划，无人机，蚁群算法，对数正太分布函数，信息素

Unmanned Aerial Vehicle Path Planning with Improved Ant Colony Algorithm

Maoxiang Tian

School of Data Science and Information Engineering, Guizhou Minzu University, Guiyang Guizhou

Received: Oct. 8^th, 2020; accepted: Oct. 23^rd, 2020; published: Oct. 30^th, 2020

ABSTRACT

Path planning is one of important topics in the field unmanned aerial vehicle (UAV) of study. In view of the ant colony algorithm (ACO) in the optimization of path planning problem that ACO has low algorithm efficiency and is easily trapped into local optimal optimization in the optimization of path planning, path planning puts forward the pheromone evaporation factor that improves Ant Colony Algorithm based on the normal distribution function, and then improves the pheromone intensity and introduces roulette algorithm. And it focuses on the computer simulation and the result analysis of the ACO. The results show that the algorithm can guarantee the UAV to reach the destination in the shortest distance, and reduce the iteration times of the algorithm which verifies the feasibility and efficiency of the algorithm.

Keywords:Path Planning, UAV, Ant Colony Algorithm, Logarithmic Normal Distribution Function, Pheromone

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 导言

无人驾驶的飞机简称“无人机”(unmanned aerial vehicle，简称UAV)；在海湾战争和近年来的利比亚、叙利亚战争中，UAV在战场上表现非常的优秀，发挥着显著的作用。UAV的路径规划是智能飞行器领域的一个热点问题，其目的是在复杂的环境下，满足起点到终点的最优路径。目前，国内外研究无人机的路径规划的工作已经做了大量的仿真实验，其中包括Dijkstra算法 [1]，A*算法 [2]，神经网络 [3]，模糊逻辑 [4]，粒子群算法 [5]，鸽群算法 [6]，遗传算法 [7]。

针对蚁群算法路径规划中容易陷入局部最优的问题，本文采用了对数正太分布函数来改进信息素蒸发因子和改进路径上信息素增加强度系数，引入了轮盘赌算法来增加算法的随机性，通过MATLAB仿真的实验结果表明该方法的可效性和正确性。

2. 环境建模

栅格法 [8] 是无人机的环境进行建模的常用方法之一，采用此方法在对一些障碍物进行膨胀处理，即无人机可以沿着障碍物的边界行走，可以避免复杂的曲线计算。在栅格法中，对于栅格的粒度的选择尤为重要，粒度小精确度就越高，储存空间就越大，算法时间越长，搜索空间越大。相反粒度越大，规划的路径就不会太精确。

设无人机的飞行步长为a，则规定栅格的大小为无人机的飞行步长 $a=1$，空间中有障碍物区域和可以飞行区域，无人机在飞行时可以选择可飞行区域，也可以选择障碍物区域，经过障碍物区域时无人机会从上空飞越。在建模过程中，将对障碍物进行模糊处理，如果一块栅格中的全部或部分被障碍物填充，则认为此栅格为障碍物栅格。

记f为空间区域中的任意栅格，C作为所有栅格的集合，其中 $tab{u}_k$ 作为障碍物的集合，任意栅格f属于坐标系中确定的栅格坐标 $\left(x,y\right)$，记为 $f\left(x,y\right)$，其中x表示f的行数，y为f的列数， $G=\left\{1,2,3,\cdots ,M\right\}$ 为栅格序号的集合， $f\left(1,1\right)$ 的序号记做1， $f\left(1,2\right)$ 的序号记做2， $f\left(1,3\right)$ 的序号记做3， $f\left(2,1\right)$ 的序号记做 $N_x+1$ ( $N_x$ 是多少列栅格)……， $f_i$ 的栅格坐标 $\left(x_i,y_i\right)$ 与序号 的栅格坐标关系式为

$\{\begin{array}{l}{x}_i=a\ast \left(mod\left(i,MM\right)-0.5\right)\\ y_i=a\ast \left(MM+0.5-ceil\left(i/MM\right)\right)\end{array}$ (1)

MM为整个栅格的大小，ceil为 $i/MM$ 取整部分，mod为 $i/MM$ 取余数部分。对于任意的二维地形，无人机航迹规划要求是使无人机从起点以最短路径到达终点，满足起点和终点位于栅格序号的范围内且起点不等于终点，完成栅格法的建模后将蚁群算法为解决路径规划的方法在MATLAB中实现。

若的搜索空间是二维的10 × 10的栅格地图，网格编号为1~100。先从左到右，再从上到下编号1为起点，编号100为终点。对栅格编号后就可以根据编号找到栅格坐标，这种对应的关系有助于程序运算。如果一个栅格的编号为10，它的坐标为(9.5, 0.5)，如图1。

图1. 为搜索方向示意图

在栅格地图中0表示可以通过，1表示障碍物不能通过。

首先对航路规划空间进行划分，构造路径搜索的最小单元。本文采用网格划分，航路由一系列相邻网格节点连接形成，每个航迹点的下一节点的搜索范围是以其为中心的8个相邻节点，如果无人机在栅格序号15上时，栅格序号15被认为是九宫格的中心栅格，则下一步无人机将从上、右上、左上、下、右下、左下、左、右，向周围共8个栅格移动，则下一步移动到栅格的序号为4，5，6，14，16，24，25，26。如图1所示。

3. 蚁群优化算法的基本原理及数学模型

3.1. 状态转移规则

对于每只蚂蚁 $k\left(k=1,\cdots ,m\right)$，己经访问过的节点存一个禁忌表 $tab{u}_k\left(k=1,\cdots ,m\right)$ 表示其在以后的搜索中将不能访问这些节点。设蚂蚁k当前所在节点为i，则其选择节点j作为下一个访问对象的概率为：

$p_{ij}^k\left(t\right)=\{\begin{array}{l}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}{{{\displaystyle \sum }}_{j\in allowe{d}_k}{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }},j\in allowe{d}_k\\ 0,\text{otherwise}\end{array}$ (2)

其中， $allowe{d}_k=\left\{C-tab{u}_k\right\}$ 表示节点可到达的且没有走过的节点的集合，C作为所有栅格的集合。 $\alpha$ 是信息素因子， $\beta$ 是启发因子， ${\tau }_{ij}$ 表示边 $\left(i,j\right)$ 上信息素量， ${\eta }_{ij}\left(t\right)$ 是一个启发式信息，通常由 ${\eta }_{ij}\left(t\right)=\frac{1}{d_{ij}}$ 表示， $d_{ij}$ 为当前节点到下一个节点的距离。

3.2. 信息素更新

残留信息素的更新处理如下式进行调整：

${\tau }_{ij}\left(t+n\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+{\displaystyle {\sum }_{k=1}^m\Delta {\tau }_{ij}^k},0<\rho \le 1$ (3)

$\Delta {\tau }_{ij}^k=\{\begin{array}{l}\frac{Q}{L_k},第k只蚂蚁经过节点\left(i,j\right)\\ 0,\text{otherwise}\end{array}$ (4)

$\Delta {\tau }_{ij}^k$ 表示第k只蚂蚁在节点i到节点j的路径留下信息素量，它等于蚂蚁k此次迭代路径长的倒数。m表示蚂蚁个数， $L_k$ 表示路径长度，为第k只蚂蚁在本迭代中走过所有节点的路径总长，Q为信息素增加强度系数， $\rho$ 表示蚂蚁释放信息素的蒸发率。

4. 改进的蚁群算法

4.1. 对数正太分布的信息素蒸发因子

4.1.1. 对数正太分布的定义

定义：如果随机变量X的函数 $Y=\ln X$ 服从正太分布 $N\left(\mu ,{\delta }^2\right)$，则称X服从参数 $\mu$ 和 ${\delta }^2$ 的对数正太分布 [9]。

从定义可看得出，对数正太分布和正太分布两个函数有着千丝万缕的联系。

令 $\varphi \left(y\right),\phi \left(y\right)$ 分别表示正太分布与表示正太分布函数的分布函数和概率密度，其中

$\phi \left(y\right)=\frac{1}{\sqrt{2\pi }\delta }{\text{e}}^{\frac{-1}{2{\delta }^2}{\left(y-\mu \right)}^2},y\in R$ (5)

$Y=\ln X~N\left(\mu ,{\delta }^2\right)$ 则 $X={\text{e}}^Y$ 且 $Y~N\left(\mu ,{\delta }^2\right)$，于是当 $x>0$ 时

$F_X=P\left(X\le x\right)=P\left({\text{e}}^Y\le x\right)=\varphi (\; ln\; x\; )$

从而 $f_x\left(x\right)={F^{\prime }}_X\left(x\right)=\frac{1}{x}\phi \left(\ln x\right)=\frac{1}{\sqrt{2\pi }\delta }{\text{e}}^{\frac{-1}{2{\delta }^2}{\left(\ln x-\mu \right)}^2}$，当 $x\le 0$ 时，易得 $f_x\left(x\right)=0$

故对数正太分布函数的概率密度函数为

$f_x\left(x\right)=\{\begin{array}{l}\frac{1}{\sqrt{2\pi }x\delta }{\text{e}}^{\frac{-1}{2{\delta }^2}{\left(\ln x-\mu \right)}^2},x>0\\ 0,x\le 0\end{array}$ (6)

根据对数正太分布函数的定义，可以把对数正太分布的计算转化成正太分布函数来计算。

4.1.2. 对数正太分布函数的信息素蒸发系数的改进方式

信息素蒸发系数 $\rho$ 影响蚂蚁之间相互影响的强弱，全局搜寻能力的大小和算法收敛速度，也是影响路径上信息素量大小的重要因素。当蒸发过大时，以前搜索过的路径还会着再次选择的可能性较大，会降低算法的全局搜索能力。相反，信息素蒸发系数 $\rho$ 越小时，全局搜索能力强，但算法的收敛速度较慢。

由于信息素蒸发的会随着时间的变化而变化，所以根据对数正太分布函数的定义来改进信息素蒸发因子 $\rho$，让 $\rho$ 的值随迭代次数的变化服从对数正太分布函数。在寻找最优路径的过程中，为了增加蚂蚁选择路径的随机性，提高蚂蚁的全局搜索的能力，避免蚁群陷入局部最优。本文对信息素蒸发因子 $\rho$ 进行如下改进：

$\rho =\frac{1}{\sqrt{2\pi }\delta k^{\frac{1}{2}}}{\text{e}}^{\frac{-1}{2{\delta }^2}{\left(\frac{\ln k}{2}-\mu \right)}^2},k\in K$ (7)

其中，设随机变量 $k^{\frac{1}{2}}$ 服从对数正太分布，K表示最大迭代次数， $\mu$ 称为对数均值， ${\delta }^2$ 称为对数方差，记为 $k^{\frac{1}{2}}~LN\left(\mu ,{\delta }^2\right)$。设 $\mu ,\delta$ 为常数。对数正太分布函数 $LN\left(\mu ,{\delta }^2\right)$ 是一个偏态函数，对数正太分布函数的曲线随着k的增大 $\rho$ 逐渐减小并趋近0。本文中取 $\mu =0$。在多次的计算机仿真实验中 $\delta =1$ 时，算法的收敛性相对来说比较好。图2是 $\mu =0$，$\delta =1$ 时的信息素蒸发因子 $\rho$ 对数正太分布图像。

图2. 为信息素蒸发系数

4.2. 改进信息素增加强度系数

为了增强对最优路径的利用使得最优路径有比较高的信息素，本文将信息素增加强度系数Q进行如下调整：

$Q=Q_0+\ln k$ (8)

其中信息素增加强度系数初值为 $Q_0$ 常数，k为蚁群的迭代次数(指蚂蚁出动的次数)。方程式表明随着迭代的增加，信息素增加强度增大，能避免蚁群陷入局部最优，进而提高改进后算法的全局搜索能力。

4.3. 轮盘赌算法

轮盘赌算法是在蚂蚁寻找终点食物的路上，首先从当前节点运用状态转移规则来计算下一个节点的选择概率，然后结合轮盘赌算法得到积累概率比随机数大的第一个可选择点作为行走的下一步。这样增加了蚁群算法的随机性，提高了收敛算法的速度。

5. 蚁群算法的主要步骤

步骤一：二维的环境建模，把栅格地图转换邻在接矩阵

步骤二：参数初始化

步骤三：将m只无人机放起始点S (0.5, 0.5)处等待出发

步骤四：无人机根据公式(2)由当前节点选择下一个节点，这样迭代下去，最后到达终点T(19.5, 19.5)得到最优航路；

步骤五：对飞行区域中的节点根据公式(7) (8)来改进信息素蒸发因子和信息素增加强度，在由公式(3) (4)进行信息素浓度的更新，并记录当迭代次数的最短路径；

步骤六：若没有达到迭代次数，则转至步骤四继续执行，直到满足迭代条件；否则，终止运算，输出最优解 [10]。

6. MATLAB仿真与分析

对本文中基于对数正太分布函数的ACO算法进行仿真实验，使用PC为联想电脑，系统为Windows7，CPU为Core i5-6200U，内存为4 G，软件为MATLABR2018A。实验采用20 × 20的二维静态栅格地图。

参数分析

信息素启发式因子 $\alpha$ 值越大，无人机选择走过的路就越大，搜索路径的随机性就越小， $\alpha$ 值越小，搜寻范围就缩小，容易陷入局部最优。

期望启发式函数因子 $\beta$ 越大，无人机容易选择局部最短的路径，算法的收敛速度加快了，但随机性不高。

无人机数量m越多，得到最优的解更越精确，但会生出很多重复解，随着算法接近最优值，信息的正反馈作用下降，增加了时间的复杂度。

信息素增加强度Q₀越大，则无人机在路径上释放的信息素就大，信息素的正反馈作用对无人机的选择更强烈，使运算速度更快，收敛越早，同样也容易陷入局部最优。

迭代次数K越小，算法得到的最短路径不一定使最优路径，K越大，算法的迭代时间越长，经典蚁群算法和改进算法参数 [11] 如表1所示。

表1. 本文算法的实验参数设置

图3. 为经典ACO的运动轨迹

在相同的实验环境下，考虑最优规划路径问题，将传统蚁群算法和基于对数正太分布函数的蚁群算法模拟效果进行比对分析，模拟结果见图3、图4。可以看出蚁群算法融入对数正太分布函数UAV的避障能力增强。

由图3与图4中的二维栅格地图可得，改进后的ACO的无人机轨迹转折比经典ACO少四个转折，说明本文改进的ACO是行之有效的。

从图5与图6的可知，改进的ACO的曲线收敛速度快，且振动幅度小。经过多次的仿真实验得到下面的结论。

如表2所示 [11]，实验结果表明：本文提出的改进ACO比经典ACO的最短路径还少了12.4%，收敛也速度提升较快，从而提高了全局搜索的效率。

图4. 为改进后的ACO的运动轨迹

图5. 经典ACO收敛曲线变化趋势

图6. 改进后的ACO收敛曲线变化趋势

表2. 本文算法与经典ACO的实验数据比较

7. 结束语

在复杂环境下传统蚁群算法收敛速度慢、易陷入局部最优，本文引入了对数正太分布函数改进信息素蒸发因子的蚁群算法MATLAB仿真实验。结果证明：改进的蚁群算法比传统蚁群算法的搜索路径长度减少了12.4%，且大大地减少了算法的迭代次数，提高了算法的收敛速度，从而提高蚁群算法全局搜索的效率。

文章引用

田茂祥. 改进蚁群算法的无人机路径规划
Unmanned Aerial Vehicle Path Planning with Improved Ant Colony Algorithm[J]. 计算机科学与应用, 2020, 10(10): 1900-1907. https://doi.org/10.12677/CSA.2020.1010200

参考文献