遗传算法在机器人路径规划中的应用分析研究

《遗传算法在机器人路径规划中的应用分析研究》由会员分享，可在线阅读，更多相关《遗传算法在机器人路径规划中的应用分析研究（71页珍藏版）》请在装配图网上搜索。

1、毕业论文题目：遗传算法在机器人路径规划中的应用分析研究摘要移动机器人路径规划作为自主式移动机器人技术的一个重要组成部分，是研究移动机器人技术较为活跃的课题之一，吸引了国内外大批的研究学者。随着各种新方法和新技术的不断出现，对路径规划的研究有了更广阔的天地。我国在智能移动机器人研究方面虽然已经取得了一定的成果，如地面自主导航车、水下自主机器人和飞行机器人等。但由于起步较晚，在研究和应用方面都落后于一些西方国家，而且还没有达到完全实用。因此，进行这项研究，具有一定的理论和工程应用意义。首先从移动机器人的历史和现状出发，对比了国内外的不同发展状况，对移动机器人领域的研究方向进行了综述。着重介绍了移动

2、机器人路径规划中常用的方法，对栅格法、遗传算法等进行了逐一的分析阐述。应用于机器人路径规划的有很多传统的优化方法，本文主要介绍的最基本的一种算法-遗传算法在机器人路径规划中的应用。遗传算法（简称GA）是一种借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换，伴随着算法的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体，也就是不断地接近于最优解。本文采取了栅格法对机器人工作空间进行划分，用序号标识栅格，并以此序号作为机器人路径规划参数编码。同时引入间断无障碍路径概念以简化初始种群产生，而且

3、采用了遗传算法操作对初始路径进行寻优，这里遗传算法操作主要指的是选择操作、交叉操作、变异操作；寻优主要是选取适当的个体评价函数及适应函数对路径进行寻优。最后采用MATLAB对机器人路径进行仿真，静态显示进化过程中生成的路径并显示机器人在障碍物存在情况下避障的运动过程。对不同参数设置下的路径进行比较，不同种群大小的适应度值进行统计分析，并将不同环境下的最佳路径与最差路径作比较。传统优化方法在机器人路径规划这类复杂非线性优化问题中缺乏足够的鲁棒性。遗传算法是国际上80年代中期以来获得广泛应用的一种新型参数优化方法，它基于自然选择原理和群体进化机制，有许多区别于传统优化方法的特点，对机器人路径寻优效

4、果更明显。关键词 ：遗传算法，机器人，路径规划，优化Abstract To be a important component of the independent -like migration robot technology, the motion robot way plan is one of more active topics of motion robot technology and has attracted large quantities of the domestic and foreign research scholar. With new method and n

5、ew technologys unceasing appearance, there is a broader world to research the way plan. Although our country had already made certain progress in intelligent migration robot research aspect, such as ground autonomous navigation vehicle, submarine independent robot and flight robot and so on .But it

6、starts late, it falls behind some Western country in the application aspect and has not achieved completely usability. Therefore, it has certain theory and project application significance to conduct this research. Firstly， from the history and the present situation of moved robot ，comparing the dom

7、estic and foreign different development condition , it starts the summary. from the research direction of migration robot. It introduces commonly used method in motion robot way plan emphatically, and has carried on the analysis elaboration one by one to the grid law, the genetic algorithm and so on

8、 Applied to the plans in the robot way has many traditional optimized methods, this article mainly introduce the most basic one algorithm - genetic algorithm in the application of the robot way plan .The genetic algorithm (GA) is one kind which profits from the biosphere natural selection and the na

9、ture heredity mechanism randomisation searching algorithm, it introduces his basic Darwin Evolution theory of the survival of the fittest” to string structure, and carries on organized but the stochastic exchange of information between the strings. Following algorithm advance, the fine quality is re

10、tained gradually and combined, thus produces a better individual unceasingly and also closes to the optimal solution unceasingly . The article adopts the method of grid work to divide robot space , with the serial numbers to identify grid, and as the parameters of code of robot path planning .And th

11、is paper introduces barrier-free path concept to simplify the initial population and using the genetic algorithm operation for the initial route optimization of genetic . The operations mainly refer to selection operation , crossover operation and variation operation. This paper mainly adopts indivi

12、dual evaluation function and The fitness function for optimal selection . Finally using MATLAB to simulate robot path. Traditional optimization methods which is used in this kind of complex nonlinear optimization problems lack of robustness. it displays the path of evolution statically and displays

13、the avoidance movement of the robot in the environment of obstacles .Finally, different optimized paths under different parameters are compared; fitness values of various population sizes are statistically analyzed and best optimized paths and worst optimized paths in different environments are comp

14、ared as well. Genetic algorithm is a new parameters optimization method which has won extensive application in the whole world since the middle of 1980s.It is based on natural selection principle and group evolution mechanism. There are many characteristics which are different from traditional optim

