基于细胞自动机的移动机器人导航方法研究

摘要

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

目录

文摘

英文文摘

第1章 绪 论

1.1 研究背景和意义

1.1.1 课题背景

1.1.2 研究意义

1.2 移动机器人导航方式

1.3 移动机器人定位方法

1.3.1 相对定位方法

1.3.2 绝对定位方法

1.3.3 同时定位与地图构建（SLAM）

1.4 移动机器人路径规划方法研究现状

1.4.1 传统的路径规划方法

1.4.2 基于智能算法的路径规划方法

1.5 课题来源

1.6 研究内容与论文安排

第2章 基于细胞自动机的环境建模

2.1 细胞自动机

2.1.1 细胞自动机的构成

2.1.2 细胞自动机的特征

2.2 基于细胞自动机的环境建模

2.2.1 模型的限制条件

2.2.2 模型的结构设计

2.2.3 模型的边界条件

2.2.4 模型的演化规则

2.3 本章小结

第3章 基于细胞自动机模型的移动机器人路径规划算法

3.1 移动机器人导航系统

3.2 基于细胞自动机模型的移动机器人路径规划算法设计

3.3 基于细胞自动机模型的移动机器人导航实验

3.3.1 实验过程

3.3.2 算法实现步骤

3.3.3 仿真结果与分析

3.4 算法复杂度分析

3.5 基于细胞自动机与基于遗传算法的路径规划算法对比实验

3.6 基于细胞自动机与基于人工势场的路径规划算法对比实验

3.6.1 硬件系统

3.6.2 软件系统

3.6.3 Pioneer3-DX移动机器人传感器配置

3.6.4 导航相关类及主要函数介绍

3.6.5 仿真实验及分析

3.7 本章小结

第4章 细胞自动机与传统算法相结合的路径规划算法

4.1 基于启发式规则细胞自动机模型的路径规划算法

4.1.1 细胞自动机的演化过程

4.1.2 基于启发式规则细胞自动机模型的路径规划算法步骤

4.1.3 仿真实验及分析

4.2 基于细胞自动机模型和人工势场相结合的路径规划算法

4.2.1 人工势场法

4.2.2 基于细胞自动机模型和人工势场相结合的路径规划算法步骤

4.3 本章小结

结论

参考文献

攻读硕士学位期间所发表的学术论文

致 谢