自主导航是移动机器人的核心功能之一,也是机器人领域研究的重要课题,包括环境建模、定位、地图处理、路径规划与末端控制等一系列内容。在路径规划过程中,规划算法会耗用大量的运行时间与存储空间在无效路径的搜索上,而通过地图预处理技术可以有效降低机器人工作空间的复杂度,从而提升路径规划过程的整体效率。传统地图预处理技术包括手工标记、多分辨率栅格地图、导航网络以及拓扑抽象等,但这些方法在处理栅格地图中的凹形障碍物(concave obstacle)时,通常缺乏灵活性,并且在预处理过的地图中,规划算法依然不能避开搜索该类区域。针对凹形障碍物问题,本文提出了一种快速标记填充凹形区域的算法,主要工作如下:首先,本文提出了一种通用解决方案——FC(Filling the Container)算法。该算法模拟重力下水流的性质,通过对地图进行数次遍历即可有效填充任何非结构化的凹形区域。文中给出了凹形区域定义以及该类型区域不存在最优路径的证明,并对单凹形区域以及复合型凹形区域的填充处理流程进行了详细描述,同时给出了算法的伪代码与严格分析。在实验中,数张测试地图表明了这一方法的有效性,并对比了填充凹形区域前后,路径规划算法的性能区别。其次,针对移动机器人在同一地图上重复路径规划这一场景,提出块分解算法。通过对填充块构建索引表以建立块之间的联结关系,经由分解方法消除阻碍起始点与目标点的填充块,恢复了机器人工作空间中的区域连通性,达到复用填充处理地图的目的。解决了已填充凹形区域地图空间中,随机重设起始点或目标点位于某一填充块之中情况下,采用取消所有填充处理造成的重复执行FC算法产生大量耗时问题。该方法对原始算法的性能影响有限,但可以避免FC算法的重复运行。最后,本文对FC算法的凹形区域填充非完整性进行了详细论述,解释了非完整填充的原因与其必要性。证明了FC算法以及块分解算法处理过的地图中路径最优解存在性。