遗传算法与机器人路径规划

摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。

关键词：路径规划；移动机器人；避障；遗传算法

Genetic Algorithm and Robot Path Planning

Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. 

Key words: Path planning, mobile robot, avoid the obstacles, genetic algorithm    

1路径规划

1.1  机器人路径规划分类

（1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类：

1，已知环境下的对静态障碍物的路径规划；

2，未知环境下的对静态障碍物的路径规划；

3，已知环境下对动态障碍物的路径规划；

4，未知环境下的对动态障碍物的路径规划。

（2） 也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型：

1，基于环境先验完全信息的全局路径规划；

2，基于传感器信息的局部路径规划。

（第二种中的环境是未知或部分未知的， 即障碍物的尺寸、 形状和位置等信息必须通过传感器获取。）

1.2  路径规划步骤

无论机器人路径规划属于哪种类别，采用何种规划算法， 基本上都要遵循以下步骤： 

1, 建立环境模型， 即将现实世界的问题进行抽象后建立相关的模型；

2, 路径搜索方法， 即寻找合乎条件的路径的算法。

1.3路径规划方法

1.3.1传统路径规划方法

（1）自由空间法 （free space approach）　基于简化问题的思想 , 采用“结构空间” 来描述机器人及其周围的环境。 这种方法将机器人缩小成点 ,将其周围的障碍物及边界按比例相应地扩大 ,使机器人点能够在障碍物空间中移动到任意一点 ,而不与障碍物及边界发生碰撞。

（2）图搜索法   采用预先定义的几何形状构造自由空间，并将其表示为连通图，然后通过搜索连通图进行路径规划。这种方法比较灵活，改变初始位置和目标位置不会重构连通图，但是障碍物比较多时，算法会比较复杂，且不一定能找到最短路径。

 （3）人工势场法（artificial potential field）  既是把机器人工作环境模拟成一种力场。目标点对机器人产生引力，障碍物对机器人产生斥力，通过求合力来求控制机器人的运动。

1.3.2  智能路径规划方法

（1）基于模糊逻辑算法（fuzzy logic algorithm）的机器人路径规划     此方法基于传感器的实时信息，参考人的的经验，通过查表获得规划信息，实现局部路径规划。通过把约束和目标模糊化，利用隶属度函数寻找使各种条件达到满意的程度，在模糊意义下求解最优解。

（2）基于神经网络（NN）的机器人路径规划    主要是基于神经网络结构构造出来能量函数，根据路径点与障碍物位置的关系，选取动态运动方程 ，规划出最短路径。

（3）基于遗传算法（GA）的机器人路径规划  遗传算法运算进化代数众多，占据较大的存储空间和运算时间，本身所存在的一些缺陷(如解的早熟现象、局部寻优能力差等)，保证不了对路径规划的计算效率和可靠性的要求。为提高路径规划问题的求解质量和求解效率，研究者在其基础上进行改进。

机器人路径规划算法的方法很多，除了上面介绍的常见的路径规划方法外，还有基于蚁群算法的路径规划，基于微粒群算法的路径规划，结合模拟退火算法的遗传算法等。

前面对路径规划的方法做了整体的介绍，下面则要讲解的具体的算法：遗传算法在路径规划中的应用。

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

2.1 遗传算法相关知识

遗传算法(GA)由美国Miehigan大学的JohnHolland等在20世纪60年代末期到70年代初期研究形成的一个较完整的理论方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。

遗传算法包括三个基本操作：选择，交叉和变异。

2.2  路径规划的具体步骤

利用遗传算法进行路径规划时，一般包含：环境建模，编码，群体初始化，确定适应度函数（fitness function），遗传操作。

2.2.1环境建模

所谓建模是指建立合理的数学模型来描述机器人的工作环境.本次涉及的机器人工作环境都是障碍物已知的二维空间。本文中遗传算法应用的环境都是基于下面条件考虑的：

（1）机器人被看做是一个点；

（2）障碍物的尺寸都向外扩展半个机器人半径。

如图2.1所示

图2.1  路径规划环境模型图

Fig.2.1 Path planning environment model diagram 

2.2.2编码

在机器人的工作环境图中可以看到，机器人的运动轨迹由若干直线段构成，每段直线段是机器人运动的基本单位。 

机器人到达目标点的整个路径可表示成： 

其中Li是第i段直线段的矢量表示，它的两个端点分别可以表示为Pi和Pi+1,符号“+”表示矢量的运算。可以以O表示原点，于是

于是整个机器人的运动路径可以表示为如下的路点矢量集合：

设Pi的坐标点可以表示为（xi，yi），那么在算法实现时，路径就可以以坐标点形式储存。这样就完成了对染色体的编码，所有的路径T是可能的一个满足条件路径。

2.2.3 群体初始化

群体初始化往往是随即产生的，这里所讲的两种遗传算法都是随即生产从出发点到目标点的任意一条可行路径集合作为初始群体。例如在第一个遗传算法应用中采用均匀分布的方法进行群体初始化。

2.2.4 适应度函数

规划出路径的优劣程度要有一个评价的标准。适应度函数就是为了评价这个优劣程度。在这个适应度函数中以路径长度和障碍物作为评价指标，并使所求解向指标渐小的方向进化。该函数的构造如下：

                                                        (1)

在函数中a1，a2是权重系数，分别强化了不同指标的重要性。第一项表示路径的总长度，第二项是障碍物的排斥函数。

                                                                    (2)

    M是障碍物的个数，βi是第i段直线与第j个障碍物的排斥度。定义为：

                                                                (3)

