Motion planning among time dependent obstacles

Paths and cycles (05C38) Convex sets in (2) dimensions (including convex curves) (52A10) Analysis of algorithms and problem complexity (68Q25) Artificial intelligence (68T99) Computing methodologies and applications (68U99)

Review text

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.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Motion planning among time dependent obstacles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1096427)