• CN: 11-2187/TH
  • ISSN: 0577-6686

›› 2004, Vol. 40 ›› Issue (10): 56-61.

• Article • Previous Articles     Next Articles

COMPLETE COVERAGE OF KNOWN SPACE——RECTANGULAR DECOMPOSITION

Tian Chunying;Liu Yu;Feng Shenshen;Zhu Shiqiang   

  1. State Key Laboratory of Fluid Power Transmission and Control, Zhejiang University
  • Published:2004-10-15

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

CLC Number: