基于元胞遗传算法的机器人路径规划研究

李昌华，石如雪，李智杰，张 颉

(西安建筑科技大学 信息与控制工程学院，西安 710055)

0 引言

移动机器人路径规划是指在复杂环境中，在不同条件的约束下，搜索从起点到终点的最优或近最优路径[1]。移动机器人路径规划建模主要有以下难点：(1)障碍物的定义[2]；(2)有效路径的确定[3]。在过去几十年里，许多学者对此进行了大量的研究，并提出了一系列算法来解决这一优化问题。其中，元胞自动机建模具有时间、空间、状态均离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的优点，成为解决移动机器人路径规划问题的有效方法之一[4]，元胞密度的增加能够提高障碍物表示的精度，但也造成了算法的复杂度提升，搜索范围呈指数增长[5-6]。因此，需要一种具有更好的多样性和收敛性的智能算法来解决此问题。

近年来，智能算法由于其结构简单，控制参数较少，得到了广泛的研究和应用，尤以遗传算法应用最广。遗传算法是通过模拟自然界的进化过程来搜索最优解[7-8]，不仅具有编码效率高、自组织性和自适应性较强等优势，也可以同时处理多个个体，具有内在隐并行性[9]。但针对复杂环境设计相应的遗传算子易产生非法个体，存在较大困难。Vincent等[10]将遗传算法与粒子群算法相融合去处理在三维复杂环境下的问题，使用“单程序，多数据”并行编程缩短执行时间，实现实时路径规划；魏彤等[11]将插入算子和删除算子引入经典遗传操作算子中，在适应度函数中考虑路径连贯性，计算的适应度值最高的路径为最优路径。

然而遗传算法本身运算效率低，求解移动机器人路径规划问题时容易陷入局部收敛。为了解决上述问题，引入元胞遗传算法，元胞遗传算法不但拥有元胞自动机的部分特性，也继承了遗传算法的优良品质，它通过内部隐性迁移机制作用，使得中心个体在其周围邻居间进行遗传操作，保留了种群的多样性，也减少了算法陷入局部收敛的可能性[6]。

在本文中，对移动机器人路径规划问题使用元胞模型进行环境建模，使用元胞遗传算法，借由分解演算法的慢度，考虑路径平滑因素，找出可能的距离短且平滑的路径，作为最优性准则，寻找路径规划问题的最优解。结果表明，改进的元胞遗传算法为移动机器人提供了一个高精度、低碰撞、低损耗的路径。

1 元胞遗传算法

1.1 元胞遗传算法思想

元胞自动机和遗传算法结合而成的元胞遗传算法具有启发性的生物学思想。元胞遗传算法可描述为：基于元胞自动机的模型，将遗传算法种群中的每个个体都视为一个元胞，将个体随机映射到二维网格中，添加演化规则，进行个体选择、交叉和变异操作等遗传操作，但遗传操作仅限于元胞邻域范围内。通过种群不断得演化和迭代，最终寻找到最优个体的解。

元胞自动机中使用简单的进化规则操作就可以模拟复杂系统的变化过程，并展示局部种群如何影响整个种群的进化过程。元胞遗传算法思想还源于不断变化的系统性能，可以有效解决复杂问题。

1.2 元胞自动机邻域模型

John Von Neumann于20世纪50年代，提出了元胞自动机模型(cellular automata，CA)，该模型是根据预先指定的规则在时间和空间上由一系列离散单元形成的模型,它不同于通常基于定义的函数建立的动态模型，它的单元空间由一系列具有相同规格的单元组成,在这个空间中，每个单元格处于有限数量的状态，并且每个单元格根据特定的演化规则更新其自己的状态。

经典的元胞自动机模型分为Von Neumann邻域模型和Moore邻域模型，Von Neumann邻域模型是中心元胞只有上、下、左、右四个方位的邻域元胞可供使用，Moore邻域模型的中心元胞的邻域是除Von Neumann邻域的四个元胞外还包括左上、右上、左下、右下共8个方位的邻域。使用元胞模型可以根据邻域元胞的占用状态快速判断是否有障碍物，很好地达到避障效果。

1.3 隐性迁移机制

在元胞自动机中，邻居彼此重叠的个体具有隐性迁移机制，该机制可使最优解在整个种群中平稳扩散。因此，与非结构化种群遗传算法相比，元胞遗传算法可以更持久地保持种群多样性。这种扩散迁移机制允许元胞遗传算法在搜索解空间时在全局搜索与局部优化之间取得平衡[6]。邻域中会影响个体迁移的重叠程度随邻域的大小而变化。通过更改规模，可以调整邻域重叠的程度，从而影响全局搜索和局部优化之间的平衡，保持进化过程中的种群多样性。这保证了使用元胞遗传算法可以用来解决实际的复杂问题。

2 算法的模型构建

图1 显示机器人R所在单元格及其相邻单元格