15、ization methods and has better effect in robot path optimization.KEY WORDSGenetic Algorithms, robot, path planning, optimize目录摘要1英文摘要2第一章 绪论.61.1课题的研究背景.61.2国内外路径规划发展状况.81.3路径规划解决的基本问题.101.4论文主要研究内容（原理）概述.111.4.1遗传算法的基本运算过程如下.141.4.2路径规划的实现.151.4.3 机器人路径最优化的实现.151.5本章小结.15第二章 机器人路径规划和遗传算法162.1 路径规划研

16、究概述.162.1.1 路径规划分类.162.1.2 路径规划问题特点.162.1.3路径规划方法.172.1.4 优化问题1922遗传算法192.2.1遗传算法定义.192.2.2 遗传算法特点.192.2.3 编码.202.2.4适应度函数.202.2.5初始群体的选取.21第三章基于遗传算法的机器人路径的优化223.1.参数设定.223.2环境建模.223.3生成初始种群.233.4 适应度函数设置.243.5 选择操作.253.5.1 什么是轮盘赌选择.263.6 交叉操作.283.7 终止条件.29第四章 仿真及结果分析.314.1 仿真程序.314.2 仿真结果及分析.35致谢38

17、参考文献.39图列和表列图1 交叉操作示意图.13 图2 变异操作示意图. .14图3 机器人路径空间模型 . 22图4 初始种群产生流程图23图5选择操作得流程图 26图6转盘法示意图 27表1 10个染色体种群按比例的选择过程 27图7交叉操作示意图. 28图8整个优化过程流程图.30第一章 绪论1.1课题的研究背景现代机器人的研究始于20世纪中期，其技术背景是计算机和自动化的发展，以及原子能的开发利用。 自1946年第一台数字电子计算机问世以来，计算机取得了惊人的进步，向高速度、大容量、低价格的方向发展。 大批量生产的迫切需求推动了自动化技术的进展，其结果之一便是1952年数控机床的诞生

18、。与数控机床相关的控制、机械零件的研究又为机器人的开发奠定了基础。 另一方面，原子能实验室的恶劣环境要求某些操作机械代替人处理放射性物质。在这一需求背景下，美国原子能委员会的阿尔贡研究所于1947年开发了遥控机械手，1948年又开发了机械式的主从机械手。 1954年美国戴沃尔最早提出了工业机器人的概念，并申请了专利。该专利的要点是借助伺服技术控制机器人的关节，利用人手对机器人进行动作示教，机器人能实现动作的记录和再现。这就是所谓的示教再现机器人。现有的机器人差不多都采用这种控制方式。 作为机器人产品最早的实用机型是1962年美国AMF公司推出的“VERSTRAN”和UNIMATION公司推出的

19、“UNIMATE”。这些工业机器人的控制方式与数控机床大致相似，但外形特征迥异，主要由类似人的手和臂组成。 1965年，MIT的Roborts演示了第一个具有视觉传感器的、能识别与定位简单积木的机器人系统。 1967年日本成立了人工手研究会（现改名为仿生机构研究会），同年召开了日本首届机器人学术会。 1970年在美国召开了第一届国际工业机器人学术会议。1970年以后，机器人的研究得到迅速广泛的普及。 1973年，辛辛那提米拉克隆公司的理查德豪恩制造了第一台由小型计算机控制的工业机器人，它是液压驱动的，能提升的有效负载达45公斤。 到了1980年，工业机器人才真正在日本普及，故称该年为“机器人元

20、年”。 随后，工业机器人在日本得到了巨大发展，日本也因此而赢得了“机器人王国的美称”。 随着计算机技术和人工智能技术的飞速发展，使机器人在功能和技术层次上有了很大的提高，移动机器人和机器人的视觉和触觉等技术就是典型的代表。由于这些技术的发展，推动了机器人概念的延伸。80年代，将具有感觉、思考、决策和动作能力的系统称为智能机器人，这是一个概括的、含义广泛的概念。这一概念不但指导了机器人技术的研究和应用，而且又赋予了机器人技术向深广发展的巨大空间，水下机器人、空间机器人、空中机器人、地面机器人、微小型机器人等各种用途的机器人相继问世，许多梦想成为了现实。将机器人的技术（如传感技术、智能技术、控制技

21、术等）扩散和渗透到各个领域形成了各式各样的新机器机器人化机器。当前与信息技术的交互和融合又产生了“软件机器人”、“网络机器人”的名称，这也说明了机器人所具有的创新活力。机器人是20世纪人类最伟大的发明之一，自60年代初问世以来，经历40多年的发展已取得很大的进步。机器人技术的出现和发展，不仅使传统的工业生产面貌发生了根本性变化，而且对人类社会产生深远的影响。目前工业机器人已走向成熟，而具有特定任务的机器人也开始进入实用化研究阶段。这些机器人在工业生产、航天、军事、交通、安全、医疗、老人和残疾人服务等多个领域具有十分重要的应用价值。在机器人研究的早期，机器人的结构、运动学、控制和信息处理是研究的

22、重点。随着机器人技术的发展，单个机器人的能力、鲁棒性、可靠性、效率等都有很大的提升。一方面，人们希望机器人能完成一些复杂的、需要高效率的、并行完成的任务，但这些复杂的任务由单个机器人已很难完成，需要多个机器人组成的团队相互协调与合作共同完成，这导致了机器人的应用方式从部件式单元应用向系统式应用的方向发展。另一方面，人们也希望通过多机器人间的协调与合作，来提高机器人系统在作业过程中的效率，进而当机器人工作环境发生变化或系统局部发生故障时，多机器人之间仍可通过本身具有的协调与合作关系完成预定的任务。如何组织由多个机器人构成的群体系统，以及在这样的群体系统中如何实现机器人的协调与合作已成为当前机器人

23、学研究领域的一个新课题。80年代以来，多机器人系统凭借着比单个机器人更高的精度、刚度、承载能力和灵活性而进入我们的生活中，从而引起了越来越广泛的重视。随着机器人向系统应用的方向发展，人们提出了多机器人群体的组织和控制问题，也就是多机器人协调合作问题，并形成了协作机器人学。多机器人协调合作是多机器人系统中一个重要部分，可以使多机器人系统将整体优势发挥得淋漓尽致。多移动机器人协调系统的研究是机器人技术发展的必然，也将随着机器人应用领域的迅速发展而越来越广泛。机器人技术的发展科学技术共同发展的一个综合性的结果，它的发展归功于第二次世界大战之后各国为加强了本国的经济的发展，就加强了经济的投入。比如说日

24、本，战后开始进行的汽车制造工业，那个时候由于人力的缺乏，它迫切需要一种机器人来进行大批量的制造，提高生产效率降低人的劳动强度，这是社会发展本身的一个需求。另一方面它也是生产力发展的必然结果，也是人类自身发展的必然结果。随着人类的发展和社会发展，人们在探讨自然、改造自然、认识自然的过程中越来越需要一种解放人类的“奴隶”，这种“奴隶”能够代替人们去从事复杂和繁重的体力劳动，实现人们对不可达世界的认识和改造。这也是人们在科技发展过程中的一个客观需要。那什么是机器人呢？机器人是具有一些类似人的功能的机械电子装置，或者叫自动化装置，它仍然是个机器，它有三个特点，一个是有类人的功能，比如说作业功能，感知功

25、能，行走功能，还能完成各种动作，它还有一个特点是根据人的编程能自动的工作，这里一个显著的特点，就是它可以编程，改变它的工作、动作、工作的对象，和工作的一些要求，它是人造的机器或机械电子装置。但从完整的更为深远的机器人定义来看，应该更强调机器人智能，所以人们又提出来机器人的定义是能够感知环境，能够有学习、情感和对外界一种逻辑判断思维的这种机器。那么这给机器人提出来更高层次的要求.。机器人的发展有三个阶段，那么也就是说，我们习惯于把机器人分成三类，一种是第一代机器人，那么也叫示教再现型机器人，它是通过一个计算机，来控制一个多自由度的一个机械，通过示教存储程序和信息，工作时把信息读取出来，然后发出指

26、令，这样的话机器人可以重复的根据人当时示教的结果，再现出这种动作，比方说汽车的点焊机器人，它只要把这个点焊的过程示教完以后，它总是重复这样一种工作，它对于外界的环境没有感知，这个力操作力的大小，这个工件存在不存在，焊的好与坏，它并不知道，那么实际上这种从第一代机器人，也就存在它这种缺陷，因此，在20世纪70年代后期，人们开始研究第二代机器人，叫带感觉的机器人，这种带感觉的机器人是类似人在某种功能的感觉，比如说力觉、触觉、滑觉、视觉、听觉和人进行相类比，有了各种各样的感觉，比方说在机器人抓一个物体的时候，它实际上力的大小能感觉出来，它能够通过视觉，能够去感受和识别它的形状、大小、颜色。抓一个鸡蛋

27、，它能通过一个触觉，知道它的力的大小和滑动的情况。 那么第三代机器人，也是我们机器人学中一个理想的所追求的最高级的阶段，叫智能机器人，那么只要告诉它做什么，不用告诉它怎么去做，它就能完成运动，感知思维和人机通讯的这种功能和机能，那么这个目前的发展还是相对的只是在局部有这种智能的概念和含义，但真正完整意义的这种智能机器人实际上并没有存在，而只是随着我们不断的科学技术的发展，智能的概念越来越丰富，它内涵越来越宽。同时机器人能够通过传感器感知环境，并通过执行器对环境起作用。机器人是现代科学技术发展的佼佼者，将在21世纪发挥出越来越重要的作用，使人类的生产活动和家庭生活发生巨大的变化。自从被誉为机器人

