APP下载

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

2018-07-11张晓玲王正存吴作君

中国石油大学胜利学院学报 2018年2期
关键词:模拟退火栅格蚂蚁

张晓玲,王正存,吴作君

(中国石油大学胜利学院 机械与控制工程学院,山东 东营 257061)

机器人路径规划问题是指,在已知机器人的起始和目的地坐标,明确环境信息条件下,找到一条能连接起始坐标和目的地坐标的最短路径。现有的机器人路径规划方法有蚁群算法(Ant Colony Algorithm,ACO)[1],神经网络算法[2],人工势场法[3],模拟退火算法[4]等。其中智能路径规划算法中的蚁群算法在机器人路径规划中被广泛应用。蚁群算法是由意大利学者M.Dorigo[5]在1991年提出的一种受自然界生物的自催化行为启发而产生的通用启发式进化算法。它采用正反馈机制、分布式计算方法,具有较强的优化能力和较强的鲁棒性[6],经常用来解决各种分布式环境下的组合优化问题。蚁群算法不足之处在于,寻优过程中当问题规模变大时,存在收敛精度变低问题。笔者采用改进的蚁群算法在搜索路径过程中,使用模拟退火算法迭代和蚁群算法进行搜索路径,利用回火条件,可以寻找到最优路径。

1 机器人运行环境建模

机器人路径规划首先需要对其运行环境或工作空间建模,考虑到栅格分解法具有精度高、方便实现等优点,因此选用栅格法对机器人环境进行划分。

设机器人的工作环境为二维平面上的方格区域,起始坐标和目的地坐标分别表示为S和T。每个栅格采用经纬度坐标进行位置标示,并以地图左下角的栅格S为机器人的起点,右上角栅格T为机器人的目的地。采用序号法对图1中每一个栅格进行编号,其中黑色方块表示环境中的障碍物,并采用八叉树表示路径搜索方向。

如果机器人在栅格地图上t时刻所在的经纬度为Lt(xt,yt),则在下一时刻的位置为Lt+1(xt+1,yt+1),此次移动长度dt为

(1)

假设从设置的起始点开始移动,要经过n步到达所设目标终点,则此次所寻找路径的长度为

(2)

用栅格法建立机器人的运行环境和工作空间模型后,下一步则需要结合合理有效的优化方法寻找所有路径中最短的路径。

图1 栅格地图模型

2 基于传统蚁群算法的路径规划

2.1 蚁群觅食分析

研究发现,每只蚂蚁觅食过程中在其行走路径上会留下一种为信息素的化学物质,一定范围内的其他蚂蚁能感觉到这种物质,且倾向于朝信息素浓度高的方向移动[7]。如果在某一条所走过的路径上被留下的信息素总量的浓度越高,则其他蚂蚁倾向选择这条路径的概率就会越大,因此有了信息素这种媒介物质,最终使得绝大多数蚂蚁选择最短的路径行走。

2.2 基于传统蚁群算法的机器人路径规划步骤

步骤1:将算法中各类参数初始化,如蚁群中蚂蚁数量、最大迭代次数等;

步骤2:在栅格地图初始化时,将机器人看做一只蚂蚁,蚂蚁运动时受到各路径上信息素浓度影响,根据每条路径上的信息浓度决定下一步方向。蚂蚁在t时刻当前位置为i,往位置j移动的概率Pij(t)为

(3)

式中,α,β为控制信息素和启发信息影响大小的参数;allowed是可选的前进方向集合。

步骤3:计算每个蚂蚁所产生的路径长度。

步骤4:更新信息素浓度。

τij(t+1)=ρτij(t)+Δτij(t,t+1).

(4)

(5)

式中,τij(t+1)为在第t次迭代时边ij上的蚂蚁释放的信息素;ρ为信息素维持因子;Δτij(t,t+1)为每个蚂蚁在某个边ij上留下所产生信息素之和。

步骤5:使所有蚂蚁执行步骤2,得到n条路径,找出所有路径中最短的可行路径,并按式(4)更新信息素矩阵。

步骤6:将当前迭代值与设定的最高迭代值进行比较,若超过限定值则终止循环迭代,否则回到步骤2,进入下一次迭代过程,直到满足该条件退出。

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

3.1 模拟退火算法

模拟退火算法是对金属退火过程的模拟,先用高温将金属融化,然后逐渐冷却,直到形成良好的晶体结构,即进入一种具有最小能量的状态[8]。模拟退火算法也可用于路径规划算法以避免陷入局部最优。

模拟退火算法迭代过程如下。

第一步:某个温度T下得到一个解(结合蚁群算法时,指用蚁群算法优化得到的解)。

第二步:若当前温度T下得到的解比前一时刻温度的解好,则采用这个新的解,否则转第三步。

第三步:计算温度T下接受劣解的概率。

(6)

其中,随机产生一个[0,1]区间的随机数X,如果X

