基于遗传算法的移动机器人路径规划研究.pdf

1、西安科技大学硕士学位论文基于遗传算法的移动机器人路径规划研究姓名：崔建军申请学位级别：硕士专业：测试计量技术及仪器指导教师：魏娟 论文题目：基于遗传算法的移动机器人路径规划研究 专 业：测试计量技术及仪器 硕 士 生：崔建军 （签名）指导教师：魏 娟 （签名）摘 要 目前，随着智能机器人技术的发展，人们对移动机器人的导航，动态避障，路径规划等方面提出了更高的要求。移动机器人运动环境的多变性和复杂性，决定了移动机器人路径规划问题是机器人领域一个研究重点。路径规划作为移动机器人研究中的一个重要研究内容，它是移动机器人按照某一性能指标（如距离、时间、能量等）寻找一条从起始状态到目标状态无碰撞的最优或

2、次最优路径，使之尽可能的平滑和安全。遗传算法是建立在自然选择和群体遗传学基础上的随机、迭代和进化过程，是路径规划研究领域中的一种十分有效地算法。本论文在结合目前多种路径规划方法优缺点的基础上，选择遗传算法来解决移动机器人的路径规划问题。论文在阐述移动机器人的研究状况和发展趋势的基础上，分析了目前移动机器人的路径规划方法，重点研究了基于遗传算法的移动机器人路径规划方法。主要内容有：首先，采用栅格建立地图的方法建立机器人的地图模型，并用序列号法进行编码以及用间断无障碍路径结合启发式方法产生遗传算法的初始种群；其次，选取路径最短设定适应度函数；最后，进行遗传操作，包含有：用轮赌盘方法进行选择、用重合

3、点交叉法进行交叉、以一个较小的概率进行变异和交叉概率和变异概率的自适应调整方法等内容。论文是在静态环境下，对移动机器人进行的全局路径规划，利用 MATLAB 仿真对移动机器人路径规划进行模拟，从而验证了这种仿生的智能算法的有效性。关 键 词：移动机器人；路径规划；遗传算法；最优或次最优路径 研究类型：应用基础研究 Subject :The Research of Mobile Robot Path Planning Based on Genetic Algorithm Specialty :Measuring and Testing Technologies and Instruments N

4、ame :Cui Jian jun (Signature)Instructor :Wei Juan (Signature)ABSTRACT At present,with the development of intelligent robotics,People put forward higher requests for the Mobile Robot Navigation,dynamic obstacle avoidance,Path Planning etc.The robot motion of the varied and complex environments determ

5、ines mobile robots the path planning problem which is a key research area in the field of intelligent robots.As a mobile robot path planning is an important research content of the mobile robot study,it is a mobile robot index according to the performance(such as distance,time and energy,etc.)from t

6、he beginning to the end to find a optimal or Sub-optimal path without collision target state,which is as smooth and safe as possible.This paper is based on combining the advantage and disadvantage of the current multiple path planning methods and it chooses Genetic Algorithm to solve the problems of

7、 mobile robot path planning.This paper is based on describing the mobile robot research status and its development trend,then analyses the mobile robot path planning methods,and focus on a path planning method based on the genetic algorithm.Main contents include:First,using the grid method establish

8、es a map of the robot model,using the serial number of methods encodes the robots path,and using intermittent combination of barrier-free path heuristic method creates the initial population;Second,selecting the shortest path set fitness function;Finally,do the genetic operations,it includes:using r

9、ound gamble method to choose,using coincidence cross-cross method,using a small mutation probability,crossover probability and mutation probability of adaptive adjustment methods,etc.This article is the global mobile robot path planning in a static environment.Using MATLAB simulation of mobile robot

10、 path planning for simulation,it verifys this intelligent bionic algorithm.Key words:Mobile Robot Path Planning Genetic Algorithm Optimal or Sub-optimal path Thesis :Application Basic Research 1 绪论 11 绪论 自古以来人们一直梦想着可以制造一种像人一样的机器，来代替人类做各种工作,帮助人们完成复杂而危险的任务，使人类从繁重的体力劳动解放出来。公元前 2 世纪，古希腊人发明了最早的机器人-自动机，它是

