基于改进蚁群算法的自主移动机器人三维路径规划研究

智能自主移动机器人在军事任务、航天探案、交通运输及物流系统等领域广泛应用,实时地形环境智能自主机器人路径规划确保机器人在复杂环境中找到起始点到目标点的较优化路径,保证机器人安全高效地执行任务,是机器人领域的一个重要研究方向和热点。国内外学者已经在智能自主移动机器人的路径规划算法等领域取得了丰硕的研究成果,如启发式A*算法、人工势场法(APF)、快速随机搜案树法(RRT)、随机路标法(PRM)、遗传算法和蚁群算法等,这些方法各有优点,也各自存在一定的局限性。启发式A*算法虽然在理论上路径规划时间最优,但由于栅格的地图随着搜索空间的增加,其搜索节点会指数级增加导致计算数据庞大,搜案路径速度变慢(”;人工势场法(APF)虽然算法简单易实现,但由于势力场的原因导致在障碍物相近时无法发现路径或目标点,而且当位姿环境比较复杂,障碍物数目多时容易陷入局部极小;快速随机搜索树法(RRT)采用随机采样规划方法,不需要预处理,搜索速度快,尤其是高维空间优势明显,但是该算法本身具有随机性,产生的路径具有绕远或者明显的拐角,使得路径曲折4;随机路标法(PRM)搜索路径受到采样点数目限制,无法覆盖整个自由空间,且分布随机,所以得到的路径可能只是次优路径5-7;遗传算法容易收敛到局部最优解,但对新空间的探索能力有限;蚁群算法是一种自发的寻优算法,它有全局最优、正反馈作用以及鲁棒性比较强等优点,但由于蚊群算法中初始信息素匮乏,蚊群算法一般需要较长的搜索时间但收敛速度慢、易陷入局部最优。

文献[13]提出一种AdaDelta算法,其基本思想是用一阶的方法近似模拟二阶牛顿法,替代人工设置学习率,找出梯度下降方向,对低频参数进行大幅度更新,而对高频参数进行小幅度的更新,所以AdaDelta算法非常适合处理稀疏数据,大大地提高了随机梯度下降(SGD)的鲁棒性,能够很好地改善蚂蚁算法初始信息素不足这一问题。

本文针对蚁群算法初始信息素匮乏的缺点,引入AdaDelta算法来增加信息素较多路径的选择概率,生成初始信息素的分布,来避免算法陷入局部最优,从而提高算法的性能,同时通过将目标函数离散化来实现路径规划,提高时间效率和求解精度。

1基于改进蚁群算法的路径规划

蚁群算法(ant colony optimization,ACO)是受自然界中蚂蚁搜索食物行为启发的一种群智能优化算法,算法由若干个蚂蚊共同构造解路径,通过在解路径上遗留并交换信息素提高解的质量,进而达到优化的目的。

在蚊周系统模型中为:
基于改进蚁群算法的自主移动机器人三维路径规划研究
式中,Q表示信息素的强度,L以表示第k只蚂蚁在一次成功的完整路径中所走的路径长度。

在蚁密系统模型中:
基于改进蚁群算法的自主移动机器人三维路径规划研究
蚁量模型和蚁密模型都是在完成一步动作之后,利用局部信息更新的信息素,而蚊周系统是在蚂蚁完成一个完整的路径之后再更新路径上的信息素,是利用的整体信息。在求解旅行商问题时,蚁周系统算法模型明显好于其他两种算法,因此通常是采用式(1)来作为蚊群基本算法的模型。

1.1Adadelta算法

梯度下降法是最常用且有效的优化算法,常见的梯度优化算法有随机梯度下降(SGD)、Momentum、Nesterov、adagrad、adadelta等方法,上述方法学习率的收敛曲线比较如图1。SGD即随机梯度下降,其更新方向完全依赖于当前的测量,因而其更新不稳定,随即引入Momentum、Nesterov方法使得学习率更新的时候在一定程度上保留之前更新的方向,同时利用当前梯度微调最终的更新方向,在一定程度上增加稳定性,从而学习地更快,并且还有一定摆脱局部最优的能力,但上述的方法所有参数都使用了同一个更新速率,Adagrad就是针对这一问题提出的,自适应地为各个参数分配不同学习率的算法,但Adagrad算法存在学习率是单调递减的,训练后期学习率非常小的问题。
基于改进蚁群算法的自主移动机器人三维路径规划研究
Adadelta算法是基于Adagrad算法的一种梯度优化算法,不依懒于全局学习率,对低频参数进行大幅度更新,而对高频参数进行小幅度的更新,因为这一点Adagrad算法非常适合处理稀疏数据,基本思想是用一阶的方法,近似模拟二阶牛顿法,大大地提高了随机梯度下降鲁棒性,其基本思想如下:
基于改进蚁群算法的自主移动机器人三维路径规划研究
1.2改进蚁群算法

蚁群算法有着搜索速度比较慢,比较容易陷入局部最优的缺点,要想改善蚁群算法的性能,必须解决两者之间的平衡问题,引进梯度下降优化算法Adadelta,从以下三个方面改进蚁群算法。

1)增加初始信息素选择概率。修改蚂蚁到下一个栅格地图低势场位置的概率。基本的蚁群算法选择下一栅格地图低势场位置主要取决与信息素的浓度以及两个栅格地图位置之间的距离,而信息素浓度与规划路标点之间距离长度的参数设置只能凭借经验,所以前期的工作量比较大,寻优过程缓慢,容易陷入局部最优,引入Adadelta算法梯度概念,利用梯度来改变栅格地图位置蚂蚁选择的概率,从而来增加栅格地图路标位置选择的随机性。
基于改进蚁群算法的自主移动机器人三维路径规划研究
2)改进信息素更新规则。在基本的蚁群算法中,当种群完成一次循环之后,所有的蚂蚁都会进行信息素的更新,不能充分体现出最优路径的指导作用,导致一些劣质的信息会干扰下一代的种群搜索,有的蚂蚁的信息素经过正反馈的作用之后,有可能会导致蚁群算法搜索过程陷入早熟的现象,即容易陷入局部最优解,引入Adadelta算法,利用参数的变化来对蚁群算法中的信息素更新,在每次循环中,加入更多的启发信息,引入梯度变化量参数,在蚂蚁搜索的不同阶段适当的改变参数,来改变信息量的释放,从而大力更新有用的信息素,摒弃无效信息素。如式(10)所示,△Xt是梯度更新参数,k为加权系数。
基于改进蚁群算法的自主移动机器人三维路径规划研究
3)动态的调整信息素挥发系数。在全局路径规划中,信息素挥发系数ρ的作用是母庸置疑的,当搜索环境相对比较复杂时,信息素挥发系数ρ过大会增加正算法的正反馈作用,ρ过小会增加搜索最优路径的时间。为了避免随着时间和循环次数的增加,算法陷入局部最优,提出信息素挥发系数自适应化,如公式(11):
基于改进蚁群算法的自主移动机器人三维路径规划研究
1.3改进蚁群算法实现

