基于可拓遗传算法的机器人路径规划

王科俊，徐晶,王磊，张燕

(哈尔滨工程大学自动化学院，哈尔滨 150001, E-mail: kyssia@163.com)

摘要: 本文将可拓理论应用到遗传算法中解决路径规划问题。在原有遗传算法基础上，用扩展物元来表示机器人的位置信息，使计算机能够较容易读懂这种语言，加快了计算速度；用关联函数作为遗传算法的适应度函数，使算法更容易找到最优化路径；采用可拓工程方法中的三种可拓变换形式，丰富了遗传算法的变异方式。实验证明，可拓遗传算法的机器人路径规划能有效提高的机器人路径规划的速度和准确性。

关键词：可拓遗传算法；路径规划；机器人

中图分类号：TP242.6

The Path Planning for Robots Based on the Genetic Extension Algorithms

Wang Ke-jun,Xu Jing,Wang Lei,Zhang Yan

(School of Automation，Harbin engineering University ,Harbin, 150001, China, E-mail: kyssia@163.com)

Abstract：The paper proposes a technique that extension theory is used in genetic algorithms to solve the problem of path planning. Based on the original genetic algorithm, extended matter elements present the position of robots, which makes the computer reading the language much easier and accelerates the computing speed. As the fitness function in genetic algorithms, dependent function makes the algorithm easier to find the optimization path. Three kinds of extension transformation in extension engineering method are adopted which enrich the mutation patterns in genetic algorithm. Final experiment proves that the extension genetic algorithms effectively improve the speed and accuracy in robot path planning.

Key words：extension genetic algorithms; path planning; robot

目前，国内外对机器人路径规划方法的研究主要有两大类，传统方法与智能方法。传统方法主要包括：梯度法、栅格法、枚举法、人工势场法、自由空间法、A*等图搜索方法及随机搜索法等。其中梯度法易陷入局部最小点，图搜索法、枚举法不能用于高维的优化问题，势场法则存在丢失解的部分有用信息的可能。用于机器人路径规划的智能方法主要有模糊逻辑、神经网络、遗传算法等，而模糊方法主要用于在线的规划中，自适应性较差。神经网络方法对于环境复杂的情况，规划能力较差，遗传算法则是目前应用较多的一种方法，受到了广大研究者的重视．但是，用遗传算法进行机器人路径规划时，随机产生初始种群，种群规模大导致搜索空间较大，删除冗余个体能力较差，大大影响了路径规划的速度，特别是环境复杂或多机器人路径规划时，这种缺点更是明显。笔者在原有基于遗传算法的机器人路径规划方法的基础上，引入了可拓学理论，对遗传算法进行了改进，以提高机器人路径规划的速度和能力。

1 基于栅格的可拓遗传算法路径规划

可拓学是1983年由我国学者蔡文提出的一门原创性学科，主要研究不相容问题的转化与解决的规律。经过二十年的发展已经形成了它的理论框架，并且在信息、知识生成、管理、营销、策划、控制、数据挖掘等许多领域得到了应用。可拓学现在已经成为人工智能领域中一个新的学术研究热点。

本文将可拓理论应用到遗传算法中解决路径规划问题。

（1）采用可拓物元的表示方法来表示机器人的位置信息；

（2）将可拓学中的主要概念――关联函数作为遗传算法的适应度函数；

（3）采用可拓工程方法中的三种可拓变换形式，丰富了遗传算法的变异方式。

1.1 栅格表示模型

为了模拟机器人的工作环境需要对其工作空间建立模型，只考虑机器人工作空间的平面状况，在二维空间中采用栅格法来建立机器人的工作空间模型，按照机器人及工作空间的大小来确定栅格的数目，以保证机器人可以在其中自由移动。用直角坐标法在矩形的工作空间中建立多个等值大小的小栅格(以10×10的栅格为例)。将直角坐标法同序号法相结合使用，根据条件的不同按照映射关系进行变换。自由空间和障碍物均可表示成栅格块的集合。划分后的机器人工作空间如图2所示，图中阴影区为障碍物。

