A Tagging Method for Distributed Constraint Satisfaction
Title | A Tagging Method for Distributed Constraint Satisfaction |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Guesgen, H. Werner |
Other Numbers | 536 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-37.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-037 |
Abbreviated Authors | H. W. Guesgen |
ICSI Publication Type | Technical Report |