Exploring an Unknown Cellular Environment.

摘要

We investigate the exploration problem of a short-sighted mobile robot moving about in an unknown cellular room. In order to explore a cell, the robot must enter it. Once inside, the robot knows which of the 4 adjacent cells exist and which are boundary edges. The robot starts from a specified cell adjacent to the room's outer wall; it visits each cell, and returns to the start. Our interest is in a short exploration tour, that is, in keeping the number of multiple cell visits small. For abitrary environments containing obstacles we provide a strategy producing tours of length S # C+ 1 2 E+H- 3, where C denotes the number of cells---the area---, E denotes the number of boundary edges---the perimeter---, and H is the number of obstacles.