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

徐超毅,龚桥梁

(安徽理工大学 经济与管理学院,安徽 淮南 232001)

随着机器人研发技术的发展和节能环保理念的推广,移动机器人在物流仓储环节的应用迅速发展,机器人的路径规划问题成为物流应用领域的热点问题[1]。如果机器人能在最优路径上移动,将会大大缩减物流时间、降低运送成本。

路径规划是指在有障碍物的环境中,搜寻一条从出发点到目的地无碰撞的最佳路线[2]。自动导引运输车(Automated Guided Vehicle,AGV)的路径规划一直是国内外专家探索的热门话题,学者们提出了多种有效的思路解决这个问题。AGV的路线规划主要包含两类方法:地图信息表达方法和搜索策略方法[3]。地图信息表达方法包括自由空间法、拓扑法和栅格法[4];搜索策略方法包括A*算法[5]、dijkstra方法[5]、蚁群算法[7]以及粒子群算法[8]等。其中,蚁群算法被普遍看作是一个有效且稳定的集群算法。该算法具有分布式运算、易与其他方法融合以及正反馈等优势。但该算法存在收敛速度慢、路径状况差以及在复杂地图上搜索效率不高等问题。众多学者对这些问题进行了研究[9]。文献[10]提出将蚁群的主要参数设为微粒群的定位信息,并设置适应值评估变量,以诱导微粒向评价指数更高的方位收敛,从而高效地运行蚁群算法解决机器人路径规划难题。文献[11]提出了采用D*算法的改进启发变量和子节点扩展形式,将蚁群算法的评价函数用于运算,并利用栅格法构建地图模型,以便在各种难度的栅格环境上选择多个目标开展仿真对比试验。文献[12]修改了蚁群算法的节点转移概率公式和信息素更新方式,将A*算法快速寻解特性与传统蚁群算法进行融合,使AGV寻优效率得到显著优化。由此可见,学者们一般将蚁群算法与其他算法融合以克服其收敛慢、路径远的缺点。但是蚁群在其他算法的规划路线上进行扩散的随机性被削弱,导致容易陷入局部最优,而降低获得整体最优路径的可能性。

本文对传统蚁群算法进行了改进。在A*单向搜索[13]的基础上,在栅格环境中运用A*头尾双向搜索得出初始路径,并进一步提高算法的收敛速度。文献[14]采用了在较优路径周边区域内线性递减改变信息素的方式,而本文在优势区域内以整体优化信息素浓度的方式给予蚁群在区域内更高的搜索自由度,以提高蚁群寻优的随机性。

1 栅格法环境建模

环境建模是解决机器人路径规划问题的关键,它将实际工作环境映射到一个虚拟环境中,以便更好地理解和预测机器人的行为。栅格法因其简单高效、可行性强以及可靠性高,已被广泛应用于解决机器人路径规划问题[15]。

栅格法是一种用于描述环境信息的有效方法,它将障碍物所在区域标示为1、可自由通过地区标示为0,以便在创建的环境模型中找到最佳的可通过途径。因此,栅格的合理设定对于路径规划至关重要。

创建栅格地图。将地图左下角首个栅格作为坐标原点。每个栅格的坐标为(x,y)。将左下角的首个栅格的坐标记为(0,0)。任意栅格的编号记为N。从左下角的栅格开始编号,编号从0开始。坐标和编号的转换函数为

x=int(N/Gsize)+1

(1)

y=N%Gsize+1

(2)

式中:Gsize为每行栅格的个数;int为取整函数;%为取余数。

为真实还原物流AGV在仓储物流的工作环境以及提高算法的仿真程度和实用性,本文采用栅格法构建一般环境和复杂型环境两种地图(见图1)。

AGV行进时一定要占据栅格。在真实环境下,AGV会有多个方向可以考虑,为使行进方向简单化,在仿真环境中将AGV设置为以各栅格中心点为准,每一步前进可供选择的方向有8种,分别为右前、右后、左前、左后等4个斜方向以及前后左右4个直行方向(见图2)。

图2 AGV的行进方向

2 传统蚁群算法基本理论

