动态环境下机器人路径的新型启发蚁群规划

贺道坤，周 南

（1.南京信息职业技术学院智能制造学院，江苏南京 210023；2.湖南大学金融与统计学院，湖南长沙 410082;3.长沙商贸旅游职业技术学院湘商学院，湖南长沙 410116）

1 引言

智能机器人是人类文明进步的标志性产物，机器人可以代替人类完成服务型、重复型、劳动力密集型、危险型等工作，从而实现节约人工成本、保护人类安全、提高工作效率等目的[1]。对于移动机器人，路径规划是机器人完成其余工作的基础，路径规划的质量决定了完成其余任务的效率甚至决定了任务成败[2]。因此，研究机器人路径规划问题具有重要的现实意义。

机器人路径规划主要关注可行性和最优性两个方面，其中可行性是指安全无碰、路径平滑可跟踪等方面，最优性是指路径满足最短、最平滑等指标，其中最优性是以可行性为基础的。根据环境中障碍物的运动情况，路径规划分为静态规划和动态规划；根据对环境信息的掌握程度，路径规划分为全局规划和局部规划[3]。

从路径规划方法的角度讲，可以分为传统方法和智能方法，传统方法包括自由空间法、拓扑图法、快速搜索随机树[4]、A*算法、D*[5]算法、人工势场法等；智能方法包括人工鱼群算法、蚁群算法、粒子群算法、遗传算法等[6]。

文献[7]针对RRT算法路径冗余问题，首先提出了Quick−RRT算法缩短了RRT初始路径，并进一步提出了双树Quick−RRT算法，缩短了路径程度并提高了收敛速度。文献[8]将粒子群算法融入到狼群算法中，提出了改进狼群算法并应用于路径规划，在一定程度上缩短了路径长度。

文献[9]将势场力构造为一种新的启发信息引入到蚁群算法中，而后使用三次B样条曲线对路径进行平滑，与传统蚁群算法比，改进算法规划的路径更短，拐点数量更少。

上述路径规划算法中，智能规划算法因其普遍适用性好、路径质量高等优点而成为主流方法。但是，智能规划算法得到的路径质量取决于算法优化性能，因此智能规划算法研究的本质是对算法优化性能的提升。

这里研究了动态环境下机器人的路径规划问题，首先提出基于新型启发蚁群算法的全局路径规划方法，机器人沿最优路径时进行动态障碍物探测，当检测到障碍物时根据碰撞类型实施正面避撞和侧面避撞。上述方案既保证了机器人沿最优路径行驶，也保证了机器人行驶安全。

2 路径规划问题描述与建模

2.1 问题描述与环境模型

机器人路径规划描述为，规划出一条由起点到目标点的路径，该路径在满足无碰、可跟踪等约束条件下，需实现路径最短、最平滑等最优化指标。路径规划的前提是环境建模，这里建立二维环境的栅格模型。

首先依据机器人高度和工作环境中的障碍物高度分布，将三维环境在二维中进行投影，从而将工作环境简化为二维。

使用方形栅格对二维环境进行分割，得到二维环境的栅格模型。

将机器人的最大半径记为rrob，所有障碍物按原形状向外扩展尺寸rrob，则后续处理中可以将机器人视为质点。

在栅格模型中，当栅格中包含障碍物时，即使该障碍物未占满栅格，也将该栅格视为障碍物栅格。

障碍物分布，如图1（a）所示。其栅格模型，如图1（b）所示。

图1 栅格环境模型Fig.1 Grid Model of Environment

将图1（b）中的障碍物栅格属性赋值为1，可自由行驶栅格的属性赋值为0，则栅格模型可以使用0−1矩阵表示为：

之所以将栅格环境模型转化为0−1矩阵形式，是因为图1（b）所示形式机器人无法辨识和识别，而机器人对矩阵形式是可以识别的。

2.2 路径评价指标

这里进行路径规划具有两个优化目标，第一个目标为规划路径最短，描述为：

式中：f1—路径长度；S—起点；G—目标点；dij—栅格ij间距离。

第二个目标为规划路径平滑性最好，使用拐点数量路径平滑性进行评价。

3 全局路径规划

本节首先对传统蚁群算法进行简介，并针对蚁群算法的性能缺陷进行改进，给出了初始信息素梯度分布策略，并引入了新型启发信息，提出了新型启发蚁群算法。

3.1 传统蚁群算法与问题分析

在栅格环境中，机器人可选栅格分为四叉树和八叉树两种情况，四叉树是指可选栅格为前后左右四个栅格，八叉树指可选栅格为前、后、左、右、左前、左后、右前、右后等八个栅格，这里选择八叉树模式。

