机器人导航技术是移动机器人研究领域中的一项关键技术，涉及到机器人的感知、规划、执行等诸多方面。随着移动机器人应用范围深度和广度的延拓，对导航算法提出了更高的要求。如何降低算法的复杂度，提高实时性和克服局部极小点都是导航算法必须解决的问题。　　 细胞自动机（Cellular Automata，CA）具有结构简单，并行计算能力强的优点，被广泛应用于复杂系统研究。本文在建立环境细胞自动机模型的基础上设计了移动机器人路径规划算法，该算法不仅克服了局部极小点，而且具有很好的实时性，取得的主要研究成果包括：　　 （1）建立了移动机器人工作环境的细胞自动机模型，并基于这种模型设计了移动机器人路径规划算法，该算法分为细胞自动机的演化和路径的搜索两个过程。提出了细胞自动机分别按照机器人移动的曼哈顿距离演化和按照机器人起始点与目标点的相对位置演化两种规则，并分别给出了沿起点和终点两个方向出发的演化过程。　　 （2）针对移动机器人按照曼哈顿距离规则规划出的路径移动时紧靠障碍物存在碰撞危险的问题，提出了基于细胞自动机模型路径规划算法的改进策略。改进后的算法增加了对障碍物的边缘检测并建立了障碍物增长后的细胞自动机模型。实验结果表明，改进后的算法可以保证移动机器人在移动时远离障碍物，避免碰撞。　　 （3）开发了基于细胞自动机模型的移动机器人路径规划仿真软件，实现了算法的可视化。在不同环境地图下对算法进行了反复实验，实验结果表明，本文提出的算法可以使移动机器人很好的完成导航任务。作为比较，在Pioneer3-DX平台实现了基于人工势场法的移动机器人导航，在Matlab平台下开发了基于遗传算法的可视仿真软件，并分别同本文提出的算法进行了比较和分析，比较和分析结果表明，本文的算法克服了人工势场法陷入局部极小点问题，运行时间优于遗传算法。　　 （4）本文设计了基于启发式规则细胞自动机模型的移动机器人路径规划算法。这种算法将细胞自动机模型与A*搜索算法相结合，以A*算法的启发式函数作为细胞自动机的演化规则。仿真实验结果表明，该算法可以快速找到一条无碰路径。最后，对细胞自动机模型和人工势场法相结合的未知环境中移动机器人的路径规划算法进行了探讨。　　 课题得到国家自然科学基金（60774077）、国家863计划（2007AA042226）、北京市教育委员会科技计划面上项目（KM200810005016）和北京市教委科技创新平台项目（0020005466018）的资助。本文的研究工作对于移动机器人的导航算法研究具有一定的参考意义。