移动机器人同时定位和地图构建(Simultaneous Localization and Map-Building，SLAM)问题是移动机器人研究领域的基本问题与研究热点。SLAM问题中，地图如何表示是一个重要问题。栅格地图和特征地图是最常用的尺度地图。栅格地图能够满足高层导航任务的需要，但是，对于大规模环境，这种方式计算和存储代价高。特征地图环境表示非常有效，但不利于路径规划。　　 细胞自动机(Cellular Automata，CA)具有结构简单，并行计算能力强的优点，被广泛应用于复杂系统研究。本文在实现特征点地图构建的基础上，提出了一种基于细胞自动机构建环境地图的方法，实现了机器人的同时定位和地图构建，满足了高层导航的需求。论文针对移动机器人在室内环境下的定位、地图构建、同时定位与地图构建进行研究，取得的主要研究成果如下：　　 (1)对关键点的检测及定位方法进行研究，提出了精确提取及定位关键点的方法。该方法首先分别通过颜色阈值分割、轮廓提取、多边形逼近以及设置矩形轮廓提取出关键点所在的显著性标志物，其次根据该显著性标志物的特点，采用Hough变换提取线段，并通过最小二乘法进行直线拟合，求出关键点的精确的像素坐标，最后对求取的关键点进行精确的位姿计算。该方法实时性好、精度高，为后续的机器人视觉避障提供了一定的理论依据。　　 (2)针对图像在成像过程中产生的几何畸变，采用一种极线校正的方法对图像进行校正。重点研究了尺度不变特征变换(Scale Invariant Feature Transform，SIFT)方法和Harris角点特征提取方法。通过实验验证，SIFT特征点是处理特征匹配和定位精度最好的特征点，也是最适合视觉SLAM应用的特征点。并针对SLAM匹配过程中出现的误匹配点，提出了一种改进方法，提高了匹配精度。　　 (3)采用视觉里程计进行移动机器人的定位。主要包括机器人的全局定位和机器人路径的局部跟踪。左右帧图像匹配构建局部地图，以局部地图作为参考帧，前后帧图像特征点匹配来估计机器人运动参数，用于机器人全局定位。在估计机器人运动参数，即相对位置关系时，将每一时刻进行左右帧图像匹配的特征点保留，在前后帧图像匹配时仅匹配保留的特征点，而非重复提取特征点匹配，提高了匹配搜索效率和定位的实时性。最后，对两种基于视觉里程计的定位方法进行了实验比较。　　 (4)首先实现了特征点地图的构建，并提出了细胞自动机环境模型的构建方法。其次，分别采用两种不同的模型，实现机器人的同时定位和地图构建，并对实验结果进行比较。实验结果证明，基于细胞自动机的环境模型能够更好的模拟现实环境，构建地图的精度比较高。最后鉴于细胞自动机在机器人路径规划方面的优势，在构建的环境地图上完成了机器人的最优路径规划。　　 课题得到国家自然科学基金(60774077)、国家863计划(2007AA042226)、北京市教育委员会科技计划面上项目(KM200810005016)和北京市教委科技创新平台项目(0020005466018)的资助。本文的研究工作对于移动机器人的导航算法研究具有一定的参考意义。