An approach to the movers' problem that combines oriented matroid theory and algebraic geometry

Abstract

This paper investigates the partition of the configuration space induced by basic contacts between polyhedra, using their combinatorial interpretation in terms of oriented matroids. It is shown that solving motion planning problems using this cellular decomposition can be analytically expressed in terms of invariants, without explicit use of artificial coordinate frames. One of the main aims of this paper is to draw the attention of the reader to some results from the theory of matroids which are directly applicable to path planning, and many other geometric problems arising in robotics. In particular, the relevance of the concept of mutation in the context of collision-free path planning is highlighted. Moreover, it is proved that the set of mutations contains the walls of a given cell in configuration space, and that this set, as one moves from one cell to a neighbour one, can be updated in linear time with the number of vertices. This provides a simple way to detect a large amount of redundant constraints from purely combinatorial considerations, without relying on the manipulation of algebraic equations.