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

Abstract: A new cellular decomposition approach，rectangular decomposition，is proposed for the purpose of complete coverage path planning. Firstly, the known grid map is used to build each obstacle into a rectangular model. Secondly, the critical points of each model are used to decompose the environment into rectangular cells. Each cell can be represented as a node in a graph, and then a Hamilton path is found in this graph. Because the environment is very complicated and sometimes there are some unexpected obstacles in the environment, sensors are needed and a local template algorithm is designed. The novelty of the proposed algorithm is that Hamilton path can be found in the topology of the environment and reduce the redundancy produced by the robot when it moves from one cell to the next. A simulation based on a grid map validates this algorithm.

Key words: Complete coverage, Grid map, Hamilton path, Mobile robot, Rectangular decomposition