Artificial Intelligence Foundations of Computational Agents

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.

PossibleWorlds, Variables, and Constraints

Variables and Worlds

Constraint satisfaction problems are described in terms of variables and possible worlds. A possible world is a possible way the world (the real world or some imaginary world) could be.

Possible worlds are described by algebraic variables. An algebraic variable is a symbol used to denote features of possible worlds. For this chapter, we refer to an algebraic variable simply as a variable. Algebraic variables are written starting with an upper-case letter. Each algebraic variable X has an associated domain, dom(X), which is the set of values the variable can take.

A discrete variable is one whose domain is finite or countably infinite. A binary variable is a discrete variable with two values in its domain. One particular case of a binary variable is a Boolean variable, which is a variable with domain ﹛true, false﹜. We can also have variables that are not discrete; for example, a variable whose domain corresponds to the real line or an interval of the real line is a continuous variable.