基于改进蚁群算法的机器人路径规划研究

摘  要：在将蚁群算法应用于机器人路径规划时，针对如何调节收敛速度与种群多样性之间矛盾的问题，提出了改进的蚁群算法。在状态转移规则中，引入防死锁因子，改进启发函数，提升收敛效率;在信息素更新过程中，提出一种全局信息素分步更新策略;在整体结构上，提出了多层并行蚁群模型，极大缩减了整体运行时间。改进的蚁群算法可保持种群多样性与收敛速度之间的一种平衡。

关键词：机器人;蚁群算法;路径规划;种群多样性;收敛速度

中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2021）12-0018-05

Abstract： When applying ant colony algorithm to robot path planning， an improved ant colony algorithm is proposed to solve the problem of adjusting the contradiction between convergence speed and population diversity. In the state transition rule， the anti deadlock factor is introduced to improve the heuristic function and improve the convergence efficiency; in the process of pheromone updating， a global pheromone step-by-step updating strategy is proposed; in the overall structure， a multi-layer parallel ant colony model is proposed， which greatly reduces the overall running time. The improved ant colony algorithm can maintain a balance between population diversity and convergence speed.

Keywords： robot; ant colony algorithm; path planning; population diversity; convergence speed

0  引  言

随着新兴技术产业的快速发展，移动机器人路径规划研究已成为移动机器人技术研究的重中之重。在移动机器人自动导航过程中，有效的路径规划可以帮助移动机器人避开工作场所中的障碍，缩短途经路径的长度。蚁群算法是一种启发算法，在解决移动机器人路径规划问题上有着良好的鲁棒性与并行性，目前有很多学者将其广泛应用于解决路径规划的问题中。王晓燕等[1]提出了一种根据栅格位置不均衡性分配初始信息素的方法。许凯波等[2]提出了一种基于信息素二次更新策略的双蚁群算法，提升了寻优能力，但却导致运行时间的增加。王秀繁等[3]将粒子群算法与蚁群算法相融合，提出了一种解决物流配送路径规划问题的算法。罗艳媚等[4]将人工势场法与蚁群算法相融合，提出了一种新算法。其他算法与蚁群算法相融合的方法虽然提高了路径搜索效率，但是运行时间较长、算法结构较复杂。大多数学者在平衡蚁群算法的多样性与收敛速度、优化算法架构等方面的研究较少。因此，本文作者设计了一种改进的多层运行蚁群算法，從状态转移规则、信息素更新策略、蚁群算法整体结构等多个方面来平衡蚁群算法的收敛速度与种群多样性两者之间的矛盾。

1  栅格法环境建模

在对移动机器人路径进行规划时，需要先完成对移动机器人行驶环境的建立。本文采用栅格法中的直角坐标法对移动机器人所在的工作场所构建二维模型，将移动机器人可选择的栅格颜色设置为白色，将移动机器人不可经过、不可选择的栅格颜色设置为黑色，称为障碍栅格，从而得到与移动机器人行驶环境相似的栅格地图，如图1所示。

2  改进的蚁群算法在机器人路径规划中的应用

蚁群算法是由Dorigo、Maniezzo等人提出的，主要用于寻求最优路径，基本思路是：相关参数的初始化，取得可行路径、构建可行路径空间，更新信息素，是否满足终止条件，得到最优路径。

2.1  初始化

在蚁群算法中，相关参数的初始化设定为：

M为种群规模，即种群中蚂蚁数量，选取时需要考虑算法的收敛速度与全局搜索能力，取值为10～50。

G为最大迭代次数，即蚂蚁遍历次数，一般为算法的终止条件，取值为100～500。

Q为蚁群循环一次后释放的信息素总量，受算法正反馈机制的影响，取值为1～100。

ρ为信息素的挥发系数，其取值对算法的搜索力与收敛能力都有影响，取值为0～1。

α为信息启发式因子，其取值影响蚂蚁对信息素的反应能力，取值越大，蚂蚁对信息素的反应能力越强，取值为0～2。

β为期望启发式因子，其取值影响蚂蚁对起点、终点、路径长度的反应能力，取值为0～20。

2.2  改进的状态转移规则

在基本蚁群算法中，由于蚂蚁在搜索路径过程中只能前进不能后退，当遇到障碍物或者是之前已经走过的节点时，会陷入死锁状态，发生停滞。为此，引入防死锁因子Sj：

其中，Sj为节点j的防死锁因子，Gj为节点j相邻的栅格总数量，Bj为与节点j相邻的障碍栅格数量，Lj为蚂蚁之前走过的且与节点j相邻的栅格数量。防死锁因子的引入，可以让蚂蚁在搜索过程中有效避开障碍物或是之前已经走过的节点，降低死锁概率。

与此同时，基本算法的启发函数仅涉及了当前节点与下一节点之间的距离，并没有考虑与起点、终点的距离，这样也容易导致蚂蚁在选择下一节点时陷入死锁状态，被迫停止搜索，为此，改进启发函数ηij：

