Consistency Techniques in CSPs | ||
Extending the CSP Model to Cope With Partial Information |
Consistency Techniques in CSPs | ||
General Description | ||
Constraint Satisfaction Problems (CSPs) play a central role in many
Artificial Intelligence fields. For solving these problems
backtracking can be used. However, backtracking suffers from
trashing which can be solved by applying constraint propagation
algorithms that reduce a priori the search space. These techniques are
based on the idea of removing combination
of assignments which cannot appear in the solution.
Different degrees of consistency algorithms have been proposed.
We are currently investigating a meta Constraint Logic Programming (CLP) architecture which is able to reach whatever degree of consistency not by changing the algorithm, but by adding several levels each performing its own propagation method. Each level is a CLP on finite domain solver reasoning on the constraints of the underlying level. In particular, each level reasons on consistent k-tuples provided by the k-consistency of the underlying solver. The architecture is described in the Technical Report DEIS-LIA-95-004. In this way, for reaching higher levels of consistency we do not have to increase the complexity of the algorithm, but we have to add as many levels as we need, depending on the algorithm performed at each level. The overall consistency reached by the system is the sum of the consistency of different levels minus one. This application of the multi-level architecture is a specialization of a general scheme. The CLP can be seen as a general scheme which can be specialized by defining the domain and the operational semantics. In the same way, our architecture is general and can be specialized by defining the domain of each level and its operational semantics. In addition, we have to define some linking rules for connecting different level knowledge and control.
| ||
Current and Future Works | ||
| ||
Keywords | ||
| ||
Participants | ||
About this Server |
DocMaster |
LIA WebMaster |
|