优化多步长蚁群算法求解机器人路径规划问题*

胡佳斌,王祥澍,张 琪,全瑞坤

(1.重庆大学 重庆大学—辛辛那提大学联合学院,重庆 400044；2.重庆大学 电气工程学院,重庆 400044)

0 引 言

机器人路径规划问题指在有障碍物的环境中,搜索规划一条从起点到终点距离最短的无碰撞路径。路径规划问题是机器人导航与控制的基础问题,在无人驾驶技术快速发展,智慧城市建设过程中,其作为一项核心技术得到更多的重视。现有的路径规划算法包括粒子群算法[1]、遗传算法[2]、人工势场算法[3]、模拟退火算法[4]和A*算法[5]。粒子群算法计算简单,但其后期收敛缓慢且易于局部最优解；遗传算法鲁棒性较强,能够得到全局最优解,但其所需计算量大,收敛过慢,局部搜索能力差；人工势场法计算量小,路径平滑,但易陷入局部最优；模拟退火算法局部搜索能力强,运算较快,但初始参数对结果影响较大,易陷入局部最优。A*算法效率高,操作简单,但其受到评估函数影响,后期计算量大且路径未必最优[6]。

蚁群优化(ant colony optimization,ACO)算法因具有正反馈,较强的鲁棒性,易于与其他算法结合等优点,一直受到了研究人员的广泛关注。但其存在搜索时间长,收敛慢,易被初始参数影响,易局部最优等问题。很多学者针对其缺陷进行研究和改进。文献[7]通过加大对迭代过程最优解的利用,加快算法的收敛速度,但是容易限于局部最优解；文献[8]以自适应信息素挥发系统改进信息素更新的方式,增强算法的全局搜索能力；文献[9]通过将蚂蚁每次固定移动一个步长扩大至多个步长,加快蚁群算法的收敛程度；文献[10]通过对于蚂蚁信息素初始的分配加快蚁群算法前期的收敛。

本文基于蚁群算法对机器人的路径规划问题进行求解。

将多步长蚁群算法与简化算子[4]结合,并对蚁群算法的启发函数以及信息素更新公式进行改进,从而加快蚁群算法的收敛速度,获得更优化的蚁群算法路径长度。

1 栅格法

路径规划的地图构建方法主要包括栅格法、几何法和拓扑法[5]三种方法,本文采用栅格法进行地图建模,使用20×20的栅格地图,每个栅格的边长为1,将机器人视为处于栅格中心,机器人只能从一个栅格中心移至另一栅格中心。

2 蚁群算法的基本原理

蚁群算法是模拟自然界蚂蚁运动中随机过程的一种算法。蚂蚁在移动过程中会留下信息素,信息素会随着时间的推移而不断挥发。多个蚂蚁经过的地方,留下的信息素浓度会不断增加,进而吸引更多的蚂蚁选择,形成正向反馈，最后,蚂蚁便会形成一条最优路径。

2.1 状态转移概率

在蚁群算法中,第k轮第m只蚂蚁从i点到j点的概率为

(1)

式中allowedm为可选节点；τij为i点到j点的信息素浓度；ηij为启发函数；ηij为j点到i点距离的倒数;α为信息素的启发因子,其值越大,信息素的影响就越大,随机性就越差;β为启发函数影响因子,其值越大,越容易陷入局部最优。

2.2 信息素更新

自然界的信息素会随着时间推移不断挥发,在蚁群算法中,每一轮所有蚂蚁完成自己的路线后,路径上的信息素浓度都会被更新

τij(n+1)=(1-p)τij(n)+Δτij

(2)

(3)

式中Q为信息素浓度常量,而Lk为本次蚂蚁迭代所经历的距离长度。

3 改进蚁群算法设计

传统蚁群算法存在收敛速度慢和路径会出现冗余拐点。因此,本文从信息素更新方法和增加规划路径平滑度方面对算法进行了改进。

3.1 改进的启发函数

初始的蚁群算法采用启发函数为

(4)

式中dij为机器人目前位置到下一个位置的距离。

此函数设计将导致机器人倾向于向正向移动,使算法陷入局部最优。故本文将启发函数改为

(5)

式(5)即只考虑机器人下一个可移动节点与终点的距离关系。这样机器人就更倾向于选择更靠近终点的节点,从而加快算法的收敛速度。

3.2 视野域与活动域[9]

传统蚁群算法中,机器人只能向周围8个方向移动,这种移动方法会导致最终规划路径存在大量冗余拐点。多步长蚁群算法中,其引入视野域与活动域的概念。机器人移动的可选节点为视野域范围内的可活动域[9]。如图1所示,此图为7×7的机器人视野域,机器人位于正中心的栅格中,节点{4,5,6,7,9,10,11,12,15,16,17,18,19,20,21,22,23,24,26,27,28,29,30,33,34,40}为机器人的可行域。机器人可移动方向增加,移动灵活性增强,全局搜索能力增强。

图1 多步长蚁群算法range为3时的视野域

3.3 简化算子[4]

简化算子可以减少规划路径冗余拐点,缩短路径长度。假设一条原始路径为P,将路径上的拐点依次记为P1,P2,P3,…,Pn,如图2所示，此图中n=4。

图2 未经过简化算子的路径