其中，daj表示t时刻，起点a与下一节点j之间的距离， daj= ，（xi，yi）为当前节点i的位置坐标，（xa，ya）为起点a的位置坐标;dij表示t时刻，当前节点i与下一节点j之间的距离;djz表示t时刻，下一节点j与终点z之间的距离;改进的启发函数不仅涉及了当前节点与下一节点之间的距离，还涉及了与起点、终点的距离，使得蚂蚁在选择下一节点时远离起点，向终点靠近。

引入防死锁因子，改进启发函数后，得到新的状态转移概率公式：

其中，τij（t）表示t时刻，两节点（i，j）之间的信息素浓度;ηij（t）表示t时刻，节点i选择节点j的启发函数;Sj为防死锁因子，allowk表示节点i可选择的下一节点的集合;改进的状态转移规则降低了蚂蚁选择障碍物栅格节点与之前已经过的节点的概率，减少了探索时间，提高了整体的收敛效率，但并没有减弱种群的多样性，使得收敛效率与种群多样性之间保持较好的平衡关系。

2.3  信息素更新

在基本的蚁群算法中，信息素的更新主要是对从起点到终点的整条路径进行信息素浓度的增加，容易陷入局部最优[5]。

本文提出了一种全局信息素分步更新策略。将最大迭代次数设为N，在前面的N/2次迭代过程中，任何蚂蚁都不释放信息素，充分保证蚂蚁对最优路径的探索，保持了种群多样性;在之后的N/2次迭代过程中，每次迭代皆对蚂蚁构建的所有路径进行排序，并按照路径的优劣实施不同程度的信息素奖励政策，并记录每条路径出现次数，当该路径出现次数达到一定数值后，该条路径不再更新，从而避免出现局部最优现象。具体公式为：

其中，n为当前迭代次数，N为最大迭代次数;ρ为蚂蚁遗留在路径上信息素的蒸发系数;∆τij表示蚂蚁走完整条路径后信息素的变化量，主要是增加量;Lk表示第k只蚂蚁所走的整条路径的长度。改进的全局信息素分步更新策略，在迭代前期使所有蚂蚁尽可能地搜索所有路径，保证了蚂蚁的探索力与种群的多样性，在迭代后期，采用全局信息素更新策略，提高了收敛效率，并且引入了当前最优路径次数记录动作，防止出现局部最优。

2.4  单层蚁群算法的终止条件

单层蚁群算法的终止主要依靠迭代次数是否已为最大迭代次数，若蚁群迭代次数未达到最大迭代次数，则进入下次搜索;反之，结束搜索，输出本层的最优路线。

2.5  算法结构

建立多层并行蚁群模型。在m层并行蚁群模型中，每一层都是一个完整的蚁群算法运算，将每层蚁群算法得到的最优路径进行比较，从中选出最优路径，该模型将多个蚁群算法依次运算的时间总和缩短为单个蚁群算法运行时间，极大缩减了得到最优解的整体运行时间，提高了整体运行效率。改进的蚁群算法如图2所示。

3  仿真及结果分析

为了比较改进的蚁群算法与基本蚁群算法，在两种不同复杂程度的栅格环境，即分别在10×10简单栅格地图环境、20×20复杂栅格地图环境下从收敛迭代次数、行走路线、最优路径长度等角度对两种算法进行对比分析，如图3、表2所示。使用MATLAB R2016a仿真平台，相关参数设置如表1所示。

通过图3与表2的对比可知，在10×10简单栅格地图环境下，本文改进的蚁群算法在寻求最优路径、迭代次数等方面得出的结果皆优于基本蚁群算法。

20×20栅格地图环境不仅增加了栅格规模，还增加了障碍物数量，提高了障碍物分布密度，地图环境复杂，如图4、表3所示。

通过图4与表3的对比可知，在20×20复杂栅格地图环境下，改进蚁群算法寻求的最优路径优于基本蚁群算法寻求的最优路径。

4  结  论

由于基本的蚁群算法应用于移动机器人路径规划时，易出现搜索死锁、收敛速度与种群多样性之间的矛盾，本文从状态转移规则、信息素更新策略、算法整体运行模型多个角度进行了研究，提出了一种多层并行运行的蚁群算法。对两种算法进行仿真比较分析，結果表明改进的蚁群算法可有效地防死锁，并且极好地建立了种群多样性与收敛速度之间的一种平衡，在迭代次数、最优路径长度等方面都有较大的提升。

参考文献：

[1] 王晓燕，杨乐，张宇，等.基于改进势场蚁群算法的机器人路径规划 [J].控制与决策，2018，33（10）：1775-1781.

[2] 许凯波，鲁海燕，黄洋，等.基于双层蚁群算法和动态环境的机器人路径规划方法 [J].电子学报，2019，47（10）：2166-2176.

[3] 王秀繁，梁峰.基于PSO-ACO融合算法的物流车辆路径优化与控制研究（英文） [J].机床与液压，2020，48（12）：155-160.

[4] 罗艳媚.一种求解多目标优化问题的改进蚁群算法 [J].电脑知识与技术，2020，16（32）：226-229.

[5] 李毅，胡建成.改进的蚁群优化算法在机器人路径规划中的应用 [J].内江师范学院学报，2019，34（12）：40-44.

作者简介：张丹丹（1990—），女，汉族，山东德州人，助教，硕士，研究方向：物流信息技术、智能优化算法。