提出了在动态环境中，移动机器人的一种路径规划方法，适用于环境中存在已知和未知、静止和运动障碍物的复杂情况。采用链接图法建立了机器人工作空间模型，整个系统由全局路径规划器和局部路径规划器两部分组成。在全局路径规划器中，应用遗传算法规划出初步全局优化路径。在局部路径规划器中，设计了三种基本行为：跟踪全局路径的行为、避碰的行为和目标制导的行为，采用基于行为的方法进一步优化路径。其中，避碰的行为是通过强化学习得到的，仿真和实验结果表明所提方法简便可行，能够满足移动机器人导航的高实时性要求。
动态环境移动机器人遗传算法路径规划
1绪论
移动机器人在进行工作时，往往要求根据某一准则（如路线长度最短、能量消耗最少等），在结构化空间中沿一条最优（或次优）的路径行走。为寻求这条行走路径，人们提出了路径规划的可视图法、人工势场法等。但是，可视图法搜索路径的算法复杂，效率不高；而人工势场法有可能产生极小路径点，使得机器人停滞不前，从全局上把握不了路径的质量。近来随着遗传算法等新的全局最优化方法的发展和应用，也有文献利用遗传算法来规划机器人路径。但文献所介绍的方法产生的无效路径太多，使得计算效率太低，甚至找不出最优路径。
针对这种动态环境的特点，本文从系统的观点提出一种路径规划新方法。整个系统包括两个层次，全局规划层采用改进遗传算法根据整体环境信息决策出初始全局优化路径，而局部规划层采用基于行为的方法根据局部高分辨率信息实时修正初始全局优化路径.基于行为的方法，是一种简单、实时性强的控制机器人运动的方法。该方法根据任务的不同将机器人的运动分解为几个基本行为，通过传感器和通信信息对环境做出快速反应，以利于机器人迅速完成任务。设计了三个基本行为，即跟踪全局路径的行为、避碰的行为和目标制导的行为。其中，避碰的行为采用强化学习得到。
2模型的建立
2.1遗传算法
遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。遗传算法的基本思想是：在问题的求解过程中，把搜索空间视为遗传空间，把问题的每一个可能解看作一个个体，个体里面有基因，所有的个体组成群体。依据某种评价标准对每一个个体进行评价，计算其适应度，并根据适应度对每一个个体进行选择、变异和交叉操作，淘汰适应度小的个体，留下适应度大的染色体，从而得到新的群体，新的群体优于旧的群体。对新的群体再施加自然选择法则，结果一代胜过一代，直到达到预定的优化标准。以上就是遗传算法的基本原理。
2.2路径规划建模
本文在对移动机器人路径规划时采用栅格法来表示，即用大小相同的栅格来划分机器人的工作空间。首先，移动机器人通过势场生成一个障碍物地图，然后机器人利用障碍物地图来规划一条安全的路径，该路径是使机器人由起点运动到终点的一条无碰路径。
障碍物的位置一旦被传感系统如视觉传感器探测到，则赋给与那些位置相对应的栅格一定的初始值，并根据规定的减函数向相邻栅格传播，这样就得到一张障碍物地图。在地图中，用“0”来代表开放的空间，“1”代表障碍物或墙壁，“8”为起始点，“5”为出口。整数表示的地图数组如图1所示：
（1）将环境空间划分为独立的栅格空间；
（2）首先将环境空间的每个栅格初始化为0；
（3）探测障碍物所占据的部分栅格；
（4）把1赋给障碍物所占据的栅格；
3基于遗传算法的路径规划实现
3.1问题定义
3.2算法参数选择
在遗传算法中，个体的长度、种群的长度、遗传操作概率等都是影响算法优化性能和效率的因素之一。交叉概率（CROSSOVER_RATE）用于控制交叉操作的频率。概率太大时，种群中串的更新很快，进而会使高适应度的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前。变异概率（MUTATION_RATE）是加大种群多样性的重要因素。概率太小则不会产生新的个体；概率太大则使遗传算法成为随机搜索。
3.3算法的终止条件
本文使用种群长度作为终止条件。被优选后的群体储存在m_vecGenomes种群中，用NewBabies记录群体的长度，如果其长度不小于给定的种群长度m_iPopSize，则退出循环，否则继续循环。
4动态环境仿真试验
图3所示为机器人向出口运动过程中，出现运动障碍物的情况下，利用算法不断寻找到通向出口的路径。图中分别作出最优个体的路径规划图和种群适应值及最优路径仿真过程图。需要说明的是，路径规划是寻找满足安全的最短路径，这是求最小值的问题，因此以下各图中适应值（或称路径代价）越小，则该路径越好。随着进化代数的增加，适应度值逐渐减少，路径长度也减少。参数同前三次试验的结果作比较可知，迭代次数同适应度成正比，同路径长度成反比。可以看出，本文所进行的仿真试验能够成功地利用遗传算法找到了近似最优路径，并且具有很强的实施性、实用性。
6结论
本文在分析比较目前各种移动机器人路径规划算法的优缺点的基础上，对采用遗传算法解决静态和动态环境里路径规划问题的方法作了进一步的分析研究。通过在多个复杂程度不同的环境下，分别进行静态和动态情况下的仿真，仿真结果表明，该算法能够成功地规划出近似最优的路径。