将蚂蚁m迭代t次时所在栅格记为i，则其对邻域内自由栅格j的选择概率(t)为［10］：

式中：τij(t)—栅格ij间的信息素浓度；α—信息素因子；ηij(t)—栅格ij间的启发信息；β—启发因子；allowedi—栅格i邻域可选栅格集合。

蚁群算法每完成一次迭代，则进行路径上的信息素浓度更新，为：

式中：ρ—挥发系数；△τij(t)—路径ij上遗留的信息素浓度；△(t)−蚂蚁k在路径ij上遗留的信息素浓度；M—蚂蚁数量；Lk—蚂蚁k的路径长度。

传统蚁群算法应用于栅格环境下的路径规划存在以下问题：

（1）初始信息素为均匀分布，使得蚁群算法在算法初期类似于随机搜索，算法搜索效率低、收敛速度慢；

针对上述问题，这里通过信息素的梯度分布初始化方法，解决了算法初期搜索效率低的问题；通过引入新的启发信息，解决了路径多目标优化问题。

3.2 信息素梯度分布初始化

根据数学知识，两点之间线段最短，因此起始栅格S与目标栅格G连线周围的栅格是重点搜索区域，其余栅格为非重点搜索区域，命名为一般区域，如图2所示。设置一个距离阈值dm，当栅格i与线段SG距离h≤dm，则栅格i为重点搜索区域；当栅格i与线段SG距离h>dm，则栅格i为一般区域。

图2 重点搜索区域Fig.2 Key Searching Area

一般区域不是蚂蚁的搜索重点，其信息素使用传统的均匀初始化方法，直接将栅格信息素浓度初始化为τ0。重点区域是蚂蚁的搜索重点，使用梯度初始化方法，其示意图，如图3所示。

图3 梯度初始化方法Fig.3 Gradient Initialization Method

重点搜索区域和一般区域的信息素浓度初始化方法为：

式中：τj—栅格j的初始信息素浓度；λ—信息素增量系数；dSj—起点栅格S与栅格j的距离。

分析式（4）可知，在重点搜索区域内，栅格j与目标栅格、起点栅格的距离和越小，则栅格j的信息素浓度越大。因此在重点搜索区域内，信息素浓度以线段SG向外呈现梯度递减分布。

3.3 平滑度启发信息与算法流程

对路径的平滑度进行优化，必须构造平滑度启发信息。路径平滑度取决于转角大小，机器人前进方向转角越大说明路径平滑性越差，转角越小说明平滑性越好。

在栅格环境下，机器人路径转角存在0°、45°、90°、135°这4种情况，如图4所示。

图4中A方向机器人转角为0°，B方向机器人转角为45°，C方向机器人转角为90°，D方向机器人转角为135°。依据前进方向的机器人转角构造新的启发信息为：

图4 前进方向Fig.4 Forward Direction

式中：μij(t)—转角启发信息；θij—栅格i与栅格j间夹角。

将新的启发信息引入到蚂蚁对栅格的选择概率中，为：

式中：γ—路径平滑性因子。

在此需要说明的是，当遇到U性障碍物时，调用文献[11]中的陷阱深度标记策略。结合信息素的梯度初始化方法和新启发信息原理，制定新型启发蚁群算法流程如下。

（1）初始化算法参数，包括蚂蚁数量M、信息素因子α、启发因子β、距离阈值dm；

（2）将所有蚂蚁放置在起始栅格S，并按照式（4）进行信息素浓度初始化；

（3）蚂蚁按照式（6）计算的概率选择下一栅格；

（4）当所有蚂蚁到达目标点，算法完成一次迭代，此时迭代次数＋1；

（5）判断迭代次数是否达到最大值，若否则转至（3）；若是则输出最优路径，算法结束。

4 动态避障策略整体规划方案

4.1 动态环境下避障策略

本节中的动态障碍物场景设置为运动方向固定、运动节奏与机器人一致的障碍物，所谓运动节奏一致是指障碍物速度与机器人速度一致。在这种场景设置下，机器人与障碍物的碰撞包括正面碰撞和侧面碰撞两种情况。

（1）正面碰撞与避撞策略。正面碰撞是指机器人与障碍物相向而行至同一栅格。

为了避免正面碰撞，当机器人探索到正前方障碍物时，调用正面避撞策略。正面避撞策略为：以全局最优路径上某一栅格为目标点，调用新型启发蚁群算法规划出一条由当前栅格到避撞栅格的局部路径。