11、以水空气和蒸汽压力为动力的会动的雕像，也可以自己开门，还可以借助蒸汽唱歌。我国汉代张衡发明的记里鼓车，每行一里，车上木人击鼓一下，每行十里击鼓一下。近代工业革命以后，开始出现了初级机器人，越来越多的机器人运用到各个领域，开始从传统的工业领域向军事、医疗、服务等领域渗透，对社会的生产，生活方式产生了深远的影响。1.1 概述 现代意义上的机器人诞生于 1947 年，当时原子能实验室的恶劣环境要求使用机械代替人来处理放射性物质。随着现代控制理论和计算机技术的发展，机器人的研制和应用突飞猛进。1962 年美国的 AMF 公司生产地沃莎特兰机器人和 Unimation 公司的尤尼曼特机器人成为最早的使用

12、机器人，随之出口到世界各国，使机器人的研究进入了热潮。它综合了多学科的发展成果，代表了高技术的发展前沿，并在人类生活应用领域的不断扩大。机器人的发展大致经历了以下三个阶段：第一阶段是可编程的示教再现型机器人。它是通过一台计算机，来控制一个多自由度的机械装置，通过示教存储程序和信息，工作时把信息读取出来，然后发出指令，机器人可以重复地根据人当时示教的结果，再现出这种动作，典型的代表产品就是点焊机器人。第二阶段是有感觉的机器人。它是一种按人事先编好的程序对机器人进行控制，使其自动重复完成某种操作。这种带感觉的机器人是类似人的某种功能的感觉，比如说力觉、触觉、滑觉、视觉、听觉和人进行相类比，有了各种

13、各样的感觉，比方说在机器人抓一个物体的时候，它实际上力的大小能感觉出来，它能够通过视觉，能够去感受和识别它的形状、大小、颜色。抓一个鸡蛋，它能通过一个触觉，知道它的力的大小和滑动的情况。第三阶段是智能机器人。通过各种传感器来获取环境的信息，然后利用智能技术进行识别、理解、推理并最后作出决策，不用人的参与它就能完成运动，感知思维和人机通讯等功能。就目前的发展而言，这种智能的含义还是相对的、局部的。随着科学技术的不断发展，智能的概念越来越丰富，其内涵也越来越宽。目前，随着计算机技术和人工智能技术的飞速发展，机器人技术有了很大的提高，正逐渐渗透到人类活动的各个领域。结合这些领域的应用特点，人们发展了

14、各种特种机西安科技大学硕士学位论文 2器人和智能机器人1。机器人再不只是第一工业机器人时代的机械手臂，出现了仿人机器人、仿生机器人、空间机器人、水下机器人等等。移动机器人作为是机器人学中的一个重要分支，早在 60 年代工程界就己经开始了关于移动机器人的研究。关于移动机器人的研究涉及许多方面，具体可以分为以下几个方面:首先，移动方式的研究，可以是轮式的、履带式的、腿式(单腿式、双腿式和多腿式)的，对于水下机器人，则是推进器；其次，驱动器的控制研究，以使机器人按期望的方式运动；第三，导航或路径规划的研究，对于后者，需要考虑更多的方面，如传感器信息融合、特征提取、避障及环境映射等。因此，移动机器人是

15、一个集环境感知、动态决策与规划、行为控制与执行等多种功能于一体的综合系统。目前，移动机器人的研究出现了许多新的、挑战性的理论与工程课题，引起越来越多的专家、学者和工程技术人员的兴趣。本文移动机器人属于第三代智能机器人范畴，它的特点是能够对复杂的环境进行自主的分析、判断和决策，并实现快捷、安全、自由移动的机器人。与普通机器人相比，智能机器人能够自行完成信息搜集、处理，并作出行动决策，最终完成人们所布置的任务和指令。因此，它是一个集环境感知、动态决策与规划、行为控制与执行等多种功能于一体的综合系统。1.2 课题研究意义 自主式移动机器人不仅可以代替人们在有辐射、有粉尘、有毒等恶劣环境中作业，还可以

16、广泛用于科学考察、地质勘探、灾难营救等多个领域，对人类了解地球、征服自然、探索宇宙具有重要意义2。导航是移动机器人的核心，而路径规划技术是导航中最重要的环节，不管在科研、经济、军事上都有着重要意义3。路径规划的应用领域也不仅限于移动机器人，在其他例如虚拟现实、监督系统、计算生物学等领域也应用广泛。因此，国内外的科学家围绕路径规划展开的研究非常多，从算法设汁、算法分析、仿真实验等各个方面展开了研究。路径规划的主要内容要求移动机器人根据给予的指令及环境信息自主决定路径，避开障碍物，实现任务目标。它是移动机器人完成任务的安全保障，同时也是移动机器人智能化程度的重要标志。对路径规划算法的深入研究，能够

