邱晓磊

(淮北师范大学 体育学院,安徽 淮北 235000)

0 引言

机器人具有在复杂环境中工作的优势,因此开发用于太空探索、建设工作的机器人成为了备受关注的焦点。网球机器人是一种“迷你型”机器人,由先进材料制作的外壳能够确保其在极寒、高强紫外线辐射的恶劣环境下开展外星球表面洞穴、裂缝的勘探工作。路径规划是网球机器人开发的核心技术,许多学者对机器人路径规划问题进行了广泛而深入的研究。李明龙[1]对传统蚁群算法的启发信息与信息素更新机制进行改进,并通过仿真试验验证了改进蚁群算法所规划的路径在路径长度和算法效率上均优于传统的蚁群算法。董炫良[2]针对传统蚁群算法存在盲目搜索、收敛速度慢的问题,提出了以改进人工势场法规划路径来启发蚁群算法,减少了路径规划的盲目性,加快了算法的收敛速度。姚晓通[3]针对传统蚁群算法易陷入局部最优的问题,对传统蚁群算法的信息素更新规则进行了改进,提出了一种自定义的自适应信息素挥发因子更新方法,并通过仿真模型验证了改进的蚁群算法在最优路径长度和迭代次数上比传统的蚁群算法表现更优。本文在前人研究的基础上,对传统的蚁群算法进行改进,并将其应用于网球机器人的路径规划中。

1 问题描述和环境建模

网球机器人完成外星球表面探测,需要对周边的环境信息进行建模,采取适当的路径规划算法来完成机器人运动过程中的避障操作,最终获得机器人运动的最佳路径。结合网球机器人的工作环境,对网球机器人路径规划问题做出以下基本假设[4]:

1)网球机器人的运动空间是二维有限空间,同时障碍物的位置是确定的;

2)各种障碍物随机分布在二维有限空间中,且障碍物的形状不发生改变;

3)网球机器人的起始位置和目标位置是确定的。

采取蚁群算法来实现网球机器人在存在障碍物的环境下由起始位置到达目标位置,同时网球机器人在移动的过程中不能和已知的障碍物发生碰撞。

栅格法是环境建模的常用方法,同时考虑到网球机器人形状比较小,将其作为质点考虑。在采用栅格法所创建的环境模型中,白色的栅格为机器人可以行走的栅格,用1表示;黑色的栅格为障碍物栅格,机器人无法通行,用0表示[5]。构建网球机器人路径规划的简单环境模型与复杂环境模型,结果如图1所示。

图1 机器人路径规划环境模型Fig.1 Robot path planning environment model

2 蚁群算法及改进

2.1 蚁群算法

蚁群算法是由Marco Dorigo受到自然界蚂蚁觅食行为启发而提出的智能优化算法,在旅行商问题上被广泛应用。自然界中单个蚂蚁的觅食行为没有智能行为,而蚁群整体的觅食行为往往表现出一定的智能性。蚂蚁在觅食的过程中会在经过的路径上释放信息素,这样,之后的蚂蚁就可以在信息素的作用下表现出智能化的觅食行为。在最初觅食时,蚂蚁经过的路径上无信息素,蚂蚁选择路径是随机的,伴随着时间的推移,觅食距离短的路径经过的蚂蚁越来越多,路径上的信息素浓度也越来越大,最终蚁群会寻找到到达目标点的最佳路径。

蚁群中的个体根据信息素浓度选择下一个移动节点,同时受到当前节点和附近节点的期望信息影响。定义蚂蚁k由节点i选择节点j的转移概率为[6]

(1)

式中：τij(t)为蚂蚁在路径ij上留下的信息素浓度；ηij为路径ij上的启发信息；α为信息启发因子；β为期望启发因子；dk为蚂蚁可选节点集合。

启发信息为[7]

(2)

式中：djg为待选节点j与目标节点g之间的欧式距离。

蚁群中的蚂蚁个体经过路径时会释放信息素，同时，随着时间的推移信息素也会蒸发，即对路径上信息素的更新。蚁群算法是对所有的蚂蚁迭代完成之后进行信息素的更新，信息素更新规则为：

(3)

(4)

式中：Q为常量；Lk为蚂蚁k访问路径长度。

2.2 蚁群算法改进

传统蚁群算法进行路径规划存在盲目性且对路径规划目标点的逼近效果不理想,基于HOCAOGLU算法对状态转移规则进行改进,图2为HOCAOGLU算法原理示意图[8]。

图2 HOCAOGLU算法原理示意图Fig.2 Schematic diagram of HOCAOGLU algorithm

在图2中,S点为起始点,G点为目标点。由几何知识可知,两点之间直线段距离最短,即起始点S到目标点G之间的最短路径就是直线段SG。如果在直线段SG之间存在障碍物,那么做SG的垂直平分线ab,其中直线段Sb和直线段bG均不能与直线段SG之间的障碍物碰撞,同时设置直线段和障碍物的最短距离,要求Sb,bG和障碍物的距离均不能小于设定的最短距离,那么此时Sb,bG就是由起始点S到目标点G的最短路径。如果在Sb之间依旧存在障碍物,那么做Sb的垂直平分线,Sc,cb,bG就是由起始点S到目标点G的最短路径。按照这样的方式以此类推,最终获得由起始点S到目标点G的最短路径。很明显,靠近直线段SG的节点,节点和起始点S、目标点G的距离之和越小,所规划的路径越短。因此,构造包含权重调节因子的引导函数