接着对路径进行简化循环,将简化起始点Ps(第一次循环时s=1)依次与下一个点Pk(s+2,s+3,...,n)相连并进行判断,若两点间无障碍物,则保留此点Pk。选择此次循环最大的k值,连接Ps与Pk,保留该条连线,同时将s更新为k-1,继续循环,直到s=n-2 时,停止循环。此时所有的点都进行过简化判断,简化过程结束。简化完成的路径如图3所示。

图3 经过简化算子后的路径

每次迭代的所有蚂蚁走完全程后,对所有到达终点的蚂蚁路径使用简化算子进行简化,并用简化后的新路径替代原有路径。经过简化算子处理的路径拐点更少,路径长度更短。

简化过程中,需要判断两点之间是否存在障碍,所需运算量较为庞大。为了简化计算,本文加入了黑名单机制。初始黑名单将设置一个400×400的矩阵,表示点与点之间的通行关系,1表示不能通行,0表示可以通行。简化过程中,先通过黑名单判断Ps与Pk之间是否可以连通。如果连通，则进行简化运算并更新这两点的活动域；反之且这两点不在黑名单内,则先更新黑名单再进行简化运算。黑名单机制在算法后期可以大量缩减计算量,增加运算速度。

3.4 差异化信息素更新

传统蚁群算法中,不管是对于优质解还是劣质解,信息素更新方法都对它们一视同仁。该方法既未排除劣质解的干扰也未能发挥优质解的指导作用,减慢了算法的收敛。因此,本文将会采用差异化的信息素更新方法。同时,因为简化算子的加入,新的算法将在对路径进行简化运算前后分别进行两次更新

(6)

此处引入新变量Lk,对于走过不同路径长的蚂蚁选择不同的Lk值,并且对所有蚂蚁走过的路径长度进行排序,并将排名记为n。本文中,第一次更新时,当n≤10时,Lk取3;当n∈[11,20]时,Lk取0.7；对于其他的n值,Lk都取0。第二次更新时,当n≤3时,Lk取10;当n∈[4,10]时,Lk取1；对于其他的n值,Lk都取0。差异化的信息素更新方法拉大了劣质解和优质解对算法影响的差异,增加了算法的收敛速度。

4 改进的多步长蚁群算法步骤

1)初始化本文算法的参数；2)根据起止点位置建立栅格地图,初始化地图信息素分布；3)基于参数和地图信息,设置机器人的视野域以及初始黑名单；4)每只蚂蚁寻找未走过的栅格,用式(1)～式(4)计算出每一个可选格子的概率,用Random函数进行下一步选择,不断重复此步,直至蚂蚁没有可选栅格或达到终点；5)根据式(6)更新本轮所有蚂蚁留下的信息素信息；6)使用简化算子对路径进行优化,更新每个格子的活动域与黑名单；7)根据式(6)更新简化算子后的蚂蚁留下的信息素信息；8)通过循环步骤(4)～步骤(7),直到达到最大迭代次数,并最终找出最优路径。

5 仿真对比分析

本文针对多步长蚁群算法的不足,做出了相应改变。并在CPU为酷睿i7—8750H@2.20GHz的电脑上,MATLAB R2018a软件进行仿真验证。机器人初始位置为(1,1),目标点位置为(20,20)。蚁群算法参数为：信息素影响因子α=1,激励函数影响因子β=7,初始邻域范围range=3,信息素挥发因子ρ=0.3,迭代次数k=100,蚂蚁数量m=50。

与传统蚁群算法以及文献[9]的多步长蚁群优化(multi-step ant colony optimization,MACO)算法进行对比,图4(a)是ACO算法的路径规划,图4(b)是结合了改进的启发函数,简化算子,差异化信息素更新的简化算子蚁群优化(simplified ant colony optimization,SACO)算法的路径规划,图4(c)是文献[9]的MACO算法的路径规划,图4(d)是在SACO的基础上添加视觉域与活动域形成的简化算子多步长蚁群优化(simplified multi-step ant colony optimization,SMACO)算法的路径规划。

图4 四种算法的路径规划

四种算法对应的长度分别是42.83,30.77,32.19和29.70。

为避免随机误差,表1中ACO,SACO以及SMACO的值均为10次实验的平均数。根据表1可以看出,SACO,MACO和SMACO与传统的ACO算法在收敛趋势,拐点数,最优路径长度均有明显优势,证明其三种算法均优于ACO算法。在路径长度上,SMACO算法与SACO算法小于MACO算法,证明改进的启发函数,简化算子,差异化信息素更新这三种改进措施的结合可以增强算法的全局搜索能力。此外,与SACO算法相对比,SMACO算法的拐点数有所减小,且SMACO算法与SACO算法再路径规划上相差小于0.5,证明视野域与活动域在不影响路径规划长度的情况下,本文算法在平滑度上起到了优化作用。图5所示为四种算法的收敛变化趋势。

表1 四种算法对比

图5 四种算法的收敛变化趋势

6 结 论

本文提出结合简化算子和多步长的蚁群算法用于解决机器人路径规划问题。简化算子可以减少规划路径的冗余拐点,进一步提升全局搜索能力；差异化信息素更新方法拉大优劣质解的差异,加快收敛速度。仿真实验表明：本文算法在收敛速度上不是最优,且参数增多更加难以控制,但是迭代收敛速度明显优于原蚁群算法,最终规划路径在三种蚁群算法中最短,全局搜索能力最强。同时,本文算法的路径拐点数最少,方便机器人的移动。