一种蚁群算法与自适应机制的路径规划算法优化

李奇才,舒远仲,洪宇轩

(南昌航空大学 信息工程学院,南昌 330063)

随着移动型智能设备在生产建设、国防工业以及生活应用等领域应用的越来越宽广,各个国家对机器人领域也更加重视起来。随着工作环境的不同以及工作环境中各种未知状况的出现,此时移动机器人的移动效率和安全行走则是重要问题,故移动型智能设备的路径研究则是重点之一,研究出高效的安全路径具有很大的价值和意义。然而,移动型智能设备通常是通过激光雷达和各种传感器对工作环境进行地图建模从而进行行进路径的规划,以最小的消耗来达到对工作区域的全遍历,要求移动机器人的覆盖率高且重复率,目前移动型智能设备的路径规划技术主流的几种算法有蚁群算法、遗传算法、生物激励神经网络、模糊推理法以及对各种算法的优化等等算法。

目前,蚁群算法在移动型智能设备对于行进路径的搜索技术上具有很高的效率性,蚁群算法是属于仿生学,根据蚁群出来进行觅食,在规定区域中寻找到最短且有效路径的搜索算法。蚁群算法在组合优化问题中显示出较强的优势,是一个增强型学习系统,具有分布式的计算特性,且具有较强的鲁棒性,易于与其他优化算法融合。近几年来,由于移动机器人的应用场景显著扩大,移动型机器人更具有市场,蚁群算法的工作效率更是被国内外许多学者做大量研究,也获得了一定的成功,另外,对于一些调度类问题、各类旅行商型问题、多机编排问题、电路优化以及网络路由等提供了解决思路。

文献[1]提出了一种基于精英策略排序的蚂蚁算法通过将路径排序靠前进行信息素的释放的排序实现了对移动机器人路径的有效搜索,但是当范围较大时,导致计算量也变大;文献[2]采用了改进的D*(D-star Lite)算法通过最小化rhs值来找到最短路径,递增式实现了移动机器人在存在动态障碍和未知工作环境的路径规划;文献[3]提出了对宽广和简单的场景等一种基于图搜索的方法,该算法能用相对较少的随机采样点来找到解,运算速度高和概率完备,但不是最优路径;文献[4]采用改进A*算法实现了静态环境下的路径规划,但目标点到达较慢达时容易造成大量消耗;文献[5]基于模糊推理逻辑提出的路径规划算法,面对运动过程中的鲁棒性的能与传感器感知系统中的“感知-动作”行为进行结合处理,此方法为移动机器人路径规划提供效率较高的解决思路;文献[6]提出了A*算法与人工势场法相结合的多层次混合算法以实现动态环境下的路径规划问题,但人工势场法在局部路径规划应用中无法较好地规划出局部最短路径,降低了整体运行效率;针对蚁群算法存在质量差和效率不高的问题,文献[7]提出了最优最差蚂蚁算法,通过抑制最优与最差路径信息量之间的差距避免了停滞现象并且收敛速度更快;文献[8]提出了基于堆排序的Dijkstra算法来选择最短路径从而实现了全局路径规划;文献[9]针对移动机器人在搜索时出现的过早收敛和停滞等问题提出了一种基于最大最小蚂蚁算法MMAS,该算法将移动机器人规划出的行进路径上留的信息素根据相应的公式设定其上下界,这样根据公式不断更新最优路径避免了蚂蚁在路径搜索的过程中易陷入局部最优的问题,而且提高了求解效率,但存在着前期信息素的缺乏等问题;文献[10-11]提出了用蚁群算法解决旅行商问题。故蚁群算法采用正反馈机制,是属于启发式概率搜索的方式,在用于路径规划时,根据释放信息素和分布式计算来不断的更新最优路径,快速的收敛且不易于陷入局部最优。

