Next: MINIMUM TRAVEL ROBOT LOCALIZATION Up: Games and Puzzles Previous: Games and Puzzles Index

### MINIMUM GRAPH MOTION PLANNING

- 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 [370].

- Bad News: APX-complete [370].

- Comment: Approximable within , where and are the lengths of the longest and shortest paths of degree-2 vertices in G.