基于栅格法的矿难搜索机器人全局路径规划与局部避障

朱磊^{1, 2}，樊继壮¹，赵杰¹，吴晓光¹，刘罡¹

(1. 哈尔滨工业大学 机器人技术与系统国家重点实验室，黑龙江 哈尔滨，150080；

2. 中国科学院 长春光学精密机械与物理研究所，吉林 长春，130033)

摘要：针对矿难发生后井下环境的不确定性，提出一种以矿难前的GIS(Geographic information system)地图为基础建立环境栅格模型并结合改进遗传算法的矿难搜索机器人全局路径规划方法。效仿蚁群算法中的信息素提出基于位置信息负反馈的方法，并结合优先权分组的思想，提出一种新的有效的种群初始化方法，同时将该种群初始化方法应用到变异算子中，且依据最优解的变化情况自适应地调整交叉和变异的概率。与此同时，针对环境信息的不同变化情况，结合全局路径规划结果对机器人进行局部避障方法的研究。最后，通过仿真实验证明本方法能够快速有效地在已知环境中得到机器人的最优路径，并且能够在局部变化的环境中实现实时避障。

关键词：搜索机器人；栅格法；全局路径规划；遗传算法；局部避障

中图分类号：TP242         文献标志码：A         文章编号：1672-7207(2011)11-3421-08

Global path planning and local obstacle avoidance of searching robot in mine disasters based on grid method

ZHU Lei^{1, 2}, FAN Ji-zhuang¹, ZHAO Jie¹, WU Xiao-guang¹, LIU Gang¹

(1. State Key Laboratory of Robotics and System, Harbin Institute of Technology, Harbin 150080, China;

2. Changchun Institute of Optics, Fine Mechanics and Physics, Chinese Academy of Sciences,

Changchun 130033, China)

Abstract: Aiming at the uncertainty of the environment in mine disasters, the gird model was built based on the GIS (geographic information system) map acquired from the mine in advance, and a modified genetic algorithm was provided for global path planning. An efficient method for population initialization which adopted the position information negative feedback like the ant colony optimization and priority grouping was provided. Also the population initialization method was applied to the mutation operator. The method self-adaptively adjusted the probabilities of crossover and mutation due to the change of the best resolution. According to the condition of the environment and combining with the global path planning result a local obstacle avoidance method was presented. Finally, the simulation results verify that the provided method can provide an optimal path in known environment effectively, and reallize the real time obstacle avoidance in locally changed environment.

Key words: searching robot; grid method; global path planning; genetic algorithm; local obstacle avoidance

随着时代的发展，煤炭作为一种重要能源，在国民经济发展中起着至关重要的作用。然而，许多煤矿为了获得暴利，不顾安全生产，使得近些年来矿难事故频发。与此同时，我国矿难搜救水平的落后也使得发生灾难后伤亡人数无法得到最大限度的减少^[1]。由于矿难发生的突然性以及破坏性，救援人员很难及时得到足够多的井下环境信息，而确认井下环境的安全是救援人员下井搜救的必要条件。研究表明：当幸存者被困在矿井内超过48 h后其生还的概率将会变得很低^[2]。因此，在井下情况未知甚至危险的情况下，矿难搜救机器人成了减少伤亡、降低损失的有效手段，对于提高我国矿难搜救水平将起到关键作用。

矿难搜索机器人作为一种移动机器人，其路径规划能力决定了其智能水平的高低。移动机器人的路径规划的主要任务是在具有静态或者动态障碍物的环境中，依据一定约束条件，寻找到一条没有碰撞的路径。同时，这些路径有时候要求满足一些优化参数，例如最短距离、最小时间和最低能耗等。针对环境信息的已知程度，可以将移动机器人的路径规划分为全局路径规划与局部避障。全局路径规划方法依据已知环境信息的情况，首先需要对环境建模，然后在环境模型中搜索出一条最优的路径。因此，目前根据环境建模形式可以将路径规划方法分为可视图法^[3]，C空间  法^[4]和栅格法^[5]等。依据搜索的方法的不同又可以分为A*法^[6]、Dijkstra方法^[7]和快速搜索随机树算法^[8]等。局部避障方法往往需要处理的是未知或者部分未知的环境。较为常用的有人工势场法^[9]、基于滚动窗口的方法^[10]和基于再励学习的方法^[11]等。

