GP1 MINIMUM GRAPH MOTION PLANNING

Next: GP2 MINIMUM TRAVEL Up: Games and Puzzles Previous: Games and Puzzles

I NSTANCE : Graph , start vertex where the robot is initially placed, goal vertex , and a subset of vertices where the obstacles are initially placed.
S OLUTION : 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.
M EASURE : The number of steps until the robot has been moved to the goal vertex t .
Good News: Approximable within [ 283 ].
Bad News: A PX -complete [ 283 ].
Comment: Approximable within , where and are the lengths of the longest and shortest paths of degree-2 vertices in G .

Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997