基于遗传算法的机器人路径规划.doc

4.3 基于遗传算法的机器人路径规划4.3.1 遗传算法简介50 51在1975年前后，美国Michigan大学John H Holland教授根据达尔文的适者生存的进化理论研究出一种人工智能的方法遗传算法，这种算法以生物进化、遗传原理来设计算法的原理，在算法里面还添加了统计理论学随机过程等数学方法，最终形成了该算法一种独特的理论。遗传算法在求解时，先从一个初始群体的变量开始，依次求解出最佳解，最后得出满足预设的算法要求的迭代次数为最后结果。这种算法是迭代算法的一种。遗传算法是模拟大自然中生物生存的理念而产生的一种自然选择和群体遗传理论的查找式算法。在这个算法里面把每一个需要求解决的问题尽量编码设计成“染色体”，多个染色体接着可以形成种群，在这个过程会出现选择、变异、交叉、复制等遗传操作。遗传算法初始设定时，首先随机产生一个初值即一个种群，然后依照算法的函数对种群内的个体进行处理评估，并产生相应的对环境适应度数值。接着算法会根据这些适应度值选择优秀的个体进行下一代衍生，然后把选出来的优秀进行变异、交叉处理。目前在机器人的路径设计里面遗传算法得到广泛的应用，而且应用范围不仅在单个机器人的行进里面，而是在多个机器人的合作里面也有广泛应用，并且都取得不错的效果。遗传算法是一种鲁棒性的应用于复杂系统优化的查询式算法，遗传算法与其他只能优化算法相比时，他有以下特点：（1） 把决策变量编码化，以一编码做算法处理的对象。（2） 在算法里面以计算出的适应值为查询其他数据的信息。（3） 遗传算法的查询过程从一个种群开始查询，而不从一个一个体开始。（4） 遗传算法的查询是一种依据概率查询，而非确定值查询。遗传算法的基本流程如下图4.10所示：随机产生初始种群计算各个体适应值执行复制操作按交叉概率执行交叉操作按变异概率执行变异操作输出搜索结果算法收敛准则满足否是否图4.10 基本遗传算法的流程图4.3.2利用遗传算法进行路径规划4.3.2.1 规划空间的栅格法建模假设机器人工作空间为二维结构化空间, 障碍物位置、大小已知, 且在机器人运动过程中, 障碍物的位置、大小均不发生变化。用尺寸相同的栅格对机器人二维工作空间进行划分, 栅格大小以机器人能在其内自由运动为限。若某一栅格尺寸范围内不含任何障碍物, 则称此栅格为自由栅格, 反之, 称为障碍栅格。自由空间和障碍物均可表示成栅格块的集合。对划分好的栅格编序号，划分后的机器人工作空间如图4-11所示, 图中阴影区为障碍物。栅格标识可采用下述两种方法:(1) 直角坐标法。如图1所示, 以栅格阵左上角为坐标原点, 水平向右为轴正方向, 竖直向下为轴正方向, 每一栅格区间对应坐标轴上的一个单位长度。任一栅格均可用直角坐标()唯一标识。图4.11 规划空间及仿真结果之一(2) 序号法。如图4.11所示, 按从左到右, 从上到下的顺序, 从栅格阵左上角第一个栅格开始,给每一个栅格一个序号(从零开始计), 则序号与栅格块一一对应。上述两种标识, 互为映射关系: (4-26)或 (4-27) (4-27) 式中,mod表示取之余数,int表示取之整数。在下述讨论中, 机器人运动路径的表示将采用序号法, 因为序号较直角坐标节省内存, 表述简洁明了, 并且便于遗传算子的操作。在对路径进行评价时, 则将序号转换成坐标形式, 因为坐标法更便于表示栅格之间的相对位置, 计算路径长度及检验路径可行性52。4.3.2.2 路径规划方法1. 个体编码个体表示机器人在其工作空间中的一条运动路径。编码即是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法。编码方法可分为三大类：二进制编码方法、浮点数编码方法、符号编码方法。本文采用路径上的一系列栅格序号的顺序排列来表示机器人的一条可移动路径的遗传编码，机器人由起始位置S沿图中粗实线运动到终点位置G的路径，表示成一个个体，即：0,1,11,21,22,23,33,44,55,65,66,67,68,78,88,99。由于机器人运动路径可变, 因此, 个体长度不确定。计算机仿真研究中, 用个体最大可能长度作为个体数组维数。2. 初始种群产生初始种群是遗传算法进化计算的起点, 它由一定数目(称种群大小) 的个体组成。为了保证遗传算法的全局最优性, 初始种群应尽可能随机分布在搜索空间中每一个区域。当对机器人工作空间划分的栅格数目较大时, 产生初始种群并非易事。若采用人工选择法, 则费时费力; 若采用计算机随机生成法, 则由于路径具有目的性、无障碍性, 使得路径生成算法比较困难。为此，引入间断无障碍路径概念。定义在机器人运动起点S 到终点G之间, 用一系列随机选择、自由, 但不一定连续的栅格序号连接S 和G , 称为一条间断无障碍路径。据上述定义, 下面则为几条间断无障碍路径: 0, 99, 0, 20, 45, 75, 87, 99, 0, 11, 23, 43, 54, 65, 75, 85, 95, 97, 99,采用间断无障碍路径作为遗传算法初始种群, 可以减少初始种群产生的困难。3. 适应度函数个体适应度评价函数的选择影响到遗传算法的计算效率。文献52选取如下所示的个体适应度评价函数： (4-28)式(4-28)中：为该个体所通过的栅格数目总和，为该个体中相邻序号栅格之间的直线距离之和。从评价函数F的定义式(4-28) 可见, F与机器人运动距离D成正比, 因此, 该优化以距离最短作为目标函数。但是, 若仅取运动距离D作为评价函数, 则个体0, 99 的目标值最小, 而且经过几代迭代后, 此类个体数目将会增多, 这并非是所期望的，因此， 式(4-28) 中引入了一个修正项，它的主要目的是尽量消除遗传运算过程中产生的间断点相距太远的过短路径。4. 遗传算子(1) 选择算子 采用比例选择算子，将种群中的个体进行适应值评价后,使个体按一定概率向下一代繁殖。(2) 交叉算子 分通常意义上的交叉和重合点交叉两种方式。所谓重合点交叉是指对随机选取的两个个体, 选择栅格序号完全相同的点进行交叉操作, 当重合点多于一个时, 随机选择其一进行交叉, 当无重合点时, 不进行交叉操作。显然常规交叉操作易产生间断路径, 而重合点交叉不会产生新的断点。(3) 变异算子 分三种变异操作，个体中随机删除一个路径点;在个体中随机选择一个节点,用另一个随机产生的点代替;在个体中随机选择一个节点前插入一个新节点.显见，三种变异算子都可能产生间断路径，所以引入以下两种算子。(4) 插入算子 将间断路径用自由节点弥补,使之成为连续路径。判断个体中两相邻序号，是否连续, 可采用下述方法: (4-29)(4-29)式中, 、分别为、对应的直角坐标, 用(4-27)式计算;max, abs 分别代表取最大值和取绝对值操作。若，则与连续，否则不连续。不连续时，按中值法计算候补插入点： (4-30)(4-30)式中, in t表示取整操作。若计算得到的为自由栅格, 可直接插入。若是障碍栅格, 则选择一个与距离最近的自由栅格作为新的侯补插入点。若找不到新的侯补插入点, 即宣告插入失败, 舍去该个体,否则, 用新的侯补插入点补充到与之间。上述插入过程可重复, 直到个体变成连续可通行路径或因找不到新的侯补插入点而舍去该个体为止。(5) 删除算子 插入自由栅格的操作可能会使路径中出现重复节点，删除目的是删除路径中冗余节点,将同一个体中两相同节点之间的节点以及两相同节点中的一个一并舍去。4.3.3 仿真研究53对图4.11和图4.12所示的两种情况分别进行了计算机仿真研究，在这两种情况下，机器人运动起点S和终点G之栅格序号均为0和99。所采用的遗传算法运行参数完全相同：。图中粗实线所示分别为迭代了40代和45代之后所得到的最优运动路径。图4.12 规划空间及仿真结果之二4.3.3 结论本研究表明, 采用栅格序号作为遗传算法的编码形式, 与传统的二进制编码方法比较, 具有编码位数少、长度短、易于遗传算子操作等优点, 更适合于机器人路径规划。提出的间断无障碍路径新概念, 既简化了初始种群产生, 又方便了交叉