开题报告 路径规划.doc

开题报告_路径规划.
1 / 12
四 川 农 业 大学
学士学位论文开题报告
论文题目 移动机器人路径规划的智能算法研究
学 号： 20083499
姓 名： 杜 春 龙
指导教师：陈 松 柏
学科专业者生存"是它的核心机制。遗传算法是从代表问题可能潜在解集的一个种群开始的。在随机产生初代种群之后,按照适者生存、优胜劣汰的原理,逐代进化产生出越来越好的近似种群。在每一代中,根据问题域中个体适应度大小来挑选个体,再将挑选出来的个体,用自然遗传学的遗传算子进行组合交叉和变异,产生出代表解的解集的种群。通过这些步骤,后生代种群比前代对于环境具有更好的适应性。末代种群中的最优个体经过解码可以作为问题近似最优解。遗传算法的主要流程图如图2所示：
.
6 / 12
图2遗传算法的流程图
遗传算法的特点
作为一种智能算法,遗传算法具有如下特点：
①遗传算法在寻优过程中,只把适应度函数的值作为寻优判据。
②遗传算法是由一个问题集合〔种群开始的,而不是从一个个体开始的。故而遗传算法的搜索面很积大,适合全局寻优。
③遗传算法根据概率性的变换规则进行个体的优胜劣汰和并推动种群的进化。
④遗传算法具有隐含的并行性。
⑤遗传算法具有自组织、自适应以及内在的学习性,同时遗传算法具有很强的容错能力。
⑥遗传算法的基本思想简单。对于复杂的和非线性的问题具有良好的适应性。
遗传算法在路径规划中的应用思路
本课题采用遗传算法实现机器人的路径规划。在进行路径规划前,可对环境做如下假设,以方便以后的路径规划研究。
⑴ 将机器人所要运动的环境设想为一个二维空间。同时将机器人视为一个质点。
⑵ 对于环境中的静态的障碍物,可以作为已知信息对待；对于环境中的运动着的障碍物,可以根据检测得知其位置。
⑶ 将障碍物的边缘进行适当的边缘化处理,同时根据机器人的尺寸进行适当放大。
由于在本设计中是将遗传算法用在寻找路径上。所以,种群就表示为机器人在工作空间的多条路径,个体就是具体的某一条路径,路径上的具体某一点就是基因。
.
6 / 12
在本设计中,主要是为了根据遗传算法找出一条从初始点到目标点的最优路径。在设计的过程中要保证这条路径具有很好的可行性,即不再障碍物空间中；同时,这条路径应尽可能的平滑；再者,这条路径应该力求最短。因此,在使种群适应度函数满足这些条件下,使种群朝着越来越优的方向发展,最终找出满足这些条件的路径。
环境建模
好的环境建模,不但可以使问题简化,同时使数学方法运用于问题的解决中。目前的路径规划方法有: 栅格法、四叉树法和多边形法。其中栅格法存在表示效率不高、时空开销和求解精度存在矛盾等特点。四叉树法在计算邻接关系时,时间代价较大等缺点。同时,多边形法占用空间资源少等优点,故而在本设计中采用多边形法进行环境建模。
运用多边形法进行环境建模,主要是用多边形去逼近障碍物。如图3所示,,黑色多边形表示障碍物。在多边形法中,把机器人看成是一个质点,同时,将障碍物各顶点与目标点已经机器人质点两两相连,要求这些线段都不能穿越障碍物。该方法只需存储障碍物的各顶点的信息,股信息量较少。
三、设计方案
遗传算法的设计
．1 个体编码
在遗传算法实现路径规划中,基因为每条路径上的路径点,而这一个一个的路径点在二维空间中可以用坐标表示。所以在遗传算法中可以用浮点编码较为合适,且每个编码包含横坐标和纵坐标两个部分。用浮点编码的精度较高,更符合路径规划的要求。
初始化种群
在初始化种群时,种群太小会,将不能包含整个区域的信息,种群太大,又会时使算法的收敛速度不理想。所以在随机产生初始化种群时,引入选择机制,使初始化种群随机的包含搜索空间的每个区域。
适应度函数
在用遗传算法实现路径规划中,适应度函数主要表现为路径的长度、平滑度以及接近障碍物的程度。其中路径根据路径是否经过障碍物,又可分为可行路径和不可行路径,可行路径的适应度函数的条件表现为路径的长度、
.
8 / 12
障碍物的程度、路径的平滑度等参数。为了使可行路径由于不可行路径,所以不可行路径在可行路径适应度函数的基础上加上路径与障碍物的交叉点数。在满足适应度函数的情况下,使种群沿着最优的方向进化,最终得到符合条件的路径。
遗传操作算子
遗传算子主要包含选择、交叉、变异。它们是模仿自然选择以及遗传变异的载体。是遗传算法的核心。
控制参数
遗传算法的参数由种群的规模、交叉的概率、变异的概率、最大进化的代数等构成,这参数的选择直接影响遗传算法的性能。因此,在初始化种群阶段以及群体进化阶段,都要合理的进行选择和控制这些参数,以便遗传算法能以较快的收敛性和较