Spatial Planning: A Configuration Space Approach

TLDR

The problem of arranging or moving objects without collisions is addressed by modeling each object's position and orientation as a point in a configuration space, where forbidden configurations form configuration space obstacles. This paper aims to develop algorithms that compute the constraints on an object's position imposed by other objects. The proposed algorithms compute configuration space obstacles for polygonal or polyhedral objects.

Abstract

This paper presents algorithms for computing constraints on the position of an object due to the presence of ther objects. This problem arises in applications that require choosing how to arrange or how to move objects without collisions. The approach presented here is based on characterizing the position and orientation of an object as a single point in a configuration space, in which each coordinate represents a degree of freedom in the position or orientation of the object. The configurations forbidden to this object, due to the presence of other objects, can then be characterized as regions in the configuration space, called configuration space obstacles. The paper presents algorithms for computing these configuration space obstacles when the objects are polygons or polyhedra.