Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11533719_53 | COCOON |
Keywords | Field | DocType |
leq c,current position,abitrary environment,multiple cell,boundary edge,limited sensor,short exploration tour,simple grid polygon,online exploration problem,unknown cellular room,short-sighted mobile robot,upper bound,mobile robot,competitive analysis,online algorithms,exploration,online algorithm,lower bound,covering | Discrete mathematics,Online algorithm,Combinatorics,Polygon,Upper and lower bounds,Computer science,Exploration problem,Robot,Grid,Mobile robot,Competitive analysis | Conference |
Volume | ISSN | ISBN |
3595 | 0302-9743 | 3-540-28061-8 |
Citations | PageRank | References |
9 | 0.61 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Icking | 1 | 364 | 33.17 |
| Tom Kamphans | 2 | 62 | 9.74 |
| Rolf Klein | 3 | 143 | 16.94 |
| Elmar Langetepe | 4 | 199 | 25.87 |