改进的蚁群算法在灭火机器人多火源路径规划的应用

Application of Improved Ant Colony Algorithm in Multi-Fire Path Planning of Fire Fighting Robot

摘要: 为研究消防灭火机器人在避障环境下寻求到达多火源的最优路径规划问题，针对蚁群算法进行路径规划时易陷入局部最优、收敛速度慢等缺陷，提出一种改进的蚁群算法。首先利用栅格地图建立机器人工作环境模型，将综合权值优先规划策略引入构建好的旅行商算法中，求解出灭火的次序；进而改进转移概率算法，求解出到达各火源的具体路径，增强算法的全局搜索能力及加快收敛速度。在追求路径最短的同时考虑到机器人的转向会消耗时间，提出多指标评价函数来评价路径质量。最后进行仿真，结果表明本算法跳出局部最优能力和收敛速度有很大改进，并证明了改进算法应用在灭火机器人多火源路径规划问题上有很强的可行性和有效性。

Abstract: In order to study the problem of optimal path planning for the fire fighting robot to reach multiple fire sources in obstacle avoidance environment, the based ant colony algorithm is prone to fall into local optimality and slow convergence speed when path planning. First, the grid map is used to establish the robot working environment model, and the integrated weight priority planning strategy is introduced into the constructed traveling salesman algorithm to solve the order of fire extinguishment; then the transition probability algorithm is improved to solve the specific path to each fire source. Meanwhile, the global search ability is improved and the convergence speed is accelerated. While pursuing the shortest path and considering the robot's turning will consume time, a multi-index evaluation function is proposed to evaluate the path quality. Finally, the simulation shows that the algorithm has greatly improved the local optimal ability and the convergence speed, and proved that the improved algorithm has strong feasibility and effectiveness in the problem of multi-fire path planning for fire-fighting robots.

1. 引言

灭火机器人是一种集机械控制、人工智能等多学科先进技术为一体的现代化智能设备，用于协助救援人员开展灭火工作 [1]。对于灭火机器人，以最高效率找到一条从起点到火源的最安全、无碰撞的运动路径是保证其智能化的基础 [2]。路径规划问题一直是机器人研究领域的重要组成部分，是指在有障碍物的工作环境中，找到一条由起点到终点的最优路径 [3]。目前，求解路径规划问题的方法主要有人工势场法和遗传算法 [4]、粒子群算法 [5]、蚁群算法 [6] 等启发式算法。

蚁群算法作为一种新型启发式智能算法，于1996年由意大利学者MARCO DORIGO人等提出，被广泛应用于TSP问题 [7] (旅行商问题)、车辆路由问题 [8]、机器人路径规划问题 [9] 等。单个蚂蚁行为简单，而蚁群协作性非常强。蚁群在觅食过程中，前期路径选择的随机性较强，由于蚂蚁能够在所经过的路径上分泌信息素，且能够感知信息素强度，并向信息素浓度高的路径移动，而较短的路径上残留的信息素较多，因此能够形成一条趋向于最短的觅食路径。由此可知，蚁群算法是一种正反馈算法，随着算法的不断迭代来逼近最优解，但这存在易陷入局部最优的缺点。由于路径规划问题的搜索方向较多，蚁群算法应用在此类问题中的收敛速度慢。为此，许多研究人员对基本的蚁群算法做了改进工作。文献 [10] 采用随机选择和惯性保持相结合的方式搜寻节点，在获得不同路径的同时提高算法收敛速度。文献 [11] 引入奖惩因子，对每代的最优和最差路径进行奖励和惩罚，使算法跳出局部最优的能力增强。文献 [12] 构建了路径综合规划函数，以路径上的火焰因子和路障因子为指标，计算每条灭火机器人路径规划值，以此来评价最优灭火路径。这种引入多指标的方法，对解决系统实际运行时产生的问题有很大帮助。