蚁群算法是以大自然界蚂蚁群体从巢穴到食物之间的路径搜索为基础的群体智能启发式算法。它可以使用正反馈,帮蚂蚁寻找最短的路径[15]。通过观察各条路线上经过的蚂蚁数量,推断出各条路线的信息因子含量,帮助蚂蚁找到最短的路线,从而实现最佳的觅食效率。

2.1 转移概率选择

传统的蚁群算法是根据信息素浓度和距离确认蚂蚁的位置,其中t时刻第k只蚂蚁从当前位置到下一个位置的转移概率为

(3)

式中:τij为当前节点与可行节点路径的信息素浓度;ηij为距离启发因素,为当前节点到可选节点欧式距离的倒数;allowedk为下一可行节点的集合;α、β为权重因子,用于控制信息素浓度和距离启发因素在转移概率中的重要程度。

2.2 信息素更新

蚂蚁在完成一次路线搜寻后,将信息素留在这条路线上,先前的部分信息素会蒸发掉,下次搜寻开始时信息素的浓度计算式为

(4)

(5)

3 改进的蚁群算法

3.1 双向搜索的A* 算法

A*算法是一种具有重要应用价值的启发式搜索算法,它可以有效地帮助AGV避开障碍物并实现路径规划。A*算法的一般评价函数表达式为

f(n)=g(n)+h(n)

(6)

式中:f(n)为起点到终点的总代价;g(n)为f(n)的前一部分代价,即起点到当前所在点的代价;h(n)为f(n)的后一部分代价,即当前所在点到终点的代价。

传统A*算法的单向搜索在搜索过程中存在着路径质量差和效率低的问题,通过改进使蚁群算法能够得到更优的预搜索路径。相比传统A*算法,首尾搜索的A*算法新增了OPEN表单和CLOSED表单,依次标记为SOPEN表、EOPEN表和SCLOSED表、ECLOSED表。每一个子节点都是以当前所在栅格为起点,搜索周边8个栅格,寻找f(n)函数值极小的拓展节点,置于CLOSED表中。在找到h(n)函数值为0的拓展节点后,A*算法将停止运行。先行使用A*算法进行双向搜寻,会使得改进的蚁群算法更加高效,能更快地找到最优解。

3.2 蚁群算法信息素分布策略改进

在传统的蚁群搜索中,信息素的初始值是平均配置的,这将使蚂蚁在初期陷于盲目搜寻的困境,大大降低搜索效率。为了解决这个问题,学者们提供了诸多信息素优化策略,例如李鹏等[13]提出标记A*算法搜索的初始通道,然后在路线周围构筑优势区域,以此优化信息素。扩张栅格的个数与栅格图的尺寸、障碍物的比例有关,具体计算式为

(6)

(7)

式中:SL为扩张栅格的数量;round为取整运算;B为障碍栅格;D为地图斜长;H为栅格总数;X、Y分别为地图的长和宽。

文献[14]以线性递减的方式改变区域信息素浓度,增强了下一阶段较优解区域内蚁群搜索的倾向性。这一设计虽然提高了蚁群的收敛速度,但蚁群容易受到A*算法搜索的初始路径影响,无法完全发挥自身全局搜索的寻优优越性。本文将整个栅格环境区分为双向A*算法搜索得到的优势区域和其他区域,对优势区域整体提高设定系数的信息素浓度。这使得改进的蚁群算法既吸收了A*算法搜索的快捷性,又能发挥蚁群随机搜索、全局搜索的特点。采用这种方法可以有效避免算法在初始搜索阶段出现盲目性,同时也不会完全依赖于初始路径的指引。A*算法优化蚁群信息素分布并形成信息素较稠密区域的机理见图3。

图3 扩展栅格

信息素浓度优化方式可以表示为

(8)

式中:μ为增强系数;τ0为初始信息素浓度;Z为初始信息素增强区域。

4 改进的蚁群算法流程

(1)在栅格地图模型中运行A*算法,分别从起始点和终点开始寻优,以确定较优解,并调整初始信息素浓度。

(2)将A*算法和蚁群算法的信息素进行有效融合。

