改进自适应蚁群算法移动机器人避障路径规划

Improved Adaptive Ant Colony Algorithm for Obstacle Avoidance Path Planning of Mobile Robots

摘要: 针对传统蚁群算法在复杂网络路径规划中收敛速度慢和易陷入局部最优解的问题，本文在蚁群算法状态转移概率公式的基础上考虑了安全性因素和加权因子，在全局信息素更新过程中引入自适应动态因子，提出改进的自适应蚁群算法以更快地获取全局最优解。将改进自适应蚁群算法应用于移动机器人的路径规划，使用可视图法描绘出障碍物图像，通过真实数据进行实验分析，证明了改进自适应蚁群算法比传统蚁群算法、改进蚁群算法的收敛速度更快，路径更优，在有障碍物环境中也能合理地进行路径规划。

Abstract: In view of the traditional ant colony algorithm in path planning in complex network slow convergence speed and fall into local optimal solution of the problem, based on the ant colony algorithm on the basis of state transition probability formula considering the safety factor and the weighting factor, in the process of global pheromone update introduced adaptive dynamic factor, this paper puts forward the improved adaptive ant colony algorithm to obtain the global optimal solution more quickly. Improved adaptive ant colony algorithm was applied to mobile robot path planning, image view method was used to depict the obstacles, experimental analysis, through the real data proves that the improved adaptive ant colony algorithm has a faster speed, better path than the traditional ant colony algorithm and the improved ant colony algorithm convergence, with an obstacle in the environment can reasonably make path planning.

1. 引言

移动机器人是当前研究的热点，在人们的日常生活工作中应用广泛，人们对机器人的需求也越来越大。在使用过程中，机器人的移动路径对其能量消耗产生重要的影响，因此需要对机器人的移动路径做出合理规划。目前，路径规划技术是机器人研究领域的一个重要分支。最优路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等)，寻找出一条从起始位置到目标位置的最优无碰撞路径。当移动路线中存在大量障碍物时，机器人需要避开障碍物并不断绕行，这大大增加了机器人在路上的能量消耗。目前用于机器人路径规划的算法主要有人工势场算法 [1]、遗传算法 [2] [3]、粒子群优化算法 [4]、蚁群算法 [5]、神经网络算法 [6] 等。

目前对蚁群算法的改进主要针对信息素改进和启发信息改进。刘锴 [7] 等人提出了一种复杂环境下移动机器人路径规划的改进蚁群算法，在传统转移规则中引入指向上一节点的数组，增强了算法的逃逸能力。张成 [8] 等人在路径选择概率中引入障碍物排斥权重和新的启发因子，提高了机器人的避障能力。曾明如 [9] 等人提出势场蚁群算法，利用势场力启发信息影响系数和机器人与目标位置距离构造综合启发信息，提高了收敛速度。上述改进的蚁群算法虽然寻找到了接近的最优解的解，但在全局更新规则中未考虑较优解对最优解的影响。

基于此，为了保证蚂蚁在搜索路径过程中能够获取有效的避障路径，本文在状态转移概率公式的基础上考虑了安全性因素并引入加权因子，在全局信息素更新过程中加入双曲正切函数作为自适应动态因子，自适应地更新每次迭代较优解路径的信息素浓度，更逼近全局最优解，提高移动机器人避障路径规划的效率和安全性。

2. 改进的自适应蚁群算法

蚁群算法是以蚂蚁在寻找食物过程中寻找最短路径为原型的一种模拟进化算法。蚁群内的蚂蚁会在其经过的路径上释放信息素，其他蚂蚁感知到释放的信息素后会沿着信息素浓度较高路径行走，每只路过的蚂蚁都在这条路径上释放信息素，因此形成一种类似正反馈的机制，经过一段时间后，最优路径上的信息素浓度越来越大，整个蚁群就会沿着最短路径到达食物源了。

2.1. 状态转移概率的改进

蚁群算法中，蚂蚁主要是通过其他蚂蚁在移动期间散发的信息素浓度的大小，以及当前节点选择下一节点的启发信息，选择所要行走的移动路径。蚂蚁从当前节点转移到下一节点主要有涉及到概率选择和信息素更新这两个关键因素。当蚂蚁在行驶过程中存在复杂障碍物时，会大大降低蚂蚁搜索路径的准确性，为了使机器人在移动过程中能够尽可能地避开障碍物安全行驶，获取有效的避障路径，在路径选择概率公式中增加了安全性因素 $\phi \left(i,j\right)$， $\phi \left(i,j\right)\in \left[0,1\right]$。蚂蚁在当前节点i选择下一节点j时的安全程度用式(1)表示：

$\phi \left(i,j\right)=\frac{1}{e^{\varphi \left(j\right)}}$ (1)

