基于免疫遗传算法的移动机器人实时最优路径规划
陈 曦，谭冠政，江 斌
(中南大学 信息科学与工程学院，湖南 长沙，410083)
摘 要：以具有精英保留的免疫遗传算法(Immune genetic algorithm with elitism，IGAE)和栅格法为基础，提出一种新的移动机器人最优路径规划方法。其步骤为：首先采用栅格法对机器人工作空间进行划分，建立给定环境中移动机器人的自由空间模型；每个栅格用1个序号标识，并以路径上各栅格序号作为机器人路径的编码参数。然后，采用直角坐标和序号混合应用的方法产生初始种群，群体中每1个个体表示1条机器人路径，采用IGAE算法对种群进行优化，最终找出最优路径。为了保持种群初始化和遗传操作过程中个体所对应的路径的连续性和避障要求，在IGAE算法中引入删除、插入算子。计算机仿真实验结果表明，所提出的方法比基于全局收敛型遗传算法的路径规划方法更加快速和有效。
关键词：移动机器人；最优路径规划；免疫遗传算法；精英保留策略；插入算子；删除算子
中图分类号：TP242；TP306.1 文献标识码：A 文章编号：1672-7207(2008)03-0577-07
Real-time optimal path planning for mobile robots based on
immune genetic algorithm
CHEN Xi, TAN Guan-zheng, JIANG Bin
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: A novel method of optimal path planning for mobile robots was presented based on the proposed immune genetic algorithm with elitism (IGAE). The steps are as follows. Firstly, the grid theory is utilized to establish the free space model of the mobile robot in a given environment, and a sequence number is used to identify a grid. The sequence numbers are used to code the moving path of mobile robot. Secondly, the rectangular coordinates and the sequence number method are used to produce the initial population of IGAE, that is, the initial chromosomes are generated with a string of sequence numbers. Finally, an insertion operator and a deletion operator are defined to ensure that each obtained path is continuous and collision-free in the evolutionary process of IGAE. The results show that the proposed method is better than the genetic algorithm with elitism in the globally optimal path planning of mobile robots.
Key words: mobile robot; optimal path planning; immune genetic algorithm; elitism strategy; insertion operator; deletion operator
机器人路径规划是指在有障碍物的工作环境中，寻找一条最优的从给定起点到终点的运动路径，使机器人在运动过程中能无碰撞地绕过所有的障碍物。在实际应用中，常常要根据路径长度最短、所用时间最少或能源消耗最少等标准，来选择一条最优路径。一些研究者用人工势场法[1-3]、可视图法[2]和栅格法[3-5]等传统方法进行过机器人路径规划的研究。但传统优化方法在机器人路径规划这类复杂非线性优化问题中缺乏足够的鲁棒性。近10年来，随着人工智能研究不断取得进展，出现一些智能方法，如神经网络[6]、遗传算法[7]以及粒子群算法[8]等。目前，基于遗传算法的机器人路径规划已取得很大进展，但还有很多不足，如早熟收敛、容易陷入局部最优、局部搜索能力较弱、收敛速度慢等。在此，本文作者采用栅格法[9-11]对移动机器人工作环境进行建模，采用一种将免疫算法和遗传算法相结合的新算法 —— 免疫遗传算法(Immune-genetic algorithm with elitism，即IGAE)进行路径规划。免疫遗传算法在遗传算法的基础上引进了抗体浓度概念，并改进了编码方法，简化了种群初始化的过程。在IGAE算法中，定义插入和删除算子，以提高机器人的避障能力，保证最终所得路径的最优性。
1 移动机器人自由空间建模
采用栅格法建立移动机器人的自由空间模型。栅格法是由W. E. Howden提出的[12]。栅格粒度越小，障碍物的表示越精确，但同时会占用大量的存储空间，算法的搜索范围将按指数增加。若栅格粒度太大，则规划的路径不够精确。所以，确定栅格粒度是栅格法中的主要问题。
采用栅格法对移动机器人的自由空间建模时，需进行如下假设：
a. 不考虑高度问题，机器人工作空间为二维结构化空间。
b. 假设障碍物的位置和大小已知，并且在机器人运动过程中，障碍物的位置和大小都不发生变化。
c. 用尺寸相同的栅格对机器人二维工作空间进行划分，按照机器人及空间确定栅格数目，栅格以机器人可以在其中运动为限。若某一栅格内不含任何障碍物，则称此栅格为自由栅格，反之称为障碍栅格。建模后的机器人工作空间如图1所示，图中阴影部分表示障碍栅格。
采用下述2种方法对栅格进行标识。
a. 直角坐标法。如图1所示，以栅格图的左上角为坐标原点，水平向右为X轴正方向，竖直向下为Y轴正方向，每1栅格区间对应坐标轴上的一个单位长度。任意栅格均可以用直角坐标(x, y)惟一标识。
图1 直角坐标法和序号法建立的栅格模型
Fig.1 Grid model established by rectangular coordinates and sequence number method
b. 序号法。如图1所示，按从左到右、从上到下的顺序栅格序号逐渐增长，从左上角第1个栅格开始，给每1个栅格1个序号N，则序号也与栅格一一对应。
给出以上2种表示方法的转换关系：
下述讨论中，将序号法和坐标法混合应用，机器人运动路径采用栅格序号法表示，因为序号法比直角坐标节省内存，易便于遗传操作。对路径进行评价时，将序号转换成坐标形式，因为坐标法更便于表示栅格之间的相对位置，计算路径长度及检验路径可行性。
2 一种改进的免疫遗传算法
免疫遗传算法与遗传算法的结构非常类似，一般也包含选择、交叉和变异3种操作。不同的是，在遗传算法中，个体的品种只采用适应度来评价；而在免疫遗传算法中，个体(抗体)的品种则同时采用适应度和浓度2个指标来评价。抗体的浓度概念最初是由T. Fukuda等[13]提出来的。引入抗体浓度概念后，与遗传算法相比，免疫遗传算法的群体更新策略有了很大改变。在进行选择操作时，在遗传算法中，个体的选择概率仅与适应度有关；而在免疫遗传算法中，个体的选择概率既与适应度有关，也与浓度有关。与遗传算法相比，免疫遗传算法具有更强的群体多样性保持能力和学习能力。
2.1 免疫遗传算法中的几个重要定义
设有一个规模为m的抗体群，其中每一个抗体都可以表示成1个具有n个元素的一维向量。下面给出抗体的相似度、浓度、期望繁殖率、选择概率等定义。
定义1 在特定的、规模为m的抗体群中，假定每个抗体都可以被表示成1个具有n个元素的一维向量。任取2个抗体v={v1, v2, …, vn}和w={w1, w2, …, wn}，设抗体v和w的适应度分别为fv和fw，假定ε是1个适当小的正常数(ε＞0)，若
成立，则称抗体v与抗体w相似。其中：
为反映抗体v与抗体w品质相似性的指标；e 称为抗体相似度阈值。这里，抗体的品质是指它的适应度，适应度越大的抗体其品质越好。若取e =0.02而式(3)成立，则称抗体v与抗体w在品质上有98%的相似性。
式(3)是一种新的抗体相似度定义方法。这种定义有2个优点：
a. 与基于信息熵[13]和欧氏距离[14]的抗体相似度定义相比，这种采用百分比表示的定义对2个抗体相似程度的描述更直观；
b. 与基于信息熵和欧氏距离的抗体相似度定义相比，这种新定义的计算量更小。
2.1.1 基于信息熵的抗体相似度定义
对二进制串而言，等位基因数为2(即等位基因等于0或1)。假定1个抗体可用1个含n个二进制位的染色体表示，根据概率论的理论，任一抗体的第j (j=1, 2, …, n) 个基因座上的等位基因为0或1的概率是等可能的，其概率Pi, j的取值范围为Pi, j ?[0, 0.5, 1]。根据文献[13]中抗体相似度定义，判断2个抗体v与w是否相似，共需执行2n次log对数运算，2n次乘法运算，n+1次加法运算，2次除法运算以及1次大小比较运算。
2.1.2 基于欧氏距离的抗体相似度定义
根据文献[14]中的抗体相似度定义，判断2个抗体v与w是否相似，共需执行n+1次减法运算，n-1次加法运算，n次平方运算(相当于n次乘法运算)，1次除法运算，1次平方根运算，1次绝对值运算以及2次大小比较运算。
2.1.3 本文给出的抗体相似度定义
根据定义1，判断2个抗体v与w是否相似，共需执行(n+2)/2次除法运算以及2次大小比较运算。
如果近似认为减法与加法的计算量相等、除法与乘法的计算量相等，那么，本文给出的抗体相似度定义其计算量远比基于信息熵和欧氏距离的要小。考虑到抗体相似度的计算是免疫遗传算法中计算量最大的一部分，所以，所给出的定义对提高免疫遗传算法的计算效率有很大的促进作用。
定义2 在特定的、规模为m的抗体群中，与抗体k(k=1~m)相似的抗体(包括抗体k自身)的个数称为抗体k的浓度，记为ck。
定义3 对于特定的、规模为m的抗体群，抗体k(k=1~m)的期望繁殖率ek 定义为：
定义4 对于特定的、规模为m的抗体群，设抗体k(k=1~m)的期望繁殖率为ek，则抗体k被选择进行复制(克隆)的概率Psk为：
从式(5)可以看出，免疫遗传算法的选择概率不仅与个体的适应度有关，而且与个体的浓度有关。这是免疫遗传算法与遗传算法最大的区别。
2.2 精英保留策略
“精英保留”策略是针对遗传算法提出来的[15]。对遗传算法来说，能否收敛到全局最优解是其首要问题。G. Rudolph[16]采用有限马尔可夫链理论证明了：仅采用交叉、变异和选择3个遗传算子的标准遗传算法(Canonical genetic algorithm，即CGA)，若交叉概率Pc ?(0, 1)，变异概率Pm?(0, 1)，并且采用比例选择法，则它不能收敛到全局最优解。
为了防止当前群体的最优个体在下一代丢失，导致遗传算法不能收敛到全局最优解，de. K. A. Jong[15]提出了“精英选择”策略。该策略也称为“精英保留”策略，其思想是，把群体在进化过程中迄今出现的最好个体(称为精英个体elitist)不进行配对交叉而直接复制到下一代中。这种选择操作又称为复制。精英选择方法的定义如下。
定义5[15] 设遗传算法进化到第t代时，群体中a*(t) 为最优个体。又设A(t+1)为新一代群体，若A(t+1)中不存在a*(t)，则把a*(t) 加入到A(t+1)中作为A(t+1)的第n+1个个体，这里n为群体的大小。
为了保持群体的规模不变，若精英个体被加入到新一代群体中，则可以将新一代群体中适应度最小的个体淘汰。精英个体是种群进化到当前为止遗传算法搜索到的适应度最高的个体，它具有最好的基因结构。采用精英保留的优点是：遗传算法在进化过程中，迄今出现的最优个体不会被选择、交叉和变异操作所丢失和破坏。精英保留策略对改进标准遗传算法的全局收敛能力产生了重大作用，具有精英保留的标准遗传算法是全局收敛的[16]。
3 基于免疫遗传算法的最优路径规划
3.1 个体编码
个体表示移动机器人在其工作空间中的一条运动路径。如图1所示，机器人由其起始位置S沿图中实线所示路径运动到终点位置E，即为1个个体。该个体用直角坐标形式可表示为：{(0, 0), (0, 1), (0, 2), (1, 3), (2, 4), (3, 5), …, (9,9)}。若每一位坐标用4位二进制数表示，则同一个体可表示为：{0 000, 0 000, 0 000, 0 001, …, 1 001, 1 001}。若用栅格序号表示，则同一个体可表示为：{0, 10, 20, 31, 42, 53, …, 99}。由此可见，个体采用栅格序号编码较直角坐标或二进制编码长度短、简明、直观。
3.2 种群初始化
初始群体是遗传算法迭代运算的起点，它由一定数目的个体组成，在机器人运动的起点S到终点E之间，用一系列随机选择、自由、不一定连续的栅格序号连接S和E。在种群初始化过程中，确保个体基因位上填充的都为自由栅格，并且初始种群中的每个个体的长度大于3，再经过插入、删除操作生成一系列不间断无障碍路径。采用这种操作方法有利于种群初始化。
3.3 个体适应度函数
个体的适应度函数与免疫算法的计算时间和效率密切相关。这里所讨论的问题是求从起始点到终点的1条最优路径，且该路径不能与障碍物相交，以确保机器人按这条路径运动时不与障碍物发生碰撞。选取如下个体适应度函数：
由式(6)可见，f与机器人运动距离L成反比，因此，该优化问题以距离最短作为目标函数。但是，若仅取运动距离L作为评价标准，则个体容易陷入早熟收 敛。因此，在式 (6) 中引入
，其目的是尽量消除算法运行过程中所产生的间断点相距太远的过短路径。
3.4 遗传算子
3.4.1 选择算子
采用比例选择方法，其基本思想是：各个个体被选中的概率与其适应度成正比而与浓度成反比，即使个体按照与期望繁殖率成正比的概率向下一代群体 繁殖。
3.4.2 交叉算子
交叉是指把2个父代个体的部分结构替换重组而生成新个体的操作。这里采用单点和重合点混合的交叉方式。重合点交叉是指随机选取得2个个体，选择栅格序号完全相同的点进行交叉操作。当重合点多于1个时，随机选择其一进行交叉。若没有重合点，则随机选择交叉点进行单点交叉。
3.4.3 变异算子
采用从个体中以一定概率选择1个起点和终点之外的序号作为变异点进行变异操作。
3.4.4 删除算子
为了保持种群初始化和免疫操作过程中个体所对应的路径的合理性，引入删除算子。定义机器人运动的8个方向，分别是：上、下、左、右、右上、右下、左上、左下。对于图1所示模型，以右下方向为最优路线。所以，当机器人的右方、左下方、右下方的栅格都在路径上时要删除右方和左下方的栅格，使机器人向右下方运动，从而保证路径最短。
3.4.5 插入算子
引入插入算子的主要作用是为了保持种群初始化和免疫操作过程中个体所对应的路径的连续性。插入操作分以下2步进行。
第1步，使间断路径相临化。把间断路径用自由栅格弥补，使路径上的栅格都是相邻栅格。可采用下式来判断个体中2个序号为Z1和Z2的栅格是否相邻：
不相邻时，按中值法计算候补插入点：
若计算得到的N为自由栅格，则可将其直接插入；若N为障碍栅格，则选择一个与N最近的自由栅格作为新的候补插入点；若找不到这样的候补插入点，则宣告插入失败，舍去该个体，否则，用新的候补点插入到Z1和Z2 之间。上述插入过程重复执行，直到个体中的每个栅格都是相邻栅格为止。
第2步，使路径连续化。相邻栅格存在几种位置关系，如图2所示。
(a) 可插入栅格；(b) 不可插入栅格
图2 相邻栅格之间的位置关系
Fig.2 Relationship between positions of adjacent grids
在图2(a)中，栅格1和4虽然为相邻栅格，但并不是连续路径的一部分，所以，为了保证路径的连续性，需要插入栅格3；图2(b)中，由于路径为不连续路径，故舍去。
3.5 机器人移动路径规划算法流程
利用免疫遗传算法进行移动机器人路径规划的算法流程可归纳如下。
Step 1 对于一个给定的移动机器人路径规划问题，采用栅格理论建立移动机器人的自由空间模型，并采用免疫遗传算法进行优化。
Step 2 随机产生m个初始个体(抗体)，对个体进行删除和插入操作，保证初始群体中个体所对应路径的连续性和无障性。
Step 3 确定每个个体的适应度，将适应度最大的抗体作为精英抗体保存在1个专用变量中(适应度越大，则对应目标函数的路径越短)。
Step 4 若为第1代抗体群，则转到Step 7；否则，继续执行下步操作。
Step 5 确定每个抗体的适应度；若这一代抗体群中没有与精英抗体适应度相同的抗体，则将保存在专用变量中的精英抗体复制1个到抗体群中，并将该抗体群中适应度最小的抗体删除；否则，继续。
Step 6 若这一代抗体群中适应度最大的抗体其适应度大于精英抗体的适应度，则将抗体群中适应度最大的抗体复制1个，并以它作为新的精英抗体替代保存在专用变量中的精英抗体；否则，继续。
Step 7 依据抗体的相似度定义，即式(3)，计算每个抗体的浓度。
Step 8 依据式(4)计算每个抗体的期望繁殖率；依据式(5)计算每个抗体的选择概率；根据选择概率应用比例选择法对抗体群执行选择和复制操作。
Step 9 对抗体群执行交叉操作，交叉概率
Step 10 对抗体群执行变异操作，变异概率
。
Step 11 判断设置条件是否满足。若条件满足，则输出结果，算法停止；若条件不满足，则返回到Step 5，继续循环操作。
4 计算机仿真实验及结果分析
分别采用精英保留遗传算法(GAES)和本文提出的带精英保留的IGAE免疫遗传算法去寻找相同环境下机器人的最优路径，并比较2种算法的收敛速度和搜索到的最好结果。2种算法基本参数设定如下：机器人的仿真运动环境为15×15栅格空间；最大进化世代N=50；群体规模为60；交叉概率Pc=0.6，采用相同点交叉和单点交叉结合的方法；变异概率Pm =0.01；b=1.5。需优化的目标函数为：
即目标函数F与适应度f成反比，与路径长度L成正比。
4.1 动态仿真
为了直观体现算法的有效性，进行仿真实验。这里用VISUAL C++ 6.0平台进行动态仿真，动态仿真过程所采用的工作空间是由15×15个栅格组成，分别用S和E表示机器人路径的起点和终点。仿真结果如图4和图5所示。其中：实线表示算法所产生的最优路径。
从图3和图4可看出，IGAE算法比GAES算法的收敛速度快且搜索到的路径短。IGAE产生的最优目标函数值和收敛代数分别为：F1=28.527 0，N1=6；GAES产生的最优目标函数值和收敛代数分别为：F2=29.705 5，N2=10。
图3 IGAE算法动态仿真结果
Fig.3 Simulation results of IGAE algorithm
图4 GAES算法动态仿真结果
Fig.4 Simulation results of GAES algorithm
4.2 IGAE与GAES的比较
4.2.1 计算效率比较
表1所示为IGAE算法和GAES这2种方法的计算效率对比结果，是以50次随机实验结果为基础统计出来的。从表1可以看出，IGAE算法的计算效率比GAES算法计算效率高。
表1 IGAE算法和GAES算法的计算效率比较
Table 1 Comparison of computation efficiency obtained by IGAE algorithm and GAES algorithm
4.2.2 收敛速度比较
2种算法在1次实验中最佳目标函数值的变化曲线如图5所示。从图5可以看出，IGAE算法的收敛速度比GAES算法的收敛速度快。
1—IGAE算法；2—GAES算法
图5 IGAE算法和GAES算法的收敛过程
Fig.5 Convergence tendencies of IGAE algorithm and GAES algorithm
4.2.3 解的波动性
为了比较IGAE和GAES这2种进化算法在多次实验中所产生的最优解的波动情况，采用这2种算法分别对目标函数各进行50次仿真实验，各种算法每次实验的初始群体都是随机选取的。引入样本标准差δ作为波动性评估指标：
表2所示为50次实验中目标函数的最大值、最小值、平均值、最大值与最小值的差值以及根据式(10)计算2种算法在N=50次仿真实验中的样本标准差δ。
表2 IGAE算法和GAES算法样本标准差δ的比较
Table 2 Comparison of standard deviation δ of IGAE algorithm and GAES algorithm
由表2可知，多次运行IGAE算法所产生的解的波动范围比GAES算法的波动范围要小得多，说明IGAE算法所产生的解集中度较高，稳定性较强。
5 结 论
a. 采用IGAE算法很好地解决了遗传算法(GA)中存在的早熟收敛、局部搜索能力较弱、收敛速度慢等问题。
b. 计算机仿真实验结果表明，采用这种基于免疫遗传算法的路径规划方法不仅可以有效地找到全局最优路径，而且完成一次路径规划所需的时间仅为几十毫秒，完全可用于对移动机器人进行在线路径规划。
c. 所提出的基于免疫遗传算法的路径规划方法在收敛速度、计算效率和解的波动性方面都优于基于精英保留遗传算法的全局路径规划方法。
参考文献：
[1] Ge S S, Cui Y J. New potential functions for mobile robot path planning[J]. IEEE Transactions on Robotics and Automation, 2000, 16(5): 615-620.
[2] 李 磊, 叶 涛, 谭 民. 移动机器人技术研究现状与未来[J]. 机器人, 2002, 24(5): 475-480.
LI Lei, YE Tao, TAN Min. Present state and future development of mobile robot technology research[J]. Robot, 2002, 24(5): 475-480.
[3] 王醒策, 张汝波, 顾国昌. 基于势场栅格法的机器人全局路径规划[J]. 哈尔滨工程大学学报, 2003, 24(2): 170-174.
WANG Xing-ce, ZHANG Ru-bo, GU Guo-chang. Potential grid based global path planning for robots[J]. Journal of Harbin Engineering University, 2003, 24(2): 170-174.
[4] 于红斌, 李孝安. 基于栅格法的机器人快速路径规划[J]. 微电子学与计算机, 2005, 22(6): 98-100.
YU Hong-bin, LI Xiao-an. Fast path planning based on grid model of robot[J]. Microelectronics & Computer, 2005, 22(6): 98-100.
[5] 庄慧忠, 杜树新, 吴铁军. 机器人路径规划及相关算法研究[J]. 科技通报, 2004, 20(3): 210-215.
ZHUANG Hui-zhong, DU Shu-xin, WU Tie-jun. Research on path planning and related algorithms for robots[J]. Bulletin of Science and Technology, 2004, 20(3): 210-215.
[6] 陈少斌, 蒋静坪. 基于神经网络和粒子群优化算法的移动机器人动态避障路径规划[J]. 系统仿真技术, 2006, 2(4): 192-197.
CHEN Shao-bin, JIANG Jing-ping. Neural network and particle swarm optimization based on dynamic obstacle avoidance and path planning for mobile robots[J]. System Simulation Technology, 2006, 2(4): 192-197.
[7] 刘彩虹, 胡吉全, 齐晓宁. 基于混合遗传算法的连续空间下机器人的路径规划[J]. 武汉理工大学学报: 自然科学版, 2003, 27(6): 819-821.
LIU Cai-hong, HU Ji-quan, QI Xiao-ning. Path design of robot within continuous space based on hybrid genetic algorithms[J]. Journal of Wuhan University of Technology: Natural Science, 2003, 27(6): 819-821.
[8] 秦元庆, 孙德宝, 李 宁, 等. 基于粒子群算法的移动机器人路径规划[J]. 机器人, 2004, 26(3): 222-225.
QIN Yuan-qing, SUN De-bao, LI Ning, et al. Path planning for mobile robot based on particle swarm optimization[J]. Robot, 2004, 26(3): 222-225.
[9] 张 颖, 吴成东, 原宝龙. 机器人路径规划方法综述[J]. 控制工程, 2003, 10(5): 152-155.
ZHANG Ying, WU Cheng-dong, YUAN Bao-long. Progress on path planning research for robot[J]. Basic Automation, 2003, 10(5): 152-155.
[10] 周郭许, 唐西林. 基于栅格模型的机器人路径规划快速算法[J]. 计算机工程与应用, 2006, 21(1): 197-199.
ZHOU Guo-xu, TANG Xi-lin. A fast algorithm based on grids for mobile robot path planning[J]. Computer Engineering and Applications, 2006, 21(1): 197-199.
[11] 张捍东, 董保华. 栅格编码新方法在机器人路径规划中的应用[J]. 华中科技大学学报: 自然科学版, 2007, 35(1): 50-53.
ZHANG Han-dong, DONG Bao-hua. Application of path encoding novel mechanism based on grids in path planning for mobile robot[J]. Journal of Huazhong University of Science and Technology: Nature Science Edition, 2007, 35(1): 50-53.
[12] Howden W E. The sofa problem[J]. The Computer Journal, 1968, 11(3):299-301.
[13] Fukuda T, Mori K, Tsukiyama M. Parallel search for multi-modal function optimization with diversity and learning of immune algorithm[C]//Dasgupta D. Artificial Immune Systems and Their Applications. Heidelberg, Springer-Verlag, 1999: 210-220.
[14] 郑日荣. 基于欧氏距离和精英交叉的免疫算法研究[D]. 广州: 华南理工大学自动化科学与工程学院, 2004: 60-71.
ZHENG Ri-rong. Artificial immune algorithm based on euclidean distance and king-crossover[D]. Guangzhou: College of Automation Science and Engineering, South China University of Technology, 2004.
[15] de Jong K A. An analysis of the behavior of a class of genetic adaptive systems[D]. Michigan: University of Michigan, 1975: 76-9381.
[16] Rudolph G. Convergence analysis of canonical genetic algorithms[J]. IEEE Trans on Neural Networks, 1994, 5(1): 96-101.
收稿日期：2007-07-28；修回日期：2007-09-21
基金项目：国家自然科学基金资助项目(50275150)；教育部博士点基金资助项目(20040533035)
通信作者：谭冠政(1962-)，男，湖南湘潭人，博士，教授，博士生导师，从事机器人路径规划研究；电话：13973188535；E-mail: tgz@mail.csu.edu.cn
