Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

### 4.8.4 Exploiting Propositional Structure in Local Search

Stochastic local search is simpler for CSPs that are in the form of propositional satisfiability problems, with Boolean variables and constraints that are clauses. Each local search step can be made more efficient for three main reasons:

- Because only one alternative value exists for each assignment to a variable, the algorithm does not have to search through the alternative values.
- Changing any value in an unsatisfied clause makes the clause satisfied. As a result, it is easy to satisfy a clause, but this may make other clauses unsatisfied.
- If a variable is changed to be true, only those clauses where it appears negatively can be made unsatisfied and similarly for variables becoming false. This enables fast indexing of clauses.

It is possible to convert any finite CSP into a propositional
satisfiable problem. A variable *Y* with domain
*{v _{1},...,v_{k}}* can be converted into

*k*Boolean variables

*{Y*, where

_{1},...,Y_{k}}*Y*is true when

_{i}*Y*has value

*v*and is false otherwise. Each

_{i}*Y*is called an

_{i}**indicator variable**. There is a clause for each false tuple in each constraint, which specifies which assignments to the

*Y*are not allowed by the constraint. There are also constraints that specify that

_{i}*Y*and

_{i}*Y*cannot both be true when

_{j}*i≠j*. There is also a constraint that one of the variables

*Y*must have value

_{i}*true*. Converting a CSP into a propositional satisfiability problem has three potential advantages:

- Each local step can be simpler and therefore implemented more efficiently.
- The search space is expanded. In particular, before a solution
has been found, more than one
*Y*could be true (which corresponds to_{i}*Y*having multiple values) or all of the*Y*variables could be false (which corresponds to_{i}*Y*having no values). This can mean that some assignments that were local minima in the original problem may not be local minima in the new representation. - Satisfiability has been studied much more extensively than most other types of CSPs and more efficient solvers are currently known because more of the space of potential algorithms has been explored by researchers.

Whether the conversion makes search performance better for a particular example is, again, an empirical question.