共3 项分别对应:①直线段与障碍物相交时;②直线段距离障碍物do≤ ds； ③直线段远离障碍物 do > ds 。其中γ为使直线段不与障碍物相交所要移动的最短距离，do 为直线段到障碍物的距离，称ds为安全距离,当 do ≥ ds后,算法将不再试图使路径进一步远离障碍物,称该线段和障碍物无排斥。

给出适应度函数后，在后面的运行过程中，算法试图使适应度函数最小化并认为使得该函数取得较小值的解为较优解。

2.2.5 遗传操作

●交叉算子

交叉操作对两个对象操作，对对象进行随即分割，然后重组得到两个新的个体。交叉根据分割点的数量分为单点交叉和多点交叉，单点交叉是多点交叉的一种特殊形式。基本的操作如下图2.2所示：

图2.2 多点交叉操作

Fig.2.2 Multi-point crossover operation

在图中，父染色体被随机四个分割点分为五部分，标有箭头的部分互换。这样完成交叉操作后产生两条子染色体

基本的交叉操作产生的子代染色体的长度可能不等，结果是，对应的适应度函数也发生变化。对交叉算子的改进是使为了获得更低函数值的适应度函数。前面已经给出路径的表达式。这里给出一个线段的相交函数：

                                                      （4）

0表示第i段直线与所有的障碍物不相交，1表示第i段直线与障碍物相交。并定义如下路段与障碍物相交状态变化函数：

                                                    （5）

gi可能的取值为：1，0，-1。为1时第i+1点前段直线与障碍物不相交后一段相交，-1的时候相反，为0的时候说明前后段的情况相同。

这里选择分割点的原则是：

选择 gi为 1 时对应的变化点作为1号父个体的第一分割点，选择紧随该点之后使得 gi为 -1 的点作为第 2分割点。对于2号父个体， 选择过程恰好相反， 选择 gi为 -1时对应的变化点作为2号父个体的第一分割点， 选择紧随该点之后使得gi为1的变化点作为第 2 分割点。更多的分割点同理可得。

除此之外还要考虑交叉点数的选取，前面的交叉操作会使最后的染色体很短，所以后续的操作要设定染色体的长度，设定标准如下。

                                                               （6）

●变异算子

变异过程中，个体中的分量以很小的概率或步长产生转移。 对于给定路径， 该操作对路径上的各路点pi 以一定的概率改变其坐标。

标准变异对地图中的信息并没有加以利用，变异是随机的搜索，常常导致路径劣化。而改进型变异算子优先选取和障碍物相交的线段的端点进行变异，同时变异所得的路点坐标在障碍物之外， 并且使变异所得的路点新坐标满足：

                                （7）

通过这样的约束条件保证了每次变异对路径优化的非负效果。

●插入算子

该算子在其所作用路径上增加路点。考虑路径上某一直线段               与障碍物相交，并且有端点坐标Pi处于障碍物外部空间。于是通过在Pi与Pi+1之间插入合适的端点    ，一定可以得到               不与障碍物相交。同理，对于Pi+1处于障碍物外部空间时，一定可以有   

不与障碍物相交。对于Pi与Pi+1均位于障碍物内部的情况，该算子将随机生成坐标值，满足    位于所有障碍物的外部空间。 

●删除算子

该算子在所操作路径上记录所有位于障碍物内部空间的路点，随机选择其中之一并予以删除。对于不和障碍物相交的路径，该算子则在其全体路点中随机选择删除点。

3  仿真结果与总结

3.1  仿真结果

图3.1 算法输出结果1

Fig.3.1 Algorithm output 1

其代价函数值为 109.9561，路径全长 109.9561.

图3.2 算法输出结果2

Fig.3.2 Algorithm output 2

其代价函数值为 80.0835，路径全长80.0835.

图3.3 算法输出结果3

Fig.3.3 Algorithm output 3

其代价函数值为 76.1412，路径全长76.1412.

在上面三个仿真图中，适应度函数的值和路径值是一样的。上面的仿真的群体规模都是100，进化50次，染色体变异概率0.3，权重系数a1，a2分别是1，1000。 

算法比较

表1  成功率对比

Tab.1  Success rate comparison

Tab.2  Average price comparison

Tab.3  Standard deviation comparison

3.2  总结

本文讲述了遗传算法如何规划路径的过程。这种遗传算法能使机器人在复杂的环境中优化出一条合适的路径。本文中的遗传算法基于坐标值对染色体编码，很好的利用了地图中的信息，提高了算法的收敛速度。但是这种算法的不足之处是参数不能随工作过程而自动调整，这是有待改进的地方。 

致谢  感谢陈万米老师的指导，在此表示感谢！

参考文献：

[1]    Ayala-Ramirez V,Perez-Garcia A,Montecillo-Puente F J,et al. Path planning using genetic algorithms for mini-robotic tasks[C].Hague Netherlands: IEEE SMC'2004 Conference Proceedings,2004:3746-3750. 

[2]    唐国新，陈雄，袁杨．机器人路径规划中的改进型遗传算法 ［J］．计算机工程与应用，2007，43（22）：67－70．

[3]  卢谨.基于遗传算法的机器人路径规划研究[D].杭州:浙江工业大学.2005. 

[4]    Tu J,Yang S.Genetic algorithm based path planning for a mobile robot [C] . Taiwan: Proc of IEEE Intl Conf on Robotics and Automation, 2003:1221-1226.