（2）侧面碰撞与避撞策略。侧面碰撞是指机器人由45°、90°、135°等方向与障碍物发生碰撞。当机器人探测到（45～135）°方向内的障碍物时，调用侧面避撞策略。侧面避撞策略为：机器人在原栅格等待一个周期，待障碍物驶出碰撞栅格后，机器人继续沿最优路径行驶。

4.2 机器人行驶与避撞方案

综合新型启发蚁群算法的全局路径规划方法与动态避撞策略，机器人在动态环境中的行驶方案为：首先使用新型启发蚁群算法规划出一条全局最优路径，而后机器人沿最优路径行驶；当机器人出现正面碰撞问题时则调用正面避撞策略，当机器人出现侧面碰撞问题时则调用侧面避撞策略，如此循环往往复直至到达目标点。整体方案，如图5所示。

图5 机器人行驶与避撞方案Fig.5 Robot Travel and Anti−Collision Project

5 仿真验证与分析

5.1 全局规划路径验证

首先在20×20规模栅格环境中进行路径规划，起点栅格S坐标为（0.5，19.5），目标栅格为（19.5，0.5）。为了进行比较，分别使用传统蚁群算法、文献[11]多种群蚁群算法、这里新型启发蚁群算法进行路径规划，为了验证算法性能稳定性，每个算法独立运行10次。三种算法得到的最优路径，如图6所示。

图6 各算法规划的路径Fig.6 Path Planned by Each Algorithm

观察图6中3种蚁群算法规划的路径可以直观看出，这里新型启发蚁群算法规划的路径最短，路径平滑性也最好；文献[11]的路径长度和拐点数量次之，传统蚁群算法规划路径最长，且观点数量最多。为了进一步比较算法性能，统计路径长度、拐点数量、收敛次数等参数的最优值及均值，结果，如表1所示。

表1 各算法规划路径参数Tab.1 Path Parameters of Different Algorithm

结合表1和图6可以看出：（1）从最优路径的角度看，传统算法最优路径长度为31.21，拐点数量为14，收敛迭代次数为70，在3 种算法中长度最大、拐点数量最多、迭代次数最多；其次为文献[11]规划路径；这里算法的路径长度最小、拐点数量最少，迭代次数最少；（2）从平均水平看，这里算法规划的路径长度均值最小，拐点均值最少，迭代次数也最少。

这是因为这里新型蚁群算法信息素初始化对重点搜索区域使用了梯度初始化方法，有效提高了算法初期的搜索效率，所以收敛次数远少于另外两种算法。另外，这里算法中引入了路径平滑度这种新型启发信息，引导蚂蚁尽量沿直线行走，因此路径拐点数量明显减少，同时减小了路径长度。因此，这里新型启发蚁群算法在全局路径规划中具有优越性。

5.2 动态避撞方案验证

在图6所示的20×20规模栅格环境中设置2个动态障碍物，障碍物1由栅格H（2.5，16.5）出发，在栅格H与栅格P（8.5，16.5）之间做直线往返运动，障碍物1从第3个周期开始运动。

障碍物2由栅格Q（17.5，3.5）出发，沿X轴135°方向做直线运动，从第10个周期开始运动。

机器人的碰撞检测位置与避撞结果，如图7所示。

在图7（a）中，机器人运动4步后，探测到动态障碍物M1，根据M1所在栅格及运动方向，判断两者发生侧面碰撞，且碰撞栅格为P1位置，此时机器人调动侧面避撞策略，如图7（b）所示，机器人在图中所示位置等待1个周期后继续前进。

图7 避撞策略验证Fig.7 Clarification of Anti−Collision Strategy

在图7（c）中，机器人运动至所示位置时，探测到动态障碍物M2，根据M2所在栅格及运动方向，判断两者会发生正面碰撞，且碰撞栅格为P2位置，此时机器人调用正面避撞策略。

以图7（d）中R栅格为临时目标点进行局部路径规划，局部避撞路径如图7（d）所示，机器人按照局部规划路径行驶实现避撞。

由以上避撞过程和分析可知，这里制定的正面避撞和侧面避撞策略在设定动态场景中可以实现有效避撞，保证了机器人的行驶安全。

6 结论

这里研究了机器人在动态环境下的路径规划问题，首先使用新型启发蚁群算法进行全局路径规划，而后制定了机器人行驶的避撞策略。

经验证得出以下结论：

（1）新型启发蚁群算法规划的路径长度短、收敛速度快、平滑性好；

（2）这里制定的正面避撞策略和侧面避撞策略在设定动态场景下可以实现有效避撞，保证机器人安全行驶。