目标是找到机器人到达目的地的最短路径和转向次数最少的路径。考虑到元胞自动机网格的性质，可以认为网格环境对应于元胞自动机。元胞自动机是一个离散的时间动态系统，即在每个时间点上，所有的细胞都根据传递函数同时移动。结果，目标环境适应元胞自动机的功能，使得所有障碍物在每个时间阶段保持不变。

我们先假设要达到出口目标G。因此，从目标点G移动到一行，并为每个单元格指定一个数字，通过这种方式将标签分配到单元格。单元格编号如图2所示。

图2 单元格编号

网格被转换成一个加权网格，使得每个除障碍物之外的网格相对应的数字显示从所在位置到目标的最小距离，而不考虑元胞的位置。每个单元的数量开始移动，每个单元与其相邻单元之间的最小距离计算到距G点最近的单元，并分配给该单元。

图3 加权模式网格

3 路径规划

由于元胞自动机模型是将地图划分为网格，基于网格的模型中的路径查找包括遍历平方单元的中心。在网格上计算的地图存在以下问题：它们产生高度不切实际的空间利用率，不能保证回程的等效性，扭曲了路径长度和机器人的行驶时间，因此需要加入平滑度因素进行调节，以此来改进适应度函数，以求得到更加平滑和距离最短的路径。

3.1 适应度函数

考虑到元胞的工作环境和环境的屏障轮廓，有必要确定元胞能够以最低的成本通过的路径。将要被最小化的适应度函数分成判断路径的路径长短和平滑程度两部分来考虑。

路径长度的计算公式如下：

(1)

式中,PL表示元胞行进的路径长度，或者换句话说，表示从起点到终点的路径距离；(xi，yi)为第i个路径节点的坐标。

适应度函数的第一部分，采用轮盘赌的方式，因为要求的是机器人的最短路径，所以取距离的倒数：

f1=1/PL

(2)

由于动力学和运动学的限制，机器人在行驶时不应转弯太多，因此所产生的路径需要平滑。路径越平滑，三个连续点的夹角越大，相邻三个点形成的角度也越大。会出现的四种情况是180度，钝角，直角和锐角，其中180度的三个点位于一条直线，光滑度最好，其次是钝角和直角。由于机器人动力学的限制，机器人路径不得具有锐角。因此，对于除直线以外的三种情况，惩罚函数值分别取5、20和无穷大。适应度函数的第二部分是惩罚的总和，可以根据实际情况改变惩罚值的大小。计算公式如下：

AB2=(xi+1-xi)2+(yi+1-yi)2

(3)

BC2=(xi+2-xi+1)2+(yi+2-yi+1)2

(4)

AC2=(xi+2-xi)2+(yi+2-yi)2

(5)

(6)

(7)

A、B、C为连续三点构成的三角形的三个角，AB、BC、AC为三角形的三条边。

PS表示与路径的平滑度有关的函数。

适应度函数的路径长度部分和路径平滑度部分分别取一个权重，构成完整的适应度函数：

f=af1+bf2

(8)

3.2 遗传算子

搜索引擎设计成从一个起点创建一条路径。这条路径就是种群中一个个体，然后将所有种群中的个体视为一个元胞，将个体随机映射到二维网格中，添加演化规则，在元胞邻域范围内进行如下的遗传操作，并存储最佳和最差响应。

3.2.1 选择操作

在算法选择操作中采用异步元胞遗传算法，父代个体按照以下原理被选择，来优化生成路径：

1)按照顺序扫描方式，依次选择中心元胞个体；

2)参考Moore邻域结构，找到中心元胞个体周围邻居；

3)计算邻居个体适应度，通过轮盘赌方式选择出与中心元胞交叉的邻居个体。

轮盘赌的方式可以有效的防止算法陷入局部最优解，保证了部分非最优的个体。计算公式如下：

(9)

3.2.2 同点交叉

采用同点交叉:

1)先确定一个交叉概率Pc，将选择出的邻居与中心个体一一配对；

2)然后对每一对个体产生一个[0，1]的随机数r，如果r

3)若无除了起点和终点以外的其它相同点时，则对该对个体随机指定的基因位置进行交叉操作。

3.2.3 邻域变异

变异主要是为了防止生成无效路径，用以增加种群的多样性，设定变异算子如下：

1)首先确定突变概率Pm，生成0到1之间的随机数，然后比较突变概率Pm。如果小于Pm，则执行变异操作；

2)随机选择一个交叉后的父代路径点作为路径的变异点，如果选择的点是起点或者终点，则路径不变；

3)确定修改后的路径是否有效，如果无效，返回2)直到找到适当的变异点；

4)计算新变异后路径的目标值，将其与初始目标值进行比较，选择目标值较小的路径，然后将其分配给种群。

3.3 元胞遗传算法流程

Begin

初始化种群P0；

初始化种群个体在元胞空间的生死状态S(0)；

Repeat

For 某个状态为生的个体Ii

遗传操作：

选择：选择Ii的邻居Ni内的最优个体Ib；

交叉：对两个个体中用相同点的位置进行交叉操作；