从P的计算公式可以看到,随着温度T的上升,P的值是越来越小的,随着迭代的进行,接受劣解的概率下降,与自然界中晶体退火结晶的过程非常相似,从而实现了模拟退火算法。

3.2 带回火的模拟退火-蚁群算法路径规划步骤

采用模拟退火-蚁群算法进行路径寻优时,加入回火,回火机制是指当温度低于设定回火下限温度时,温度慢慢升温到回火上限温度。回火本质上是在一段温度范围内反复循环降温过程,使得当前解不断得到优化,可以得到更好的解,消除快速降温时产生的局部最优[8]。因此带回火的模拟退火-蚁群算法的迭代步骤如下。

步骤1:初始化算法中各类参数,如蚁群中蚂蚁的数量antnumber,迭代次数maxgen,冷却系数q,初始温度T0,回火温度下限Tmin,回火温度上限Tmax,回火次数Hmax等。

步骤2:设置蚁群算法的启发值和信息素浓度的初始大小进行模拟退火-蚁群算法的寻优。

步骤3:进行蚂蚁搜索,设置起点并根据式(3)计算蚂蚁向各个方向移动的概率Pij,并根据概率公式移动到新位置后再进一步计算下一步移动的概率并移动,重复这个过程直到搜索到所设定的目的地或者找不到目的地直接退出。

步骤4:计算目标函数,判断新路线是否优于原有路线,如果优于则接受新路线,转到步骤5;否则根据模拟退火机制按照式(6)计算接受较劣新线路(劣解)的概率,若概率满足条件则接受劣解,否则放弃。

步骤5:根据式(4)、(5)进行信息素浓度更新,并更新温度(模拟退火冷却过程,温度逐渐降低),判断是否满足回火条件(回火次数未达到或者温度低于最小回火温度),满足则进行回火,回火次数自增1。

步骤6:判断模拟退火算法迭代过程是否已经完成,若未完成则继续下一步迭代运算,相反,若完成则结束迭代循环。

步骤7:输出结果,算法运行结束。

4 仿真研究

首先随机生成一个15×15的栅格地图仿真机器人路径搜索的运行环境,然后基于同一地图,分别运用传统蚁群算法和带回火的模拟退火-蚁群算法进行机器人路径规划的仿真研究,得到结果如图2~5所示。

比较图2和图4的目标函数值(最优路径长度)可以看出,传统蚁群算法稳定在175左右,改进的带回火模拟退火-蚁群算法稳定在163左右。图3和图5的路径搜索线路也表明,相对传统的标准蚁群算法,本文提出改进后的优化方法查找到的移动路径明显更短。但通过观察图2和图4两种算法下的迭代次数,发现改进蚁群算法在迭代次数(63次)上稍逊于传统蚁群算法(57次)。为更合理地对比传统蚁群和改进蚁群算法,在不同大小的栅格地图上对两种算法进行多次仿真试验,结果如表1所示,分别记录了各自的迭代次数、最短路径值和平均运行时间。

图2 传统蚁群算法优化过程

图3 传统蚁群算法最优路径

图4 改进蚁群算法优化过程

图5 改进蚁群算法最优路径

栅格地图大小迭代次数传统算法改进算法最优路径长度传统算法改进算法运行时间/s传统算法改进算法 11×114574165.8155.25.96.3 15×155763174.9163.214.914.4 20×205379191.2188.233.731.0 25×254759199.6182.682.880.6 30×307479200.0208.4195.0193.3 35×359196248.1208.7274.9257.0 40×407474222.7199.1452.1438.0

对表1分析可得,改进算法在迭代次数上虽不占优势,略高于传统算法,但两种算法基于同一大小的栅格环境下实际运行时间相差无几,反而在栅格不断增多的情况下,改进算法的收敛速度要快于传统蚁群算法。从最优路径方面比较,除了在30×30大小的栅格地图上改进算法得到的最优路径相对传统算法稍长,其他结果均明显优于传统蚁群算法。因此,综合看来,在机器人寻找最优路径上,改进蚁群算法有一定的优越性。

5 结束语

针对基本的蚁群算法在解决移动机器人路径规划寻找最优搜索路径时存在收敛精度不够的问题,引入带回火的模拟退火原理处理蚁群算法得到的路径值,从而提出一种改进算法。最终的改进蚁群算法相比传统蚁群算法,具有更强的寻优能力,能够找到更好的机器人移动路径。

展开全文▼

猜你喜欢

模拟退火栅格蚂蚁
结合模拟退火和多分配策略的密度峰值聚类算法
基于邻域栅格筛选的点云边缘点提取方法*
基于A*算法在蜂巢栅格地图中的路径规划研究
基于遗传模拟退火法的大地电磁非线性反演研究
改进模拟退火算法在TSP中的应用
我们会“隐身”让蚂蚁来保护自己
蚂蚁
基于模拟退火剩余矩形算法的矩形件排样
不同剖面形状的栅格壁对栅格翼气动特性的影响
蚂蚁找吃的等