Next: MINIMUM TRAVEL ROBOT LOCALIZATION
Up: Games and Puzzles
Previous: Games and Puzzles
where the robot is
initially placed, goal vertex ,
and a subset
of vertices where the obstacles are initially placed.
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.
The number of steps until the robot has been moved to the goal vertex t.
- Good News:
- Bad News:
are the lengths of the longest and shortest paths of degree-2
vertices in G.