17、不断提高移动机器人的导航性能和智能水平，促进移动机器人的进一步发展。不论是地面移动机器人还是飞行机器人或水下机器人，路径规划和避障问题是他们面临的一个共同的技术问题，移动机器人路径规划及避障作为自主式移动机器人技术的一个重要组成部分，现在仍然是研究的一个重要方面。特别是随着移动机器人应用领域1 绪论 3的不断发展，对移动机器人的路径规划及避障提出了新的要求。以及各种新方法和新技术的不断出现，使路径规划的研究有了更广阔的天地，国内外在这方面都进行了大量的研究。但是我国在智能移动机器人研究方面虽然己经取得了一定的成果，但由于起步较晚，在研究和应用方面都落后于一些西方国家，而且还没有达到完全实用。因

18、此，进行这项研究对我们国家来说具有一定的理论意义和现实应用意义。在全局环境已知的路径规划研究方面，不少学者已经做了大量工作，并取得了令人满意的效果。由于移动机器人的实际工作环境大多是多变不固定的，有时移动机器人在实际前进过程中会遇到某些未知的静态或动态的障碍物，此时移动机器人该采用何种策略躲避障碍物同时又安全的到达目的地，这些都成为移动机器人路径规划的研究热点。我们只有在对环境已知的移动机器人路径规划研究十分深入的情况下，才能更好对移动机器人进行路径规划。例如巡逻机器人巡逻的小区，搬运机器人从事搬运的车间。因此，我们完全可以利用这些已知的环境信息，然后再来针对环境中的其他特殊情况运用不同的策略

19、完成局部未知环境中的路径规划。简而言之，就是首先用全局路径规划器根据静态环境模型规划出一条从起点到终点的最短路径；然后在机器人沿前述路径的实际行进过程中运用局部的静态路径规划。1.3 国内外研究现状和发展趋势 我国对移动机器人的研究起步晚，目前正处在发展阶段，随着我国经济的持续发展，移动机器人市场需求将呈现快速增长的趋势，预计每年增幅在百分之二十左右，进一步推动了移动机器人研究的发展。主要研究包括，清华大学研制的智能移动机器人THMR-V，其涉及以下五个方面的关键技术：基于地图的全局路径规划技术、基于传感器信息的局部路径规划技术、路径规划的仿真技术、传感器信息融合技术及智能移动机器人的设计和实

20、现技术。2000 年 11 月由我国独立研制的第一台具有人类外观特征、可以模拟人类行走与基本操作功能的移动机器人，在长沙国防科技大学首次亮相，它标志着我国机器人技术已跻身国际先进行列。哈尔滨海尔哈工大机器人技术有限公司研制的DY-I 型导游机器人，由伺服驱动系统、避障及路径规划系统、语言事变及合成系统组成，在一定的环境下实现自主行走、避障，并且能够通过语言系统和人进行交谈。此外，还有中科院沈阳自动化所研制的具有自主知识产权的 AGV(Automated Guided Vehicle,AGV)和防爆机器人、中科院自动化所研制的移动机器人 CASIA-I 和上海交通大学研制的 FRONTIER 自

21、主移动机器人等。目前，北京航空大学、北京理工大学、东北大学、南开大学等高校以及国内一些高科技企业也一直从事于智能移动机器人的研究和开发工作。此外，我国已经能够批量生产智能移动机器人。国际上移动机器人开始于 20 世纪 60 年代末期。斯坦福研究院(SRI)研制的移动机器人 Shakey4，如图 1.1 所示。其目的是研究应用人工智能技术，在复杂环境中移动机器 西安科技大学硕士学位论文 4人系统的自主推理、规划与控制。20 世纪 70 年代，随着计算机技术和传感器技术的快速发展，人们开始将传感器技术应用于移动机器人上，这一时期典型代表作是美国Stanford 大学人工智能实验室研制的 Stanf