蚁群算法(Ant clony optimization,ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的方法,在移动机器人领域应用的非常广泛,并且对于移动型智能设备传统蚁群系统具有快速收敛的能力,但往往会陷入局部最优。并且蚁群算法在用于路径规划时,由于存在初始信息素的匮乏,并且需要较长的搜索时间和容易出现停滞现象。同时对于移动型智能设备在一些路径规划算法搜索后得到的实际行进路径,容易出现不符合移动机器人实际的运动轨迹以及蚁群算法前期信息素匮乏而导致收敛速度慢的缺点和问题。

针对此类问题,提出了一种自适应机制来建立新的自适应信息素更新策略,以提高移动型智能设备的最优路径的搜索能力,同时还提出了一种蚁群算法与自适应机制的路径规划优化方法来解决该问题,并且通过移动机器人进行实验证明本文提出的方法的具有很好的性能性。首先动态更新信息启发因子α、期望启发因子β以及信息素;然后,增加了自适应阈值来克服求解过程停滞,陷入局部最优解的问题,随着迭代次数的增加,阈值对蚂蚁寻优过程的影响不断减小,直至完全由信息素和启发信息来指导蚂蚁寻优;最后,对蚁群算法生成的路径进一步优化处理,使其更符合移动机器人在实际环境工作中的运动轨迹。实验的结果表明,所提出的方法能有效的解决该问题。

1 环境建模

栅格法对环境地图进行建模有较高的效率和准确度,尤其是移动机器人在工作区域内进行环境建模较多。故本文使用文献[12]的栅格法来建立机器人的工作环境地图,如图1所示。以单元栅格的形式描述工作环境的信息,存储环境信息。栅格法对环境地图建模通常是以不超过自身体积大小为一个单元栅格,环境中每一个单元栅格都有不同的状态来表示环境中对应点的环境信息,故将整个建成的工作环境地图转换成具体信息的数字地图。在对工作环境建完图后,机器人在行进过程中通过激光雷达和传感器感知周围环境的信息,有障碍物的地方标记为障碍栅格,即不能通过,无障碍物可通行的地方标为自由栅格,蚂蚁所走的节点即为自由栅格的中心。建立栅格地图主要过程为:建立一个m×m的栅格矩阵存储环境信息,将无障碍物的地方对应的单元栅格标记为0,有障碍物的地方对应栅格标记为1。本文采取栅格法建模后的环境图来说明,如图1所示。图1中黑色栅格表示有障碍物的地方,空白格为无障碍物可通行的地方,对一些体积没有占满一个单元栅格的障碍物进行膨化处理,直至占满一个单元栅格为止,这样方便机器人可以在工作环境栅格地图上简化成一个点行进运动,在可通行自由栅格区域中搜索一条有效且最短的路径。

图1 栅格图

2 蚁群算法的改进

2.1 传统蚁群算法

传统的蚁群算法是根据蚂蚁在出洞觅食搜寻到最短路径后,供后来的蚁群沿最短路径到达目的地得到的启发,在1991年由Marco Dorigo等提出。在研究的过程中,他们发现蚂蚁在出来觅食时,会在它们经过的路上留下信息素,用于进行信息的传递,并且蚂蚁走过的路径越长,该路径上留下的信息素因为挥发的多导致信息素浓度变低,相反越短的路径上面的信息素挥发的时间短导致该路径上的信息素浓度高,更易于引导后来的蚁群来走最短的路径。根据此提出一种基于正反馈机制的蚁群算法。这种仿生算法是一种多群体的智能搜索算法,达到了整体最终走的是搜索到最优路径的目的,蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,故此类算法应用在集成电路设计、数据挖掘和调度类问题等领域比较多,近几年来,经过不断的优化和改进,应用的领域也逐渐变多,但是同时也存在收敛速度慢,容易陷入局部最优(Local optimal),而且存在前期缺乏信息的问题和在移动机器人的研究中,不符合机器人实际的运动轨迹等缺点。

2.2 蚁群算法的改进方法

步骤1 输入初始的信息素参数,由初始得到的信息素构成信息素矩阵,然后选择好蚂蚁开始的起点和到达的终点,设置好算法数学公式中的参数。设置的参数包括算法进行迭代总次数N,每次迭代的蚂蚁总数M,蚂蚁搜索时留下信息素浓度的强度系数Q以及信息素的挥发系数ρ,初始的信息启发因子α和初始的期望启发因子β。

步骤2 在传统蚁群算法中,当蚂蚁需要从地图中的某个节点转移到其他节点是由该节点到其他节点路径上的信息素量的大小决定的,所以将蚂蚁置于起点,根据各个节点的信息素,计算在t时刻,蚂蚁k从节点i转移到节点j的当前状态转移概率，即

(1)

步骤3 利用公式λt=1-e-(t2/Tmax)获取当前自适应阈值,其中,λt为当前自适应阈值,t为当前时刻,Tmax为预设的迭代时间;

步骤5 更新目前为止最优路径以及该最优路径的长度。

步骤6 重复步骤3到步骤6,直到蚂蚁达到终点。

步骤7 重复步骤3至步骤7,直到这一代的M只蚂蚁全部遍历。

步骤9 重复步骤3～步骤9,直到迭代完成;

步骤10 对生成的路径进行优化处理,使得路径转折处变少,更加贴近移动机器人实际行走情况,在栅格面积足够小且栅格数足够多的情况下,经过优化处理的路径是平滑的曲线;如图2所示,dot(i)为路径中的节点,R=dot(i),imax为路径节点总的数量。

图2 路径优化处理

路径优化处理步骤如下：

步骤1 初始化处理,令R为蚁群算法进行搜索路径的初始节点。另外,蚁群算法搜索到的路径为依次首尾相连的若干个线段。

步骤2 依次将节点R与其后不在同一条线段的所有节点连接,指定相连的另一个节点为Sf,f为非零自然数。

步骤3 判断节点R与另一个节点Sf组成的路径是否穿越了障碍栅格,如果所有的R与Sf组成的路径中都经过障碍栅格,则令R为当前节点的下一节点,返回步骤2,否则执行步骤4。

步骤4 将绕过障碍栅格的R与Sf组成的路径的中间连接节点删除,判断Sf节点是否为终点,若是则执行步骤5,结束算法,否则令R为当前节点的下一节点,继续执行步骤2。

步骤5 依次连接没有被删除的各节点形成新路径代替蚁群算法生成的路径。

所提的算法中的更新机制使移动机器人前期缺乏信息素的情况下,可继续通过更新机制来大大的提高对未知环境的自适应性的准确性和有效性,加快收敛速度和最优路径的搜索速度。

算法流程如图3所示。

图3 算法原理流程图

3 实验分析

为验证本文所提出的改进的自适应蚁群算法在移动机器人进行路径规划的可行性、有效性,基于移动机器人模型和RobotStudio6.04进行实验,运行环境为:WIN10(64bit),CPU为Core i5-650,内存为8 GB,实验环境划分为10×10的3D栅格环境,障碍物如图1所示设置。将从以下几点进行实验验证:

1) 引入参数和设置节点;

