In this paper we study the problem of motion planning in the presence of time dependent, i.e. moving, obstacles. More specifically, we will consider the 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 we introduce time-dependent graphs. It is shown that a path existence problem in time-dependent graphs is PSPACE-complete. Using this result we will demonstrate 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. Furthermore we introduce the notion of the c-hull of an obstacle: the c-hull is the collection of all positions in space-time at which a future collision with an obstacle cannot be avoided. In the low-dimensional situation D=1 and D=2 we develop polynomial-time algorithms for the computation of the c-hull as well as for the motion planning problem in the special case where the obstacles are polyhedral. In particular for D=1 there is a O(n lg n) time algorithm for the motion planning problem where n is the number of edges of the obstacle. © 1988 Springer-Verlag.
https://doi.org/10.1007/BF02915447Cite as:
@article{Sutner_1988,
doi = {10.1007/bf02915447},
url = {https://doi.org/10.1007%2Fbf02915447},
year = 1988,
month = {oct},
publisher = {Springer Science and Business Media {LLC}},
volume = {26},
number = {1-2},
pages = {93--122},
author = {K. Sutner and W. Maass},
title = {Motion planning among time dependent obstacles},
journal = {Acta Informatica}
}