22、ord Cart 移动机器人，它以视觉传感器为主，能够准确地跟踪地面上的轨线。Stanford Cart 每移动 1m，就停下来通过摄像机的图片对环境进行分析，规划下一步的运动路径。由于当时计算机性能的限制，Cart 每一次规划都需要耗时约 15min。还有法国开发的 HiLare 移动机器人，它有 4 个 80286 处理器，并装配有超声波、里程计和激光测距仪等传感器。70 年代末，许多世界著名的公司开始为大学实验室及各大研究机构设计、制作移动机器人平台，其中著名的 Pioneer 机器人在世界各国的许多大学和科研机构被广泛应用。这些平台被用于研究与教育目的，进而促进移动机器人向多种研究方向

23、的出现。图 1.1 移动机器人 Shakey 80 年代以后，移动机器人的研究进入高速发展时期。尤其在计算机技术、机器人技术及人工智能理论的推动下，国际上广泛开展对智能移动机器人进行研究。特别是 90年代以来，以研制具有高水平的环境信息传感器和信息处理技术、高适应性的移动机器人控制技术以及真实环境下的规则技术等为标志，开始了移动机器人更高层次的研究，如 Engelberger 创建的 TRC 公司在 1990 年推出的世界上第一台机器人护士 Helpmate,由行走部分、行驶控制器及大量的传感器组成，用于医院传送各种医疗物品。Carnegie Mellon 大学的机器人研究所于 1993 年完

24、成了移动机器人在未知或动态环境下的路径规划研究，该所与 1995 年完成自动驾驶车跨越美国的实验，时速达 80/，全程自动1 绪论 5驾驶率为 98%。此外，瑞士联邦理工学院苏黎世机器人研究所开发的 MoPS 服务机器人，具有良好的人机交互与智能导航功能，能够在室内完成分送邮件、文件和资料等办公室任务。其它典型的移动机器人还有 Manchester 大学的 Nomad 机器人和 Real World interface 公司生产的 RHINO 机器人等。同时，伴随网络技术的飞速发展，网络技术大大丰富了移动机器人的控制手段，使得移动机器人的人机交互更加便利，诸如 Carnegie Mellon

25、大学机器人研究所开发的博物馆导游机器人 Minerva 和基于 Web 的室内自主移动机器人 Xaiver,它们自身不仅具有较高的自主性，而且网络技术又给异地使用者提供了远程操作的手段。随着移动机器人的研究更加广泛，在 2004 年 1 月美国 NASA 火星探测移动机器人“勇气号”（图 1.2 所示）和“机遇号”（图 1.3 所示）先后在火星表面顺利登陆。“勇气号”和“机遇号”的成功着陆标志着智能移动机器人的研究工作已经提高到了一个前所未有的高度。图 1.2 勇气号 图 1.3 机遇号 可以预见在 21 世纪，移动机器人将会出没在人类生活的每个角落,人们要求未来的移动机器人要具备高度的智能化

26、，能够完成各种复杂困难的任务。而其中的一个重要环节就是移动机器人的路径规划问题。移动机器人路径规划被描述成：在一个给定的环境内，从一个起始点能达到终止点，它根据一定的任务要求(路径最短、时间最短等)寻求一条连接起点到终点且能避障的移动机器人的运动路线，即最优或次最优路径，即是一个带有约束的优化问题。西安科技大学硕士学位论文 6随着计算机、传感器及控制技术的发展，目前移动机器人的路径规划已经取得了很 大进展5。但仍不能令人满意，还应在以下几个方面进行研究：1)全局路径规划与局部路径规划的有效结合 全局路径规划技术目前已经取得了丰硕的研究成果，理论研究也比较完善。但由于是建立在周围环境已知的基础上

27、，因此它所适应的范围相对有限。特别是具有各种不规则障碍物的复杂环境中，很可能会失去作用。局部路径规划能够适应未知环境，但反应较慢，而且对规划系统要求较高。因此，把二者结合起来才能达到较好的规划效果。2)智能算法引入路径规划 智能算法通过模拟人或动物的行为而逼近非线性，具有自组织、自学习功能。特别是这些算法与传统路径规划方法相结合，使得移动机器人更加灵活、更加智能化。3)多传感器信息融合的引入 多传感器融合技术能有效的利用多个传感器信息，克服单一传感器信息的不完备性和不确定性，能够更加准确全面的作出路径规划。多传感器融合技术也是智能移动机器人的关键技术之一，国内外许多学者在移动机器人领域对信息融

