基于遗传算法的机器人路径规划

1、2002年10月沈阳建筑工程学院学报(自然科学版文章编号:167l一202】(200204030204基于遗传算法的机器人路径规划张颖1,吴成东1,于谦2(1沈阳建筑工程学院自动控制系,辽宁沈阳110015;2辽宁CAD发展中心,辽宁沈阳¨0015摘要:采用栅格法表示机器人工作环境模型,用序号编码,直角坐标与序号混合应用,采用遗传算法产生初始路径种群,并对其优化找出最短路径,然后增加删除、插入算子达到路径规划中避障的要求用MATLAB语言进行仿真研究,仿真结果表明遗传算法进行避障和路径规划的有效性和可行性关键词:机器人;路径规划;遗传算法;插入、删除算于;避障中图分类号:TPl8文献

2、标识码-一基于遗传算法的机器人路径规划已有很多方法,但是还不尽完善,需要进一步改进Kazuo sugibara等提出的基于遗传算法的机器人路径规划方法。在时变、未知环境下取得了很好的避障及路径规划结果.但是在编码过程中,该方法采用了二进制定常编码方法,增加了个体长度,同时也增加了运算的复杂度.李强等12】提出了一种基于进化的移动机器人路径规戈方法,这种方法是基于四又树模型而提出的,这种算法具有良好的全局搜索性能,但在搜索效率上较一般的搜索算法(如A。算法并无明显的提高.孙树栋等【31提出的应用于机器人路径规划的遗传算法的改进方法采用栅格序号编码.缩短了个体长度,但是其插入过程采用中值法插入,这

3、样插入的栅格很容易为障碍栅格,使得此处的运算比较复杂.笔者在上述方法的基础上重新定义了插入和删除算子,该方法简单而且搜索和避障能力强,提高了机器人的避障能力,保证了最终所得到的路径为最短的避障路径.1环境模型的建立收稿日期:2002一0626基金项目:辽宁省自然科学基金项目(002107作者简介:张颖(1979.女,硕士研究生.图l直角坐标法建立的栅格用序号法对每个小栅格进行编号.其中每个编号口都与其直角坐标一一对应,其映射关系为户=丁+10y而在MATI。AB语言中,z和,与p的关系为fT=陀m(声,10+0.5ly=.衙(p,10十0.5其中,rem表示取余操作,fix表示取整操作.m98

4、7654321Oh 基于遗传算法的机器人路径规划作者:张颖, 吴成东, 于谦作者单位:张颖,吴成东(沈阳建筑工程学院自动控制系,辽宁,沈阳,110015, 于谦(辽宁CAD发展中心,辽宁,沈阳,110015刊名: 沈阳建筑工程学院学报(自然科学版英文刊名:JOURNAL OF SHENYANG ARCHITECTURAL AND CIVIL ENGINEERING INSTITUTE年,卷(期:2002,18(4被引用次数:16次参考文献(7条1.Kazuo Sugibara.John Smith Genetic Algorithms for Adaptive Motion Planning

5、of an Autonomous Mobile Robots 19975.Goldberg D E Genetic algorithms in search 19897.David Beasley.David R Bull and Ralph R. Martin. An Overview of Genetic Algorithms 1993(02相似文献(10条仿真系统-计算机工程与应用2009,45(322.学位论文李江抒多移动机器人路径规划算法与导航系统研究2004本文主要研究了多移动机器人协调系统中的多移动机器人路径规划算法与导航系统。导航系统采用了全局路径规划与局部路径规划算法相结合的

6、方式。全局路径规划采用改进的动态规划算法,将其他机器人位置信息加入机器人路径规划当中。局部路径规划采用人工势场法,使机器人不断朝目标运动的同时避免与环境、障碍物发生碰撞。通过在分布式仿真系统上进行的实验,充分证明了路径规划算法与导航系统适于多移动机器人协调,性能比较好。本文主要研究了以下内容:1.构建适合于多移动机器人的导航系统;2.提出一种适用于多移动机器人的路径规划算法;3.利用分布式多移动机器人仿真系统验证导航系统与路径规划算法。导航系统采用全局路径规划与局部路径规划算法相结合的方式。导航系统启动后,机器人和服务器建立连接,服务器会读取数据库中的地图信息,将地图信息传送给机器人。机器人先

7、做全局路径规划,从地图信息中提取出拓扑图,结合地图信息中的数据,搜索最优路径,完成全局路径规划。全局路径规划的结果是由道路,站组成的一条全局路径。机器人在每段道路中进行局部路径规划算法,在朝局部目标点运动的同时,要与墙壁保持安全距离,并且要避免与其他机器人相撞。每到达一个局部目标点,机器人就朝终点接近一步,并最终完成服务器给定的任务。在导航系统中,全局路径规划给机器人全局的指导,目标明确,避免了仅用局部路径规划时造成的机器人运动的盲目性。同时又发扬了局部路径规划的优势,具有良好的实时性,避免碰撞。在导航系统中,全局路径规划采用改进动态规划算法。改进动态规划算法是在传统的动态规划算法的基础上,加

8、入机器人的位置信息作为道路的动态权重,从而产生了适用于多机器人的路径规划算法。机器人在做路径规划时,当一条道路被多个机器人占用,随着机器人数量的增加,道路的权重也会增加,达到一定数量时,机器人就自然选择那些在道路的长度上略长,但机器人数量较少的道路,从而有效改善了道路的状况,使整个系统运行更顺畅。改进动态规划算法的复杂度为0(n,搜索效率高,但计算量却没有明显增加。同时,机器人还设有十字路口检测模块,在遇到一条道路有多个出口时,就由该点到目标点再次做全局路径规划,保证机器人选择最优路径。局部路径规划采用人工势场法。人工势场实际上是对机器人运行环境的一种抽象描述,目标点对机器人产生引力,环境中的

9、障碍物和其他机器人产生斥力,最后根据引力和斥力的合力来决定机器人的运动方向,使机器人绕过障碍物的同时朝目标前进。应用人工势场法规划出来的路径比较平滑、安全,在数学描述上简洁、使用方便。在多移动机器人协调系统中,解决机器人之间的碰撞是一个非常关键的技术,人工势场法完全满足多移动机器人系统对局部路径规划算法的要求。最后利用分布式多移动机器人仿真系统验证多移动机器人导航系统与路径规划算法。分布式多移动机器人仿真系统是为了验证多机器人算法而设计的,采用分布式体系结构。仿真系统包括显示模块,服务器模块,机器人模块,通信模块及部分。服务器负责任务分配,收集机器人的信息,与机器人进行信息交互。机器人负责全局路径规划,局部路径规划,计算机器人的坐标,完成服务器给定的任务。利用分布式多移动机器人仿真做了一系列实验,包括全局路径规划算法实验,局部路径规划算法实验,以及多移动机器人路径规划实验。全局路径规划实验验证了改进动态规划算法