基于改进蚁群算法路径规划的具体实现步骤描述如下:根据环境构建模型,初始化系统的各个参数。将所有的蚂蚁放在起点ST,蚂蚁k(k=1,2,3,…m)从起点出发,并捋初始起点放在禁忌表tabuk中。

根据选择概率公式(9)来选择下一个栅格地图合适势场位置,当蚂蚁k到达一个规划路标点后,上一个环境路标点就添加到禁忌表tabuk中。再判断蚂蚁是否到达了终点T,如果没有,就一直搜索下去,直到到达终点T。若某个蚂蚁陷入局部最优,停滞不前,则把它踢出搜索群。

利用公式(10)进行信息素更新。迭代次数N=N+1,若Nmax,清空禁忌表tabuk,继续循环搜索;若算法的迭代次数达到Nmax,则输出当前群体中最短的路径长度,输出最短优化路径。

2仿真实验及其分析

为验证基于Adadelta算法的改进蚁群算法的正确性和可行性,本文采用MATLAB对三维实时地形环境及势场建模,对比分析了人工势场法、传统蚁群算法和改进蚁群算法三种方法下的三维路径规划效果。

将自主移动机器人放置在20km*20km*2km的随机三维环境中,设定蚂蚁种群个数为m=50,最大迭代次数为Nmax=101,起始点分别为绿色点ST(O,10,1)和红色点END(20,0,0),三维路径规划环境建模如图2所示,其三维环境投影势场分布如图3所示,图中蓝色逐渐变为红色表明地势高度由低到高。
基于改进蚁群算法的自主移动机器人三维路径规划研究

基于改进蚁群算法的自主移动机器人三维路径规划研究

基于改进蚁群算法的自主移动机器人三维路径规划研究
其三维环境下规划路径长度对比如图4所示,黑色是人工势场算法下的路径规划,可以看出由于势力场的原因导致在该算法下无法发现路径抵达目标点,蓝色线是基本蚁群算法下的规划路径(长度为131.5km),红色是改进后蚁群算法的规划路径(长度为126.3km),图5为规划路径的势场投影。
基于改进蚁群算法的自主移动机器人三维路径规划研究

基于改进蚁群算法的自主移动机器人三维路径规划研究
图6为最佳个体适应度变化收敛曲线对比。适应度值为在当前迭代次数下的次优路径,随着迭代次数的增加,进而发现全局最优路径,迭代次数越少,表示算法的收敛速度越快,适应度值越小,表示规划路径越短。

3结束语

由于基于Adadelta算法改进的蚁群算法增加了初始信息素随机性,动态的调整信息素挥发系数,使得算法的收敛速度明显增加,迭代次数约为传统蚁群算法的2/3。可见改进后的算法在得到较优路径之外,收敛速度也明显提高。

基于改进蚁群算法的自主移动机器人三维路径规划研究-AGV吧
基于改进蚁群算法的自主移动机器人三维路径规划研究
此内容为付费资源,请付费后查看
20积分
付费资源
© 版权声明
THE END
喜欢就支持一下吧
点赞10 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容