全向移动机器人的使用使人们的日常生活逐渐受到影响, 在全向移动机器人领域中, 全遍历路径规划一直以来都是一个热点研究话题, 路径规划的任务是在已知地图信息环境或未知地图信息环境中, 依据时间和距离最短、能耗最低等指标, 规划一条全向移动机器人从起点到终点的安全无碰撞路径^[1].

目前, 国内外很多学者都在全向移动机器人全遍历路径规划中做了大量研究, 在国外的研究中, 将全向移动机器人应用到制造行业的研究进展比较显著, 尤其是美国和日本两个国家最先将移动机器人引入到国际范围内, 美国制定了地面天人作战平台的战略计划, 从上世纪80年代初, 就掀起了研究全向移动机器人的序幕. 日本除了研究全向移动机器人以外, 还将中间件的研究作为未来发展的重点^[2]; 国内的全向移动机器人研究也越来越多, 国内早就将全向移动机器人技术的开发研究作为机器人研究的重要发展领域^[3]. 传统蚁群算法运用赋权矩阵, 将机器人途经的最短路径、活动范围中的障碍物等要素形成一种连通关系, 并采用蚁群算法对各要素的空间距离进行优化, 从而得到路径规划结果. 虽然传统蚁群算法考虑了障碍物等对路径距离产生影响的问题, 但是该算法收敛速度慢, 容易陷入局部最优的缺点. 杨洋等^[4]为了解决移动机器人在路径规划中遇到的问题, 提出面向未知地图的六足机器人路径规划算法. 该算法利用测距组与模糊规则对障碍物的形状进行分类, 并建立环境地图, 引入修正的斥力函数, 采用人工势场法进行局部路径规划. 仿真实验结果显示, 该路径规划方法具有较高的可行性, 但是该方法没有充分考虑全遍历环境的影响, 导致规划得到的路径较长. 王毅等^[5]根据双圆弧理论提出基于圆弧-直线-圆弧理论的移动机器人路径规划方法, 在实验室环境下, 采用履带式移动平台对该方法进行了实验验证. 实验结果表明, 该方法在路径规划中横向误差均值和纵向误差均值均较低, 表明该方法在应用时具有一定的有效性, 但是不能有效获取最优路径.

基于以上背景, 对蚁群算法进行改进, 并将其应用到全向移动机器人全遍历路径规划中, 从而提高全向移动机器人全遍历路径的规划性能.

1 全向移动机器人全遍历路径规划方法设计 1.1 建立全向移动机器人全遍历环境模型

采用拓扑建模方法^[6]建立全向移动机器人全遍历环境模型, 将全遍历环境表示为一张具有拓扑意义的图, 主要分为可视图建模法和Voronoi图建模法. 可视图建模法^[7]是以全遍历环境中的障碍物模型为基础, 将每一个障碍物都采用多边形来表示, 在可视图中找到全向移动机器人的起点和终点, 并与障碍物之间用直线连接, 在连接过程中确保所有连线都不可以穿过障碍物, 将最后得到的图称为可视图. 如图1(a)所示. Voronoi图建模法^[8]是先找出障碍物的顶点位置和边界, 将其余起点和终点相连, 得到Voronoi图, 如图1(b)所示.

在图1的基础上, 根据全向移动机器人的全遍历空间大小, 将全向移动机器人的全遍历区域划分为等间隔的栅格, 栅格由全向移动机器人的尺寸来决定. 将全向移动机器人在栅格环境中移动点作为建模的质点, 灰色表示障碍物, 白色表示自由区域.

在新的环境建模坐标系中, 以 $S\left( {{x_{{\rm{start }}}},{y_{{\rm{start }}}}} \right)$ 为原点, 连接全向移动机器人的起点和终点坐标, 顺时针旋转 $\phi $ 度之后将其作为X轴, 将移动机器人在原坐标系下的位置坐标 $\left( {X,Y} \right)$ 转换为 $\left( {X',Y'} \right)$ , 变换式如下:

$\left[ {\begin{array}{*{20}{c}} {{X^\prime }} \\ {{Y^\prime }} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\cos \theta }&{ - \sin \theta } \\ {\sin \theta }&{{\kern 1pt} {\kern 1pt} - \cos \theta } \end{array}} \right] \times \left[ {\begin{array}{*{20}{l}} X \\ Y \end{array}} \right] + \left[ {\begin{array}{*{20}{c}} {{x_{{\rm{start }}}}} \\ {{y_{{\rm{start }}}}} \end{array}} \right]$

