摘要：提出移动机器人的一种新的完全遍历算法:矩形分解算法.首先通过机器人环境学习建立栅格地图,对环境中的障碍物实行矩形化建模.而后应用矩形化模型中的关键点将环境分解成为矩形块,最后在这个分块环境的拓扑图中寻找到一条Hamilton路径,机器人沿此路径即可实现对环境的完全遍历.为处理复杂的局部情况,又提出基于模板的局部环境处理算法.矩形算法的优点在于机器人可以实现完全自主的复杂环境遍历,并且可以处理未知障碍,从而使算法适合于任意非结构化的工作环境.

关键词：矩形分解算法 hamilton路径 完全遍历 栅格地图 移动机器人 

单位：浙江大学流体传动及控制国家重点实验室; 杭州; 310027