变异：随机选择两个不相同的中间点，将这条路径一中这两个点为起始点重新生成路径；

计算适应度f；

If min(f)

用子代的最优个体替换掉Ii；

End

End

然后用规则更新元胞空间内的生死状态；

Until

找到最优解或到达最大运行代数(即满足停止运行条件)；

End

以上是元胞遗传算法的算法流程，使一条长度确定的且为实数的路径点即为元胞遗传算法中的染色体，将较好的染色体逐步缓慢的扩散到新的种群中，通过不断进化最终找到合适的最优路径。算法停止的条件，首先，得到的解是可行的或者是已经达到最大运行次数。第二，连续重复30次后目标函数是恒定的则停止运算。在前一步得到的可接受响应中，选择目标函数值最小的响应作为最优响应。

4 仿真实验与分析

为了验证算法的性能，对算法的优化路径结果进行仿真，在Windows7(CPU2.4 G，内存512 M)下，运用MTLAB建立仿真平台，模拟实现路径输出，对实验结果进行分析。

4.1 实验1基本遗传算法路径规划和元胞遗传算法路径规划的路径

针对规划空间为20×20，种群规模为200，基本遗传算法和元胞遗传算法均取交叉概率为0.8，变异概率为0.1，运行代数为50，进行测试。关于环境尺寸、单元数量和障碍物数量的信息见表1。

表1 环境信息表

考虑到遗传算法产生随机答案，在每次运行时会得到不同的响应。为了评估算法产生的响应，进行多次仿真，然后根据最佳答案或给出的答案的平均值，对结果进行分析和评估。两种算法路径寻优结果对比如图4所示，收敛性曲线对比如图5所示。

图4 基本遗传算法和元胞遗传算法输出结果

图5 收敛性曲线对比图

分析实验1的结果，基本遗传算法路径规划距离为35.970 6，元胞遗传算法路径规划距离为31.177 9，即路径规划距离缩短了13.32%；使用基本遗传算法的机器人在行进过程中进行了16次转向，使用元胞遗传算法的机器人进行了15次转向，即转角绝对值之和减小了6.38%。

由图5的两种算法的收敛曲线对比图可以看出，元胞遗传算法的收敛速度和最优路径长度均优于基本的遗传算法。这是因为元胞遗传算法的初始种群合理的使用了Moore邻域模型构造，并且元胞空间中邻居个体间进行交叉操作，使群体间的优势个体迅速扩散，一定程度上避免了基本遗传算法的早熟现象，降低了陷入局部收敛的可能性。

4.2 实验2：平滑度因素对路径规划的影响

针对规划空间为20×20，种群规模为200，交叉概率为0.8，变异概率为0.1，最大运行迭代次数为50，对是否加入平滑度因素分别进行收敛测试，测试结果如图6和图7所示。

如图6是在仅考虑路径长度情况，不考虑平滑度因素情况下的元胞遗传算法路径规划结果(a)和进化的迭代次数与路径长度关系(b)；图7是考虑路径长度与平滑度因素共同作用下的元胞遗传算法路径规划结果(a)和进化的迭代次数与路径长度关系(b)。

图6 不加入平滑度因素

图7 加入平滑度因素

分析实验2可知，在不考虑路径平滑度的情况下，即路径长度参数a=1，平滑度参数b=0时，机器人在行进过程中经过16次转向，在第18次迭代时寻找到最优路径，路径距离为31.177 9。在考虑路径平滑度的情况下，即路径长度参数a=5，平滑度参数b=3时，机器人在行进过程中经过15次转向，在第20次迭代时寻找到最优路径，路径距离也为31.177 9。

两次实验得出的路径距离没有发生变化，但是加入平滑度参数的结果2中，机器人路径的转折次数少于不考虑平滑度参数的结果1，但是相应的代价就是结果2的迭代次数比结果1多。得出结论：算法在考虑路径平滑度因素情况下，可得到更加平滑的路径，但是是以迭代时间为代价的。但就以为机器人寻找高精度、低碰撞、低损耗的路径的目的来说，一点点时间代价在允许范围内，因此，加入平滑度参数的改进是有效的。

5 结束语

对于基本遗传算法进行机器人路径规划时，路径进行插入修复无法保证解的可行性，且算法易陷入局部最优的问题，结合元胞自动机模型的空间特性，定义环境时首先排除了障碍物所在的格栅位置，增强了路径规划环境建模的通用性；接着，利用元胞遗传算法的隐性迁移机制，并在算法适应度函数中加入路径平滑因素，改进了元胞遗传算法。仿真实验表明，所提的元胞遗传算法和基本遗传算法相比，机器人行驶路径长度减少了13.32%，转角绝对值之和减小了6.38%，得到了距离短且平滑的路径，提高了移动机器人的行驶效率和平稳性。算法在局部优化时保持了群体的多样性，一定程度克服了算法的早熟，有效解决了移动机器人路径规划问题，对机器人寻找高精度、低碰撞、低损耗的路径具有重要意义。