(3rd-May-2020)
A fundamental idea in AI is to exploit structure in a domain. One form of structure for CSPs arises from the exploitation of aspects of restricted classes of variables and constraints. One such class is the class of propositional satisfiability problems. These problems are characterized by
Boolean variables: a Boolean variable is a variable with domain {true,false}. Given a Boolean variable Happy, the proposition happy means Happy=true, and ¬happy means Happy=false.
Clausal constraints: a clause is an expression of the form l1∨ l2 ∨ ...∨ lk, where each li is a literal. A literal is an assignment of a value to a Boolean variable. A clause is satisfied, or true, in a possible world if and only if at least one of the literals that makes up the clause is true in that possible world.
Arc consistency simplifies the network by removing values of variables. A complementary method is variable elimination (VE), which simplifies the network by removing variables.
The idea of VE is to remove the variables one by one. When removing a variable X, VE constructs a new constraint on some of the remaining variables reflecting the effects of X on all of the other variables. This new constraint replaces all of the constraints that involve X, forming a reduced network that does not involve X. The new constraint is constructed so that any solution to the reduced CSP can be extended to a solution of the larger CSP that contains X. In addition to creating the new constraint, VE provides a way to construct a solution to the CSP that contains X from a solution to the reduced CSP.
Comments