The following are the main points you should have learned from this chapter:

• •

  Instead of reasoning explicitly in terms of worlds or states, it is almost always much more efficient for an agent to reason in terms of variables or features.

• •

  Constraint satisfaction problems are represented as a set of variables, domains for the variables, and a set of hard and/or soft constraints. A solution is an assignment of a value to each variable that satisfies a set of hard constraints or optimizes the sum of the soft constraints.

• •

  Arc consistency and search can often be combined to find assignments that satisfy some constraints or to show that there is no assignment.

• •

  Stochastic local search can be used to find satisfying assignments, but not to show there are no satisfying assignments. The efficiency depends on the trade-off between the time taken for each improvement and how much the value is improved at each step. Some method must be used to allow the search to escape local minima that are not solutions.

• •

  Optimization can use systematic methods when the constraint graph is sparse. Local search can also be used, but the added problem arises of not knowing when the search is at a global optimum.