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

张屹，刘铮，胡方军，詹腾，丁昌鹏

(三峡大学机械与材料学院，湖北宜昌 443002)

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

张屹，刘铮，胡方军，詹腾，丁昌鹏

(三峡大学机械与材料学院，湖北宜昌 443002)

在移动机器人路径规划问题中，环境建模约束定义难，遗传算法求解易陷入局部收敛，针对上述问题通过建立栅格坐标、栅格序号和栅格状态三者之间的关系，简化了障碍物约束和有效路径判断，同时引入多样性保持较好的元胞遗传算法，使用定长实数编码对生成的路径进行优化。仿真实验表明，由于算法具备较好的隐性迁移机制，保持了解的多样性，提高了算法收敛效率，使移动机器人路径规划问题得到了有效解决。

元胞邻居;遗传算法;移动机器人;环境建模;路径规划

移动机器人路径规划要求在具有障碍物的环境内按照一定的评价标准，寻找一条从起始点到终点的无碰撞路径［1］。目前，移动机器人路径规划环境建模中，主要难点是定义障碍物和判断有效路径［1－2］，采用栅格法建模有利于解决上述问题。但与此同时，随着栅格密度的增加，障碍物表示精度提高，也使得算法的搜索范围呈指数式增加，所以需要多样性和收敛性较好的智能算法对其进行求解。

智能算法中，尤以遗传算法应用较为广泛，遗传算法编码效率高，不产生无效路径，但本身运算效率低，求解移动机器人路径规划问题时容易陷入局部收敛［1－2］。由于元胞遗传算法既继承了遗传算法的优良品质，又拥有元胞自动机的部分特性，它通过内部隐性迁移机制作用，使得中心个体在其周围邻居间进行遗传操作，保留了种群的多样性，也降低了算法陷入局部收敛的可能性［3－4］。本文作者通过建立栅格坐标、序号和状态的关系，对移动机器人路径规划问题进行环境建模，引入元胞遗传算法，采用定长实数编码方式［5］对路径进行优化。最后，通过多次对各种大小不同的栅格情况进行仿真，以解决移动机器人路径规划问题。

1 元胞遗传算法

1.1 元胞遗传算法思想

元胞遗传算法继承遗传算法的基本思想，同时结合元胞自动机理论，以元胞个体为出发点模拟自然界进化过程［4］。通常情况下，其初始种群个体依次分布于环形连通的网状空间拓扑结构中［6］，所有个体只与相邻个体进行相互作用，遗传操作被限制在邻域范围内进行，其解在种群内平缓的扩散，不同范围内的个体收敛到搜索空间的不同区域，形成一个个的小生境保持种群多样性，从而增强算法的探索能力，使得元胞遗传算法表现出基本遗传算法所不及的性能，因此元胞遗传算法被认为当前解决复杂问题的一种有效方法［4］。

1.2 元胞邻居结构

通常，二维元胞自动机中使用较多的邻居主要有以下4种结构类型:Von.Neumann邻居结构、Moore邻居结构、扩展的Moore邻居结构和Margolus邻居结构［7］，算法采用不同的邻居结构收敛的效果也不同。

图1 元胞遗传算法中常见的4种邻居结构

1.3 隐性迁移机制

元胞遗传算法中，相邻个体的邻居互相重叠，这种重叠为算法提供了一种隐性的迁移机制。这种机制能使求到的最优解平缓地在整个种群中扩散，从而使元胞遗传算法相对于非结构化种群的遗传算法能更持久的保持种群多样性。由于这种扩散，元胞遗传算法在对解空间进行搜索的时候能保持全局探索和局部寻优的良好平衡。邻居间的重叠度随着邻居规模的增长而增长，而重叠度影响着个体的迁移，通过改变邻居规模来调节邻居的重叠度，从而影响全局探索和局部寻优的平衡以及进化过程中的种群多样性。图2中绘制了Von.Neumann邻居结构的重叠度，其中黑色区域的个体同属于个体1和个体2的邻居，颜色最淡的区域的个体是个体1的邻居，另一种颜色较淡区域的个体属于个体2的邻居。

图2 Von.Neumann邻居结构下的隐性迁移

2 环境建模［5，8－11］

2.1 环境表示

栅格法是一种较为传统的环境建模方法，它将机器人工作环境离散成一系列的二值信息网格单元，同时对障碍物和自由空间网格进行标识，其栅格粒度的大小直接影响障碍物的表示精度，会占用计算机大量的存储空间，使得算法的搜索范围呈指数式增加。目前，栅格的标识方法有坐标法和序号法，序号法要求对路径进行不间断编码，增加了编码的难度，而坐标法能有效实现本文定长实数编码的需要。结合两种标识方法，建立两者一一对应的关系，为障碍物判断奠定基础。

