移动机器人路径规划是在一个存在障碍物的有界工作空间内，依据相应的评价标准(路径长度、能量消耗等)规划出一条安全无碰撞而且较优的可行路径^[1]。一般来说，可将路径规划分为静态^[2-3]和动态路径规划两类。在实际中，机器人所处的大多数是一种动态变化的工作环境，因此，研究动态路径规划问题更具有实用价值。目前，已有不少学者对此进行了大量研究并提出了多种路径规划方法与策略^[4-8]。近年来，由于遗传算法具有并行性、全局搜索能力等优点，所以在路径规划中得到广泛的应用。例如，文献^[9]将基于协进化机制的改进遗传算法应用到求解多机器人全局路径规划中。文献^[10]利用一种基于改进遗传算法求解机器人路径动态规划问题。文献^[11]将一种新的变异方法应用到求解机器人动态路径规划中。文献^[12]采用二次规划的方法对出现新的障碍物进行求解，虽然仿真结果表明该方法是可行的，但是却大大增加了路径规划时间。Lee等人^[13]利用有向非循环图与初始化种群相结合的方法对路径规划方法进行研究。文献^[14]利用改进的交叉概率和变异概率对路径规划方法进行研究。然而，随着研究的不断深入，传统遗传算法所存在的问题(如算法容易出现停滞现象、陷入局部最优^[15]等)逐渐被发现。因此，为解决基本遗传算法存在的不足，针对静态和动态障碍物同时存在于工作环境中的路径问题进行规划，并且将全局路径规划与局部路径规划相结合进行优化，首先利用改进的遗传算法对全局最优路径进行搜索，然后利用局部避碰规划策略确定一条距离较短且安全无碰撞的路径，实验仿真表明了该方法在静态及动态路径规划中的有效性和可行性。

1 环境的描述

实现路径规划的基础是对机器人的工作环境加以建模^[16]。所以针对静态和动态障碍物同时存在情况，利用栅格法对机器人路径规划进行建模，以机器人能自由运动为前提条件，通过对障碍物、机器人以及工作空间的大小比较来确定栅格的数目和大小，如图 1所示，每个序号m都和直角坐标有着一一对应的关系，如式(1)所示。

$m=x+10y$

(1)

假设机器人在二维平面上的有限区域内工作，机器人运动的起始点和目标点分别用S和G表示，其在一个栅格上可以沿8个方向到达相邻的栅格，如图 2所示。

另外，做出假设条件如下：(1) 机器人是圆形的，其直径为R，不管任何时间，通过传感器机器人能够感知到半径为r范围内的环境信息，该信息是以当前所在栅格的中心为圆心。(2) 将已知的静态障碍物边界向外扩展R/2，则机器人可用其中心点来表示，在规划过程中作为质点考虑。(3) 机器人的速度为V_R，环境中的动态障碍物为圆形，其直径为单个栅格的宽度(每一个正方形栅格表示一个单位面积)，速度为V_O并且做匀速直线运动，V_R和V_O恒定。

2 基于改进遗传算法的移动机器人路径规划 2.1 编码

在此采用栅格序号对个体进行编码，即机器人的每条路径可以表示为从S运动到G的过程中，由其依次所经过的栅格序号组成，如图 1中的某一条路径可表示为{S,11,22,33,43,54,65,76,77,88,G}。

2.2 种群的产生

在生成初始种群时，若要得到连续路径，机器人可以从其周围的8个相邻栅格中选取一个自由栅格作为下一个栅格，这种选择方法虽然可以保证路径是连续的，产生的路径也具有多样性，但是产生的路径质量不高，同时也会增加进化代数，影响收敛速度^[17]。因此，对于上述的不足，提出从其相邻8个栅格中选取5个作为备选栅格，即{1,2,3,4,8}这5个方向的栅格。

生成初始种群的具体步骤：

Step 1 根据机器人所处的当前栅格，从其相邻的5个备选栅格中选出自由栅格，然后再依次求出其到目标点G的距离D_i和被选作为下一个栅格的概率p_i

${{p}_{i}}=\frac{1/D}{\sum\limits_{i=1}{{}}1/{{D}_{i}}}i\le 5$

(2)

Step 2 随机在0~1之间生成一个数p。

Step 3 若p₁+p₂+…+p_i-1<p≤p₁+p₂+…+p_i，则选择p_i对应的栅格作为下一个栅格。

Step 4 把当前栅格加入搜索禁忌表，避免重复选择，并且当前栅格序号用下一栅格序号所取代。

Step 5 如果当前栅格所有的备选栅格都是障碍物栅格，则取消生成该个体，直接转至步骤1，重新选择生成下一个体。

Step 6 判断是否到达目标点，若未到达，则转至步骤(1)继续生成下一个体；若到达目标点，则把当前路径保存下来。

Step 7 当个体数目达到种群规模M时结束。

2.3 适应度函数的确定

采用路径的总长度D(L)的倒数作为适应度函数，如式(3)所示。

$F\left( L \right)=\frac{1}{D\left( L \right)}$

(3)

2.4 遗传操作

(1) 选择操作

首先采用轮盘赌法执行选择过程，然后对于所选出的新种群采用精英策略，即在父代种群中，按一定比例选取最优个体不经过遗传操作而直接复制到子代。

(2) 交叉操作

选用单点交叉方法，由于路径的不同而导致个体长度的不同，因此，对于随机选择的两个个体，其交叉点的位置不一定相同，这里选取相同序号点处进行交叉(起点S和终点G除外)，以保证路径的连续性，其过程如图 3所示。如果具有相同序号的点不止一个，则任选其一进行交叉，如果无相同序号点时，从两个个体中随机选取两个序号点进行交叉。如果交叉后所产生的是非连续路径，以上半段的终点和下半段的任意栅格分别作为起始点和目标点，采用生成初始种群的方法进行修补成一条连续的路径。

(3) 变异操作

传统的随机变异操作将会导致间断路径的产生，因此，采用一种改进的变异方法，即随机选取个体中的一个栅格(S与G除外)，并将它作为障碍物栅格删除，对于产生的间断路径，采用与上述相同修补方法。变异操作结束后，对于种群中相同的个体保留其一。这种变异方法可以保证路径是连续的，同时也可以加快搜索速度和提高搜索质量。

然而，在遗传操作过程中，选择和变异操作使得种群规模M发生了变化，其计算如下

$M\left( t+1 \right)=M\left( t \right)+A\left( t \right)-D\left( t \right)$

(4)

$A\left( t \right)=M\left( t \right)*{{p}_{\tau }}$

(5)

式中:M(t)为第t代遗传时的种群规模；A(t)为第t代遗传时所增加的个体数量；D(t)为第t代遗传时被删除的个体数量；p_r为复制概率。

在算法的各个阶段，变异概率p_m应当随着进化过程发生变动，早期的p_m可大，后期的p_m宜小。此外，遗传算法中群体规模M是较为重要的一个参数，变异概率还与M有关，并且变异概率应当随群体规模的增大而减小，因此，变异概率可以按式(6)自适应调整。

${{p}_{m}}\left( t \right)=\frac{k}{M\left( t \right)}\times exp\left( -\frac{t}{2} \right)$

(6)

式中:p_m(t)为第t代遗传时的变异概率；M(t)为第t代遗传时的群体大小；k > 0。

3 动态环境中移动机器人避碰策略

当有移动的障碍物存在于机器人的工作环境中时，允许两者都有8个运动方向，如图 2所示，其之间的碰撞类型主要有3种形式，即：侧面碰撞、正面碰撞和追尾碰撞^[18]。

针对3种碰撞形式，采取的相应避碰策略如下。

(1) 等待策略：若预测到侧面碰撞将有可能在两者之间发生时，那么机器人在到达碰撞点之前原地等候ΔT时间，等障碍物越过碰撞点后机器人方可继续按全局路径行进，即可免于碰撞。ΔT的值为

$\Delta T=max\{\frac{{{D}_{R}}}{{{V}_{R}}},\frac{{{D}_{O}}}{{{V}_{O}}}\}$

式中D_R和D_O分别表示机器人和障碍物的直径。

(2) 返回策略：当正面碰撞将在两者之间发生时，且机器人当前行进方向与前一步不同，如图 4所示，对于这种情形，若要实现两者避碰，机器人直接返回上一栅格即可。

(3) 选点策略：当追尾或正面碰撞将在两者之间发生时，并且障碍物当前行进方向与机器人前一步行进方向相同时，此刻机器人只需在预测的碰撞点附近可行栅格中重新寻找一自由栅格作为下一步运动方向，则避碰将免于发生。若在预测发生碰撞点的附近可行区域中未寻找到自由栅格而且V_O≤V_R，则机器人采取返回策略，如图 5所示。

4 仿真实验结果及分析

为了验证本文算法的有效性，运用Matlab进行仿真，针对环境中有新增的静止障碍物和有移动障碍物两种情况，分别进行实验仿真。

4.1 静态路径规划仿真

(1) 首先，在由图 6所示的障碍物(用栅格中的黑色表示)分布情况下，应用改进的遗传算法对机器人进行全局路径规划。仿真时，设初始种群大小为30，交叉概率为0.7，初始的变异概率为0.1，最大遗传代数为100，k=1，实验结果如图 6所示。

(2) 在图 6所示的环境中，当出现新增静态障碍物时，其仿真结果如图 7所示。

(3) 基本遗传算法与改进的遗传算法分别运行100次后，各指标的统计结果如表 1所示。

4.2 动态路径规划仿真

假设机器人与动态障碍物的速度相同，当无动态障碍物时，则移动机器人按照原优化的路径行走(图 5)。当预测到将与障碍物在下一步发生正面碰撞，采取选点策略，重新规划路径的实验结果如图 8所示。当预测到与障碍物发生侧面碰撞时，采取等待策略，再按照原优化路径行进，实验结果如图 9所示。当障碍物在机器人的前面，如果V_O< V_R，将会发生追尾碰撞，应采取选点策略，重新规划路径的实验结果如图 10所示。

5 结 论

(1) 利用栅格法对机器人路径规划进行建模，采用栅格序号对个体进行编码，提出了生成初始种群的方法，以改善产生路径质量和收敛速度。

(2) 设计出了自适应变异概率以及采用精英策略，以提高算法的求解质量。

(3) 对动态环境中避碰进行分析并给出了协调避碰策略。机器人静态及动态路径规划问题的实验结果表明:该算法能够取得较为满意的规划效果，求解结果优于基本遗传算法。