- 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*.