复杂环境下机器人路径规划研究
摘 要移动机器人具有高度的智能性和自动化性，能够很好地满足人类对于工作越来越高的要求，因此移动机器人在人类社会发展中占据了一个越来越重要的位置。在机器人研究领域里，对机器人在工作环境里进行路径规划既是一个重点，也是一个难点。路径规划的定义就是在具有障碍物的工作环境中，按照一定的评价标准（其评价标准主要由机器人要完成的工作决定），寻找一条从起始位置到目标位置的路径。在复杂的应用场景中（如机器人导航，灾害搜救，科研探索）对机器人的行进路径进行合理规划也是机器人完成任务的重要保证。本文设计了两套路径规划方案，一套方案是基于Dijkstra算法，另一套方案则是基于遗传算法。基于Dijkstra算法的路径规划方案中，第一步工作就是要结合可视图法对环境信息进行处理，然后对处理之后的环境信息使用Dijkstra算法求出最短路径。在基于遗传算法的路径规划方案中，遗传算法中的种群个体是路径，其染色天编码由路径点的序号组成。在方案中将环境中的路径点分为7个工作区域，其个体编码时依次从工作区域中取出路径点。这样不仅能满足工作需求，也为机器人指定了一个前进方向。另外方案中也对基本遗传算子进行了改造，并加入惩罚算子和平滑算子，使其能满足实际路径规划要求。本文在MATLAB环境下分别对两种规划方案进行了仿真。结果表明，两种方案各有优点和缺点，在复杂度高并且对机器人有工作需求的环境中遗传算法效果比较好。
Keyword: Mobile Robot, Path Planning, Genetic Algorithm, Dijkstra Algorithm 目录
摘 要 I
ABSTRACT II
第1章 绪论 1
1.1选题背景 1
1.2路径规划研究现状 3
1.3 目前常用的路径规划方法 4
1.3.1传统方法 4
1.3.2 智能方法 5
1.3.3 路径规划方法小结 6
1.4 论文结构 7
第2章 基于Dijkstra法的路径规划研究 8
2.1 Djkstra算法原理 8
2.2 基于Dijkstra算法路径规
*好棒文|www.hbsrm.com +Q: ^3^5`1^9`1^6^0`7^2#
划方案 8
2.2.1 可视图法处理环境信息 8
2.2.2 最小路径计算 9
2.3 本章小结 10
第3章 基于改进遗传算法的路径规划研究 11
3.1 基本遗传算法原理 11
3.1.1 遗传算法整体流程 11
3.1.2基本遗传操作 12
3.2 基于遗传算法的路径规划方案 18
3.2.1 基于路径规划的编码 19
3.2.3 适应度函数和惩罚算子设计 20
3.2.3 基于路径规划的选择操作设计 22
3.2.4 基于路径规划的交叉操作设计 22
3.2.5 基于路径规划的变异操作设计 24
3.2.6 平滑算子设计 25
3.2.7 结束条件 26
3.3 本章小结 26
第4章 路径规划仿真及分析 27
4.1 基于Dijkstar算法的路径规划仿真结果 28
4.2 基于改进遗传算法路径规划的仿真结果 28
4.3仿真结果分析 36
4.4本章小结 38
第5章 总结 39
5.1 课题研究成果 39
5.2 主要工作 39
5.3 课题后续发展 39
参考文献 41
致谢 44
附录 45
第1章 绪论
1.1选题背景
机器人是一种具有智能性和自动化性的机器装置,它既可以按人类的指挥进行工作，也可以按预置在其内部的程序进行工作。人类的机器人行业的发展[1]一般是以1959年美国人德沃尔与英格伯格制造出世界上第一台真正意义上的工业机器人为开始标志。
工业型机器人是第一代机器人，它不配备任何传感器，只能按照预置的程序进行简单的流水线工作。第二代机器人则开始配备传感器，使其能够对自身运动的属性如速度，位置等进行感知，也拥有对环境较强的适应能力。比起第一代机器人来说，第二代机器人更具有通用性。第三代机器人也就是我们现在很流行的智能机器人，配有视觉传感器以及摄像头，其拥有一个自己的知识数据库和对应的传感器系统，就如同人类拥有大脑和神经系统一样。它能够根据人的指令进行工作，也可以对外部环境进行预判，从而独立完成任务。
机器人领域的研究发展速度越来越快，这也导致人类的生活和工作越来越离不开机器人。从工业机器人到科研机器人再到家用机器人，机器人也越来越方便着人类的生活，特别是在某些人类不方便工作的场合（如外星球，救灾现场），可以使用机器人代替人类去完成工作。这样既可以极大地提高了人类工作的效率，同时也保证了人类的安全。因此，在复杂环境下为机器人进行合理路径规划，提高机器人的工作效率和工作质量，也就具有了很重要的意义。
图11 第一代工业机器人
图12 第二代感知型机器人
图13 第三代智能机器人
1.2路径规划研究现状
移动机器人路径规划技术是机器人利用自身的传感器结合预置算法完成规划出一条合理的行驶路线，尽量以时间、空间上的最小消耗来完成任务，机器人路径规划有4个基本目标。
1、能够使机器人从起点行驶到终点。
2、规划出的路径能够出避开障碍物，某些情况下需要经过特定的地点，让机器人能够完成对应的任务（如救火机器人需要到达特定地点取消防设备，并在特定地点进行救火操作）。
3、规划出具有一定平滑度的路径，让机器人能够安全完成路径行驶。
4、路径规划耗时时间尽量短，不能让路径规划时间占据了太多机器人工作时间。
移动机器人路径规划最早是在上世纪七十年代韦斯利和佩雷兹开始研究的。他们为移动机器人在几何多面体障碍物之间进行路径规划提出了解决算法，并且将应用范围推广到了配置空间上。此算法能够在相当复杂的环境中进行非常精确的路径规划，但是此算法非常耗时，因此其在动态环境规划中显得无能为力。
在此之后的几十年伴随着机器人技术的不断发展和革新，机器人路径规划研究也有了长足的发展，到目前位置机器人路径规划研究有主要分为3个方向 [2]。
1、基于环境模型的路径规划，可细化为基于完全已知环境的全局路径规划和基于部分环境信息或者完全未知环境的局部路径规划。基于完全已知环境的全局路径规划，又称为离线路径规划，根据所获取环境中障碍物的精确关系，并根据传感信息所得到的机器人的运动策略，计算出一个无碰撞且路程优秀的路径；基于环境信息部分为止或者完全未知的局部路径规划，其规划主要根据传感器所传来的周围环境信息，来规划出一条周围环境上的无碰撞最短路径。
2、基于事例学习的路径规划，其规划思想就是根据过去的规划经验并且经过调整之后对现有问题求解。在基于事例的路径规划中，系统会建立一个数据库，来存储所处理过的环境和这个环境下的路径规划方案。对一个新的环境进行路径规划时，系统就会去这个数据库中找到和当前环境类似的已处理过的环境，并针对已处理的环境中的路径规划方案进行调整，给出适合当前环境的路径方案。
Keyword: Mobile Robot, Path Planning, Genetic Algorithm, Dijkstra Algorithm 目录
摘 要 I
ABSTRACT II
第1章 绪论 1
1.1选题背景 1
1.2路径规划研究现状 3
1.3 目前常用的路径规划方法 4
1.3.1传统方法 4
1.3.2 智能方法 5
1.3.3 路径规划方法小结 6
1.4 论文结构 7
第2章 基于Dijkstra法的路径规划研究 8
2.1 Djkstra算法原理 8
2.2 基于Dijkstra算法路径规
*好棒文|www.hbsrm.com +Q: ^3^5`1^9`1^6^0`7^2#
划方案 8
2.2.1 可视图法处理环境信息 8
2.2.2 最小路径计算 9
2.3 本章小结 10
第3章 基于改进遗传算法的路径规划研究 11
3.1 基本遗传算法原理 11
3.1.1 遗传算法整体流程 11
3.1.2基本遗传操作 12
3.2 基于遗传算法的路径规划方案 18
3.2.1 基于路径规划的编码 19
3.2.3 适应度函数和惩罚算子设计 20
3.2.3 基于路径规划的选择操作设计 22
3.2.4 基于路径规划的交叉操作设计 22
3.2.5 基于路径规划的变异操作设计 24
3.2.6 平滑算子设计 25
3.2.7 结束条件 26
3.3 本章小结 26
第4章 路径规划仿真及分析 27
4.1 基于Dijkstar算法的路径规划仿真结果 28
4.2 基于改进遗传算法路径规划的仿真结果 28
4.3仿真结果分析 36
4.4本章小结 38
第5章 总结 39
5.1 课题研究成果 39
5.2 主要工作 39
5.3 课题后续发展 39
参考文献 41
致谢 44
附录 45
第1章 绪论
1.1选题背景
机器人是一种具有智能性和自动化性的机器装置,它既可以按人类的指挥进行工作，也可以按预置在其内部的程序进行工作。人类的机器人行业的发展[1]一般是以1959年美国人德沃尔与英格伯格制造出世界上第一台真正意义上的工业机器人为开始标志。
工业型机器人是第一代机器人，它不配备任何传感器，只能按照预置的程序进行简单的流水线工作。第二代机器人则开始配备传感器，使其能够对自身运动的属性如速度，位置等进行感知，也拥有对环境较强的适应能力。比起第一代机器人来说，第二代机器人更具有通用性。第三代机器人也就是我们现在很流行的智能机器人，配有视觉传感器以及摄像头，其拥有一个自己的知识数据库和对应的传感器系统，就如同人类拥有大脑和神经系统一样。它能够根据人的指令进行工作，也可以对外部环境进行预判，从而独立完成任务。
机器人领域的研究发展速度越来越快，这也导致人类的生活和工作越来越离不开机器人。从工业机器人到科研机器人再到家用机器人，机器人也越来越方便着人类的生活，特别是在某些人类不方便工作的场合（如外星球，救灾现场），可以使用机器人代替人类去完成工作。这样既可以极大地提高了人类工作的效率，同时也保证了人类的安全。因此，在复杂环境下为机器人进行合理路径规划，提高机器人的工作效率和工作质量，也就具有了很重要的意义。
图11 第一代工业机器人
图12 第二代感知型机器人
图13 第三代智能机器人
1.2路径规划研究现状
移动机器人路径规划技术是机器人利用自身的传感器结合预置算法完成规划出一条合理的行驶路线，尽量以时间、空间上的最小消耗来完成任务，机器人路径规划有4个基本目标。
1、能够使机器人从起点行驶到终点。
2、规划出的路径能够出避开障碍物，某些情况下需要经过特定的地点，让机器人能够完成对应的任务（如救火机器人需要到达特定地点取消防设备，并在特定地点进行救火操作）。
3、规划出具有一定平滑度的路径，让机器人能够安全完成路径行驶。
4、路径规划耗时时间尽量短，不能让路径规划时间占据了太多机器人工作时间。
移动机器人路径规划最早是在上世纪七十年代韦斯利和佩雷兹开始研究的。他们为移动机器人在几何多面体障碍物之间进行路径规划提出了解决算法，并且将应用范围推广到了配置空间上。此算法能够在相当复杂的环境中进行非常精确的路径规划，但是此算法非常耗时，因此其在动态环境规划中显得无能为力。
在此之后的几十年伴随着机器人技术的不断发展和革新，机器人路径规划研究也有了长足的发展，到目前位置机器人路径规划研究有主要分为3个方向 [2]。
1、基于环境模型的路径规划，可细化为基于完全已知环境的全局路径规划和基于部分环境信息或者完全未知环境的局部路径规划。基于完全已知环境的全局路径规划，又称为离线路径规划，根据所获取环境中障碍物的精确关系，并根据传感信息所得到的机器人的运动策略，计算出一个无碰撞且路程优秀的路径；基于环境信息部分为止或者完全未知的局部路径规划，其规划主要根据传感器所传来的周围环境信息，来规划出一条周围环境上的无碰撞最短路径。
2、基于事例学习的路径规划，其规划思想就是根据过去的规划经验并且经过调整之后对现有问题求解。在基于事例的路径规划中，系统会建立一个数据库，来存储所处理过的环境和这个环境下的路径规划方案。对一个新的环境进行路径规划时，系统就会去这个数据库中找到和当前环境类似的已处理过的环境，并针对已处理的环境中的路径规划方案进行调整，给出适合当前环境的路径方案。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jxgc/zdh/3041.html
