四 川 农 业 大 学
学士学位论文开题报告
论文题目 移动机器人路径规划的智能算法研究
学 号：
姓 名： 杜 春 龙
指导教师： 陈 松 柏
学科专业： 农业电气化与自动化
所在学院： 信息与工程技术学院
2011 年 4 月 10 日填
四川农业大学本科生毕业论文（设计）开题报告
毕业论文（设计）题目 移动机器人路径规划的智能算法研究
选题类型 应用型 课题来源 自选题目
学 院 信息与工程技术学院 专 业 农业电气化与自动化
指导教师 陈松柏 职 称 高级实验师
姓 名 杜春龙 年
级 2008-1 学
号
一、本课题的研究意义，现状、水平和发展趋势
项目的现状与背景
国内外现状
1.1.1 国外机器人发展状况
随着社会的进步和科学技术的日新月异，人们越来越希望能够创造出一种帮助自身完成各种功能的机器包括一些存在巨大安全隐患的作业。早在20世纪60年代，世界各国就开始了机器人的研究。从第一台机器人诞生至今，机器人技术取得了非凡的发展，现已发展成为一门集机械、电子、计算机、控制、传感器、信号处理等多学科门类为一体的综合性尖端科学]1[。
1.1.2 国内机器人的发展状况
在智能机器人方面，我国也做了不少研究。同国外的研究相比，我国在智能机器人方面的研究起步较晚，但发展较为迅速。国家“863"智能机器人专家组将智能机器人的研究作为今后发展的重点]1[。在最近的十年里，我国已经陆续研制出一些机器人。这些机器人都较为成功的利用了多传感器信息融合技术和路径规划。这些机器人都具备一定的自主能力。同时，在核工业机器人、排险机器‘人水下机器人、室外移动机器人、爬壁机器人等方面，我国也取得了一定的研究成果]3,2[。
机器人的发展趋势
机器人作为科技进步的产物，有如下优点：
① 可以代替人们进行高危作业。
② 可以代替人们进行简单、枯燥的工作。
③ 可以不断重复相同的工作而不知疲倦。
正是因为它有这些优点，故而它在国民生产、医疗保健，特别是工业方面有广泛的应用。目前机器人的发展趋势有如下几个方向]4[：
① 工业机器人的性能不断提高而价格却在不断降低；
② 工业机器人的控制系统逐步向基于PC机的开发型控制发展，其成本低，具有标准网络功能，同时系统可靠性、易操作性、可维修性得到了大幅度的提高。
③ 机器人不断向人机交互控制方向发展。
④ 机器人不断向实用化方向发展。
研究的意义 虽然我国已经在机器人方面已经有了不少成果，但是相对于国外来说，还是有一定的差距。在机器人的路径规划方面，还有许多问题亟需解决。在已有的路径规划方案中，仍有一些地方需要改进，主要有以下几个方面]5[：
① 算法的求解精度较差，算法的时空开销都较大。
② 算法的灵活性有待进一步提高。
③ 算法的稳定性不是很理想。部分算法存在局部最优的问题。
④ 算法的收敛性不能满足实时性的要求。
在充分考虑了以上问题的情况下，本课题采用遗传算法实现机器人的路径规划。设计的遗传算法除能解决以上问题外还具有如下优点]6,5[：
① 克服了人工势场法中的局部极小值问题，对于各种问题的寻优具有很好的适应性，鲁棒性较强。
② 通过设计合理的适应度函数体现不同的标准。具有很好的灵活性。
③ 通过引入一定的选择机制，加快其收敛速度。同时由于其在宏观上具有一定的方向性，所以它较以往的随机搜索算法搜索效率较高。
二、研究方案
设计的主要内容
本课题主要研究内容是利用智能算法实现移动机器的路径规划。根据环境信息是否已知，又可以分为环境已知的全局路径规划和环境未知的局部路径规划。其中全局路径规划无法解决动态避障和复杂多变的环境问题。而局部路径规划，由于没有完整的环境信息，无法达到全局的最优，只能达到某种程度上的次优。本课题在充分结合两者的优点的情况下，实现机器人的路径规划。 预期达到的目标
2.2.1 机器人能够判断出所遇到的障碍物的位置并能自动进行避障处理。
2.2.2 机器人能够自动寻找出一条从出发点到目标的路径。
2.2.3 寻找出的路径应尽可能平滑。
2.2.4 寻找出的路径应尽可能短。
研究中存在的难点
2.3.1 环境的建模
2.3.2 算法的设计及仿真。
2.3.3 软件与硬件的结合。
路径规划总体设计
课题采用两重遗传算法实现路径规划。第一重遗传算法主要实现存在静态障碍物时的路径规划；第二重循环主要实现存在动态障碍物时的路径规划，主要结构如图1所示。 显示输出第二重遗传算法机制动态障碍物输入产生新的初始种群新加静态障碍物输入第一重遗传算法机制初始路径种群输入固定静态障碍物输入动态障碍物输入静态障碍物输入初始种群输入初始障碍物输入动静态环境下的可行路径
图1 路径规划总体设计
遗传算法原理及特点
2.4.1 遗传算法的原理
遗传算法是根据达尔文的进化论，模拟自然选择的一种智能算法，“适者生存”是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。在随机产生初代种群之后，按照适者生存、优胜劣汰的原理，逐代进化产生出越来越好的近似种群。在每一代中，根据问题域中个体适应度大小来挑选个体，再将挑选出来的个体，用自然遗传学的遗传算子进行组合交叉和变异，产生出代表解的解集的种群。通过这些步骤，后生代种群比前代对于环境具有更好的适应性。末代种群中的最优个体经过解码可以作为问题近似最优解。遗传算法的主要流程图如图2所示： 初始化种群计算种群适应度选 择交 叉变 异产生新种群结束？输出结果NY
图2 遗传算法的流程图
2.4.2 遗传算法的特点
作为一种智能算法，遗传算法具有如下特点]7[：
①遗传算法在寻优过程中，只把适应度函数的值作为寻优判据。
②遗传算法是由一个问题集合（种群）开始的，而不是从一个个体开始的。故而遗传算法的搜索面很积大，适合全局寻优。
③遗传算法根据概率性的变换规则进行个体的优胜劣汰和并推动种群的进化。
④遗传算法具有隐含的并行性。
⑤遗传算法具有自组织、自适应以及内在的学习性，同时遗传算法具有很强的容错能力。
⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。
2.4.3 遗传算法在路径规划中的应用思路
本课题采用遗传算法实现机器人的路径规划。在进行路径规划前，可对环境做如下假设，以方便以后的路径规划研究。 ⑴ 将机器人所要运动的环境设想为一个二维空间。同时将机器人视为一个质点。
⑵ 对于环境中的静态的障碍物，可以作为已知信息对待；对于环境中的运动着的障碍物，可以根据检测得知其位置。
⑶ 将障碍物的边缘进行适当的边缘化处理，同时根据机器人的尺寸进行适当放大。
由于在本设计中是将遗传算法用在寻找路径上。所以，种群就表示为机器人在工作空间的多条路径，个体就是具体的某一条路径，路径上的具体某一点就是基因。
在本设计中，主要是为了根据遗传算法找出一条从初始点到目标点的最优路径。在设计的过程中要保证这条路径具有很好的可行性，即不再障碍物空间中；同时，这条路径应尽可能的平滑；再者，这条路径应该力求最短。因此，在使种群适应度函数满足这些条件下，使种群朝着越来越优的方向发展，最终找出满足这些条件的路径。
2.4.4 环境建模
好的环境建模，不但可以使问题简化，同时使数学方法运用于问题的解决中。目前的路径规划方法有: 栅格法、四叉树法和多边形法。其中栅格法存在表示效率不高、时空开销和求解精度存在矛盾等特点]6[。四叉树法在计算邻接关系时，时间代价较大等缺点。同时，多边形法占用空间资源少等优点，故而在本设计中采用多边形法进行环境建模。
运用多边形法进行环境建模，主要是用多边形去逼近障碍物。如图3所示,，黑色多边形表示障碍物。在多边形法中，把机器人看成是一个质点，同时，将障碍物各顶点与目标点已经机器人质点两两相连，要求这些线段都不能穿越障碍物。该方法只需存储障碍物的各顶点的信息，股信息量较少。
三、设计方案
遗传算法的设计
．1 个体编码
在遗传算法实现路径规划中，基因为每条路径上的路径点，而这一个一个的路径点在二维空间中可以用坐标表示。所以在遗传算法中可以用浮点编码较为合适，且每个编码包含横坐标和纵坐标两个部分。用浮点编码的精度较高，更符合路径规划的要求。
3.1.2 初始化种群
在初始化种群时，种群太小会，将不能包含整个区域的信息，种群太大，又会时使算法的收敛速度不理想。所以在随机产生初始化种群时，引入选择机制，使初始化种群随机的包含搜索空间的每个区域]9[。
3.1.3 适应度函数
在用遗传算法实现路径规划中，适应度函数主要表现为路径的长度、平滑度以及接近障碍物的程度。其中路径根据路径是否经过障碍物，又可分为可行路径和不可行路径，可行路径的适应度函数的条件表现为路径的长度、障碍物的程度、路径的平滑度等参数。为了使可行路径由于不可行路径，所以不可行路径在可行路径适应度函数的基础上加上路径与障碍物的交叉点数。在满足适应度函数的情况下，使种群沿着最优的方向进化，最终得到符合条件的路径。
3.1.4 遗传操作算子
遗传算子主要包含选择、交叉、变异。它们是模仿自然选择以及遗传变异的载体。是遗传算法的核心。
3.1.5 控制参数
遗传算法的参数由种群的规模、交叉的概率、变异的概率、最大进化的代数等构成，这参数的选择直接影响遗传算法的性能。因此，在初始化种群阶段以及群体进化阶段，都要合理的进行选择和控制这些参数，以便遗传算法能以较快的收敛性和较高的搜索效率找出一条满足要求的路径。
方案分析
3.2.1方案可行性分析
3.2.1.1 项目实现的理论知识保障
本设计涉及的知识有：人工智能技术、传感器技术，机器人技术，控制技术、电子技术等。
由实现所涉及知识来看，本设计都紧紧与我们的学科知识相连，但是又不仅仅限于我们学科以内。在往后的学习中，我将进行有针对的学习。
3.1.2 项目的技术保障
本设计主要实现用智能算法实现机器人的路径规划。