在直角坐标系XOY中，路径点序列的坐标是二维的，通过坐标变化后的新坐标系为X'OY'，X'轴为起始点S与目标点G的连线，如图3所示。坐标变换方法:以机器人原始坐标原点为原点，以起始点S与目标点G的连线为X'轴，建立新坐标系X'OY'。原坐标系XOY与新坐标系X'OY'’的变换公式如下:

图3 路径编码方法

将起始点S和目标点G连线的线段n等分，等分点为xi，过xi点作直线Li与X'轴正交，随机地在直线Li上选择通过栅格的点Pi，从而形成一条随机的路径。如此这样，就将优化的路径点简化成一维的y坐标编码优化问题。编码采用实数编码，编码格式如图4所示。

图4 编码格式

2.2 障碍判断

通过利用坐标法对移动机器人路径进行编码，再求解两相邻点间线段上有限点的坐标，利用序号和坐标之间的一一对应关系返回栅格序号，结合栅格状态判断线段是否穿过障碍。只要所求得的栅格不是障碍物，则该生成路径有效，否则重新生成下一栅格，继续判断直至路径有效。

3 路径规划

3.1 适配值函数

3.1.1 路径最短适配值函数

如图3，移动机器人路径规划就是在起点与终点之间寻找一个点的集合P={S，y1，…，yi，…，yD，G}，要求两相邻点之间的线段没有通过障碍物，所以问题的解就是寻找最短的有效路径，如式 (2)表示:

式中:L'是单个栅格的对角线长度;m为大于1的正实数，可以保证移动机器在不同垂线人不会经过同一栅格;LSG为起始点S到目标点G的距离;(Xi，Yi)是第i条垂线与SG的交点Pi在坐标系X'OY'中的坐标，对应表示相应的栅格，此时不表示起始点和目标点。

3.1.2 栅格状态、坐标和序号的关系

(1)栅格状态。通过定义栅格的状态判断障碍物位置，如果栅格状态gridState为1，此栅格为障碍物，不允许机器人通过;如果栅格状态gridState为0，此栅格可通过。

(2)直角坐标法。以栅格左下角为坐标原点，水平向右为x轴正方向，竖直方向为y轴正方向，以每一个栅格中心点 (x，y)表示该栅格，如此栅格均可唯一标识。

(3)序号法。按照从左到右，从上到下的顺序，从栅格左下角第一个栅格开始，给每一个栅格编号，记为P(从1开始计数)。

结合序号法和直角坐标法，栅格内点 (x，y)与栅格序号P有如下对应关系

通过栅格坐标与栅格序号之间的一一对应关系，结合栅格状态反求栅格序号，如此可以判断移动机器人是否通过障碍物，也能及时避免穿越障碍。

3.2 遗传操作

3.2.1 选择操作

元胞遗传算法重点在于选择操作，采用异步元胞遗传算法对生成路径进行优化，父代个体被选择的原理如下:

步骤1:按照顺序扫描方式，依次选择中心元胞个体;

步骤2:参考Von.Neumann邻居结构，找到中心元胞个体周围邻居;

步骤3:由以下公式，计算邻居个体适应度，通过轮盘赌方式选择出与中心元胞交叉的邻居个体。

3.2.2 交叉操作

采用单点交叉，首先确定一个交叉概率pc，将选择出的邻居与中心个体一一配对，然后对每一对个体产生一个 ［0，1］的随机数r，如果r＜pc，则对该对个体随机指定的基因进行交叉操作。

3.2.3 变异操作

变异主要是为了增加种群的多样性，为了防止生成无效路径，修改变异算子如下:

步骤1:在交叉后的父代路径中随机选择一个路径点作为变异点，如果选到起始点，则路径保持不变;

步骤2:在路径变异点处，用通过该点垂线上的自由栅格代替变异点;

步骤3:判断变异后的路径是否为有效路径，无效则返回步骤2，直到找到合适的变异点。

步骤4:计算变异后新路径的目标值，并与初始目标值比较，选择出目标值较小的路径，赋予新的种群。

3.3 算法执行伪代码

算法执行伪代码如下:

以上是元胞遗传算法执行的伪代码，染色体由一条长度确定且为实数的路径点组成，通过对原始种群实施一连串遗传操作，并最终判断染色体即移动机器人路径是否穿越障碍物，将较好的染色体逐步缓慢地扩散到新的种群中，通过不断进化最终找到合适的最优路径。

4 仿真实验

在仿真实验中，算法的相关参数设置如下:种群规模100，进化代数50，交叉概率0.05，变异概率0.01，m=1.2，左下角为起点，右上角为终点。在环境不同的两幅10×10的图中进行多次仿真，典型结果如图5和图7，其中图6、图8分别为图5和图7对应的进化代数与适应度值关系。

图5、图7中最优路径真实解为13.899 5，对其做多次仿真，统计结果如表1。

图5 算法输出结果a