近年来，随着人工智能的发展，现代启发优化方法也被逐渐引入到路径规划中。Glasius等^[12]提出了一种基于Hopfield网络的实时、动态避障神经网络模型，能够避免局部最小点，但是很难适应高速的动态环    境。Xue等^[13]采用等距分布粒子群并结合危险度地图的方法，获得全局最优路径。Huang等^[14]提出了使用模糊逻辑行为对移动机器人在未知环境中进行实时路径规划。Zhang等^[15]采用目标吸引函数对基于蚁群算法的机器人路径优化进行了改进，从而使其能够顺利到达目标点。Ghorbani等^[16]设计了一种在非结构环境下基于知识遗传算法的路径规划方法。

利用栅格法表示地图十分简单且操作方便，已经成为地图表示方法中的一种常见方法。遗传算法作为一种优化方法，由于其鲁棒稳定性，也已经成为机器人路径规划问题的主要研究方向之一。因此，国内外的学者提出了一些基于栅格法的改进遗传算法用于机器人路径规划^[17-18]，并且在煤矿与矿难搜索机器人中也有应用^[19-20]。但是遗传算法较大的计算量、较慢的收敛速度以及由于早熟而陷入局部最优都是其主要问题。为了克服以上的缺点，借鉴蚁群算法信息素的思想，一些学者提出了基于信息正反馈的改进遗传算  法^[21-22]。本文作者提出了一种基于栅格模型的负反馈遗传算法对机器人进行全局路径规划。采用一种新的种群初始化方法生成初始路径，从而保证了初始生成路径的多样性与可行性。对变异算子进行了改进，并且自适应地调整交叉和变异的概率，从而避免了早熟现象。然后结合全局路径规划方法提出了一种基于栅格变化的局部避障方法。

1  环境模型的建立

机器人的路径规划中，基于真实环境的地图建模是十分重要的。众所周知，矿难发生后，井下的确切环境信息是很难直接获得的，但是并不是所有的信息都是未知的。为此做出如下定义，称在矿难中未被破坏的环境区域为“半可知道区域”。对于这样的区域其附近的环境信息是可以不用通过传感器就能确定的。由此可以做出这样的假设，将井下的所有环境区域均认定为“半可知道区域”。这些“半可知道区域”的信息可以从煤矿井下的GIS地图所获知，从而可以以此为基础对机器人进行全局路径规划，得到一个从井口到事故发生地点的一条最优的运动路径，这样当机器人进入井下后就可以照此路径前进。当机器人进入到破坏过的区域，则采取局部路径规划方法。通过局部避障方法与全局路径规划方法的结合，机器人能够顺利地到达事故发生地。考虑到用栅格方法表示二维的环境信息十分简便有效，应用也很广，因此，本文采用栅格法对环境进行建模。图1所示为一个基于栅格法建立的一个10×10栅格环境地图。空白栅格表示自由空间也就是机器人能够自由通过的地方，而阴影栅格表示的是障碍物空间，一般是在障碍物的实际边界的基础上加上一个通常和移动机器人的大小有关的安全距离，并且将其补为长方形。这样机器人就可以被看作环境中的一个点，可以不用考虑其尺寸大小^[23]。由于算法将会对栅格被选中的次数进行计数，因此，在初始时将栅格矩阵中的阴影栅格设置值为-1，空白栅格设置值为0。

栅格的表达和编码方式对于遗传算法也是一个关键因素，简单方便的编码方式，能够使得算法效率更高。为此，采用了序号法和二维直角坐标2种方法相结合的方式来表示栅格模型。利用序号法存储算法所产生的路径，既很容易操作，又能够节省存储空间。这样如图1所示的一个从1到100的无碰撞路径可以表示为 (1, 2, 3, 14, 25, 36, 47, 58, 69, 80, 90, 100)。当需要评价一个路径的优劣的时候，又通过式(1)把序号转换为二维直角坐标^[24]。这样可以很容易地得到2个节点之间的相对位置以及判断路径的可行性。

            (1)