(3)蚁群采用轮盘赌的方法决定前往的下个节点。

(4)当蚁群搜寻结束后,将其生成的信息素与原有的信息素进行融合,以刷新全局的信息素,从而提升搜索效率。

(5)开始新一轮的搜索,使蚁群重新回到起始点,并在达到预定的迭代次数后,结束搜索,找出最优的路径。

5 算法仿真

将传统蚁群算法、A*算法、改进蚁群算法分别置于20 m×20 m的一般型和复杂型两种栅格环境下运行。重点比较蚁群算法改进前后的寻优表现。

5.1 算法参数设置

蚁群算法的性能主要受信息启发因子和信息素挥发因子的影响[16]。设定机器人初始坐标为(0.5,19.5),终点坐标为(19.5,0.5)。依据文献[17]对主要参数进行了优化:蚂蚁数量为100,最大迭代次数为100,μ为0.001,ρ为0.5,α、β均为2。

5.2 仿真环境1

在一般栅格环境中分别验证3种算法以验证改进蚁群算法的优越性,3种算法求解的路径如图4和表1所示。

表1 在仿真环境1中的各算法结果对比

表2 仿真环境2下的运行结果

a 传统蚁群算法

通过改进蚁群算法能够改善蚁群随机搜索导致的盲目性大、路径拐角过多等缺点,也能够克服A*算法容易进入“凹角”型障碍的不足,得出的最优路径明显减少了拐弯和迂回次数,寻优轨迹较传统蚁群算法和A*算法路线更为平滑。改进蚁群算法得出的寻优路径在距离长短方面明显优于传统蚁群算法,路径长度减少了7.622 m;在蚁群搜索前加入了A*的双向搜索,运行时长25.103 s,优于传统蚁群算法的25.742 s。通过对图表数据的分析可知,所提出的改进蚁群算法在多个方面均优于传统的蚁群算法。

5.3 仿真环境2

为了更好地验证改进蚁群算法的可行性和效果,在20 m×20 m的栅格环境中增加了形状不规则障碍的数量,并将障碍物设置成小块、密集的布局,以增加路径选择的复杂性和难度。同时为考验蚁群搜索和A*算法在面临陷阱时的回退能力,在栅格环境中引入了H型和U型障碍。仿真环境2下3种算法的运行轨迹和结果如图5和表1所示。

a 传统蚁群算法

由图5可以看出,传统蚁群算法在面临复杂栅格环境时,盲目性较强,多次出现回退、转弯现象;而A*算法虽然得出的路径较为平整,但囿于局部障碍,无法得到整体最优解。改进蚁群算法与传统蚁群算法相比,其给予双向搜索得出的路径区域更高信息素的特点,为蚁群提供了范围更小的较优解区域,规避了H型和U型障碍,减少了回退和转弯次数,显著改善了寻优能力。改进后的算法迭代次数由24次减至7次,效率显著提高。相较于传统A*算法只能单向寻优的不足,改进后的蚁群算法首尾搜索方式在复杂环境中更能克服单向A*算法易受单个障碍影响路径走向而无法得到最短寻优路径的缺点,结果表现为A*算法最短路径长度为30.385 m,大于改进算法的29.213 m,同时寻优路线转弯次数为12次,多于改进算法的9次。

6 结论

(1)改进蚁群算法结合了A*算法快速寻优和蚁群算法随机寻优的特点。利用A*算法进行首尾双向搜寻,给予栅格环境中双向A*寻优区域信息素,在较优解路径周围区域按设定系数增加信息素浓度,提高了蚁群算法的收敛速度,增强了蚁群整体的搜索能力。

(2)对3种算法进行了在不同环境下的仿真试验。与传统的蚁群算法和A*算法相比,改进蚁群算法具有更强的路径寻优能力,速度更快,路径转弯次数少,可为提高物流机器人的工作效率提供一定参考。

(3)改进蚁群算法虽然在路径距离、路线平滑程度上优于传统蚁群算法和A*算法,但仍存在行进路线与障碍物产生接触的问题。下一步可考虑提升栅格环境内机器人寻优的仿真程度,提高算法的应用价值。