目前，与多火源路径规划相关的文献研究相对不足。考虑到蚁群算法具有很强的鲁棒性和搜索能力，以及容易与多种启发式算法结合等优点，将蚁群算法融入TSP问题，并改进蚁群算法的启发式函数，在宏观上规划出灭火次序；将蚁群算法的转移概率公式进行改进，在微观上规划出灭火的具体路径。最后根据多个指标构建路径评价函数，通过仿真对改进后的蚁群算法进行验证。

2. 环境建模

对灭火机器人进行路径规划时需要根据其工作环境进行空间建模，常用的建模方法有：可视图法、拓扑法、栅格法等。由于栅格法具有建模方便、易于实现等特点，因此使用栅格法建模。

将一个平面空间G等分成20 × 20的栅格，每个栅格的边长为1，并将其按从左至右、从上到下的顺序编号，得到栅格集为 $AS=\left\{g_1,g_2,\cdots ,g_{400}\right\}$ 。以G的左上角为坐标零点，横向为x轴纵向为y轴建立直角坐标系。对于 $\forall g_i\in AS$ 在坐标系中对应一确定的坐标 $\left(x_i,y_i\right)$ ，记作 $g\left(x_i,y_i\right)$ ，映射关系为：

$\{\begin{array}{l}{x}_i=MOD\left(i,20\right)\\ y_i=INT\left(i,20\right)+1\end{array}$ (1)

式中，MOD表示i对20做取余运算，INT表示i对20做取整运算。设灭火机器人为质点，并将障碍物做膨化处理，根据公式(2)建立栅格地图。

$g\left(x_i,y_i\right)=\{\begin{array}{l}a,第x_i行第y_i列栅格上有火源\\ 1,第x_i行第y_i列栅格上有障碍物\\ 0,其他\end{array}$ (2)

式中，a为常数，表示该栅格上火源的火势大小。若栅格上有障碍物则此栅格为黑色，否则为白色，表示机器人可通过。空心圆所在的栅格为机器人的起点，实心圆则为火源，圆的半径长短表示火势的大小。栅格地图如图1所示。

Figure 1. Fire fighting robot path planning map model

图1. 灭火机器人路径规划地图模型

两栅格之间的距离为中心点的连线距离，机器人有8个移动方向：北、东北、东、东南、南、西南、西和西北。根据栅格地图可得机器人每步可移动的长度为1或 $\sqrt{2}$ ，机器人的运动情况如图2所示。

Figure 2. Fire fighting robot moving direction

图2. 灭火机器人移动方向

两栅格之间的弧表示机器人可沿该弧运动，记作 $\langle g_i,g_j\rangle$ ，其中 $g_i,g_j\in AS$ 且 $g_i,g_j=0$ 。E为弧的集合， $d_{ij}$ 为弧 $\langle g_i,g_j\rangle$ 上的权值。本文灭火机器人多火源路径规划即视为在E中找到一个子集 $S=\left\{\langle g_{start},g_a\rangle ,\cdots ,\langle g_b,g_{fire}\rangle \right\}$ ( $g_{start}$ 为起点栅格、 $g_{fire}$ 为火源栅格且 )，且 ${\displaystyle \underset{\langle g_i,g_j\rangle \in S}{\sum }{d}_{ij}}$ 值最搜索问题。

3. 改进的蚁群算法

3.1. 基本蚁群算法

基本蚁群算法在灭火机器人多火源路径规划的应用主要包括移动规则和信息素更新规则 [6]。根据移动规则，蚂蚁k由当前栅格i转移到下一栅格j时的转移概率 $p_{ij}^k\left(t\right)$ 如下：

$p_{ij}^k\left(t\right)=\{\begin{array}{l}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }\times {\left[{\eta }_j\left(t\right)\right]}^{\beta }}{{\displaystyle \underset{v\in allowe{d}_k}{\sum }{\left[{\tau }_{iv}\left(t\right)\right]}^{\alpha }\times {\left[{\eta }_j\left(t\right)\right]}^{\beta }}},j\in allowe{d}_k\\ 0,j\notin allowe{d}_k\end{array}$ (3)

其中 ${\eta }_j=\frac{1}{d_j}$ , ${\eta }_j\left(t\right)$ 为启发式函数， $d_j=\sqrt{{\left(g_y-j_y\right)}^2-{\left(g_x-j_x\right)}^2}$ , $d_j$ 表示栅格点j与终点g的几何距离。 $allowe{d}_k$ 表示蚂蚁k下一步转移可选择的栅格集； ${\tau }_{ij}\left(t\right)$ 表示由栅格i转移到栅格j路径上的信息素浓度；由栅格j转移到终点g的距离 $d_j$ 的倒数决定； $\alpha$ 为信息启发式因子，表示信息素的重要性； $\beta$ 为期望启发因子，表示路径上启发性信息的重要性。

信息素更新规则要求每一次迭代后，为了避免残留信息过多使得算法陷入局部最优，要对蚁群所经路径进行信息素更新，信息素的更新规则如下：

${\tau }_{ij}\left(t+1\right)=\rho {\tau }_{ij}\left(t\right)+{\displaystyle \underset{k=1}{\overset{m}{\sum }}\Delta }{\tau }_{ij}^k$ (4)

$\Delta {\tau }_{ij}^k=\{\begin{array}{l}\frac{Q}{L_k},第k只蚂蚁在时刻t和t+1之间经过\left(i,j\right)\\ 0,否则\end{array}$ (5)

式中 $\Delta {\tau }_{ij}^k$ 为蚂蚁k在路径 $\left(i,j\right)$ 中留下的信息量；m为蚂蚁数量； $\rho$ 为信息素挥发系数，取值为0到1；Q为常量，表示蚂蚁所留信息素强度； $L_k$ 为蚂蚁k在本次循环中走过的路径总长度。

3.2. 多火源灭火次序规划

在灭火机器人实际工作过程中，由于当前点到各个火源的距离不相等、火源的火势不同，因此在规划每条线路前必须先合理的规划出灭火顺序。此问题为从出发点开始找到一条路径能够遍历所有的点，且这条路径所有边的权值之和为最优值，因此可以视作TSP问题，即旅行商问题。

在蚁群算法中，启发式函数 ${\eta }_{ij}$ 的值表示蚂蚁k由栅格i转移到栅格j的期望程度，对于多火源次序规划问题，转向下一点的期望程度应考虑路径的长度、火势的大小和火源的危险系数，因此构建综合权值函数对启发式函数进行改进。

$R_{ij}\left(d,b\right)=d_{ij}\times b_j$ (6)

$b_j=\frac{1}{s_j\times w_j\times a_j}$ (7)

${\eta }_{ij}=\frac{1}{R_{ij}\left(d_{ij},b_j\right)}$ (8)

其中 $R_{ij}\left(d,b\right)$ 为节点间路径综合权值，权值越小，则路径长度越短、火焰因子越小，蚂蚁k由栅格i转移到栅格j的期望程度就越高；d为节点间的几何距离；b为火焰因子，由火焰面积s、火焰强度w、危险系数a乘积的倒数决定。

改进启发式函数后，将蚁群算法应用在TSP问题中解决多火源灭火次序规划问题的算法关键步骤如下：

1) 以起点和火源所在的栅格中心为点，构建有向连通图；

2) 用综合权值函数 $R_{ij}\left(d,b\right)$ 计算各点之间边的权值；

