机器人路径规划问题的蚁群优化算法

机器人路径规划问题的蚁群优化算法

艳1,包啓立2

(1.皖西学院计算机科学与技术系六安2370122.深圳大学管理学院深圳518060)

【摘要】:研究了机器人在静态障碍物环境下的路径规划问题,根据问题模型的特性设计了一种蚁群优化求解算法。该算法利用前一轮选择的路径对可行解的信息素进行相应的调整,再按转移概率选择路径,经过多次迭代搜索得出最短路径,已达到对机器人的路径优化。

【关键词】:路径规划,蚁群优化算法,路径优化

0.引言

机器人的路径规划问题是人工智能研究的一个重要方面,在机器人技术迅速发展的今天,路径规划的研究作为机器人行动的基本问题正被人们更广泛地重视起来。目前已经有不少关τi(x,y):=τi(x,y)ρ+△τkj*(x,y)(2)于这方面的研究了,使用的求解方法有神经网络、遗传算法和人工试场等。路径规划指的就是移动机器人在有障碍的环境中,寻找一条从起点道终点的路径,这条路径不仅能使机器人障碍,而(3)

[1]

且要在一定指标下如距离、时间、能量等尽可能的优化。

其中ρ[0,1]表示信息素残留系数;△τkj*(t)表示蚂蚁引起的由于蚁群等智能优化算法的日益兴起,现在有很多人开始

使用蚁群、粒子群等算法来求解一些以前解法存在明显不足的路径上的信息素量的增加;S集是记录下来的蚁群搜索到的所问题。本文就是针对在静态障碍物环境中,通过蚁群优化算法在有路径;mini∈sdisti是经过i点且路径方向选择相同中的最短路起点与终点之间选择最优路径,并由此确定机器人路径规划中径的总长度。每一步的基本方向选择。3.2转移概率的计算

在搜索路径的过程中,蚂蚁会根据路径上的信息素的多寡1.环境描述

我们这里假设机器人在行进中是能够在起点处就探测到自来选择运动的方向。蚂蚁k要从i点选择方向继续移动,根据文己与静态障碍物的距离,而且静态障碍物的形状为规则矩形,且献[5]其移动概率可使用如下公式进行计算:所摆放的方向是一致的。这样我们在机器人每一步的方向选择上只需用上、下、左、右来表示四个方向。我们将机器人的起点二维坐标记为(0,0),将终点坐标记为(1,p),p值由两点确定的矩(4)形区域中长宽比例进行计算,这样才能确定两个方向上的路径

式中τi(x,y)表示通过点i的同一方向上的信息素值;ηi(x,y)计算时比例为1:1。

定义三维变量τ(x,y)表示某点i的信息素,其中(x,y)表示是前一轮迭代后记录下的通过点i路径的总路径长度的倒数,(0,0)和(1,p)这个矩形坐标区域的某点的位置,而τ(x,y)则表表示蚂蚁保持前一轮搜索到的路径的期望程度。参数α(0≤α≤示对应这一点的信息素的值。1)表示信息素对路径选择的重要性。β(0≤β≤1)就是作为启发因

静态障碍物的位置用四维变量A(x,y,c,k),其中(x,y)表子来调节局部搜索相对于信息素的重要程度。示此障碍物离起点(0,0)点最近的一点,而c,k分别表示该障碍3.3算法步骤物的长度(对应x方向)和宽度(对应y方向)。Step1.初始化:

(1)定义参量和变量,给相关参变量赋初值。2.算法基本原理

蚁群算法是由意大利学者M.Dorigo[2-3]及其导师Colorni于(2)初始化m个蚂蚁的数据,对蚂蚁每一步的方向选择进1991年在其博士论文中提出的一种模拟蚂蚁群觅食过程寻求行随机选择,以获得初始化路径,根据式(1)初始化信息素的值。最短路径的群体智能算法[4]。蚂蚁没有视觉,它们在觅食过程中Step2.循环变量n初值为1,根据式(2)和(3)式更新信息素无法依靠眼睛记住食物和巢穴的位置,所以它们会在其走过的的值;路径上留下信息素,这样不仅可以给路径做标记,使自己不致于Step3.根据3.2中的转移概率求出新一轮可行解;迷失方向,还可以为其他蚂蚁对路径的选择提供线索。蚂蚁可以Step4.根据m个蚂蚁得到的路径总长度求最短路径,更新通过信息素在巢穴到食物源之间找到最佳路径,也可以说最短当前最优解并输出;路径,因为当一些路径上通过的蚂蚁越来越多时,信息素也会越Step5.当n不满足循环结束条件时(循环的停止条件为相来越多,而在相同的时间区间内较短的路径会有更多的机会被邻两次循环搜索中最优解的差别小于0.001),令n:=n+1,转到选择,因此较短路径上的信息素浓度就会高于较长路径上的,其Step2;否则执行Step6;他蚂蚁察觉到后就会选择信息素浓度较高的路径觅食,逐渐寻Step6.输出Step5中得到的最优解。找到最优路径。4.结束语

本文只是针对了静态的障碍物进行研究,在具体计算中对环境3.求解算法

做了很多假设,影响了解法的普适性;而且由于篇幅有限,没有3.1信息素的计算及调整

在未生成任何信息素值时,对于蚂蚁当前的方向可以进行列出仿真算例。以后将逐渐把各个假设去除,加入动态障碍物,随机选择。使得环境更加动态化,改进算法以增加算法的通用性。

蚂蚁k(x,y):

?(x,y)?Q参考文献:(1)其中τk0(x,y)y)坐标点上留下的1.刘天孚,程如意.带精英策略和视觉探测蚁群算法的机器人路径规划[J].

(下转第86页)

信息素量,Q为常数。

迭代过程中要对全局信息素进行更新,在第j次迭代过程中i点上信息素的更新方法如下:

Word文档免费下载Word文档免费下载:机器人路径规划问题的蚁群优化算法 (共2页,当前第1页)

机器人路径规划问题的蚁群优化算法相关文档

最新文档

返回顶部