基于改进蚁群算法的巡检机器人避障路径规划方法设计

李 鹏，闵小翠，王建华

(广州华立科技职业学院，广东 广州 511325)

0 引言

机器人的避障路径规划一直是机器人研发领域重要的研究课题。人们将人工智能与机器人研发领域进行结合[1]，从而有效地解决了机器人工作时的避障规划问题[2]。巡检机器人作为实用性机器人的一种，在工作时准确地躲避工作空间中的障碍，快速移动到目标区域，更是该类机器人工作安全进行的保障[3]。

封硕等[4]提出基于双粒子群算法的矿井搜救机器人路径规划，该方法在计算障碍物时存在一定问题，导致其在规划路径时所需的迭代次数多。毛鹏军等[5]提出基于Q-学习的果园机器人避障算法研究，该方法截取雷达数据时存在一定问题，所以在进行路径规划时的收敛速度慢。

为解决上述方法中存在的问题，提出基于改进蚁群算法的巡检机器人避障路径规划方法。

1 环境建模

在巡检机器人工作的二维环境空间内，存在若干障碍物，因此要基于可视的已知信息对该空间进行遍历，构建巡检机器人工作环境的二维栅格地图模型[6]。

1.1 环境空间划分

设定巡检机器人在工作区间的移动区域为A，构建一个二维坐标系，该移动区域的左下角设定为O点，水平向右为坐标系X轴方向，垂直向上为坐标系Y轴方向。若巡检机器人的最小活动步长为δ，且在构建的二维坐标系X、Y方向的最大值为Xmax和Ymax，基于δ对巡检机器人的移动区域进行划分处理，使每行的栅格数为Nx=Xmax/δ，每列的栅格数为Ny=Ymax/δ，由此构建m×n的栅格矩阵，结果为

(1)

c为向上运算因子。

1.2 建立像素矩阵

假定A中存在静态障碍物l个，经过膨胀处理后，会在构建的栅格地图中占一定位置，因此要将构建的二维栅格地图划分为障碍区域集O以及自由活动区域集F，且F=A-O。依据该项划分结果，完成障碍物空间的像素矩阵的构建，过程为

(2)

其中，构建的像素矩阵标记为M(i,j)形式。

1.3 识别栅格

在对巡检机器人进行路径规划时，需要对构建的栅格地图进行有效识别，识别时可利用序号法以及直角坐标法对栅格进行识别。

a.序号法：在构建的二维直角坐标系中，依照从下至上、由左至右的顺序对栅格进行排序，并对栅格进行序号标记。

标记时，设定C={1,2,…,M}为栅格的序号集，坐标系中g(1,1)为序号1，g(1,2)为序号2，直至标记完成。

b.直角坐标法：依据上述构建的二维直角坐标系，获取每个栅格的区间边长。首先设定g∈A为地图中的任意栅格，A中的所有g的集合标记为Ag，则O∈Ag。若Ag中的每一个g在坐标系中都有属于自己的位置(x,y)，则将该位置记为g(x,y)。

由于2种标识方法都基于栅格地图，所以2种方法属于互相映射关系，结果为

(3)

舍余运算标记为mod；求余运算标记为int。

将上述的2种标识方法结合，对获取的像素矩阵进行编码处理，获取序号的单元坐标[7]。过程中需要对像素矩阵与单元序号，以及单元坐标到单元序号之间的映射关系进行获取，结果为

(4)

i为x轴方向的障碍位置；j为y轴方向的障碍物位置；gx(i,j)为x轴的单元序号映射关系；gy(i,j)为y轴的单元序号映射关系；N(i,j)为像素矩阵与单元序号之间的映射关系；m为障碍物数量；δ为机器人步长。

将获取的2个映射关系进行整合，获取坐标单元与序号之间的映射关系，结果为

N(x,y)=mx(y+0.5δ-1)+x+0.5δ

(5)

N(x,y)为坐标单元与序号之间的映射关系。

1.4 逻辑对应

依据上述分析可知，机器人移动区域∀g∈Ag，且g∉O，那么g为栅格中的可行节点，将所有的可行节点进行整合，构建可行域记作F。

首先需要依据逻辑边获取判定条件，过程中设定Ni∈F，那么栅格点Ni与栅格点Nj二者间就可以生成逻辑边，过程为

(6)

d(Ni,Nj)为获取的逻辑边。

由于栅格法会将连续的路径信息进行离散化处理，因此可将巡检机器人的移动轨迹划分成单个的运动信息，并将其保留在各个栅格中。再基于栅格中保存的信息，将机器人的移动方向进行细致的划分。

2 路径规划

基于上述构建的环境模型，利用改进的蚁群算法完成对巡检机器人避障路径的规划[8]。

2.1 蚁群算法

