zbMATH — the first resource for mathematics

Exploring simple grid polygons. (English) Zbl 1128.68504
Wang, Lusheng (ed.), Computing and combinatorics. 11th annual international conference, COCOON 2005, Kunming, China, August 16–29, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28061-8/pbk). Lecture Notes in Computer Science 3595, 524-533 (2005).
Summary: We investigate the online exploration problem of a short-sighted mobile robot moving in an unknown cellular room without obstacles. The robot has a very limited sensor; it can determine only which of the four cells adjacent to its current position are free and which are blocked, i.e., unaccessible for the robot. Therefore, the robot must enter a cell in order to explore it. The robot has to visit each cell and to return to the start. Our interest is in a short exploration tour, i.e., in keeping the number of multiple cell visits small. For abitrary environments without holes we provide a strategy producing tours of length $$S \leq C + \frac{1}{2} E - 3$$, where $$C$$ denotes the number of cells – the area –, and $$E$$ denotes the number of boundary edges – the perimeter – of the given environment. Further, we show that our strategy is competitive with a factor of $$\frac43$$, and give a lower bound of $$\frac76$$ for our problem. This leaves a gap of only $$\frac16$$ between the lower and the upper bound.
For the entire collection see [Zbl 1078.68006].

MSC:
 68T40 Artificial intelligence for robotics 68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: