文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 移动机器人路径规划的一种改进蚁群算法
侵权投诉

移动机器人路径规划的一种改进蚁群算法

提出了一种复杂静态环境下的移动机器人避碰路径规划的改进蚁群算法。基于栅格法的工作空间模型,模拟蚂蚁觅食行为,并针对移动机器人的路径规划的需要,将一些特殊功能赋予常规的蚁群算法。为了避免移动机器人的路径死锁,在路径搜索过程中,当蚂蚁探索到一个死角时,建立了相应的死角表,同时用惩罚函数来更新轨迹强度。仿真研究表明:该算法能明显改善路径规划性能,并且算法简单有效。

第8期毛琳波,等:移动机器人路径规划的一种改进蚁群算法   999

流与相互协作,最终找到从蚁穴到食物源的最短路径)来求解TSP问题,这种算法称为蚁群算法。

用于寻找最短路径的蚁群算法来源于蚂蚁寻食的过程。人们经过大量的研究发现,蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递,从而能相互协作,完成复杂的任务。同时,蚂蚁在运动过程中,能够在它所经过的路径上留下这种物质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着该物质强度高的方向移动。这种物质在蚁群算法中称为信息素。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流选择出最佳路线,达到搜索食物的目的。

在蚁群算法中,蚂蚁k(k=1,2,…,m)在运动过程中,会根据各条路径上的信息素轨迹量决定下一步的转移方向,采用伪随机概率规则来进行当前位置的转移。定义q0为[0,1]之间的一个实数,q为一个随机产生的数,取值在[0,1]之间。则由下面的规则进行转移:

 j=

maxj∈#(Α

Β

i)[Σ(i,j)][Γ(i,j)],

ifq≤q0

J,

otherwise

(2)

J根据下式的概率Pk(i,j)来随机选择: Pk(i,j)=ΑΒ

6

[Σ(i,q)]Α[Γ(iΒ,

ifj∈allowed(i)q∈allowed(i)

,q)]0,

otherwise

(3)

式中:j为蚂蚁k所选择的下一个位置点;J为由式

(3)所决定的随机变量,与一个位置点对应;Σ(i,j)为位置i,j之间的信息素;Γ(i,j)为能见度的局部启发式函数,定义为Γ(i,j)=T di,j,T为一个常数,

di,j为位置i与j到目标点的距离;Pk(i,j)为蚂蚁k

由位置点i转移到位置点j的概率;Α,Β分别为信息素量与能见度启发函数的影响权值;allowed(i)为蚂蚁k在位置i处的可行领域(即与点i相邻且尚未被蚂蚁k访问过的位置的集合)。

随着时间推移,信息素轨迹将会逐渐挥发。每只蚂蚁从位置i移动到位置j时,都要进行一次局部信息素的更新。局部信息素的更新将改变边(i,j)上的信息素数量,从而使蚂蚁所选择的路径更加多样化。局部信息素更新规则如下:

Σ(i,j)=Υ Σ(i,j)+(1-Υ) Σ(i,j)(4) Σ(i,j)=Σ0 dj

(5)

式中:Υ为信息素的遗留程度;Σ0表示信息度轨迹强

度的一定常数;dj为蚂蚁k在本次搜索中已走过的路径长度;当Σ(i,j)<Σmin时,令Σ(i,j)=Σmin。

算法每搜索一次,都要进行一次全局信息素的更新。这将使蚂蚁更加趋向于选择最佳路径,更新规则如下:

m

Σ(i,j)=ΥΣ(i,j)+(1-Υ)6

Σk

i,j(6)k=1

Σki,j=

Q Lkmin,

if(i,j)∈tourdesiried

0,

otherwise

(7)

式中:Q为表示信息度轨迹强度的一定常数;Lkmin为

本次搜索中最短路径的长度;(i,j)∈tourdesired表示蚂蚁k所走的边(i,j)属于最短路径的集合;当Σ(i,j)<Σmin时,令Σ(i,j)=Σmin。2.2 用于路径规划时的改进策略

本文采用相向并行搜索算法进行路径搜索,即将所有蚂蚁分成相同数量的两组分别从起始点和目标点开始相向并行搜索路径,而且每组中的各只蚂蚁也是同时并行进行路径的搜索。采用相向并行路径搜索算法可以适应比较复杂的地形,有效地提高搜索效率。将蚁群算法用于路径规划中存在的一些问题,本文针对其中两个方面进行了改进。2.2.1 距离与方向启发式信息概率 在初始时刻,由于各条边上信息素都是相同的,这使得前面的位置转移选择规则的作用不明显,因此,建立距离与方向的启发式信息概率来规划初始时的路径。启发式信息概率定义如下:

 Υki,j=

(j,e)Κcyj

([(Maxdistist,

a(i),e-Dj,e)Ξ+Λ]Κ+cyj)

j∈all6

owed(i)

  j∈allowed(i)0, 

 otherwise

(8)

式中:Distj,e是从j点到目标点e的距离;allowed(i)是点i周围的可行区域;Ξ、Λ、Κ、c都为确定的常数;

yj=1- Ηj Π,这里 Ηj∈[0,Π],是指当前时刻和下

个时刻方向角改变的绝对值大小,定义如下:  Ηj= Ηj-Ηc = arctan[(yj-yi) (xj-xi)]-arctan[(yi-yc) (xi-xc)]

(9)式(8)决定了当依赖于距离和方向信息时,蚂蚁k从当前点i向下一点的移动概率。运用距离与方向启发式信息概率来搜索规划初始时刻的路径,可以使

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email