3) 每次迭代前将所有蚂蚁放置在起点；

4) 蚂蚁根据转移规则，即公式(3)和公式(10)选择下一节点；

5) 蚂蚁每前进一步更新相应的禁忌表；

6) 所有蚂蚁找到终点后，当前迭代结束，并更新信息素；

7) 迭代次数加1，若未达到设定的迭代次数，转向步骤(3)；

8) 设定的迭代次数完成后，得出最优灭火次序。

3.3. 路径搜索

宏观上规划出最佳灭火次序之后，接下来在栅格地图上规划依次到达每个火源的具体灭火路径。由于基本的蚁群算法存在易陷入局部最优解、收敛速度慢等不足，随着问题规模的增大，算法的缺陷会对最优解产生很大影响，因此针对这些问题对蚁群算法进行改进。

在基本的蚁群算法中，蚂蚁采用随机概率选择节点。虽然增强了算法的全局搜索能力，但降低了收敛速度。为此对转移概率公式 [10] 进行如下改进：

$\{\begin{array}{l}{p}_{ij}^k\left(t\right)=\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }\times {\left[{\eta }_j\left(t\right)\right]}^{\beta }}{{\displaystyle \underset{v\in allowe{d}_k}{\sum }{\left[{\tau }_{iv}\left(t\right)\right]}^{\alpha }\times {\left[{\eta }_j\left(t\right)\right]}^{\beta }}},r>r_0\\ j=\arg \max \left\{{\left[{\tau }_{iv}\left(t\right)\right]}^{\alpha }\times {\left[{\eta }_j\left(t\right)\right]}^{\beta }\right\},r\le r_0\end{array}$ (9)

