4 Features and Constraints

Instead of reasoning explicitly in terms of states, it is often better to describe states in terms of features and then to reason in terms of these features. Often these features are not independent and there are hard constraints that specify legal combinations of assignments of values to variables. As Falen's elegant poem emphasizes, the mind discovers and exploits constraints to solve tasks. Common examples occur in planning and scheduling, where an agent must assign a time for each action that must be carried out; typically, there are constraints on when actions can be carried out and constraints specifying that the actions must actually achieve a goal. There are also often preferences over values that can be specified in terms of soft constraints. This chapter shows how to generate assignments that satisfy a set of hard constraints and how to optimize a collection of soft constraints.

• 4.1 Features and States
• 4.2 Possible Worlds, Variables, and Constraints
  • 4.2.1 Constraints
  • 4.2.2 Constraint Satisfaction Problems
• 4.3 Generate-and-Test Algorithms
• 4.4 Solving CSPs Using Search
• 4.5 Consistency Algorithms
• 4.6 Domain Splitting
  • 4.6.1 Exploiting Propositional Structure
• 4.7 Variable Elimination
• 4.8 Local Search
  • 4.8.1 Iterative Best Improvement
  • 4.8.2 Randomized Algorithms
  • 4.8.3 Evaluating Randomized Algorithms
  • 4.8.4 Exploiting Propositional Structure in Local Search
• 4.9 Population-Based Methods
• 4.10 Optimization
  • 4.10.1 Systematic Methods for Optimization
  • 4.10.2 Local Search for Optimization
• 4.11 Review
• 4.12 References and Further Reading
• 4.13 Exercises