Motion planning among time dependent obstacles (Q1096427)

In this paper motion planning in the presence of time dependent, i.e. moving, obstacles is studied. More specifically, consider the following problem: given a body B and a collection of moving obstacles in D- dimensional space, decide whether there is a continuous, collision-free movement of B from a given initial position to a target position subject to the condition that B cannot move any faster than some fixed top-speed c. As a discrete, combinatorial model for the continuous, geometric motion planning problem time-dependent graphs are introduced. It is shown that a path existence problem in time-dependent graphs is PSPACE- complete. Using this result one can show that a version of the motion planning problem (where the obstacles are allowed to move periodically) is PSPACE-hard, even if \(D=2\), B is a square and the obstacles have only translational movement. For \(D=1\) it is shown that motion planning is NP- hard. Define the c-hull of an obstacle to be the collection of all positions in space-time at which a future collision with the obstacle cannot be avoided. In the low-dimensional situation \(D=1\) and \(D=2\) polynomial-time algorithms for the computation of the c-hull as well as for the motion planning problem are given. In particular for \(D=1\) there is a O(n log n) time algorithm for the motion planning problem where n is the number of edges of the obstacles.