28、合技术的研究非常活跃。多传感器技术融合技术主要包括加权平均法、Kalman 滤波、Bayes 估计、Dempster-Shafer 证据推理、模糊逻辑和神经网络等。4)基于慎思/反应混合式的路径规划 传统的基于模型自顶向下的感知规划执行是一种典型的慎思结构。它利用已知的全局环境模型为移动机器人提供最优动作序列，并到达目标点。该方法适于解决复杂静态环境中的路径规划。但慎思规划需要一定时间来执行对于环境中未预测到的变化反应较慢。而基于反应式行为的路径规划，由于缺乏全局环境信息，作出的路径规划可能不是全局最优。因此，将两种方法结合对于路径就更加有效。5)多智能移动机器人的路径规划 随着移动机器人应用

29、范围的扩大，单体机器人有时很难胜任工作，迫切需要多个移动机器人的协同作业，即单体机器人的路径规划要与多移动机器人之间统一实现协调与避障。因此，多智能移动机器人系统已经成为人们关注热点。1.4 遗传算法的进展 在 20 世纪 50 年代和 60 年代，少数计算机科学家开始独立地进行了所谓的“人工进化系统”研究，找出一种进化的思想，它可以发展为许多工程问题的优化工具，这就是早期的研究形成了遗传算法的雏形。60 年代初期，柏林工业大学的 Rechenberg 和 H.ESchwefel 等在进行风洞实验时，利用了生物变异的思想来随机改变参数值，最后获得了较好的效果。随后，他们对这种方法进行了深入研究

30、，形成了进化计算的另一个分支进化策略(Evolutionary Stratege，ES)，如今 ES 和 GA 已呈融合之势。也是在 20 世纪1 绪论 760 年代，L.J.Fogel 等人在设计有限态自动机时提出了进化规划，他们借用进化的思想对一组 FSM 进行进化，以获得较好的 FSM。当时由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构。20 世纪 60 年代中期，John Holland 在 A.S.Fraser 和 H.J.Bremermann 等人工作的基础上提出了一种位串码的编码方法。随后，Holland 将该算法用于自然和人工系统的自适应行为的研究中，并

31、于 1975 年出版了其开创性著作“Adaptation in Natural and Artificial Systems”。最终，Holland 等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作为其广泛、成功地应用奠定了基础。20 世纪 70 年代以来，关于遗传算法的论文比较有代表性的有 A.D.Bethker 的“用作函数优化器的遗传算法”、De Jong 的“一类遗传自适应系统的行为分析”、T.E.Davis 的“从模拟退火收敛理论向简单遗传算法的外推”。在 20 世纪 80 年代中期，是遗传算法快速发展时期。近年来，

32、随着以遗传算法为主题的多个国际会议在世界各地定期召开，其中比较知名的国际会议有 International Conference on Evolutionary Programming 和 IEEE International Conference on Evolutionary Computation 等，对遗传算法都有较大的推动。人们比较重视遗传算法的一些基本问题，De Jong 称为“重访基本的假设”，这方面的研究内容主要有：表示和形态发生学；拉马克算子等的引入；非随机配对和物种形成；分散的、高度并行的模型；自适应系统；共同进化系统。同时遗传算法在应用研究方面的长处主要得益于其求解的有效

33、性、现有仿真环境下易于实现、可扩充性和易于与其他方法相结合，随着理论研究的不断深入和应用领域的不断拓广，遗传算法取得长足的发展。我国有关遗传算法、进化计算的研究，从 20 世纪 90 年代以来一直处于不断上升的阶段并在许多领域取得了令人瞩目的成果。1997-2009 年 13 年间发表在国内二级以上学术刊物上有关遗传算法，进化算法的文章呈逐年上升趋势，该类研究获得不同渠道的经费资助比例也在逐年上升。同时，国内出版了许多相关书籍，先后有武汉大学刘勇、康立山等于 1995 年出版了非数值并行计算遗传算法；陈国良、王煦等于 1996 年出版了遗传算法及其应用；周明、孙树栋于 1999 年出版了遗传算法原理及其应用；王小平、曹立明于 2002 年出版了遗传算法理论、应用与软件实现；陈伦军等于2005 年编著的机械优化设计遗传算法；巩敦卫于 2007 年出版的交互式遗传算法原理及其应用；巩敦卫,孙晓