1
$\begingroup$

What is the goal of a constraint solver? How are constraints propagated in a constraint satisfaction search?

Any references are also appreciated.

$\endgroup$
2
$\begingroup$

You want Chapter 6 of Russell & Norvig's AI: A Modern Approach, for a starting place.

The goal of a constraint solver is to find an assignment of values to variables such that every variable is assigned a value, but none of a list of constraints are violated.

An example problem that a constraint solver can solve is the problem of assigning students to groups for a project. The variables are the names of the students. Each variable has a set of possible values it could take on that correspond to the names of the groups. The constraints prohibit assigning certain students to the same group (perhaps they hate each other), or require certain students to be assigned to the same group (perhaps they like each other). More complex constraints are also possible (e.g. at least 2 of these 5 students need to be in the same group).

Constraint propagation is the idea that several constraints might logically imply a stronger constraint. As a simple example, suppose that student $S$ must be assigned to group $1$. That's one constraint. Suppose further that student $T$ must be assigned to the same group as $S$. That's another constraint. Together, however, they imply that $T$ must be assigned to group $1$.

Most constraint solvers operate by iteratively trying to assign values to variables and then backtracking when a constraint is violated. When assignments are made, different constraint propagation methods make different decisions about how much computational effort to spend deriving the logical consequences of constraints, as opposed to simply trying more assignments of values to variables until the consequences become apparent (one of the existing constraints gets violated).

The simplest form of constraint propagation is called forward checking. After each speculative assignment of a value to a variable, forward checking looks at all the constraints the variable is involved in. It then derives the logical consequences of the assignments. For example, continuing with the student problem from above, if $S$ was assigned value $1$, then forward checking would notice the constraint $S=T$, and would, effectively, add the constraint $T=1$ (it actually does something a little different, but it has this effect). As another example, if the assignment $T=2$ were made, forward checking would notice that $S=T$, and would add the constraint $S=2$. It would also detect the contradiction that $S=1$ and $S=2$ are both constraints, and would declare the assignment $T=2$ invalid.

More advanced constraint propagation methods can reason about these kinds of logical consequences before assignment are made. For example, they could derive that $T=1$ before the program starts. Wikipedia has a good summary of these, starting with arc consistency.

$\endgroup$
  • $\begingroup$ I could understand the idea of local consistency. What does this actually mean? $\endgroup$ – Lexi May 1 at 13:10
  • $\begingroup$ @Lexi That seems like it should be its own question on this site. It would be a good one to ask though! $\endgroup$ – John Doucette May 1 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.