28、之父的著名科学家约瑟夫恩格尔伯格在1959年推出了世界上第一台机器人以来，出现了形形色色的机器人，其中一些机器人由于功能独特而引人注目。随着机器人在工业领域的应用越来越广泛，与外界环境交互的能力要求也在提高，机器人需要解决以下几个问题，分别为确定在哪，应该去哪，以及怎么到达那里。最后一个问题，机器人怎么到达哪里的需求就是所谓的路径规划问题，它是机器人研究领域中的一个重要分支，主要是指如何获得外部环境信息，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的路径。移动机器人的路径规划是一种比较复杂的带约束条件的优化问题，而遗传算法能够模仿自然选择与适者生存的生物进化过程，是求解优化问题的一

29、种有效方法。采用遗传算法对移动机器人进行路径规划时，具体算法的路径编码机制，将直接影响算法的实现和代码的运行效率针对移动机器人不同的工作环境和具体特点，现已提出了多种基于定长编码或动态编码的机制本文提出了一种基于栅格的十进制路径编码机制，使得障碍物的辨识以及遗传算法的实现更为简单，增强了算法的通用性。自主导航是机器人相关技术的研究核心之一，而路径规划是移动机器人自主导航的基本环节之一，对于真正实现机器人自主导航非常关键，因此本文将重点研究多机器人的路径规划问题。机器人路径规划主要解决个问题：（）使机器人能从初始点运动到目标点；（）用一定的算法使机器人能绕开障碍物，并且经过某些必须经过的点；（）

30、在完成以上任务的前提下，尽量优化机器人运行轨迹。1.2国内外路径规划发展状况机器人路径规划的研究始于20世纪70年代，就目前来看，机器人的发展仍然处于初级的阶段，需要去完成的工作仍然很多，特别是在许多具体的环境中仍要具体问题具体分析。在机器人中有一类机器人叫做进化机器人，它用进化算法来实现机器人控制、机构等方面的优化，在路径规划运用中，主要是能够进化出合适的运动轨迹。自从提出遗传规划以来，遗传规划已经在许多方面得到了应用，如缠绕的螺旋线的分辨，图像压缩，符号回归等问题。遗传规划在机器人路径规划中的应用也是国外许多学者研究的目标，并且己经出现了许多令人兴奋的成果。其中比较早，影响也比较大的是人工

31、蚂蚁的问题，这些应用遗传规划来规划路径的蚂蚁能够自主地寻找食物并吃掉食物，而且能够避开障碍。除了人工蚂蚁问题外还有割草机问题，在割草机问题中，割草机必须要在执行一次程序后割草机才能够到达正方形草坪的每一个部分。其环境及任务与人工蚂蚁问题的环境基本相似。 移动机器人的路径规划问题已经研究了很长时间，也产生了很多方法，如全局-空间法、人工势场法以及人工神经网络法每一种方法都具有各自的优点；但总的看来，以上方法都或多或少地存在着一些问题，如算法计算量大、容易陷入局部最优解以及自适应能力差作为优化算法中的一种，遗传算法在许多优化问题中得到了广泛应用并取得了很好效果近年来，遗传算法同样被应用于移动机器入

32、的路径规划问题中目前有专家利用经典遗传算法对移动机器人进行路径规划，它采用固定长发的二进制编码方式，遗传算子也只有交叉和变异两种虽然然该方法具有一定的自适应性，但其在使用过程中必须满足一个约束条件，那就是沿着所规划出的路径前进，其路径中各点横坐标（或纵坐标）必须是单调上升的后来又有专家提出了一种自适应移动机器人路径规划算法，它采用变长度的实数编码方式，将路径中每个点的横、纵坐标和该点的连通性信息作为基因进行编码，其适应度函数则考虑了多个性能指标，如路径的长度、路径的光滑性以及路径的安全性针对路径规划问题的特点，该算法专门设计了八种遗传箅子，而且这八种算子还能根据进化过程中环境特点以及约束指标的

