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

引言

路径规划是机器人运动控制的关键,也是当前人工智能领域的研究热点。机器人的路径规划是指在有障碍物的环境中,按照一定的评判标准,找出一条从起点到终点的最优无碰撞路径。

蚁群算法作为仿生智能算法,具有较强的鲁棒性、环境适应性以及分布式计算、无中心控制的特征,国内外学者对此做了大量研究并取得了丰硕成果,这些方法在基于静态障碍环境下均能快速获得最优解,但存在路径中拐点过多、拐弯停顿耗时和产生额外机械损耗等问题。

本文从拐点数及转弯角度出发,对蚁群算法每次迭代搜索出的最短路径进行顺滑修正,进一步优化所寻路径,避免不必要的转弯,降低机器人机械损耗。

1环境建模

为便于开展路径规划,需要对机器人的行走环境做数字建模处理,将环境信息转换为机器人可识别的数学模型。为不失一般性,采用主流的栅格地图,按照以下定义对机器人行走环境进行建模:

1.1栅格定义

以机器人自身尺寸6作为栅格大小,从而可以将机器人理想化为一个质点进行处理,确保机器人每次都停留在栅格的中心位置,便于开展无碰撞路径规划。只要栅格内有障碍物存在,则视该栅格为障碍栅格,以黑色栅格表示。否则,该栅格为自由栅格,以白色栅格表示。

1.2坐标系定义

以左下角为原点、横向向右为Ⅹ轴正向、纵向向上为Y轴方向,将运动区域按栅格的大小划分为皿和Ⅳ等分,按照从左到右、从下到上顺序,将栅格编号为1,2,…,皿×Ⅳ,如图1所示。

栅格i的中心坐标(λi,yi）与栅格编号i存在以下对应关系:

经过上述定义,机器人路径规划问题其实就是在自由栅格集合中遍历出所有邻接栅格的子集,并从中搜索出一条最短的邻接栅格路径。

2平滑策略

路径的平滑程度是度量机器人能量消耗与机械损耗的一个重要参数。拐弯过程中,机器人需要经过减速、提速过程,产生额外的时间消耗、能量消耗和机械损耗,同时急拐弯还容易出现路径累计误差。

本文采取通过删除拐弯点、拉直运动路径或缓解急拐弯的方式来平滑机器人运动路径,具体措施为:障碍栅格至平滑路径起始点连线距离如图2所示,现有搜索路径i→j→k,出现拐弯点j。假设a、b分别为栅格编号i、j、k三者的最小值和最大值,搜索栅格编号子集L=(a,a+1,a+2,…,b}中的障碍栅格p,按照公式(2）计算栅格p到栅格i与栅格k中心连线的距离d,若d≤6,则可以删除拐弯栅格j,拉直栅格i和栅格k,以此达到平滑运动路径的目的。

平滑处理的算法流程如图3所示。

3基于蚁群算法的路径规划步骤

步骤1:采用栅格法构建环境地图,指定机器人初始位置和终止位置并设置各种参数,初始化信息素矩阵(信息素浓度均相同)。

步骤2:将蚂蚁种群放置于初始位置,并将初始位置加入禁忌表。

步骤3:根据当前信息素浓度计算第k只蚂蚁由栅格i转向栅格j的概率:

公式(3)中,allowdedi为与栅格i邻接的自由栅格集合,a为栅格i至栅格i路径上残留的信息素,α、8分别为信息素浓度启发因子和能见度启发因子,n为路径能见度函数,其取值由公式(4)获得:

公式(4)中,(xi+yi)和(xi+yi)分别表示栅格i和栅格i的中心点坐标。

信息素τ进行更新:

公式(5)、公式(6)中,p为信息素浓度衰减系数,0为信息素强度,Lk为第k只蚂蚁在本次迭代搜索中走过的路径长度。

步骤4:更新路径以及路径总长度。

步骤5:重复步骤3和4,引导蚂蚁到达目的地或陷入死循环,对陷入死循环的蚂蚁采取放弃策略。

步骤6:对搜索出的最短路径做平滑处理,得到本轮迭代最优解。

步骤7:重复步骤3至步骤6,直到迭代搜索结束,得到最终最优解。

4仿真实验

采用10x10的栅格矩阵模拟机器人运动环境,使用VC＋＋6.0编程对机器人路径规划进行仿真验证。

仿真实验参数需满足:种群数量m=100,迭代次数N=200,信息素权重参数a=1,启发因子权重参数8=7,信息素强度系数0=200,信息素挥发系数p=0.8,分别对基本蚁群算法和加入平滑处理策略的蚁群算法进行仿真验证,得到机器人运动规划

路径分别如图4、图5所示。

从图中可以看出,经过平滑处理,直角急拐弯由6次降低为1次,拐弯总次数由6次降低为4次,路径总长度由18s减少为15.76s。

5结语

本文研究了基于栅格地图环境的蚁群算法机器人路径规划平滑策略。针对蚁群算法在机器人路径规划过程中出现的拐弯过多、运动延时和产生额外机械损耗等缺陷,提出了对迭代搜索出的最短路径进行平滑优化处理的策略,删除不必要的拐弯点,拉直急拐弯路径,降低机器人运动停滞概率,从而减少运动耗时,降低机械损耗。仿真结果表明,采用对每一轮迭代搜索出的最短路径进行平滑处理的策略能有效提高路径搜索质量,降低机器人运动时间,减少机械磨损。