式中：mod为取余数；int为取整数；m_x为一行中的栅格个数。

图1  基于栅格法的环境模型

Fig.1  Environment model based on grid method

2  全局路径规划方法

依据本文建立的环境栅格模型，可以离线地获得机器人的最优路径规划。为此，本文提出了一种改进的遗传算法应用于机器人的全局路径规划。

2.1  种群初始化

大多数的遗传算法都是随机地产生初始种群。但是在路径规划中这样的操作会导致产生许多不可行的路径。尽管一些不可行的路径可以通过相应的遗传算子变成可行的路径，但是也会使得适应度函数需要增加一些判断条件，从而使得函数变得复杂。另外还耗费了很多的计算时间在一些不可行的路径上，既浪费了存储空间，又降低了收敛速度。甚至有的不可行的路径会使得遗传算子失去意义。例如，2个不可行路径的交叉几乎很难得到可行的路径，同样变异操作也不容易使不可行路径变为可行。由以上的分析可以看出：如果选择更为有效地种群初始化方法将会使得遗传算法更加有效。因此，本文提出了一种基于蚁群算法信息素思想的位置信息负反馈并结合优先权分组思想的种群初始化方法，从而保证了所有生成路径的可行性以及多样性。具体步骤如下所示：

Step 1：依据栅格模型，首先获得当前节点A的坐标。如果是路径的第1个节点则将初始节点S的坐标代入节点A；

Step 2：基于当前节点A与终止节点F的坐标值，可以得到从节点A到节点F的最短路径所对应的方向，然后可以依据这个方向将节点A的8个邻居节点分为3个具有优先级的组；

Step 3：从第1组到第3组优先级逐级递减。优先在第1组中选取下一个路径上的节点,如果第1组中没有合适的节点，则在第2组中选取，以此类推。如果所有邻近节点都不可用，则将起始节点S的坐标再次代入节点A并转到Step 1。由于在Step 4中将会在一个计数器中记录一个节点被选中的次数。因此，在每一组中选择临近节点时，会参考节点的计数信息。其中，节点计数值最低的节点被选中的概率最大，与计数信息正好相反；

Step 4：如果节点B满足条件，把节点B加入到路径中，然后将节点B的坐标值代入节点A。同时对节点B对应的计数器加1；

Step 5：如果节点B和节点F重合，一次循环结束，产生了一个无碰撞的路径。如果没有重合则转到Step 1继续产生下一个节点；

Step 6：将路径保存到初始种群中，并对种群个体个数计数器加1，如果产生的初始个体数目达到了种群数，结束初始化，得到了初始种群。如果没有转到Step 1继续生成。

现在举例说明如何选择下一个节点。图2所示为相邻节点的信息。假定当前节点为图2(a)中的点0。如果最短的路径方向是垂直或者水平的，比如说是从节点0到节点5的方向，第1级分组包括节点3，5和8，第2级分组包括节点2和7，第3级分组包括节点1，4和6；如果方向是斜的也就是与节点0的4个45°角的邻近点相同或者相似，例如方向为节点0到节点8，第1级分组就包括节点5，7和8，第2级分组就包括节点3和6，第3级分组就包括节点1，2和4。如果节点0的邻近点的计数信息如图2(b)所示，并且假定最优方向是节点0到节点8，那么，节点7由于具有最低的计数信息，所以最有可能被选中。

图2  相邻节点的信息

Fig.2  Information of neighbor nodes

2.2  适应度函数设计

适应度函数用于评价路径的质量，决定了算法收敛的速度以及计算效率。因为不用对路径可行性进行判断，只要考虑能量与时间的消耗即可。因此，将路径的长度和拐点的个数作为优化指标，适应度函数表达式如下

          (2)

式中：为2个相邻节点之间的路径长度；n为路径中所有节点的个数；n_n为路径中拐点的总个数。

2.3  选择算子

采用比例选择算子从而保证优良的个体可以存活在种群中。具体方法就是依据父辈的适应度大小决定子代中该个体的个数：

        (3)

式中：f_i为个体i的适应度；p_popsize为种群大小。

