A Tagging Method for Distributed Constraint Satisfaction

TitleA Tagging Method for Distributed Constraint Satisfaction
Publication TypeTechnical Report
Year of Publication1989
AuthorsGuesgen, H. Werner
Other Numbers536

Local propagation algorithms such as Waltz' filtering and Mackworth's AC-x algorithms have been successfully applied in AI for solving constraint satisfaction problems (CSPs). In general, these algorithms can only be used as preprocessing methods as they do not compute a global consistent solution for a CSP; they result in local consistency also known as arc consistency. In this paper, we introduce an extension of local constraint propagation to overcome this drawback, i.e., to compute global consistent solutions for a CSP. The advantage over backtracking approaches is that the method introduced here is easy to implement on parallel machines with an arbitrary number of processors. The underlying idea is to associate recursive tags with the values during the propagation process so that global relationships among the values are maintained.

Bibliographic Notes

ICSI Technical Report TR-89-037

Abbreviated Authors

H. W. Guesgen

ICSI Publication Type

Technical Report