(a) 直角坐标法 (b) 序号法

图2

(1) 直角坐标法。以栅格阵左上角为坐标原点，水平向右为x轴正方向，竖直向下为y轴正方向，每一栅格区间对应坐标轴上的一个单位长度。任一栅格均可用直角坐标(x, y)唯一标识。

(2) 序号法。按从左到右，从上到下的顺序，从栅格阵左上角第一个栅格开始，给每一个栅格一个序号P(从零开始计)，则序号P与栅格块一一对应。

对三类障碍物要进行可拓变换：

(1) 障碍物的合并

当移动机器人检测如上面图2所示的情况时，应进行合并。当机器人在24点或者25点搜索时，在其搜索半径内检测到34,35点时，发现其四周为障碍物，这样34, 35就被当成障碍物，同理可知24，25，34，35这四个点都被当成障碍物处理，这就是所谓的障碍物合并。

(2) 相邻对角线上的障碍物的处理

当机器人在75点或者84点搜索时，适应度函数就发生变化。

(3) 地图边界的处理

将地图的边界当成障碍物处理。

1.2 路径规划的可拓遗传算法

1.2.1 编码

用物元的表示方法来表示机器人的位置信息，即将物元的表示方法与遗传算法中的编码相结合这样能将位置数据以物元的形式在数据库中存放，使计算机能够较容易地读懂这种语言，加快了计算速度。

编码步骤:

(1) 在机器人路径规划中最重要的参数就是机器人的位置

机器人位置信息用可变物元表示:

机器人，其中，，代表位置，，，代表栅格中的序号或坐标。

(2) T =[a,b]为所对应的量值的定义域，且,为在的t个区间, 其中，形式为遗传算法编码中的浮点数形式。

（3）扩展物元表示为

机器人扩展物元表示为，其中，，表示0或1，0表示此位置没有障碍物，1表示此位置有障碍物。

1.2.2可拓适应度函数

所输入的信息中每个属性在上建立属性关联函数

对每个属性确立权系数，即取权系数，,一般参考经验数据确定。中各属性关联函数，构成关联函数向量，根据中各属性权值构造全局关联函数，即可拓适应度函数:

可拓集合用取自的实数来表示具有某种性质的程度，它的关联函数值域扩展到。可以说，可拓集合论既考虑状态，又考虑变量。因此，我们用此全局关联函数检测所输入的每条信息，把此信息集分为两大类:

第一类，，对于的事物构成信息集根据的大小也可以比较信息集中事物的优质程度，可用数字1，2, 3.…，P对应，描述所输出信息的优质程度。对于机器人所在的栅格图中，表示没有障碍物，而的大小和离障碍物的距离有关，离障碍物的距离越远则越大。，则对对应的事物进行遗传，得到新集合。

第二类，对于的事物构成的信息集,根据的大小也可比较信息集中事物的劣质程度，可用数字-1,-2,-3…-P对应，描述所输出信息的劣质程度。对于机器人所在的栅格图中，表示有障碍物，而越小，则离障碍物的中心距离越近。，则对对应的事物进行变异。

因此，通过使用上述可变关联值函数，进化过程将找到越来越好的路径。

1.2.3可拓变异

遗传算法利用复制算子和杂交算子产生具有更高适应值的个体的群体，如果父代中遗传物质较好的话，经过复制和杂交后的子代串的适应值则会较高。

遗传算法中选择复制过程可用的一种常用技术一－赌盘选择方法，即令表示群体的适应度值之总和，表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额为。选择的结果是返回一个随机选择的串，选择过程是随机的，但每个串被选择的机会却直接与其适应值成比例，那么没被选中的串则从群体中被淘汰下去，由于执行的随机性，群体中适应值最差的串有时也可能被选中，这会影响到遗传算法的执行效果。