2.4  交叉算子

算法采用单点交叉算子。首先随机的选择2个个体，然后选择2个个体中除了开始节点和终止节点的一个公共节点作为交叉节点，如果没有公共节点则不作任何操作。例如，一个个体为(1, 2, 3, 14, 25, 36, 47, 58, 69, 80, 90, 100)，另一个个体为(1, 12, 23, 34, 45, 56,67, 68, 69, 79, 89, 90, 100)。可以看到两者有两个共同节点69和90。因此，随机选择节点69作为交叉节点，交换2个个体在该节点之后的所有节点。这样交叉操作后的2个个体变为(1, 2, 3, 14, 25, 36, 47, 58, 69, 79, 89, 90, 100)和(1, 12, 23, 34, 45, 56, 67, 68, 69, 80, 90, 100)。

2.5  变异算子

变异操作使得种群变得多样，能够解决早熟问题，对于遗传算法十分重要。许多学者的研究中都是采用随机的变异操作，但是有时对于进化没有好处。因此，对传统的变异算子进行了改进。首先，仍然随机的选择一个个体的拐点进行变异，然后，选择这个拐点的邻近节点来代替拐点，邻近节点的选取不是等概率的，具有最低计数值的邻近节点被选中的概率最高，随后利用种群初始化中的方法生成一个连接变异拐点前一拐点、后一拐点和变异后的节点的路径。

2.6  删除算子

图3所示为删除算子和修正算子示意图。通常，如果一个路径的2个相交的线段的夹角是锐角或者直角，这条路径往往不是最短的路径。因此，需要删除算子来去掉一些不必要的节点改善路径。删除算子依据的原理是三角形的两边之和大于第3边。如图3(a)所示，节点3和7使得和分别为直角和45°锐角，这样通过删除算子就可以将这2个节点去掉，从而生成如图3(b)所示的新的路径(1, 2, 4, 5, 6, 8)。改变后的路径长度很明显短于改变前的。

2.7  修正算子

对于一些路径来说通过改变一些拐点的位置，可以减少转弯的次数，而并不影响路径总长度，这样使得路径得到了修正，能够获得更优的路径。如图3(b)中的节点5如果被图3(c)中节点9所替代，那么，生成的新路径将会更加合理，有利于机器人的控制。

图3  删除算子和修正算子示意图

Fig.3  Crossover and correcting operator

2.8  交叉和变异概率的选择

交叉和变异概率的大小很大程度上影响着遗传算法。交叉算子可以交换2个路径的信息，提供新的搜索节点，但是对于多样性没有任何帮助。而变异算子可以使得种群多样化。因此，首先应该选用一个较高的交叉概率从而使得算法能够产生优良的个体，一个较低的变异概率使得进化更加有效。为了避免早熟，当最优个体三代没有改变的时候，则通过一定步数减少交叉概率增加变异概率到各自设定的极限值。例如，初始的交叉概率和变异概率分别为0.5和0.05，极限值分别为0.4和0.25。这样如果步长值分别为0.25和0.5的话，经过4步之后概率都到了极限值而最优个体依然没有变化的话，则输出最优个体，算法结束。

2.9  精英保留策略

为了能够使得最优个体不会在下一代中消失，本文采用了精英保留策略。在算法中用第n+1代的最优个体与记录下来的前n代的最优个体比较。如果后者较优，则用前n代的最优个体代替第n+1代的最差个体；否则，不需要对种群进行操作，只是将第n+1代的最优个体记录下来即可。这样可以使得算法全局收敛^[25]。

2.10  方法分析

通过上述可以看出：由于本文所生成的初始路径都是可行的，而且经过各种遗传算子操作后依然是可行的路径，从而省去了许多对于路径是否可行的不必要判断，节省了计算量。采用了负反馈的机制可以使得生成的路径多样化，而且覆盖的栅格节点更多，更加有利于加速方法的收敛。通过自适应地调整交叉和变异概率，避免了早熟问题。可见本文所提方法是一种有效可行的方法。

3  局部避障方法

