Next: MINIMUM TRAVEL ROBOT LOCALIZATION
Up: Games and Puzzles
Previous: Games and Puzzles
  Index
- INSTANCE:
Graph
,
start vertex
where the robot is
initially placed, goal vertex ,
and a subset
of vertices where the obstacles are initially placed.
- SOLUTION:
A motion scheme for the robot and the obstacles. In each time step
either the robot or one obstacle may be moved to a neighbouring
vertex that is not occupied by the robot or an obstacle.
- MEASURE:
The number of steps until the robot has been moved to the goal vertex t.
- Good News:
Approximable within
[392].
- Bad News:
APX-complete [392].
- Comment:
Approximable within
,
where
and
are the lengths of the longest and shortest paths of degree-2
vertices in G.
Viggo Kann
2000-03-20