上式中 $r_0$ 为取值0.6~0.8的常数，表示变异阈值；r为0~1的随机值。改进后既可以保证算法以较小的概率按随机比例选择节点，增强跳出局部最优解的能力，又能使蚁群以较大的概率选择信息素浓度与期望函数乘积最大的节点，确保蚂蚁选择的方向性，提升算法收敛性能。

3.4. 多指标路径评价函数

宏观上规划出最佳灭火次序、微观上规划出灭火的具体路径后，需要按一个标准评价整体路径。由于灭火机器人在消防过程中需要拖着沉重的水带，转向会浪费大量时间，因此在评价路径时，不仅要考虑路径的长度，还要考虑转弯所消耗的时间。为此建立如下多指标路径评价函数：

$V\left(d,r\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}{d}_i\times r_i}$

$r_i=\{\begin{array}{l}1,第i步不转向\\ 1.2,第i步转向\end{array}$ (10)

式中 $V\left(d,r\right)$ 是路径评价函数，计算得出的值越小，则这条路径的质量越好； $d_i$ 表示第i步的机器人行进的距离； $r_i$ 是转向因子；n为机灭火器人行进的总步数。

3.5. 改进的蚁群算法流程图

首先进行本问题的环境建模，确定灭火机器人的起点和各个火源的位置。接下来将改进后的启发式函数应用进TSP问题中，求解出多个火源的灭火次序。然后对蚁群算法的转移概率公式进行改进，规划出到达各个火源的具体路径。最后分别将基本蚁群算法和改进的蚁群算法得出的路径带入到构建的路径评价函数中，根据函数的值和路径规划图得出结论。改进的蚁群算法流程图如图3所示。

Figure 3. Flow chart: improved ant colony algorithm

图3. 改进蚁群算法流程图

4. 仿真实验

为验证改进的蚁群算法在灭火机器人路径规划中的有效性，使用MATLAB进行仿真实验。按照公式(1)和公式(2)进行环境建模，蚁群算法中所取的相关参数为：蚂蚁数目 $m=50$ 、迭代次数 $K=100$ 、 $\rho =0.3$ 、 $\alpha =1$ 、 $\beta =7$ 。各火源的火势参数如表1。

Table 1. Fire parameters of each fire source

表1. 标准试验系统结果数据

基本蚁群算法中的启发式函数与路径长度相关，针对多火源的灭火问题，改进的蚁群算法还考虑了火源的火势情况，根据3.2部分设计的算法得出的灭火次序如图4所示。

(a) 基本算法解得的灭火次序 (b) 改进算法解得的灭火次序

Figure 4. Comparison of fire extinguishing sequence solved by two algorithms

图4. 两种算法解得的灭火次序对比

将表1的数据代入公式(5)和公式(8)中计算得知，采用基本算法中最短路径优先规划策略得出的几何路径长度为31、综合权值为24.45，而采用改进算法中最佳综合权值优先规划策略得出的几何路径长度为34.5，综合权值为21.47。改进算法所解得的灭火次序在几何路径长度上稍差于基本算法，但综合考虑多种因素，改进算法优化性能相较基本算法得到提升。

为了更直观的对比以上两种灭火次序，计算出灭火次序中每条边的综合权值，并按序连接得到最短路径优先规划 [12] 和综合权值优先规划两种灭火次序的综合权值对比图。如图5，可以看出，两种灭火次序都依次经过4条边，基本算法规划的次序中，边的权值波动较大，而改进算法规划的明显小于前者。因此，在综合考虑路径长度和火势大小的条件下，利用改进算法得到的灭火次序更节省灭火时间，减少灭火损失。

Figure 5. Curve: comprehensive weights of two fire extinguishing sequences

图5. 两种灭火次序的综合权值对比曲线

在求得最佳灭火次序后，为了进一步验证改进蚁群算法在规划到达各火源具体路径的优越性，用蚁群算法对以上两种灭火次序进行对比实验，得出的两种路径如图6所示，基本路径的转弯次数为24次，而改进路径的转弯次数为11次，可以看出改进路径较于前者更趋于平滑。算法迭代情况对比如图7所示，基本算法的收敛次数为51次，而改进算法的收敛次数为39次，可见改进算法在收敛性上要优于前者。

(a) 基本算法解得的灭火路径 (b) 改进算法解得的灭火路径

Figure 6. Comparison of fire extinguishing paths solved by two algorithms

图6. 两算法求解出的灭火路径对比

(a) 基本算法的迭代曲线 (b) 改进算法的迭代曲线

Figure 7. Comparison of iteration curves of two algorithms

图7. 两算法的迭代曲线对比

将图6得出的路径代入公式(12)可得出基本灭火路径的综合评价函数R_b和改进灭火路径的综合评价函数R_c。

$R_b=OD\times \frac{1}{s_D\times w_D\times a_D}+DB\times \frac{1}{s_B\times w_B\times a_B}+BC\times \frac{1}{s_C\times w_C\times a_C}+CA\times \frac{1}{s_A\times w_A\times a_A}$

$R_{\text{c}}=OB\times \frac{1}{s_B\times w_B\times a_B}+BD\times \frac{1}{s_D\times w_D\times a_D}+DC\times \frac{1}{s_C\times w_C\times a_C}+CA\times \frac{1}{s_A\times w_A\times a_A}$

将数据代入上式中，解得基本路径的综合指标为54.02、改进路径的综合指标为49.71；由图6可计算出基本路径的长度为41.04、改进路径的综合指标为45.38，可知改进算法牺牲了一点距离获得质量更好的路径。根据求解的结果，将各类求解指标列入表2中对比分析。

Table 2. Comparison of indicators solved by two algorithms

表2. 两种算法解得的各指标对比

结果表明改进算法获得了质量更好的路径的同时，在降低转弯次数和运算时间方面有显著提高。从而证明了此算法应用在灭火机器人多火源路径规划问上种的有效性和可行性。

5. 结束语

研究灭火机器人多火源路径规划问题，分析基本蚁群算法应用在此问题中的优缺点，并提出了一种改进的方案。首先，借鉴蚁群算法在TSP问题中的求解思路，并引入综合权值优先规划策略进行全局规划，得出最佳灭火次序。其次，在路径搜索方面引入变异阈值，改进转移概率函数，增强算法跳出局部最优解的能力和提升算法的收敛性能。最后，引入路径评价函数，将综合指标作为路径优劣评价标准。实验结果表明，改进算法在多火源路径规划问题中的全局搜索能力有所提升，收敛速度大大改善，路径质量优于基本算法，对于求解所研究的灭火机器人多火源路径规划问题具有很强的有效性和可行性。

基金项目

本文受山东省自然科学基金项目(ZR2017BF043)和山东省大学生创新创业训练计划项目(S201910429064，S201910429098)资助。

NOTES

^*通讯作者。