(5)

式中：dis和dig分别为当前节点和起始点、当前节点和目标点之间的距离，λ为调节因子，其表达式为

(6)

式中:Ns为当前节点次序;Nm为中间节点次序。

引入调节因子λ的作用是在搜索的前期更加侧重于直线段SG附近的节点,在搜索的后期更加侧重于目标点G附近的节点,使得蚂蚁可以更加快速地找到目标点G。改进蚁群算法蚂蚁k由节点i选择节点j的转移概率

(7)

式中:γ为启发引导因子。

信息素挥发因子ρ对路径规划的性能影响比较大。如果信息素挥发因子ρ比较小,那么信息素挥发就比较慢,不同路径上信息素浓度差别比较小,蚂蚁个体根据信息素浓度选择路径比较困难,导致算法的收敛速度比较慢;如果信息素挥发因子ρ比较大,那么信息素挥发就比较快,导致不同路径信息素浓度差别比较大,尽管会加快算法的收敛速度,但是会导致算法陷入局部最优。基于此,提出一种自适应确定信息素挥发因子ρ的方法,即

图3 改进蚁群算法的机器人路径规划算法流程Fig.3 Robot path planning algorithm flow based on improved ant colony algorithm

(8)

设定信息素挥发因子ρ的取值范围为[0,1]，ρ的初始值为0.98，若经过多次迭代，相邻两次最优解差值小于0.1%，那么自动调整信息素挥发因子为原来信息素挥发因子的0.9倍。当信息素挥发因子的值小于0.2时，设定信息素挥发因子的数值为0.2。通过自适应确定信息素挥发因子ρ可以避免该数值过大或者过小。基于改进蚁群算法的机器人路径规划算法流程如图3所示。

由图3可知,先创建栅格环境地图,并且将关联坐标加入到禁忌表中,设定网球机器人的初始位置和目标位置。采用HOCAOGLU算法对状态转移规则进行改进,根据改进的规则来选择下一个节点,同时更新节点和禁忌表,判断网球机器人是否到达设定的目标位置,如果没有到达目标位置,则继续选择下一个节点;如果到达了目标位置,那么对该路径上的信息素进行更新。同时,采用自适应确定信息素挥发因子的方法来改变路径上的信息素,判断是否达到设定的最大迭代次数,如果没有达到,则继续设定新的起始位置和目标位置;如果达到,那么输出最优规划的路径。

3 网球机器人路径规划仿真

在MATLAB R2020a环境下,搭建网球机器人路径规划仿真环境,分别为大小为10×10的简单障碍物环境和大小为20×20的复杂障碍物环境。设定简单障碍物环境和复杂障碍物环境的网球机器人起始位置均为(1, 1),简单障碍物环境的目标点位置为(10, 10),复杂障碍物环境的目标点位置为(20, 20),具体如图4所示。

图4 网球机器人起始点与目标点Fig.4 Starting point and target point of tennis robot

调节因子λ设置为:当前节点次序Ns小于中间节点次序Nm时,调节因子λ取值0.75;当前节点次序Ns大于中间节点次序Nm时,调节因子λ取值0.25。分别采用传统蚁群算法和改进蚁群算法对简单环境模型下的网球机器人进行路径规划仿真,其路径规划结果和算法收敛结果如图5所示。

(a) 传统蚁群算法

由图5可知,在简单环境模型下,改进蚁群算法所规划的路径长度明显比传统蚁群算法所规划的路径长度短,同时,改进蚁群算法在迭代28次就开始收敛,而传统蚁群算法在迭代52次才开始收敛,即改进蚁群算法对网球机器人的路径规划克服了收敛速度慢、易陷入局部最优的缺陷。

分别采用传统蚁群算法和改进蚁群算法对复杂环境模型下的网球机器人进行路径规划仿真,其路径规划结果和算法收敛结果如图6所示。

(a) 传统蚁群算法图6 复杂环境模型下仿真结果对比Fig.6 Comparison of simulation results under the complex environment model

由图6可知,在复杂环境模型下,改进蚁群算法所规划的路径长度依旧优于传统蚁群算法所规划的路径长度,同时改进蚁群算法在迭代42次开始收敛,而传统蚁群算法在迭代68次才开始收敛。

不论是简单环境模型,还是复杂环境模型,改进蚁群算法通过引入引导函数对转移概率公式进行改进,同时对信息素挥发因子进行自适应调节,使得改进蚁群算法的全局寻优能力增强,同时收敛速度加快,所规划的路径更优,路径规划所用时间大大缩短。

4 结论

网球机器人是开展外星球表面洞穴、裂缝勘探的重要工具,路径规划是网球机器人开发的核心技术。本文针对传统蚁群算法应用于路径规划存在的收敛速度慢、易陷入局部最优的缺陷,受到HOCAOGLU算法的启示,在转移概率中引入引导函数,同时采取自适应方法确定信息素挥发因子,从而对传统的蚁群算法进行改进,并将改进的蚁群算法应用于简单和复杂两种环境模型中进行仿真分析。仿真分析结果表明,改进蚁群算法相对于传统蚁群算法,所规划的路径大大缩短,同时算法收敛速度大大提升,对网球机器人的开发具有一定的参考价值。