动态环境下机器人多目标路径规划蚂蚁算法.doc

动态环境下机器人多目标路径规划蚂蚁算法.doc动态环境下机器人多目标路径规划蚂蚁算法摘要:研究了一种新颖的动态复杂不确定环境下的机器人多目标路径规划蚂蚁算法。该方法首先根据蚂蚁觅食行为对多个目标点的组合进行优化,规划出一条最优的全局导航路径。在此基础上,机器人按照规划好的目标点访问顺序根据多蚂蚁协作局部路径算法完成局部路径的搜索。机器人每前进一步都实时地进行动态障碍物运动轨迹预测以及碰撞预测,并重新进行避碰局部路径规划。仿真结果表明,即使在障碍物非常复杂的地理环境,用该算法也能使机器人沿一条全局优化的路径安全避碰的遍历各个目标点,效果十分令人满意。关键词:机器人;多蚂蚁协作;全局导航路径;局部路径中图分类号:TP24文献标识码:A文章编号:1009-3044(2008)32-1185-03 AntAlgorithmforMobileRobotPathPlanwithMulti-objectsinanUnfamiliarEnvironment XUShou-jiang (JiangsuFoodScienceCollege,Huai'an223003,China) Abstract:BasedonAntColonyOptimization(ACO),thisthesispresentsanovelalgorithmunderlyingtherobotmulti-plexandunfamiliarenvironment,-. Keywords:robot;multi-antscooperation;globalnavigationpath;localpath 1引言移动机器人运动导航或路径规划属于研究机器人控制系统的重要应用基础问题,也是机器人研究领域中的一个重要分支。它是指在有障碍物的工作环境中,如何寻找一条从给定起始点到终止点的较优的运动路径,使机器人在运动过程中能安全无碰撞地绕过障碍物,且所走路线最短。对这一问题,各国学者已经做了大量的研究,其中包括Dijkstra算法及其改进[1]、启发式搜索算法[2]、模糊算法[3]、神经网络[4]、遗传算法[5],滚动窗口规划方法[6]等等,这些方法都不同程度上提高了机器人路径规划的效率,但其研究的对象大多局限于机器人单目标搜索,对单机器人进行多目标搜索鲜有报道。随着机器人技术的发展,机器人将被应用于多目标搜索,如机器人邮递员需要将每一份邮件递送到指定的地点等。即如何保证机器人在有障碍物的工作环境中可以快速地沿一条较优化避碰路径安全无碰地访问多个目标点。在这类应用中机器人需要遍历多个目标,当目标数增多时,算法的复杂度呈指数级增长[7],将严重影响规划的时效性。