33、变化自适应地调节自身的使用概率从内容上看，该算法似乎比较完美。但这是以大量的数值计算为代价的后来又有专家采用变长度的二进制编码方式，它将机器人下一步的运行方向和运行距离作为基因进行编码，同以上研究方法相比并没有大的改进再后来又有学者提出了一种直接将路径中各点编号进行整数编码的变长度编码方式。并设计了六种遗传算子，该算法具有搜索速度较快，搜索质量较高等优点研究发现，该算法还存在着以下三个主要问题需要改进：(1)初始种群的产生方式有待于进一步研究；(2)基于启发式知识的遗传算子需要进一步设计；(3）遗传算子的使用概率应能够在线调节 国内外对自主移动机器人的导航和避障问题己经做了大量的研究工作，比如

34、哈尔滨工业大学机器人研究所在1996年11月研制成功一个“导游小姐”，该机器人能够实现避障和自主路径规划，识别障碍物的类型，具有一定的语音功能，具有极强的遥控功能。这个机器人能够根据传感器信息自主规划路径，由行走部分、行使控制器、显示器、语音识别系统和大量的传感器组成。行走部分采用差速驱动的方式。既可以在线仿真，也可以显示机器人行走的路径和某个时刻导游机器人所在的位置。大面积宽阔地面的清扫工作一直是一项繁重的体力劳动，人工清扫费时、费力且工作效率低，将机器人用于清扫服务，具有广阔的应用前景。为实现适合我国国情的宽阔地面自动清扫，清华大学与香港中文大学合作，联合研制开发出一种全方位移动清扫机器人

35、。国内在遗传规划方面研究主要是西安建筑科技大学，云庆夏教授编写的进化算法比较详细介绍了遗传规划相关内容。另外，上海交通大学自动化所利用+语言也对该算法在机器人沿墙移动问题进行了仿真实验，通过对移动机器入的行为策略进行符号型编码，然后对这些策略的组合（GP算法个体）进行自然选择，优胜劣汰，最后进化出满足任务需要的优良个体，这些个体实际上就是机器人沿墙移动的一系列指令有序组合最后的仿真结果说明了应用GP算法来演化移动机器人沿墙走行为的有效性。 近年来，自主式水下机器人由于其在海底资源探测上的优势而受到各国的关注，但因为水下环境十分复杂导致一般的规划方法都难以奏效，而水下环境的拥挤程度相对较低，机器

36、人工作在同一区域的可能性较大这一特征恰好有利于基于事例的规划方法的应用，因此该方法被广泛的用于解决水下机器入的路径规划问题.目前对机器人路径规划这一问题的研究仍十分活跃，许多学者仍在继续做大量的研究工作。1.3路径规划解决的基本问题 路径规划是机器人技术研究领域中的核心问题之一，也是机器人学中研究人工智能问题的一个重要的方面。路径规划的主要任务是在机器人所在的环境中寻求一条从已知起点到已知终点的最低代价的无碰撞路径. 路径规划技术是机器人研究领域的一个重要分支。所谓机器人的最优路径规划问题，就是依据某个或某些优化准则（如工作代价最小、行走路线最短、行走时间最短等），在其工作空间中找到一条从起始

37、状态到目标状态的能避开障碍物的最优路径。根据控制方法的不同，机器人路径规划方法大致可以分为两类：传统方法和智能方法。移动机器人的路径规划是移动机器人研究领域中非常重要的问题，总的控制目标是使移动机器人运动到目标点，总的约束是在整个过程中，机器人不碰到任何一个障碍物。该问题根据对环境信息的掌握程度可以分为两类：一类是环境信息已知的全局规划，另一类是环境信息未知的局部规划。全局规划方法依照已获取的环境信息，给机器人规划出一条路径。规划路径的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很大。局部规划方法侧重于考虑机器人当前的局部环境信息

38、，让机器人具有良好的避碰能力。很多机器人导航方法通常是局部的方法，因为它的信息获取仅仅依靠传感器系统获取的信息，并且随着环境的变化实时的发生变化。和全局规划方法相比较，局部规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息，有时会产生局部极点，无法保证机器人能顺利到达目的地。根据机器人对环境信息知道的程度不同可分为两种类型。环境信息完全知道的全局路径规划和环境信息完全未知或部分未知的局部路径规划。对于环境信息完全知道的情况到目前为止已经有许多解决方法，例如势场法。人工势场法的基本思想是将机器人在环境中的运动视为一种虚拟的人工受力场中的运动。障碍物对机器人产生斥力.目标点对机器人产生引力，斥力

39、和引力的合力控制机器人的运动。该方法结构简单，易于实现.，得到广泛应用.但有几个主要缺陷：存在陷阱区，在相近的障碍物面前不能发现路径；在障碍物面前振荡。在实际应用中，机器人的工作环境多数是处于两种极端情况之间的，即环境信息部分未知。例如在自动化车间，一方面环境的整体布局已知(如车间结构，固定设备），另一方面环境中存在着不可预知的障碍物(如其它机器人、临时堆放的物品)。本文主要研究移动机器人在 静态环境中的路径规划问题。本文只进行路径规划问题的研究，而不考虑轨迹跟踪问题，简单讲就是研究如何在含有障碍的环境空间中为机器人规划出一条从起始节点到目标节点的最短无障碍路径。构型空间法是目前研究移动机器人

40、路径规划的一个基本工具，其基本思想是用构型空 间中的一个点来表征移动机器人的位置与方向目前最常用的方法是可视图法。即在一个无向图中，将移动机器人的起始点与终止点以及移动机器人运动环境中各障碍物的顶点表征为点 的形式，从而移动机器人的有效路径就是这样的一些点之间与障碍物不相交的相互连接的线段。一个好的路径规划方法需要满足如下指标：（1）合理性返回的任何路径都是合理的，或者说任何路径对控制机器人运动都是可执行的。（2）完备性如果客观上存在一条从起点到达终点的无碰路径，该算法一定能找到； 如果环境中没有路径可通行，会报告规划失败。（3）最优性算法规划的结果路径在某个测度（如时间、距离、能量消耗等）上

41、是最优的。（4）实时性规划算法的复杂度（时间需求、存储需求等）能满足机器人运动的需要（5）环境变化适应性算法具有适应环境动态改变的能力，随着环境改变，不必全部重新计算。（6）满足约束支持移动机器人运动时的完整性和非完整性运动约束。机器人路径规划研究一般涉及到环境表达、规划方法、路径执行个方面，从而产生以下四个相关问题：（1）机器人如何从环境中有效的获取周围的障碍信息和其它相关信息。（2）机器人如何根据内部及外部传感器来回答当前处于地图中什么位置。（3）机器人如何根据其处于当前地图的位置和当前地图中信息确定行动策略。（4）如何产生合适的驱动信号使机器人运动在预定的轨迹上。为了解决这些问题，机器人

42、需要具备以下四个相关的技术：（1）传感技术。机器人通过传感器设备检测收集外部环境的信息，建立环境的全局地图和得到用于局部避障障碍物信息。（2）自定位技术。如果没有机器人的当前位置信息，也就没有局部坐标系在地图坐标系中的位置，从而无法进行运动的规划。（3）运动控制。控制机器人按照设定的路径行走，涉及到机器人的结构、运动学和动力学性质。（4）规划和决策。规划部分是智能机器人的智能部分，规划的大部分创新技术可以分为任务规划和运动规划，运动规划又分为路径规划利轨迹规划， 本文重点讨论如何解决规划与决策问题，该操作的前提是要对机器人当前所处的全局或局部环境建造模型。1.4论文主要研究内容（原理）概述对于

43、路径规划的研究已经有很多方法，其中不乏基于遗传算法的研究方法，但往往是针对静态或动态的某一种状态，全局或局部的某一种，两者结合的研究比较少见，同时目标函数一般也只是取路径最短一项标准。多目标考虑的方案不多。本文主要解决的问题是在静态环境状态下，运用遗传算法，实现路径的规划问题，找出可行路径，并实现优化。研究的重点是解决路径的归划问题，先考虑找到可行路径，后考虑路径效果。 路径规划是指移动机器人按照某一性能指标（如距离、时间、能量等）搜索一条从起始状态到目标状态的最优路径。在机器人学领域，路径规划是最基本同时也是最重要的研究课题之一作为机器智能的一部分，它的任务就是使机器人在其工作环境中能够自主

44、的从起始点运动到目标点同时满足一定的约束条件这些约束条件包括但不限于：(1)不与障碍物碰撞；(2)运动路径最短；(3)尽量远离障碍物；(4)机器人耗费能量最小；(5)运动轨迹包含某些设定的必经路点。基于不同的基本思想，有多种算法出现。包括有人工势场法（APF）、臭虫法（BUG）、随机位图法（PRM、快速随机树（RRT）、神经网络法CNN）等。这些算法都在不同的方面有着各自的优势，然而在总体上，这些路径规划算法都还存在各自的不足。如计算复杂度局部最优解，地图适应性，动态环境下有效性，全局及多目标优化能力。随着遗传算法（GA）的提出,机器人路径规划算法也得到相应的发展。通过GA在路径规划中的应用，

45、使得机器人更加的智能，其运行路径也更加逼近理想的优化要求。尤其是其优秀的全局优化能力和较高的搜索效率使得成为处理复杂环境下全局优化要求的最佳算法之一。遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工智能技术。他是建立在自然遗传学机理基础上的迭代自适应概率性搜索算法，具有坚实的生物学基础。遗传算法的工作原理为：遗传算法的基本思想来源于达尔文的进化论和门德尔的遗传学说，它是以生物进化的高度抽象模型为基础的自适应搜索策略，基于自然选择和自然遗传这种生物进化机制，把待优化问题的解的搜索空间映射为遗传空间，把每一可能的解编码为一个称为染色体的二进制串（编码的方法很多，如：二进制

46、编码；浮点数编码；参数动态编码；有序串编码），染色体的每一位称为基因，每个染色体（对应一个个体）代表一个解，遗传算法首先随机地产生若干代表优化问题侯选解的一个群体，按照预先根据目标函数确定的适应度函数计算群体中各个个体对问题环境的适应度，从而对群体中的每个成员进行评估，然后根据每个个体的适应度对各个个体所对应的染色体进行选择，抑制适应度低的染色体，继承适应度高的染色体，然后利用遗传操作符（交叉，变异等）对群体中的个体进行遗传操作，产生进化了的新一代群体。如此反复操作。一代一代不断地向更优解的方向进化，最后得到满足某种收敛条件的最适应问题环境的群体从而获得问题的最优解.遗传算法的主要实现步骤如下

47、：（1）问题的表示对于一个实际的待优化的问题，要根据具体问题确定待寻优的参数以及评价解的优劣程度的适应度函数，从而使问题适于遗传算法进行操作。（2）选择待寻优参数的编码方式和编码编码是连续问题与算法的桥梁。选择合适的强有力的编码表达方式是遗传算法的关键根据所选择的编码方式，将待优化的问题的所有参变量编码成对应的子串再将各个子串首尾联接成一定长度的串（设串长为），即染色体，每个串代表解空间中的一个解。不同的编码方式对待优化问题的求解精度和算法的收敛速度有一定的影响。二进制编码对于数值优化问题存在着精度不高的缺点，参数动态编码是一种提高遗传算法精度的新的编码方式，但是对于非线性强的多模型优化问题，

48、DPE性能不佳，浮点数编码具有精度高、便于大空间搜索的优点。目前最常用的编码方式主要是二进制编码。（3）产生初始群体选择一个整数N作为群体的规模参数。随机生成解空间的N个初始个体作为初始群体，代表待优化问题的一些可能解。遗传算法就是从这一初始群体出发，通过遗传操作模拟进化过程，最后获得问题的最优解。当然对于有些问题，具有某些先验知识的情况，可以首先将这些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本，这样选择初始群体可以使遗传算法更快地收敛到最优解。(4）计算适应度函数值计算适应度函数值可以看作是遗传算法与优化问题之间的一个接口。遗传算法评价一个解的好坏，不是取决于

49、它的解的结构，而是取决于相应于该解的适应度函数值。适应度函数反映了个体对问题环境适应能力的强弱是个体竞争的测度，它可以很好地控制个体生存的机会。（5）选择、复制一般采用与适应度函数值成比例的概率方法，个体适应度函数值越高，其被选择并复制的机会也就越多，选择复制体现了“适者生存”的自然法则。选择的目的是从群体中选出繁殖后代的双亲，复制则保留了父代的良好的基因。（6）交叉交叉是非常重要的遗传算子。交叉操作可以分为如下两个步骤，第一步是将新复制产生的个体随机地两两匹配，第二步是进行交叉操作。具体过程如下：设串的长度为则串的个数字位之间的空隙标记为，-。随机地从，L一中选取一个整数位置k将两个父母串中

50、从位置k到串末尾的子串互相交换，从而形成两个新个体。这两个新个体分别组合了其父辈个体的特性，产生了新的基因组合。图3是交叉操作示意图 图1（7）变异首先在群体中随机地选择一个个体，对于选中的个体以一定的概率随机地改变串上的某一位的值，以二进制编码为例，单靠变异操作一般不能使问题求解取得进展，因为变异发生的概率很小，但是变异能起到恢复丢失的遗传信息生成新的遗传信息的作用，从而保持群体中个体的多样性，能有效地防止遗传算法的过早收敛。图2是变异操作示意图 图2（8）遗传算法的终止遗传算法的反复执行（4）一（7）步，直至满足某个收敛准则，搜索到问题的最优解。收敛准则一般有：遗传算法找到能接受的优秀个体

51、（最优解）；遗传算法已经进化了事先预定的最大代数；在事先预定的代数内最优秀个体的适应度函数值无改进；最优秀个体占群体的比例已经达到事先规定的比例。近年来，随着智能方法的广泛应用，机器人路径规划方法也有了长足的进展，许多研究者把目光放在了基于智能方法的路径规划研究上，遗传算法是目前路径规划研究中应用较多的一种方法。遗传算法不要求适应度函数是可导或连续的，而只要求适应度函数为正；作为并行算法，它的隐并行性适用于全局搜索：另外多数优化算法是单点搜索算法，容易陷入局部最优，而遗传算法是一种多点搜索算法，因而更有可能搜索到全局最优解。由于遗传算法的整体搜索策略和优化计算不依赖与梯度信息，解决了一些其他优

52、化算法无法解决的问题。 本文主要研究的是应用遗传算法的基本思想去研究机器人的路径，去研究如何使机器人的路径达到最优。这里就相当于运用遗传算法求最优解（最小值或最大值）。比如对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型: 式中2-1为决策变量，为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。1.4.1遗传算法的基本运算过程如下: a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。 b)个体评价:计算群

53、体P(t)中各个个体的适应度。 c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。 群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。 f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。1.4.

54、2路径规划的实现路径规划的实现分为两种遗传算法机制，第一种只考虑静态障碍物的情况，找出最佳的可行路径，还包括出现静态障碍物的动态情况；机器人根据获得的最佳路径到达目的地同时处理期间出现的动态障碍物的情况，由第二种遗传算法机制解决本文主要分析静态环境下，运用以上的遗传算法实现，通过操作算子的改进，交叉率、变异率的选择以及适应度函数中加权系数的分析调整求得最佳的路径。1.4.3 机器人路径最优化的实现主要结合选择算子、交叉算子和变异算子，及目标函数设置实现。路径规划算法运用MATLAB建立仿真平台，模拟实现过程，并对实验结果进行统计分析。1.5本章小结本章主要介绍了机器人路径规划研究的一些概况。讨

55、论了机器人路径规划研究的背景，给出了研究的目的，对当前机器人路径规划领域的国内外研究状况进行总结，并介绍了路径规划所要解决的基本问题以及对应的相关的技术。最后对本文所研究的主要内容进行简短的概述。 第二章 机器人路径规划和遗传算法2.1 路径规划研究概述路径规划是智能机器人领域中的核心问题之一，也是机器人学中研究人工智能问题的一个重要的方面。典型的路径规划问题的提法是机器人路径规划是指在其工作空间中，为机器人完成某一给定任务提供一条安全高效的运动路径。一般而言，机器人完成给定任务可选择的路径有许多条，实际应用中往往要选择一 条在一定准则下为最优(或近似最优)的路径。常用的准则有：路径最短、消耗

56、能量最少或使用时间最短等。因此，机器人路径规划实质是一个有约束的优化问题。2.1.1 路径规划分类路径规划本身可以分成不同的层次，从不同的方面有不同的划分：(1) 规划方式划分从机器人路径规划的规划方式来分，路径规划问题己有的研究方法可以分为全局型方法、局部型方法以及混合型方法种。全局规划方法是一种离线的规划法，它依照已获取的环境信息，给机器人规划出一条路径。规划路径的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很大。目前全局路径规划的研究有位姿空间法、人工势场法和图搜索法等。局部规划方法是一种在线的规划法，它侧重于考虑机器人当前

57、的局部环境信息，让机器人具有良好的避碰能力。很多机器人导航方法通常是局部的方法，因为它的信息获取仅仅依靠传感器系统获取的信息，并且随着环境的变化实时的发生变化。和全局规划方法相比较，局部规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息，有时会产生局部极点，无法保证机器人能顺利到达目的地。混合型方法试图结合全局和局部的优点，将全局规划的“粗”路径作为局部规划的子目标。从而引导机器人最终找到目标点。(2) 环境角度划分从机器人工作环境的角度区分规划方法，可以分为静态确定环境规划方法和动态时变环境规划方法。静态确定环境路径规划是指环境信息是完全已知的，而且环境中的障碍物是静止的情况下，规划出一条

58、无障碍的路径。这种环境中进行的规划相对简单一些，但实际意义不是很大。动态时变环境路径规划是指环境信息是部分已知或者完全未知并存在运动的障碍物的环境中，实现路径决策。这种方法对自治机器人的发展具有重要的意义。2.1.2 路径规划问题特点路径规划问题具有如下特点：复杂性：在复杂环境尤其是动态时变环境中，机器人路径规划非常复杂，且需要很大的计算量。随机性：复杂环境的变化往往存在很多随机性和不确定因素。动态障碍物的出现也带有随机性多约束：机器人的运动存在几何约束和物理约束。几何约束是指机器人的形状制约，而物理约束是指机器人的速度和加速度。多目标：机器人运动过程中路径性能要求存在多种目标，如路径最短，时

59、间最优，安全性能最好，能源消耗最小。但它们之间往往存在冲突。2.1.3路径规划方法(1) 静态确定环境路径规划机器人在确定已知的环境下的路径归划研究已经趋于较为成熟的阶段，现有以下种典型的方法,分别是位姿空间法、图搜索法与人工势场法。A位姿空间法位姿空间法是一种无碰撞路径规划算法。其实质是根据运动物体的大小和姿态，把周围的障碍物向外扩展一定的距离，而运动物体则缩小为一个点，得到了一个位姿空问。这样把原来在物理空间中求运动物体的无碰撞问题，变换成位姿空间中求一个质点的运动路径，使问题得到简化，因此得到了广泛的应用。基于位姿空间法提出了可视图法。该方法将所有障碍物的顶点和机器人起始点及目标点用直线

60、组合相连，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，即直线是“可视的”，从而产生一条路径。位姿空间法假设机器人的尺寸大小忽略不计，会使机器人通过障碍物顶点时离障碍物太近甚至接触，并且搜索时间长。另外该法缺乏灵活性，即一旦机器人的起点和目标点发生改变，就要重新构造可视图。B 图搜索法图搜索法根据栅格法或栅格解耦法将整个环境划分单元，并将单元视为节点，其间相关关系用弧线相连，得到一个连通图，从而将路径规划问题就演变为点间搜索路径的问题。切分法，将位姿空间切分为一块块的单元，然后搜索相邻单元组成的连接图。但是切分单元的数目随着精度的提高而迅速膨胀，为了提高表示的效率，人们采用层次结构表示。网络模型，将确定性的