Solving Geometric Constraint Satisfaction Problems for Spatial Planning

Abstract

Like many important problems in artificial intelligence and operations research, spatial planning problems can be viewed as constraint satisfaction problems (CSP). Many techniques, such as consistency algorithms, have been designed to solve CSPs in which variables take on values from one-dimensional domains. The fact that spatial planning leads to multidimensional domains increases the combinatorial complexity. In this paper, we propose a . new approach to solve geometric constraint satisfaction problems. A uniform symbolic representation of different geometric constraints, based on the configuration space approach, is defined in order to achieve conjunctions of constraints bearing on the same objects and arcconsistency. The geometric focus of our approach allows a rich expressivity. In terms of complexity, it takes advantage of the compactness of intentional geometric representations, with the same idea as consistency do over intervals. The proposed principles have been implemented in the ATLAS spatial planning system, and tested in the field of microwave electronic equipment design.