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

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

0 引言

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

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