其中， $\varphi \left(j\right)=m_j-\min \left(m_{ij}\right)$ 表示蚂蚁转移到节点j的安全性， $m_j$ 是下一个节点j的障碍物数， $\min \left(m_{ij}\right)$ 是蚂蚁从当前节点 $i$ 转移到下一个所有可行节点中障碍物数最小值。 $\varphi \left(j\right)$ 越小表示障碍物越少，移动路径越安全，对蚂蚁的启发作用越强 [10]。

改进后的路径选择概率公式为式(2)，即当 $q>q_0$ 时，第k只蚂蚁由节点 转移到下一个节点j的概率为：

$P_{ij}^k\left(t\right)=\{\begin{array}{cc}\frac{{\tau }_{ij}^{\alpha }\left(t\right){\eta }_{ij}^{\beta }\left(t\right){\phi }^{\gamma }\left(i,j\right)\left(t\right)}{{{\displaystyle \sum }}_{s\in allowe{d}_k^i}{\tau }_{is}^{\alpha }\left(t\right){\eta }_{is}^{\beta }\left(t\right){\phi }^{\gamma }\left(i,j\right)\left(t\right)}& j\in {\text{allowed}}_k^i\\ 0& j\notin {\text{allowed}}_k^i\end{array}$ (2)

其中， ${\tau }_{ij}\left(t\right)$ 表示在t时刻当前节点i到下一个节点j途中信息素的浓度； ${\eta }_{ij}\left(t\right)$ 表示在t时刻当前节点i到下一个节点j路径上的启发信息， ${\eta }_{ij}=\frac{1}{d_{ij}}$， $d_{ij}$ 为节点i到节点j的欧氏距离； $\alpha$ 表示信息素增强系数，

其值越大对初始随机的信息素影响越深； $\beta$ 为期望启发式信息系数，其值越大蚂蚁就越倾向于目标节点； $\gamma$ 为安全程度因子，其值越小蚂蚁移动的路径就越安全； $s\in {\text{allowed}}_k^i$ 表示蚂蚁 $k$ 在当前节点i到下一个可选节点j的集合，每只蚂蚁对每个节点最多访问一次。

当 $q\le q_0$ 时，第 $k$ 只蚂蚁选取概率最大的节点 $\hat{j}$ 作为目标节点：

$\hat{j}=\arg {\max }_{s\in {\text{allowed}}_k^i}{\tau }_{is}^{\alpha }\left(t\right){\eta }_{is}^{\beta }\left(t\right){\phi }^{\gamma }\left(i,j\right)\left(t\right)$ (3)

q是均匀分布在0与1之间随机变量，依赖于时间t； $q_0\in \left(0,1\right)$ 是蚂蚁状态转移的阈值。第k只蚂蚁从节点i转移到下一个节点j的规则由q与 $q_0$ 比较的大小决定。

移动机器人在当前节点移动到周围可行节点距离目标节点差距较大，为了提高算法的收敛速度，在上述状态转移概率公式中引入加权因子 $l\left(l\in \left(0,1\right)\right)$。改进后的公式如下：

$P_{ij}^k\left(t\right)=\{\begin{array}{cc}l\cdot \frac{{\tau }_{ij}^{\alpha }\left(t\right){\eta }_{ij}^{\beta }\left(t\right){\phi }^{\gamma }\left(i,j\right)\left(t\right)}{{{\displaystyle \sum }}_{s\in allowe{d}_k^i}{\tau }_{is}^{\alpha }\left(t\right){\eta }_{is}^{\beta }\left(t\right){\phi }^{\gamma }\left(i,j\right)\left(t\right)}& j\in {\text{allowed}}_k^i\\ 0& j\notin {\text{allowed}}_k^i\end{array}$ (4)

2.2. 改进信息素更新机制

蚁群算法中，蚂蚁会以较高概率选择信息素浓度较高的路径，当搜索过的路径被重复搜索时，全局搜索能力下降，改变挥发系数虽然可以提高全局搜索率但是会降低收敛速度 [11]。因此提出一种自适应的改变节点i与节点j间信息素值的方法。设信息素挥发的系数为 $\rho$，改进后的局部信息素更新公式下：

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+\rho \Delta {\tau }_{ij}\left(t\right)$ (5)

$\Delta {\tau }_{ij}\left(t\right)={\displaystyle {\sum }_{k=1}^m\Delta {\tau }_{ij}^k\left(t\right)}$ (6)

$\Delta {\tau }_{ij}^k\left(t\right)=\frac{Q_{ij}}{L_k}\frac{L_{\text{localbest}}+L_{\text{localworst}}}{2}$ (7)

其中， $\Delta {\tau }_{ij}^k$ 表示第k只蚂蚁从节点i到节点j的最优路径； $Q_{ij}$ 表示蚂蚁从节点i到节点j最优路径的信息素浓度增加总和，是一个大于0的常数； $L_k$ 表示第k只蚂蚁此次迭代搜索的路径长度； $L_{\text{localworst}}$ 表示此次迭代后的最差路径长度； $L_{\text{localbest}}$ 表示此次迭代的最优路径长度。

当较短路径信息素浓度增加时，全局最优路径与单次迭代的最优路径相关性较大，容易陷入局部最优，因此在全局信息素更新规则中加入自适应动态因子，动态更新每次迭代最优路径的全局信息素浓度，

也动态更新了较优的局部最优解。传统算法的动态因子是 $f\left(x\right)=\frac{1}{2}\mathrm{sgn}\left(x\right)+\frac{1}{2}$， $x$ 为最优路径长度，虽

然加强了最优路径上信息素浓度，但在较优路径上的信息素浓度没有及时更新。为了使较优路径信息素浓度更新更具有自适应性，使用双曲正切函数作为自适应动态因子 [12]，如式(8)：

$f\left(x\right)=\frac{1}{2}\tanh \left(\omega x\right)+\frac{1}{2}$ (8)

其中， $\omega$ 为控制双曲正切函数形状参数。

通过自适应地控制每次迭代的最优解的信息素浓度在当前最优解中的权重，及时更新较优路径上的信息素浓度，发挥较优路径信息素浓度的作用。改进后的全局信息素更新公式如下：

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+\sigma \mu \Delta {\tau }_{ij}$ (9)

$\sigma =\frac{1}{2}\tan h\left(\omega \frac{L_{\text{localbest}}-L_{\text{best}}}{L_{\text{ave}}-L_{\text{best}}}\cdot \frac{L_{\text{best}}+L_{\text{worst}}}{2}\right)+\frac{1}{2}$ (10)

其中， $L_{\text{best}}$ 是所有路径中的最优路径长度； $L_{\text{worst}}$ 表示所有路径中的最差路径长度； $L_{\text{ave}}$ 表示路径的平均长度； $\mu$ 是给定的参数。

2.3. 改进后的算法步骤

步骤1初始化参数。设置初始位置S，目标位置T，最大迭代次数N，蚂蚁数m，信息素因子 $\alpha$，启发函数因子 $\beta$，路径启发因子 ${\eta }_{ij}$。

步骤2定义节点i和节点j路径上的初始信息素浓度为 ${\tau }_{ij}$。将m只蚂蚁放在初始位置S处，并将S写入禁忌表中，按照式(3)和式(4)选择下一个可以转移的目标点并将其添加到禁忌表中。

步骤3蚂蚁每次找到路径后，按照式(5)进行信息素局部更新。

步骤4重复步骤2和3，直到所有蚂蚁都到目标位置T，存储路径信息，得到m条由初始位置S到达目标位置T的路径集合 $\left\{l_1,l_2,\cdots \text{,}{l}_m\right\}$。

步骤5比较m条路径的长度并找出本次迭代的最优路径记为 $L_{\text{localbest}}$，求出m条路径的平均路径长度 $L_{\text{ave}}$，所有路径中的最优路径长度 $L_{\text{best}}$，所有路径中的最差解 $L_{\text{worst}}$，按照式(9)计算出自适应动态因子，并根据式(8)对信息素浓度进行全局更新。

步骤6重复步骤2~4，直到达到最大迭代次数N，比较输出结果，找到全局最优解。

流程图如图1。

Figure 1. Flowchart of improved adaptive ant colony algorithm

图1. 改进自适应蚁群算法流程图

3. 描绘障碍物

可视图法 [13] 是机器人全局运动规划的经典算法。在机器人路径规划中，通常用点描述机器人，其大小忽略不计，用规则的多边形描述障碍物，分别将起始点S、目标点T和多边形障碍物的各顶点(设 $V_0$ 是所有障碍物的顶点构成的集合)通过直线进行组合连接，其中起始点和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，对各顶点间连线赋权值，构造可见图 $T\left(V,E\right)$，如图2所示。其中点集 $V=V_0\cup \left\{S,T\right\}$，E为所有连接线段即可见边的集合，釆用改进的自适应蚁群算法对起始点S到目标点T的最优路径进行搜索，根据累加和比较所有直线的距离，即可找到其中最短路径 [14]。

Figure 2. Can view method

图2. 可视图法

4. 实验分析

4.1. 数据来源

根据某市传感器经纬度坐标数据，经过地图匹配算法得到传感器分布图如图3，研究区域包括一个数据中心和25个传感器，由分布图可知传感器多分布于海面上。考虑实际路况与建筑情况较为复杂以及训练模型在水陆两类环境下的适用性和兼容性，将位于海面上各传感器间的可行路径视为无障碍路径，忽略传感器在海面上的偏移，暂将海面上传感器视为移动充电机器人为其充电。

Figure 3. Sensor distribution map

图3. 传感器分布图

各传感器间部分相关系数热力图如图4所示。

Figure 4. Heat map of partial correlation coefficient among sensors

图4. 各传感器间部分相关系数热力图

4.2. 最优路径的模型建立

移动机器人从数据中心出发，遍历每个传感器一次并为其充电后再返回数据中心的最短路径问题，就是经典旅行商问题。将传感器经纬度数据从数据中心开始按照顺序依次进行编号为 $A_1,A_2,A_3,\cdots ,A_{26}$。第k条路径即从节点i到节点j的距离记为 $d_k\left(i,j\right)$。 $d_1\left(i,j\right)$ 表示数据中心A₁到第一个传感器A₂间的距离， $d_{26}\left(i,j\right)$ 时表示传感器A₂₆数据中心A₁的距离，移动充电器从数据中心出发经过26个传感器的路径总距离可以建立如下数学模型：

$D=\min {\displaystyle {\sum }_{k=1}^{26}{d}_k\left(i,j\right)},$ (15)

$s.t.d_k\left(i,j\right)\ge 0\left(i,j\right)\in \left(1,2,\cdots ,26\right)$ (16)

4.3. 模型求解

因为传感器A₁₉，A₂₀，A₂₁，A₂₃，A₂₄，A₂₆周围存在大量建筑物，对移动充电机器人的移动路径有较为重要的影响，通过可视图法描绘出大型建筑障碍物平面图如图5所示，并分析移动机器人的行走路径。

Figure 5. Sensor and building layout graph

图5. 传感器与建筑物分布平面图

设传感器A₂₃为起点S，传感器A₁₉为终点T，黑色多边形均为建筑物，把所有障碍物的顶点，起点(传感器A₂₃)，终点(传感器A₁₉)互相连接得到的线段就是可走路径，其中排除穿过障碍物的线段，从中找到最短路径即红色线的路径。传感器A₂₃与传感器A₁₉间移动机器人可行走路径示意图如图6所示。

Figure 6. Path between two sensors graph

图6. 两传感器间可行走路径示意图

增加障碍物后部分节点间距离矩阵见表1。

Table 1. Distance matrix between some nodes after adding obstacles

表1. 增加障碍物后部分节点间的距离矩阵

通过改进的自适应蚁群算法搜索增加障碍物后的移动充电机器人行驶路径中的最短闭合回路。为了提高解的质量，进行500次计算后得到最优路径如图7。

最优路线为：A₁-A₃-A₂-A₁₀-A₈-A₇-A₁₂-A₁₅-A₁₆-A₉-A₁₃-A₁₇-A₂₅-A₁₄-A₁₁-A₆-A₄-A₅-A₂₂-A₂₆-A₂₄-A₂₃-A₁₉-A₂₀-A₂₁-A₁₈-A₁。最短距离为：12.4235182234616 KM。为了验证改进后的自适应蚁群算法在解决路径规划问题的可行性与优越性，与传统蚁群算法进行比较。在相同条件下，三种算法的收敛曲线图如图8所示：

由图8和表2可知，在有障碍路径规划问题中，改进的自适应蚁群算法避开障碍物更快地搜索到了最优路径，收敛速度快，迭代次数少。与传统的蚁群算法和文献 [7] 中改进的蚁群算法相比，本文算法在实际应用中能够更有效找到最优路径。

Figure 7. The optimal path diagram under the influence of obstacles

图7. 有障碍物影响情况下最优路径图

Figure 8. Comparison diagram of three algorithms

图8. 三种算法对比图

Table 2. The results of the three algorithms are compared under the same conditions

表2. 相同条件下三种算法运行结果对比

5. 结论

在状态转移概率公式的基础上考虑安全性因素并引入加权因子，在全局信息素更新过程中构建双曲正切函数作为自适应动态因子，自适应地更新每次迭代较优解路径的信息素浓度，求出有障碍影响下的最优路径，有效地缩短了移动机器人的行驶距离，减小了其在路上的能量消耗。通过维持无线可充电传感器网络系统正常工作的问题验证算法的有效性和可行性，在有障碍物的复杂环境下也可以又快又准确地规划出一条优化路径。

基金项目

贵州省科技计划项目(黔科合基础[2019] 1122号)；贵州大学线上线下混合式课程建设项目(XJG202060)。

NOTES

^*第一作者。

^#通讯作者。