如果在机器人行进的过程中检测到周围的环境信息能够和GIS地图中的保持一致，机器人只要跟踪事先规划的全局路径即可；如果环境信息与GIS地图上的不相符时，机器人就需要启动局部避障方法。本文将针对2种环境的变化情况对机器人做出相应的局部避障策略。

3.1  障碍栅格转化为自由栅格的规划

当障碍物栅格转化为自由栅格时，会使得机器人的移动空间变得更大，不会对机器人的行进路线造成任何干扰，因此，不需对机器人的行走路径进行调整机器人依然能够到达目标节点，只要在地图中将原来的障碍栅格转换为自由栅格即可。这时候的局部避障策略就是继续跟踪全局路径规划。但是有时由于障碍物栅格的消失会使得机器人的全局最优路径可能变得不是最优的，因此，当机器人到达目标点后，将对最优路径进行一次删除算子和修正算子操作，从而可以使得返回的路径是最优的。例如，如果图3(c)中所示的障碍栅格变为自由栅格，可以看出节点1和节点6直接相连后的路径会比现在图3(c)中所示的路径性能更佳。

3.2  自由栅格转化为障碍栅格的规划

如果增加的障碍物栅格对规划的路径没有产生任何影响，只需对地图做出相应修改即可。如果障碍物栅格在机器人的行走路径上或者阻挡了机器人的行走路径，机器人就需要启动局部避障策略。这时就需要选择该障碍物栅格节点的临近栅格节点并且不在路径上的栅格节点作为新的路径上的栅格节点，然后利用和变异算子类似地操作生成一个连续路径供机器人继续跟踪。选择时根据优先级分组的思想来进行，但是优先选择使得障碍物栅格节点的上一路径节点与选择的障碍物栅格的临近栅格节点的连线方向与该障碍物栅格所在的线段的下一个线段的方向相同的栅格节点。图4所示为栅格节点的选择过程示意图。由于线段14的方向与线段23的方向一致，因此，选择节点4来代替障碍物栅格节点(图4)。

图4  栅格节点的选择过程示意图

Fig.4  Progress of choosing neighbor nodes

4  仿真结果分析

4.1  全局路径规划仿真结果

针对一些路径规划算法往往会在凹障碍物中陷入局部最优，从而无法进行规划的问题，本文在U型障碍物的环境中进行了仿真。仿真环境是一个10×10的栅格模型，其中阴影部分是一个U型障碍物，起始节点是S，终止节点是F，仿真结果如图5所示。结果显示机器人能够在如此复杂的环境中规划出一条从初始节点到目标节点的最优无碰路径，算法的鲁棒性和寻优能力都很强。

为了证实所提算法的有效性，和文献[18]中提出的方法进行了仿真比较，采用了和文献[18]一样障碍物分布的10×10栅格模型进行了仿真，如图6所示。

仿真参数设置如下，种群规模为10，交叉概率P_C的变化范围是从0.65到0.3，变异概率P_M的变化范围是从0.01到0.08，最大迭代次数为50。规划好的全局最优路径如图6中的实线所示。路径的长度为13.899 5，虽然与文献[18]中的路径长度一致，但是中间拐点的个数只有2个，规划后的路径效果更佳。而且在0.25 s内经过13代就可以收敛到最优解。可见本文提出的算法能够在较少的代数内收敛到最优解。

图5  U型障碍物环境中的仿真结果

Fig.5  Simulation result in U-shape obstacle

图6  全局路径规划仿真结果对比

Fig.6  Comparisons in global path planning

为了证明方法的一般性，在随机生成的一个较大较复杂的环境中利用方法对路径进行了规划。仿真环境和结果如图7所示，可以看出机器人能够在这种错综复杂的环境下依然能够找到最优路径，具有较强的鲁棒性。

图7  随机生成环境仿真结果

Fig.7  Result in random environment

由于本文所研究的方法是用于矿难搜索机器人的路径规划中。为此，按照矿井巷道的GIS地图得到了如图8所示的栅格地图，并应用本文所提方法得到了一条从开始节点到终止节点的最优机器人路径。

图8  煤矿GIS地图环境仿真结果

Fig.8  Result in environment based on mine GIS

4.2  局部避障仿真结果

