Artificial Intelligence: Foundations of Computational Agents,  2nd Edition

Chapter 4 Reasoning with Constraints

Every task involves constraint,
Solve the thing without complaint;
There are magic links and chains
Forged to loose our rigid brains.
Structures, strictures, though they bind,
Strangely liberate the mind.

– James Falen

Instead of reasoning explicitly in terms of states, it is typically better to describe states in terms of features and to reason in terms of these features. Features are described using variables. Often 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. In planning and scheduling an agent assigns a time for each action. These assignments must satisfy constraints on the order actions can be carried out and constraints specifying that the actions achieve a goal. Preferences over assignments are specified in terms of soft constraints. This chapter shows how to generate assignments that satisfy hard constraints and optimize soft constraints.