(1)

$\phi = \arctan \frac{a}{b}$

(2)

其中, ${x_{{\rm{start }}}}$ 和 ${y_{{\rm{start }}}}$ 表示原点坐标; a表示偏移角度; b表示目标角度.

在拓扑建模示意图的基础上, 依据移动机器人在原坐标系下的位置信息, 利用角度转换建立了新的环境模型, 接下来通过改进蚁群算法为全向移动机器人全遍历路径进行规划, 消除全遍历环境的影响.

1.2 改进蚁群算法

传统蚁群算法在规划全向移动机器人全遍历路径时初始信息素是相同的, 在启发信息上蚁群在建立第一条规划路径时, 往往比较偏向近目标点的位置^[9], 针对上述问题, 为了避免蚁群算法陷入局部最优, 对传统蚁群算法进行改进, 减小启发信息对蚁群在搜索过程中的影响, 因此, 将递减系数 $\xi $ 引入到启发函数中^[10], $\xi $ 是指函数的导数小于0, 即随着自变量的增加, 函数值持续减少, 则得到新的启发函数为:

${\eta _{ij}}\left( t \right) = \left[ {1 - \frac{{{d_{ij}} + {L_{jg}}}}{{\displaystyle\sum\limits_{s \in {\rm{ }}k}^n {\phi ({d_{ij}} + {L_{jg}})} }}} \right] \times \frac{{{N_{c\max }}}}{{\xi {N_c}}}$

(3)

其中, i和j分别为全遍历路径中机器人的起始节点和终止节点; g表示全遍历路径的中心节点; ${d_{ij}}$ 表示全遍历路径节点i到j之间的欧式距离; ${L_{jg}}$ 表示全遍历路径节点j到节点g之间的距离; ${N_{c\max }}$ 表示全遍历路径规划的最大迭代次数; ${N_c}$ 表示当前迭代次数. 将递减系数引入到式(1)中, 并根据式(1)对启发函数进行初始化, 从而为信息素的分配提供条件.

当蚂蚁k从全遍历路径节点i移动到节点j时, 就会更新局部信息素, 具体更新规则为:

${\tau _{ij}}(t) = (1 - \lambda ){\tau _{ij}}(t) + \lambda {\tau _0} + {\eta _{ij}}(t)$

(4)

其中, $\lambda $ 表示挥发系数; ${\tau _0}$ 表示正常量; 设 ${\tau _{\max }}$ 和 ${\tau _{\min }}$ 分别表示信息素的最大值和最小值, 当 ${\tau _{ij}}(t) < {\tau _{\min }}$ 时, 则令 ${\tau _{ij}}(t) = {\tau _{\min }}$ , 当 ${\tau _{ij}}(t) > {\tau _{\max }}$ 时, 则令 ${\tau _{ij}}(t) = {\tau _{\max }}$ .

当所有蚂蚁完成一次迭代之后, 更新全局信息素^[11]. 在迭代过程中, 选择最优蚂蚁路径和最差蚂蚁路径, 对最优蚂蚁执行全局更新规则^[12], 最差的蚂蚁按照下式来更新信息素:

${\tau _{ij}}(t + 1) = (1 - \rho ){\tau _{ij}}(t) - \varepsilon \frac{{{L_{{\rm{worst }}}}}}{{{L_{{\rm{best }}}}}}$

(5)

其中, $\varepsilon $ 表示更新参数; ${L_{{\rm{worst }}}}$ 表示最差蚂蚁的路径长度; ${L_{{\rm{best }}}}$ 表示最优蚂蚁的路径长度.

令迭代阈值为R, 当迭代次数小于R时, 挥发系数就会随着迭代次数的增加而减小, 当迭代次数大于阈值时, 挥发系数继续递减, 即:

