Computer Science – Computational Geometry
Scientific paper
2010-12-23
Computer Science
Computational Geometry
49 pages, 45 figures
Scientific paper
We investigate the exploration problem of a short-sighted mobile robot moving in an unknown cellular room. 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 no obstacles we provide a strategy producing tours of length S <= C + 1/2 E - 3, and for environments containing obstacles we provide a strategy, that is bound by S <= C + 1/2 E + 3H + WCW - 2, 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, and WCW is a measure for the sinuosity of the given environment.
Icking Christian
Kamphans Tom
Klein Rolf
Langetepe Elmar
No associations
LandOfFree
Exploring Grid Polygons Online does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exploring Grid Polygons Online, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exploring Grid Polygons Online will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-296945