图9所示为基于GIS地图所得的栅格环境，依据本文方法所得到的机器人的全局最优路径如图中实线所示。而图10所示为发生变化后的栅格环境，其中有三部分是由自由栅格变成了障碍栅格，有一部分是由障碍栅格变成了自由栅格。根据本文所提的局部避障策略得到的机器人最终行进路径如图10中实线所示，回程路径如图10中虚线所示。由此可见：本文提出的局部避障算法能够依据环境变化情况生成相应的最优路径，使得机器人依然能够到达目标节点。最后又通过环境信息的更新对回程路径进行了优化。

图9  初始全局路径规划结果

Fig.9  Global path planning result at beginning

图10  环境变化后的局部避障仿真结果

Fig.10  Local obstacle avoidance result after changes in environment

5  结论

(1)  提出了一种改进的遗传算法用于矿难搜索机器人的全局路径规划，并且以全局路径规划的结果为基础针对栅格的变化情况，设计了一种基于栅格变化的局部避障方法。

(2) 基于位置信息负反馈和优先级分组的思想改进了种群初始化方法，使得生成的路径都是可行的，节省了算法总体运行时间。采用了5种遗传算子，并在变异节点的替代节点的选择中采用了种群初始化的方法；以路径长度与拐点个数作为适应度函数的参数，使得算法的指标更佳优良；通过自适应地调节交叉算子与变异算子的概率从而使得算法保持多样性的同时又能提高进化速度。

(3) 针对不同的障碍形式与栅格变化情况对机器人进行了全局路径规划仿真与局部避障仿真，结果证明了方法的有效性与鲁棒性。

参考文献：

[1] 王忠民, 刘军, 窦智, 等. 矿难救援机器人的研究应用现状与开发[J]. 煤矿机械, 2007, 28(11): 6-8.
WANG Zhong-min, LIU Jun, DOU Zhi, et al. Research and application status and development of search and rescue robot for mine disaster[J]. Coal Mine Machinery, 2007, 28(11): 6-8.

[2] Casper J, Micire M, Murphy R R. Issues in intelligent robots for search and rescue[C]//Proceedings of SPIE 2000. Orlando: SPIE, 2000: 292-302.

[3] Alexopoulos C, Griffin P M. Path planning for a mobile robot[J]. IEEE Transaction on Systems, Man, and Cybernetics, 1992, 22(2): 318-322.

[4] Lozano-peres T. Spatial planning: A configuration space approach[J]. IEEE Transaction on Computers, 1983, 32(2): 108-120.

[5] Kambhampati S, Davis L S. Multiresolution path planning for mobile robots[J]. IEEE Journal of Robotics and Automation, 1986, 2(3): 135-145.

[6] Fan K C, Lui P C. Solving find path problem in mapped environments using modified A* algorithm[J]. IEEE Transaction on System, Man, and Cybernetics, 1994, 24(9): 1390-1396.

[7] Noto M, Sato H. A method for the shortest path search by extended dijkstra algorithm[C]//Proceedings of 2000 IEEE International Conference on Systems, Man, and Cybernetics. Nashville: IEEE, 2000: 2316-2320.

[8] Bruce J, Veloso M. Real-time randomized path planning for robot navigation[C]//Proceedings for the IEEE /RSJ International Conference on Intelligent Robots and System. Lausanne: IEEE, 2002: 2383-2388.

[9] Hwnag Y K, Ahuja N. A potential field approach to path planning[J]. IEEE Transactions on Robotics and Automation, 1992, 8(1): 23-32.

[10] 张纯刚, 席裕庚. 机器人滚动路径规划的算法与仿真研究[J]. 高技术通讯, 2003, 13(4): 53-57.
ZHANG Chun-gang, XI Yu-geng. Algorithm and simulation of robot rolling path planning[J]. High Technology Letters, 2003, 13(4): 53-57.

[11] Yung N H C, Ye C. An intelligent mobile vehicle navigator based on fuzzy logic and reinforcement learning[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1999, 29(2): 314-321.

[12] Glasius R, Komoda A, Gielen S. A biologically inspired neural net for trajectory formation and obstacle avoidance[J]. Biological Cybernetics, 1996, 74(6): 511-520.

[13] XUE Ying-hua, TIAN Guo-hui, HUANG Bin. Optimal robot path planning based on danger degree map[C]//Proceedings of 2009 IEEE International Conference on Automation and Logistics. Shenyang: IEEE, 2009: 1040-1045.

[14] Huang G, Tung C, Ciou J. To achieve the path planning of mobile robot for a correct destination and direction using fuzzy theory[C]//Proceedings of 2009 IEEE International Symposium on Industrial Electronics. Seoul: IEEE, 2009: 1737-1742.

[15] ZHANG Xiao-yong, WU Min, PENG Jun, et al. A rescue robot path planning based on ant colony optimization algorithm[C]//Proceedings of the 2009 IEEE International Conference on Information Technology and Computer Science. Kiev: IEEE, 2009: 180-183.

[16] Ghorbani A, Shiry S, Nodehi A. Using genetic algorithm for a mobile robot path planning[C]//Proceedings of the 2009 International Conference on Future Computer and Communication. Kuala Lumpur: IEEE, 2009: 164-166.

[17] Mansouri M, Shoorehdeli M A, Teshnehlab M. Integer GA for mobile robot path planning with using another GA as repairing function[C]//Proceedings of the IEEE International Conference on Automation and Logistics. Qingdao: IEEE, 2008: 135-140.

[18] LIAO Wei-qiang. Genetic algorithm based robot path planning[C]//Proceedings of 2008 International Conference on Intelligent Computation Technology and Automation. Changsha: IEEE, 2008: 56-59.

[19] 周巍, 李元宗. 基于改进遗传算法的煤矿探测机器人路径规划[J]. 太原理工大学学报, 2010, 41(4): 364-367.
ZHOU Wei, LI Yuan-zong. Path planning of coal mine detecting robot based on improved genetic algorithm[J]. Journal of Taiyuan University of Technology, 2010, 41(4): 364-367.

[20] 张小艳, 周筱媛, 魏娟. 煤矿救援机器人全局路径规划[J]. 西安科技大学学报, 2008, 28(2): 323-326, 335.
ZHANG Xiao-yan, ZHOU Xiao-yuan, WEI Juan. Global path planning for coalmine rescue robots[J]. Journal of Xi’an University of Science and Technology, 2008, 28(2): 323-326, 335.

[21] LEI Lin, WANG Hou-jun, WU Qin-song. Improved genetic algorithms based path planning of mobile robot under dynamic unknown environment[C]//Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation. Luoyang: IEEE, 2006: 1728-1732.

[22] 司应涛, 朱庆保, 国海涛. 基于正反馈遗传算法的机器人全局路径规划[J]. 计算机工程与应用, 2008, 44(1): 54-56, 62.
SI Ying-tao, ZHU Qing-bao, GUO Hai-tao. Global robot path planning based on positive feedback GA[J]. Computer Engineering and Applications, 2008, 44(1): 54-56, 62.

[23] LI Qing, Zhang W, Yin Y, et al. An improved genetic algorithm of optimum path planning for mobile robots[C]//Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications. Jinan: IEEE, 2006: 637-642.

[24] 陈曦, 谭冠政, 江斌. 基于免疫遗传算法的移动机器人实时最优路径规划[J]. 中南大学学报: 自然科学版, 2008, 39(3): 577-583.
CHEN Xi, TAN Guan-zheng, JIANG Bin. Real-time optimal path planning for mobile robots based on immune genetic algorithm[J]. Journal of Central South University: Science and Technology, 2008, 39(3): 577-583.

[25] Rudolph G.. Convergence analysis of canonical genetic algorithms[J]. IEEE Transaction on Neural Networks, 1994, 5(1): 96-101.

(编辑 陈爱华)

收稿日期：2010-11-22；修回日期：2011-02-20

基金项目：国家高技术研究发展计划(“863”计划)项目(2007AA041501)；哈尔滨市科技创新人才研究专项项目(2008RFQXG051)

通信作者：朱磊(1982-)，男，黑龙江哈尔滨人，博士研究生，从事矿难搜索机器人定位与导航研究；电话：13936137504；E-mail: rayjew@sohu.com