$\rho (t + 1) = \left\{ {\begin{array}{*{20}{l}} {\max \left( {\gamma \cdot \rho (t),\;\;{\rho _{\min }}} \right),{N_c} \ne R} \\ {{\rho _0},\;\;{N_c} = R} \end{array}} \right.$

(6)

其中, $\gamma $ 表示参数; $\;{\rho _0}$ 表示信息素的初始值; ${N_c}$ 表示当前迭代次数.

总结以上计算过程, 得到改进蚁群算法的实施步骤如下:

Step 1. 初始化迭代参数

选择蚂蚁行走的起点 $S$ 、终点 $G$ , 迭代次数 ${N_c}$ 、最大迭代次数 ${N_{c\max }}$ , 对蚂蚁的数量、启发因子, 递减系数等进行初始化;

Step 2. 分配初始信息素

根据蚂蚁的起点位置和终点位置采用不均衡的方式来分配信息素;

Step 3. 选择蚂蚁路径

将m只蚂蚁共同放在起点位置, 将起点位置加入到禁忌表中, 计算路径节点j到终点的距离, 得到启发信息的具体数值, 再寻找下一个路径节点, 并添加到禁忌表中, 依次循环上述过程, 直到蚂蚁到达终点;

Step 4. 更新局部信息素

蚂蚁每建立一条全遍历路径, 就会按照式(4)更新一次局部信息素, 还要保证每一条信息素的浓度;

Step 5. 更新全局信息素

待所有蚂蚁完成一次迭代之后, 寻找出这一迭代过程中最优蚂蚁和最差蚂蚁, 判断当前迭代次数与阈值的关系^[13], 确定挥发系数, 更新最优蚂蚁和最差蚂蚁行走路径的信息素, 确保信息素的浓度;

Step 6. 结束搜索

判断迭代次数是否达到最大迭代次数, 如果是, 将最优路径长度输出; 如果不是, 将禁忌表清空, 返回Step 3继续进行迭代, 直到达到最大迭代次数, 将最优路径长度输出, 结束并行蚁群算法设计.

根据蚁群算法存在的问题, 将递减系数引入到启发函数中, 更新局部信息素, 通过设定迭代阈值, 调节信息素的挥发系数, 对改进蚁群算法进行设计. 接下来通过全向移动机器人全遍历路径的规划流程设计, 实现全向移动机器人全遍历路径的规划.

1.3 规划全向移动机器人全遍历路径

在改进蚁群算法的基础上, 将其应用到全向移动机器人全遍历路径规划中, 具体步骤如下:

Step 1. 初始化全向移动机器人的行走空间及改进蚁群算法的参数;

Step 2. 利用改进的蚁群算法, 在分析环境模型的情况下^[14], 寻找全向移动机器人的全局路线;

Step 3. 将全向移动机器人放置在起点位置, 让全向移动机器人沿着Step 2的路径向终点移动, 记录一条新的全向移动机器人行走路线;

Step 4. 全向移动机器人边行走边探测周围障碍物的存在情况, 如果在行走路线上不能感应到动态障碍物, 将Step3中记录的机器人行走路线输出, 结束路径规划;

Step 5. 如果全向移动机器人在行走过程中可以感应到周围动态障碍物, 那么就要根据周围动态障碍物的运动规律^[15], 判断机器人是否会与障碍物发生碰撞;

Step 6. 如果两者之间不会发生碰撞, 全向移动机器人继续朝着终点移动; 如果两者之间发生了碰撞, 全向移动机器人就会执行避障策略, 然后继续朝着终点移动;

Step 7. 重复操作Step 3~Step 6, 直到全向移动机器人到达终点;

Step 8. 输出全向移动机器人的移动路线, 并将全向移动机器人的移动路径长度输出.

根据改进蚁群算法在全向移动机器人全遍历路径规划中的应用步骤, 设计了全向移动机器人全遍历路径规划流程, 如图2所示.

综上所述, 采用拓扑建模方法先建立了全向移动机器人全遍历环境模型, 在改进蚁群算法的基础上, 设计全向移动机器人全遍历路径规划流程, 实现了全向移动机器人全遍历路径的规划.

2 实验对比分析 2.1 地图建模

全向移动机器人全遍历环境建模是规划其路径的前提, 通过提取的全遍历路径信息, 分析得到全向移动机器人可以理解的环境地图, 使全向移动机器人可以在地图环境中规划全遍历路径.

按照八叉树规定全向移动机器人的搜索路径, 将栅格的规模设置为 ${N_x}$ 行 ${N_y}$ 列, 第 $i$ 个栅格的位置坐标表示为 $\left( {{x_i},{y_i}} \right)$ , 全向移动机器人的位置坐标与栅格序号的映射关系为:

$\left\{ {\begin{array}{*{20}{l}} {{x_i} = {R_a}\left[ {\,od \,\left( {i,{N_x}} \right) - \dfrac{{{R_a}}}{2}} \right]} \\ {{y_i} = {R_a}\left[ {{N_y} + \dfrac{{{R_a}}}{2} - \operatorname{ceil} \left( {\dfrac{i}{{{N_y}}}} \right)} \right]} \end{array}} \right.$

(7)

其中, ${R_a}$ 表示栅格变长; $od \,\left( {} \right)$ 表示取余函数; $\operatorname{ceil} \left( {} \right)$ 表示取整函数.

2.2 全向移动机器人全遍历路径长度对比试验

为了对比基于改进蚁群算法的全向移动机器人全遍历路径规划方法与其他路径规划方法的差异, 分别采用所设计方法、传统蚁群算法、文献[4]的全遍历路径规划方法以及文献[5]的全遍历路径规划方法, 对全向移动机器人的全遍历路径进行规划, 得到全向移动机器人全遍历路径长度对比结果, 如图3所示.

从图3的实验结果可以看出, 采用所设计方法来规划全向移动机器人的全遍历路径时, 建立了全向移动机器人全遍历环境模型, 可以让全向移动机器人更快适应工作环境, 并且在改进蚁群算法的基础上, 简化了全向移动机器人在寻找最优路径时的计算复杂度, 使规划得到的全向移动机器人全遍历路径长度更短; 文献[5]的全遍历路径规划方法在规划全向移动机器人的全遍历路径时, 由于该方法不能更好地适应全向移动机器人的工作环境, 使规划的路径长度较长; 文献[4]的全遍历路径规划方法在规划全向移动机器人的全遍历路径时, 由于该方法在全遍历路径寻优过程中, 路径搜索的时间比较长, 且迭代的计算过程也比较复杂, 使规划的全遍历路径长度较长. 而传统蚁群算法由于存在收敛速度慢, 容易陷入局部最优的问题, 导致路径长度更长. 根据上述分析可知, 所设计方法能够有效缩短机器人移动路径长度, 提高路径规划能力.

2.3 全向移动机器人全遍历路径规划时间对比试验

以迭代次数为自变量, 分别采用所设计方法、传统蚁群算法、文献[4]的全遍历路径规划方法以及文献[5]的全遍历路径规划方法, 对全遍历路径进行规划, 得到路径规划时间对比结果如表1所示.

从表1的实验结果可以看出, 随着迭代次数的增加, 不同方法规划全向移动机器人全遍历路径的用时都在变长, 但是所设计方法由于将并行蚁群算法应用到了全遍历路径规划中, 简化了全遍历路径的寻优过程, 从而缩短了全遍历路径的规划时间; 文献[4]的全遍历路径规划方法、文献[5]的全遍历路径规划方法以及传统蚁群算法由于迭代的过程比较复杂, 使全向移动机器人全遍历路径规划时间更长.

2.4 全向移动机器人全遍历路径规划效果对比

为了进一步验证所设计方法的优势性, 设置含有障碍物的环境, 运用不同方法在该环境中进行路径规划, 结果如图4所示.

分析图4可知, 传统蚁群算法、文献[4]的全遍历路径规划方法以及文献[5]的全遍历路径规划方法不能有效躲避障碍物, 使机器人移动过程中产生了一些不必要的路径, 加大了路径一定成本. 相比较之下, 所设计方法规划得出的路径能够有效躲避障碍物, 并且路径接近于直线, 路径长度更短. 这是由于改进蚁群算法将递减系数 $\xi $ 引入到启发函数中, 避免了蚁群算法陷入局部最优的问题, 降低了启发信息对蚁群在搜索过程中的影响, 因此, 提升了路径规划效果. 通过上述分析可知, 所设计方法能够获得最优路径.

综合以上实验结果, 基于并行蚁群算法的全向移动机器人全遍历路径规划方法无论是在路径长度和路径规划时间上, 相比于其他路径规划方法都具有更大优势, 并且该方法能够获得最优路径, 充分验证了该方法的有效性.

3 结束语

本文提出了基于改进蚁群算法的全向移动机器人全遍历路径规划方法, 结果显示, 该方法在规划全向移动机器人全遍历路径过程中具有较高的路径规划性能. 但是本文设计的路径规划方法主要应用在静态电子地图中, 在今后的研究中, 要加强在动态电子地图中的应用, 提高其在路径规划上的实用性.