Interval Arithmetic Approach to Movers' Problem

Natee Tongsiri

Research Institute for Symbolic Computation (RISC)
A-4232 Hagenberg im Muhlkreis, Austria

The goal of Movers' Problem or obstacle avoidance problem is to move an object from a given initial position to a final position without colliding with other objects in the process. In trying to solve Movers' Problems, \emph{configuration space} approach can be used. Regions in a configuration space which represent forbidden configuration of the object due to the presence of other object are called \emph{configuration space obstacles}.

The configuration space obstacles are geometric objects that can be represented using Boolean combinations of inequalities. Moreover, they can also be represented using existential quantifiers which correspond to geometric projections. If the projected variables only occur algebraically then it is possible to eliminate quantifiers and represent configuration space obstacles in the semi-algebraic form. However, no matter how it is done, the quantifier elimination is computationally hard and the output in semi-algebraic representation is often large and cumbersome. Therefore we are looking for a possibility to work directly with the quantified representation of the configuration space obstacles using interval arithmetic.

In this work, we investigate the use of an interval evaluation of formulae along with spatial subdivision and pruning. We begin the process by representing axially align boxes using intervals and evaluating the formulae over all boxes. Evaluation results of each box can then be classified as \emph{empty}, \emph{full} or \emph{undecided}, the latter of which may get divided and evaluated further. In this way, we obtain the approximation of the region of configuration space obstacles at some specified resolutions.