Semilinear Motion Planning Among Moving Objects in REDLOG

We study motion planning for rigid objects moving within a non-static, time dependent two or three-dimensional environment. As in a previous paper [19], both the object to be moved and the free space are both semilinear sets with no convexity assumptions. The admissible motions are finite continuous sequences of translations with fixed speeds along finitely many prescribed directions. But now the free space can change in a piecewise linear way with time. So the problem of path finding becomes a problem of finding a piecewise linear time-dependent trajectory of the given semilinear object from a given initial position to a semilinear set of admissible final positions that may change semilinearly with time. Moreover the trajectory is limited to a prescribed time interval. By a strong generalization of the static case we show how to model and solve this problem for a bounded number of translations by linear real quantifier elimination. The worst case complexity of the algorithms is similar as in the static case. Experimental results using the elimination facilities of the Redlog package of Reduce show the practical relevance of the approach. This concerns in particular semilinear motion planning within a static environment with additional moving objects. Applications include automatic motion planning of an automobile or aircraft within moving traffic, and automatic motion planning of a carrier for material in a factory with other moving carriers.