2) 进行平滑处理；

3) 在相同的实验环境中,将本文所述的算法得到的结果与传统蚁群算法[14]以及文献[15]中蚁群算法得到的结果进行比较。

3.1 引入参数连接节点

为了验证本文所述的算法的自适应性和效率性,对实际环境中某一区域,采用复杂环境地图进行实验。在本次实验中,蚁群算法的基本参数范围为:信息启发因子α∈{0.4,0.8,1,1.2,1.4},期望启发因子β∈{1.2,…,15},信息素强度Q∈{1,2,…,20},信息素挥发系数ρ∈{0.1,0.2,…,0.9},最大迭代次数N=100,蚂蚁总数M=50,引入的自适应阈值R∈{30,40,50,60,70,80,90,100},初始值R=30。每次实验改变公共的一个初始设置的参数,其他参数不变,为了使改变的参数取值对工作环境适应性更强,本文在实验环境中对每个参数的仿真进行10次实验取均值。经实验结果可知,α=1,β=3,Q=5,ρ=0.5,迭代次数在80附近最优。

同时,以节点R与其后不在同一条线段的3个节点进行连接,如图4所示。通过以下10×10的栅格环境地图详细说明以上优化处理的过程。

图4 优化过程

如图4a)所示，令R为蚁群算法生成的路径中的第一个节点，依次将节点R与其后不在同一条线段的节点S1、节点S2以及节点S3连接，判断RS1、RS2以及RS3组成的路径是否穿越了障碍栅格，如果RS1、RS2以及RS3组成的路径都经过障碍栅格，则令R为当前节点的下一节点，重复执行以上步骤，否则继续向下执行，如图4a)所示，RS1、RS2以及RS3组成的路径都经过障碍栅格，所以令R为当前节点的下一节点，重复执行以上步骤，如图4b)所示，RS1、RS2以及RS3组成的路径仍然都经过障碍栅格，继续令R为当前节点的下一节点，重复执行以上步骤，直到如图4c)所示，RS1组成的路径未经过障碍栅格，RS2以及RS3组成的路径仍然都经过障碍栅格，将绕过障碍栅格的RS1组成的路径的中间连接节点删除，即图4c)中所示的C1节点删除，删除后的路径图形如图5所示，此时，判断图4d)中S1节点是否为终点，若是则依次连接没有被删除的各节点形成新路径代替蚁群算法生成的路径，结束算法，否则继续令R为当前节点的下一节点，即令R为图中所示的S1节点，继续重复执行执行上述步骤，直到到达最后一个节点。最终优化后的路径如图5所示，图5的路径较为平滑，属于肉眼观察效果，实际中仍为折线，但是在栅格面积足够小且栅格数足够多的情况下，经过优化处理的路径是平滑的曲线，输出最优路径。

