Distributing Constraints by Sampling in Non-Binary CSPs
A PHP Error was encountered
Message: Undefined index: id
Line Number: 218
Nowadays, many real problems can be modeled as Con- straint Satisfaction Problems (CSPs). Generally, these problems are solved by search algorithms, which re- quire an order in which variables and values should be considered. Choosing the right order of variables and values can noticeably improve the eciency of con- straint satisfaction. The order in which constraints are studied can also improve eciency, particularly in problems with non-binary constraints. In this paper, we present a distributed model for solv- ing non-binary CSPs, in which agents are committed to sets of constraints. A preprocessing agent is com- mitted to ordering the constraints by a sample in finite population so that the tightest constraints are studied first. Then, a set of agents are incrementally and con- currently committed to building partial solutions until a problem solution is found. This constraint ordering, as well as value and variable ordering, can improve e- ciency because inconsistencies can be found earlier and the number of constraint checks can be significantly reduced.