MINIMUM GRAPH MOTION PLANNING

• INSTANCE: Graph $G=\left(V,E\right)$, start vertex $s\in V$ where the robot is initially placed, goal vertex $t\in V$, and a subset $W\subseteq V$ 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 $O(\sqrt{\vert V\vert})$ [392].

• Bad News: APX-complete [392].

• Comment: Approximable within $O(l_{\max}/l_{\min})$, where $l_{\max}$ and $l_{\min}$ are the lengths of the longest and shortest paths of degree-2 vertices in G.