图5 效果对比图

本文所述的算法与使用了传统的蚁群算法文献[14]和文献[15]中自适应蚁群算法分别在进行了仿真实验，同时比较了3种算法的效率，3种算法的实验结果如图5所示。针对运动轨迹，本文提出的算法使得机器人在行进过程中的实际运动轨迹的效果更符合真实情况。本文算法和传统蚁群算法[14]、文献[15]中所述的自适应蚁群算法的适应度值和迭代次数进行对比，如图6所示。在100次重复性的进行运算之后，遍历完整个实验环境后，得到最短的整体路径距离、迭代次数和收敛时间，结果如表1所示。

图6 3种算法的适应度值与迭代次数关系对比

表1 实验环境中3种算法仿真结果

3.2 收敛分析

在图6中本文所述的改进的自适应蚁群算法和传统的蚁群算法[14]、文献[15]中所述的自适应蚁群算法在能搜索到最优解的同时收敛速度提高了。表1表明,本文所述的算法比传统蚁群算法路径长度缩短33.8%,比文献[15]中所述的自适应蚁群算法缩短8%左右。上述实验仿真表明,本文所述的改进的自适应蚁群算法对未知环境适应性更强,并且收敛速度更快和迭代次数更少可寻找到最短路径。同时,对于前期信息素匮乏的情况下,本文所述的算法对于复杂和未知的环境有更强的适应性,且可以有效避免陷入局部最优。

3.3 实验认证

基于本文所述的算法,采用VC++2018开发语言,研发了面向车站、机场以及仓库等大型公共空间的清洁机器人路径规划软件模块和装置,并在市场上得到应用。实验场景为一个办公室,在RobotStidio软件中采用本文所述的改进的自适应蚁群算法对环境中的清洁机器人进行路径规划,通过激光雷达自主规划的路线如图7所示,最终达成预期效果。实验结果表明,本文所提的算法生成的路径更加符合移动机器人在行进过程中的实际运动轨迹,如图7所示,直观的展示了机器人运行本文提出的改进算法后在办公室中的运动场景。

图7 实验过程

综上所述,通过实验和仿真效果来看,验证了本文算法在机器人进行路径搜索时,具有自适应性和稳定性,在遍历整体环境时,更快的规划出最短路径,同时实际运动更符合移动机器人实际的运动轨迹。

4 结束语

针对目前蚁群算法在求解移动机器人的路径规划时,存在不符合移动型智能设备在运动过程中的实际运动路线、收敛速度慢、易陷入局部最优解和前期存在信息素匮乏等问题,本文基于移动机器人的应用提出了一种新的更新自适应机制来建立新的信息素改进策略,增加了自适应阈值和优化处理蚁群算法生成的运动轨迹,使生成的路径更符合机器人实际的运动路线,以及提高了移动机器人在面对未知环境的行走更加高效且适应性更好。本文所述的算法在RoboStidio中进行验证,结果表明了本文所述的算法有效性,并且在实际工程应用中,本文提出的方法能够达到实际需求。