图6 a对应的进化代数与适应度值关系

图7 算法输出结果b

图8 b对应的进化代数与适应度值关系

表1 仿真运行结果记录

图10 算法输出结果d

在种群规模225，m=1.1，其它设置参数相同的条件下，对栅格15×15的情况作了仿真，典型结果如图9，最优值为22.142 1，平均收敛代数为40代。在种群规模400，进化代数100，m=1.05，其他参数相同，对栅格20×20的情况作了仿真，典型结果如图10，最优值为30.384 8，平均收敛代数为61代。

图9 算法输出结果c

通过以上的仿真测试，元胞遗传算法均能有效地解决移动机器人路径规划问题。分析图6、图8，可以看出算法求解后最优值与平均值差距较小，说明算法的收敛性较稳定，能够准确找到最优解。分析表1发现，算法收敛时保持了稳定的进化代数，有效降低了算法陷入局部收敛的可能性。分析图5、图7、图9和图10，通过不断改变栅格规模，元胞遗传算法均能找到最优解，不仅说明算法有效，也表明移动机器人路径规划环境建模的通用性较好。

5 结论

针对目前移动机器人路径规划环境建模中约束定义复杂，以及遗传算法求解易陷入局部收敛的问题，建立栅格中心坐标与栅格序号一一对应的关系，以栅格状态定义障碍物约束简化障碍物模型，在元胞遗传算法中使用定长实数编码，充分利用算法的隐性迁移机制，不仅增强了算法的全局寻优能力，也增加了最优解的多样性。仿真实验表明，通过改进障碍物约束定义和引入元胞遗传算法，增强了移动机器人路径规划环境建模的通用性，同时也提高了算法的求解效率。

［1］蔡晓慧.基于智能算法的移动机器人路径规划研究［D］.杭州:浙江大学，2007.

［2］琚兆杰.移动机器人路径规划研究［D］.武汉:华中科技大学，2007.

［3］WHITLEY D.Cellular Genetic Algorithms［C］.Proceedings of the 5th International Conference on Genetic Algorithms，1993:658.

［4］ALBA Enrique，DORRONSORO Bernabe.Cellular Genetic Algorithms［M］.Springer，2008.

［5］严宣辉，肖国宝.基于定长实数路径编码机制的移动机器人路径编码［J］.山东大学学报:工学版，2012，42 (1):59－65.

［6］TOMASSINI M.Spatially Structured Evolutionary Algorithms:Artificial Evolution in Space and Time［M］.Heidelberg，Berlin:Springer-Verlag，2005.

［7］ALBA E，COTTA C，TROYA J M.On the Importance of the Grid Shape in 2D Spatially Structured GAs［J］.Journal of Evolutionary Optimization，2000，1(3).

［8］王强，姚进，王进戈.基于遗传算法的移动机器人的一种路径规划方法［J］.哈尔滨工业大学学报，2004，36(7): 867－870.

［9］郝博，秦丽娟，姜明洋.基于改进遗传算法的移动机器人路径规划方法研究［J］.计算机工程与科学，2010，32 (7):104－106.

［10］邓志燕，陈炽坤.基于改进遗传算法的移动机器人路径规划研究［J］.机械设计与制造，2010，7:147－149.

［11］孙树栋，曲彦冰.遗传算法在机器人路径规划中的应用研究［J］.西北工业大学学报，1998，16(1):79－83.

Path Planning of a Mobile Robot Based on Cellular Genetic Algorithm

ZHANG Yi，LIU Zheng，HU Fangjun，ZHAN Teng，DING Changpeng
(College of Mechanical＆Material Engineering，China Three Gorges University，Yichang Hubei 443002，China)

When solving the problem of path planning of a mobile robot，defining constrains in environment modeling was hard，and was easily fallen into the local convergence by traditional genetic algorithm.By aimed at the problem above，and established the relationship among grid coordinates，grid number and grid state，the constrains definition of obstacles and effective path judging were simplified，at the same time，the cellular genetic algorithm with better diversity maintaining was also brought in，while optimizing the path by using fixed-length real number encoding.Finally，the simulation results show that the algorithm maintains the better diversity and improves the efficiency of the convergence because of the implicit mechanism of migration of the algorithm，which effectively solves the problem of path planning of the mobile robot.

Cellular neighbors;Genetic algorithm;Mobile robot;Environment modeling;Path planning

TP24

A

1001－3881(2014)9－017－4

10.3969/j.issn.1001－3881.2014.09.005

2013－04－16

国家自然科学基金项目 (51275274);三峡大学研究生科研创新基金项目 (2012CX031)

张屹 (1976—)，男，博士，副教授，研究方向为机电系统现代设计方法、机电传动与控制系统设计、工业自动化与监控系统设计、CAD/CAM/CAPP/CAE/CIMS等。E－mail:jxzhangyi1976@126.com。