本文利用可拓理论中可拓变换的思路与关联函数值检验的方法选择适应值高的个体进行复制，避免了赌盘选择的概率误差，丰富了遗传算法的技术。应用可拓变换中的三种基本变换一－置换变换、扩缩变换与增删变换，改变某一特征值，进而再用关联函数重新计算其适应值，从被复制的个体中再选择优秀个体作为父代进行交叉，这样能使遗传物质较好的个体作为父代进行遗传，提高经过复制和杂交后的子代的适应值。

变异算子在遗传算法中起着相当重要的作用，它不仅被视为找回因交叉操作而遗失的优良基因的手段，而且还是探索相邻空间、优化性能的有力工具。本文中的变异操作与可拓工

中的置换变换、扩缩变换、增删变换相统一，记为置换变异，扩缩变异，增删变异。应用于路径规划中变异方式主要有三种：增加一个点，减少一个点，移动一个点，如图3所示。

（a）变异操作－增加一个点（b）变异操作－减少一个点

（c）变异操作－移动一个点

图3

1.3.4终止条件

遗传算法的终止采用最大进化代数和设定收敛条件的复合准则。当遗传算法满足设定的收敛判断条件时，遗传算法终止；若进化了指定的代数仍然没有满足设定的收敛判断条件，也令遗传算法终止本文将判断算法收敛的条件设为:若连续进化5代，最优解均未发生变化，

且种群的平均适应值提高不足1%,或算法进化代数己达到了设定的最大值。

2 机器人路径规划的仿真

为了验证提出的方法的有效性，我们进行了大量的仿真实验。实验是在WindowsXP环境下，用VC++6.0实现了上述遗传进化算法。在实验中，取n＝16，群体规模m＝20，遗传代数generation=1000；遗传算子＝0.25，＝ 0.01，这时系统能够较快的收敛。用本文提出的可拓遗传算法所规划的路径能够很好地避开障碍物，从而有效提高了机器人操作的稳定性。而且该算法的搜索时间比遗传算法的少，提高了搜索的效率。仿真结果如图4所示

	最小值	最大值	平均值
可拓遗传算法	0.56s	0.97s	0.77s
遗传算法	1.31s	2.07s	1.69s

图4

3 结论

本文的基于物元的可拓遗传算法，用物元的形式表示复杂的事物，并结合遗传算法编码的表示方法，使得路径规划算法计算简便，过程清晰,通过可拓理论中物元的可拓变换即置换变换、扩缩变换和增删变换，继而重新利用关联函数检验适应值的方法代替遗传算法的“赌盘选择”方法来选出进行复制的部分，使得计算结果更科学准确，进而，在对部分数据进行变异的过程中，采用可拓工程方法中的三种基本的物元可拓变换形式，丰富了遗传算法的变异方式。

本文研究的路径规划环境是二维空间，环境的表述相对简单，在程序设计和计算方面所花费的时间和占据的存储空间均较少。而在三维空间里，随着维数的增加，其搜索空间呈指数增加，这对算法性能提出严峻的挑战。其次，所研究的算法目前仅在计算机上进行了仿真，将其应用在实际的机器人系统中如何实现以及其效果究竟如何，还有待今后进一步研究。

参考文献:

[1] 吴成东，张颖，刘航. 粗糙集遗传算法在机器人路径规划中的应用[J].沈阳建筑工程学院学报(自然科学版).2003,19(4):326-329.

[2] Cai Wen.Extension theory and its application[J].Chinese Since Bulletin.1999,44(1):1538-1548.

[3] Shuhua Liu, Yantao Tian, Jinfang Liu. Multi Mobile Robot Path Planning Based on Genetic Algorithm[A].The 5th World Congress On Intelligent Control and Automation[C]. Hangzhou China. 2004.4706~4709.

[4] 陈刚.复杂环境下路径规划问题的遗传路径规划方法[J].机器人,2001,（3）: 230~233.

[5] 柳颖. 基于物元的可拓遗传算法[D].大连海事大学研究生论文.2005