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

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

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

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

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

来,许多学者致力于基于智能方法的路径规划研究,其应用的智能算法主要有模糊方法、神经网络和遗传算法等[1~3]。这些方法在提高路径规划性能的同时,也存在搜索空间大、算法复杂、效率不高等问题。另外,基于混合方法的机器人路径规划已经受到有关学者的关注,它具有一定的灵活性,可以互相结合,取长补短。例如,文献[4]提出了一种用于半自主移动机器人路径规划的模糊神经网络方法。文献[5]提出了一种分步路径规划方法,用链接图建立空间模型,用Dijkstra算法求得链接图最短路径,再用粒子群算法对路径进行优化,从而得到全局最优路径。一种将混沌优化与人工势场法相结合的混沌人工势场法用于机器人的路径规划,以克服传统人工势场法容易陷入局部最优[6]

的缺点。

受自然界中真实蚁群集体行为的启发,Dorigo等提出的蚁群算法是一种新型的仿生算法[7]

。该算法在求解TSP(旅行商)问题、分配问题、作业调度问题等方面已经取得了较好的成果。实践证明该算法是一种解决优化(特别是组合优化)问题的有力工具。Mazzeo等[8]将蚁群算法用于车辆路由问题,所取得的结果比其他启发性算法有更好的效果。蚁群搜索食物的过程与路径规划有着天然的联系,将蚁群算法运用到路径规划中具有很大的合理性。文献[9]提出了基于栅格法的机器人路径规划蚁群算法,但该算法没有考虑机器人路径规划中的死锁问题。本文将一种改进的蚁群算法用于移动机器人在复杂的静态环境下的路径规划,并通过在规划过程中建立死角表和惩罚函数避免路径死锁状态。仿真研究表明所提出的算法在复杂环境下规划的路径最短、快速而高效。

1 问题描述与建模

移动机器人的路径规划是智能机器人研究中的一项关键技术,路径规划的第一步就是要建立移动机器人二维工作空间的环境模型。环境建模的方法有很多种,例如,栅格法、顶点图像法、广义锥法、链接图法、拓扑图法、几何信息法等。栅格法在许多机器人系统中得到应用,是使用较为成功的一种方法[10]。栅格地图容易创建和维护,机器人所了解的每个栅格的信息直接与环境中某区域对应,借助于该地图,可以方便地进行自定位和路径规划。为实现设想的路径规划算法,本文在机器人运动空间建模时作如下假定:(1)移动机器人在二维有限空间中运动;(2)机器人运动空间中分布着有限个

已知的大小不同的静态障碍物,障碍物可以由多个栅格描述,忽略障碍物的高度信息。路径规划的目的是使机器人能够由起始位置出发,安全避碰地沿一条最短路径到达已知的目标位置。

设机器人在二维平面上的凸多边形有限区域内运动。该区域内分布着有限个不同大小的障碍物。在该区域内建立直角坐标系。假设机器人以一定的步长R运动,则x轴和y轴分别以R为单位来划分栅格。每行的栅格数Nx=xmax R;每列的栅格数Ny=ymax R。如果区域为不规则形状,则可在边界处补以障碍栅格,将其补为正方形或者长方形。其中障碍物占一个或多个栅格,若不满一个栅格,以一个栅格计。每个栅格都有对应的坐标和序列号,而且序列号与坐标之间一一对应,图1给出了栅格坐标与序列号之间关系的示意图。定义左上角第一个栅格的坐标为(1,1),记为S(1,1),对应的序列号为1;栅格坐标S(2,1),对应的序列号为2,栅格坐标S(1,2)对应的序列号为(Nx+1),其他依次类推。

图1 栅格坐标与序列号之间的关系

Fig.1 Relationshipbetweenserialnumbersandgridcoor2

dinates

  根据图1所示,坐标(xi,yi)与序列号i之间的

映射关系可以由式(1)确定:

xi=[(i-1)modNx]+1

yi=int[(i-

1) Nx]+1

(1)式中:int为舍余取整运算,mod为求余运算,Nx

为

每一行的栅格数。

2 路径规划的改进蚁群算法

2.1 蚁群算法的基本原理

蚁群算法是受自然界中真实蚁群的集体行为的

启发而提出的一种基于群体的模拟进化算法,属于随机搜索算法。文献[7]中利用蚁群搜索食物的过程与著名的旅行商问题(TSP)之间的相似性,通过模拟蚂蚁搜索食物的过程(即通过个体之间的信息交

上一页第2页

你可能喜欢

热门文档

相关文档

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