通常情况下，蚂蚁在进行信息传递时，由于信息素的原因，上一代蚂蚁遗留下的信息素会对下一代产生影响。蚁群在运动时，由于信息素的扩散，导致蚂蚁在寻找最佳路径时，2只蚂蚁的运动轨迹发生重叠，因此要将人工势场与蚁群算法进行结合，实现机器人避障路径规划[9]。因此，蚂蚁需要在障碍物与目标点的势场方向建立局部启发信息素，提高蚂蚁在寻找路径时的预避障能力，从而蚁群能够适应子空间的搜索。

设定在寻找最佳路径时遭受的障碍物斥力为f1以及f2，目标点引力标记为fa，机器人受力方向为θ，大小为λ，二者合力为f(λ,θ)。寻找过程中可根据机器人受力方向与相邻栅格之间的角度差确定信息素的扩散方向。

将信息素浓度以及目标距离设定为高斯分布，这样就能让信息素在扩散时朝目标方向进行扩散，由此构建信息素的简化扩散模型。设定该简化模型为椎体形状，高为L，顶角为γ，扩散半径为lo，栅格中i点位置的信息素标记为q(i)，第i个栅格点与第j个栅格点之间的距离为η。本次蚂蚁搜寻路径的信息素扩散过程，结果为

(7)

基于栅格的环境特性，人工势场的势场力f(λ,θ)会发生变化，所以需要依据机器人的受力方向以及受力大小将信息素进行平滑处理[10]。

(8)

(9)

基于上述计算结果，蚂蚁只需向信息素浓密的方向进行搜索，即可快速寻找出巡检机器人的最佳移动路径。

2.2 算法流程

a.基于栅格法，生成巡检机器人移动场地的环境栅格地图模型，设定有障碍物的栅格为1，无障碍栅格为0；模型的左下角为起始点S，目标点为E。

b.对蚁群以及人工势场进行初始化处理。

d.计算第k只蚂蚁从第i个栅格点转移至第j个栅格点的转移概率，结果为

(10)

e.将第j个栅格点加入BK中。并对上述过程进行迭代计算，直至全部蚂蚁到达终点。对所有蚂蚁路径进行保存。

f.更新信息素矩阵，更新结果为：

(11)

(12)

(13)

Q为信息素强度；ρ为挥发因子；Lk为第k只蚂蚁走过的最长路径。

g.在寻找出的路径中找出最短路径作为巡检机器人避障的最短路径，完成机器人的路径规划。

3 实验分析

为了验证基于改进蚁群算法的巡检机器人避障路径规划方法的整体有效性，需要对该方法进行有效测试。

分别采用基于改进蚁群算法的巡检机器人避障路径规划方法(本文方法)、基于双粒子群算法的矿井搜救机器人路径规划算法(文献[4]方法)以及基于Q-学习的果园机器人避障算法(文献[5]方法)进行巡检机器人避障路径规划测试。

a.避障路径规划方法的收敛速度对规划效果产生的影响巨大，收敛速度越快，路径的规划效果就越好。在对巡检机器人进行避障路径规划时，对3种方法的收敛速度进行测试，测试结果如图1所示。

图1 不同方法的收敛速度测试结果

分析图1可知，本文方法在进行路径搜索时所检测出的收敛速度要高于其他2种方法。由此可知，利用本文方法进行巡检机器人避障路径规划时的收敛速度快。

b.进行巡检机器人避障路径规划时，对3种方法规划的路径长度进行对比，测试结果如图2所示。

图2 不同方法的路径规划长度检测结果

分析图2可知，随着检测次数的不断增加，3种方法检测出的路径长度均有所增加，而经过本文方法所搜寻出的巡检机器人避障路径是3种方法中最短的。由此可知，本文方法在进行巡检机器人避障路径规划时的规划路径短，规划效果好。

c.路径规划过程中，迭代次数与规划路径的长度存在相关。基于上述检测结果，对3种方法在进行机器人避障路径规划时的迭代次数进行测试，测试结果如图3所示。

图3 不同方法的迭代次数检测结果

分析图3可知，路径的长度越长，巡检机器人进行避障路径规划时的所需的迭代次数就越多，而本文方法在进行巡检机器人避障路径规划时所需要的迭代次数较其他2种方法要少。

d.基于上述实验结果，对3种方法的路径规划时间进行测试，测试结果如图4所示。

图4 不同方法的规划时间测试结果

分析图4可知，随着路径长度的不断增加，3种路径规划方法的路径规划时间均呈现不同程度的增加趋势。本文方法的避障路径规划时间低于其他2种方法。

4 结束语

针对传统机器人避障路径规划方法中存在的问题，提出基于改进蚁群算法的巡检机器人避障路径规划方法。该方法首先基于栅格法构建环境地图模型；再将人工势场法与蚁群算法进行结合，通过对路径的搜寻，完成机器人避障路径的规划。实验结果表明，该方法的避障规划路径距离短、规划时间短，具有一定的有效性。