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

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

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

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

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

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

1000   华东理工大学学报(自然科学版)第32卷

蚂蚁在尽可能不改变方向的状态下较快地向目标点移动。

2.2.2 “死锁”问题求解 “死锁”状态是指机器人失去运动可能的状态。与之相类似,在本文的路径规划算法中,可能会出现“路径死锁”的情况。路径死锁是指蚂蚁在搜索路径的过程中,进入被障碍物包围的位置点,从而丧失继续运动的能力。针对这一情况,采用建立死角表和惩罚函数来防止其发生。所谓死角即为使蚂蚁产生路径死锁的位置点,如图2所示。在路径搜索过程中,当遇到死角时,将其存入死角表,并返回原位置重新选择下一个点。由于局部信息素的更新,该死角周围边上的信息素不断增强,致使蚂蚁在下一次迭代中很容易再次重复选择该死角周围的路径。如果继续这样循环下去,会延缓找到最短路径的时间,甚至找不到最短路径。为了防止出现这样的局面,采用惩罚函数使蚂蚁能够摆脱其束缚。在遇到死角时,将原来的局部信息素更新公式用惩罚函数代替。惩罚函数定义为:

Σ(i,j)=ΚΣ(i,j),0<Κ<1(10)

该惩罚函数保证了死角周围路径上信息素的减少,使得蚂蚁在下一次搜索中不再选择该路径,从而避免了遇到死角时形成的路径死锁情况,同时也提高了最优路径的搜索效率。

图2 死角说明图

Fig.2 Illustrationofdead2corner

2.3 算法步骤

基于改进蚁群算法的移动机器人路径规划算法描述如下:

  (1)初始化搜索次数N=0及各条边上的信息素Σ(i,j)=C(常数),将两组蚂蚁各m只分别置于

起始点和目标点。

(2)当N=0时,两组中的蚂蚁根据移动过程中各点周围的距离与方向的启发式信息概率式(8)选择下一个位置点;当N>0时,综合考虑伪随机概率式(2)和距离与方向的启发式信息概率式(8)选择下一个位置点,选择完毕后,按照式(4)进行局部信

息素的更新。

(3)检查两组中是否有蚂蚁相遇或者到达目标点,如果没有,转步骤(2)继续选择下一个位置点;否则转步骤(4)。

(4)若两组中有蚂蚁相遇,则连接相遇蚂蚁所走的路径,计算其长度;若有蚂蚁到达目标点,则计算到达目标点蚂蚁所走路径的长度。将本次搜索获得的最短路径与历史最短路径进行比较,如果优于历史最短路径,则取代历史最短路径,并保存其路径上各点序列号。

(5)按照式(6)进行全局信息素的更新。

(6)令N=N+1,若N<NC(预定的搜索次数),则重新将两组蚂蚁各m只置于起始点和目标点,转步骤(2);否则输出最优路径,算法结束。

3 仿真实验

为验证算法的有效性,本文做了大量的仿真实验,分别考虑了具有任意障碍物和大小不同的工作空间。图3显示了在10×10环境下遇到路径死锁情况时,采用惩罚函数前后搜索到的路径。未采用惩罚函数时,由于局部信息素的更新,使蚂蚁在死角(1,

(a)

(b)

图3 具有“死角”时两种算法规划的路径比较

Fig.3 Comparisonofthepathsplannedbytwoalgorithms

in“dead2corner”

上一页第4页

你可能喜欢

热门文档

相关文档

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