基于蚂蚁算法的移动机器人路径规划

《基于蚂蚁算法的移动机器人路径规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2003年3月重庆大学学报MaT．2oo3第26卷第3期JournalofChongqingUniversityVo1．26No．3文献编号：1000—582X(2003)03—0049—03基于蚂蚁算法的移动机器人路径规划董玉成，陈义华(重庆大学数理学院，重庆40oo44)摘要：蚂蚁算法是近几年问世并逐步引起重视的一种新的全局优化仿生算法，它模仿昆虫王国中蚂蚁搜索食物的行为特征，是一种通用型随机优化方法。移动机器人在进行工作时，往往要求根据某一准则，在工作空间沿一条最优(或近似最优)的路线行走。因此首先对

2、移动机器人的规划空间进行链接图表示，然后采用F0rd算法求出移动机器人的初始路径，最后运用蚂蚁算法对初始路径进行优化，取得了较好的效果。关键词：移动机器人；路径规划；链接图；Ford算法；蚂蚁算法中国分类号：O221’．7文献标识码：A移动机器人在进行工作时，往往要求根据某一准2)规划环境的边界及障碍物可用凸多边形描述；则(如行走路线总长度最短、能量消耗最少等)，在工3)适当缩小规划环境的边界，适当扩大障碍物的作空间沿一条最优(或近似最优)的路线行走，人们提范围，机器人用点来表示，即所谓。点机器人”。出了路

3、径规划的可视图法、人工势场法等。但是，可势链接图法对自由空间进行建模的过程是：图法的搜索路径复杂，效率不高；而人工势场法有可能1)用直线(称为链接线)划分自由空间为凸多边产生极小路径点，使得机器人停滞不前，无法从全局上形区域；把握路径的质量。2)设置各链接线的中间点为可能路径点；蚂蚁算法是近几年问世并逐步引起重视的一种新3)将机器人移动时的起点和终点分别链接到所的仿生算法，已陆续应用于一些不同的学科领域。作在凸多边形区域的各个可能路径点上。为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的对图l所示含有障碍物的

4、规划空间，经过上述算行为特征，有时也称为蚂蚁系统(AntSystem)。生物法处理后，可得到图2．所示的链接图。图中，阴影所示世界中的蚂蚁在搜索食物时，能在其走过的路径上释为障碍物，Is为起点，E为终点。放一种信息激素(Hormone)，使得一定范围内的其它蚂蚁能够觉察到并影响其行为。当某些路径上通过的蚂蚁越多，留下的信息素轨迹(Trail)也越多，以致信息素强度增大，后来的蚂蚁选择该路径的概率也越高。这种选择过程被称为蚂蚁的自催化行为(Autocatalyt-icBehavior)。笔者采用蚂蚁算法这种新

5、的全局优化的仿生算法，探讨利用它解决机器人路径规划的可能性。图l规划空间图2规划空间的链接1规划空间的链接图建模[1】进行移动机器人路径规划时，首先必须对其自由空间进行描述，即进行规划空间建模。链接图法经上述自由空间建模后，机器人路径规划问题转(MAKLINKGraph)是自由空间建模的一种较好的方化为链接图的最短路径问题，可用图论中的成熟算法法，它在构造规划空间时使用了下述假设：(如Ford和Dijkstra)，但上面所求路径只是链接图的1)移动机器人在二维平面中运动，不考虑高度最短路径。因为机器人可以沿

6、着边界行走。这样，上信息；～面所产生的最短路径就不一定是整个规划空间的最优·收稿日期：2OO2—11—08作者简介：董玉成(19r79一)，男，湖北枝江人，重庆大学硕士研究生，研究方向：评价理论、智能计算。重庆大学学报2003车路径。5)ab为第i只蚂蚁移动到第．『个等分点时所留于是，综合Ford(或Dijkstra)算法和蚂蚁算法，提下的轨迹信息量，对于△6#，有蚂蚁圈(Ant—Cycle)模出了求解机器人路径规划问题的基本思想：型、蚂蚁密度(Ant．Density)模型、蚂蚁数量(Ant—QuaIl—1

7、)先用Ford(或Dijkstra)算法求链接图的最短路t~ty)模型川，这里根据实际的问题，选择蚂蚁密度模径，得到初始路径点；型，即：r，’2)用蚂蚁算法来调整各个初始路径点，得到最优Ab={0(所选路径上与(￡)相连的路径点为的或近似最优的移动路径点。常数c，其它为O)；上述蚂蚁算法具体的构成要素如下。6)为第i只蚂蚁转移到第个等分点时的转移2．1路径编码方法概率，在这里取：如图3，假设通过Fore(或Dijkstra)算法找到了链接图的最短路径pop。⋯P⋯PP+。，其中P0=S为路p一[竺堑3：[翌

8、31径起点，PI+。=G为路径终点，优化工作就是：通过对∑[口业][6业]卢PI(i=1，2，⋯，n)的位置在PP。两点所组成的直线其中：为能见度的相对重要性(≥O)，卢为迹的段上进行调整，从而得到机器人在规划空间的最优重要性(卢≥O)。(或近似最优)的移动路径。2．3移动机器人路径规划中的蚂蚁算法P。P。下面，对移动机器人路径规划中的蚂蚁算法按伪码形式如下：Begin初始化：nc一0(nc为搜索次数)；对各直线