Distributed Constraint Propagation : A Case Study

Abstract

Constraint satisfaction techniques are now widely used in AI problem solving. Discrete constraint propagation algorithms were brought into prominence by David Waltz, who applied them to the problem of finding consistent labellings of line drawings. This paper presents the realization of a Waltz-like algorithm in terms of a society of cooperating agents. The architecture of SCENELAB is sketched, a computer system for labelling pictures drawn from scenes in the blocks world. SCENELAB is implemented in CSSA, a programming language for the realization of asynchronously concurrent processes. It is argued that this approach is not restricted to scene labelling algorithms. A class of constraints is identified which is suited to similar solutions and which SCENELAB is able to handle. Finally, some further points are more briefly addressed: a comparison of the present work to sequential and synchronized parallel versions of the Waltz-algorithm, and the problems raised by the occurrence of incomplete and erroneous picture data in real world applications.