4 Reasoning with Constraints 4 Reasoning with Constraints 4.2 Solving CSPs by Searching

4.1 Variables and Constraints

4.1.1 Variables and Assignments

An algebraic variable, or variable, is used to name a feature. The domain of variable $X$ , written $dom(X)$ , is the set of values the variable can take.

Symbols and Semantics

Algebraic variables are symbols.

Internal to a computer, a symbol is just a sequence of bits that is distinguished from other symbols. In a program we use constants to denote symbols. Some symbols have a fixed interpretation; for example, symbols that represent numbers and symbols that represent characters are predefined in most computer languages. Symbols with a user-defined meaning, but without a predefined meaning in the language, can be defined in many programming languages. Lisp refers to them as atoms. Python 3.4 introduced a symbol type called $e n u m$ , but Python’s strings are often used as symbols. Usually, symbols are implemented as indexes into a symbol table that gives the name to print out. The only operation performed on these symbols is equality, to determine whether two symbols are the same. This can be implemented by comparing the indexes in the symbol table.

To users of a computer, symbols can have meanings. A person who inputs constraints or interprets the output of a program associates meanings with the symbols making up the constraints or the outputs. They associate a symbol with some concept or object in the world. For example, the variable $S a m s H e i g h t$ , to the computer, is just a sequence of bits. It has no relationship to $S a m s W e i g h t$ or $A l s H e i g h t$ . To a person, this variable may mean the height, in particular units, of a particular person at a particular time.

The meaning associated with a variable–value pair must obey the clarity principle: an omniscient agent – a fictitious agent who knows the truth and the meanings associated with all of the symbols – should be able to determine the value of each variable. For example, the height of Hagrid only satisfies the clarity principle if the particular person being referred to and the particular time are specified as well as the units. For example, one may want to reason about the height, in centimeters, of Hagrid in a particular scene at the start of the second Harry Potter movie. This is different from the height, in inches, of Hagrid at the end of the third movie (although they are, of course, related). To refer to Hagrid’s height at two different times, you need two variables.

You should have a consistent meaning for any symbols you use. When stating constraints, you must have the same meaning for the same variable and the same values, and you can use this meaning to interpret the output.

The bottom line is that symbols have meanings because you give them meanings. For this chapter, assume that the computer does not know what the symbols mean. A computer may know what a symbol means if it perceives and manipulates the environment.

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 $\{false{}$ , $true{}\}$ . We can also have variables that are not discrete; for example, a variable whose domain is the real numbers or a range of the real numbers is a continuous variable.

Given a set of variables, an assignment on the set of variables is a function from the variables into the domains of the variables. We write an assignment on $\{X_{1},X_{2},\dots,X_{k}\}$ as $\{X_{1}{\,{=}\,}v_{1},X_{2}{\,{=}\,}v_{2},\dots,X_{k}{\,{=}\,}v_{k}\}$ , where $v_{i}$ is in $dom(X_{i})$ . This assignment specifies that, for each $i$ , variable $X_{i}$ is assigned value $v_{i}$ . A variable can only be assigned one value in an assignment.

A total assignment assigns a value to every variable.

Example 4.1.

The variable ${Class\_time}$ may denote the starting time for a particular class. The domain of ${Class\_time}$ may be the following set of possible times:

dom({Class\_time})=\{8,9,10,11,12,1,2,3,4,5\}.

The variable ${Height\_joe}$ may refer to the height of a particular person, Joe, at a particular time and have as its domain the set of real numbers, in some range, that represent Joe’s height in centimeters. ${Raining}$ may be a random variable with domain $\{true{}$ , $false{}\}$ , which has value $true{}$ if it is raining at a particular time.

The assignment $\{{Class\_time}{\,{=}\,}11$ , ${Height\_joe}{\,{=}\,}165$ , ${Raining}{\,{=}\,}false{}\}$ means the class starts at 11, Joe is 165 cm tall, and it is not raining.

Example 4.2.

In the electrical environment of Figure 1.6, there may be a variable for the position of each switch that specifies whether the switch is up or down. There may be a variable for each light that specifies whether it is lit or not. There may be a variable for each component specifying whether it is working properly or if it is broken. Some variables that the following examples use include:

•

$S_{1}\_{pos}$ is a binary variable denoting the position of switch $s_{1}$ with domain $\{{up}$ , ${down}\}$ , where $S_{1}\_{pos}{\,{=}\,}{up}$ means switch $s_{1}$ is up and $S_{1}\_{pos}{\,{=}\,}{down}$ means switch $s_{1}$ is down.
•

$S_{1}\_{st}$ is a discrete variable denoting the status of switch $s_{1}$ with domain $\{{ok},$ ${upside\_down},$ ${short},$ ${intermittent},$ ${broken}\}$ , where $S_{1}\_{st}{\,{=}\,}{ok}$ means switch $s_{1}$ is working normally, $S_{1}\_{st}{\,{=}\,}{upside\_down}$ means it is installed upside down, $S_{1}\_{st}{\,{=}\,}{short}$ means it is shorted and it allows electricity to flow whether it is up or down, $S_{1}\_{st}{\,{=}\,}{intermittent}$ means it is working intermittently, and $S_{1}\_{st}{\,{=}\,}{broke}n$ means it is broken and does not allow electricity to flow.
•

${Number\_of\_broken\_switches}$ is an integer-valued variable denoting the number of switches that are broken.
•

${Current\_w}_{1}$ is a real-valued variable denoting the current, in amps, flowing through wire $w_{1}$ . ${Current\_w}_{1}{\,{=}\,}1.3$ means there are $1.3$ amps flowing through wire $w_{1}$ . Inequalities between variables and constants form Boolean conditions; for example, ${Current\_w}_{1}\geq 1.3$ is true when there are at least $1.3$ amps flowing through wire $w_{1}$ .

A total assignment specifies the position of every switch, the status of every device, and so on. For example, an assignment may be switch 1 is up, switch 2 is down, fuse 1 is okay, wire 3 is broken, etc.

Example 4.3.

Crossword puzzles, a popular form of recreation, involve filling in squares on a grid to make words that fit clues. There are two different representations of crossword puzzles in terms of variables:

•

In one representation, the variables are the numbered squares with the direction of the word (down or across) and the domains are the set of possible words that can be used. For example, one_across could be a variable with domain $\{$ “ant”, “big”, “bus”, “car”, “has” $\}$ . A total assignment gives a word for each of the variables.
•

In another representation of a crossword, the variables are the individual squares and the domain of each variable is the set of letters in the alphabet. For example, the top-left square could be a variable $p00$ with domain $\{a,\dots,z\}$ . A total assignment gives a letter to each square.

Example 4.4.

A trading agent, in planning a trip for a group of tourists, may be required to schedule a given set of activities. There could be two variables for each activity: one for the time, for which the domain is the set of possible times or days for the activity, and one for the location, for which the domain is the set of possible locations where it may occur. A total assignment gives a time and location for each activity.

An alternative representation may have the times as the variables (e.g., each hour for each day), with domains the set of possible activity–location pairs.

The number of total assignments is the product of the number of values in the domains of the variables.

Example 4.5.

If there are two variables, $A$ with domain $\{0,1,2\}$ and $B$ with domain $\{true{},false{}\}$ , there are six total assignments, which we name $w_{0},\dots,w_{5}$ as follows”

•

$w_{0}=\{A{\,{=}\,}0,B{\,{=}\,}true{}\}$
•

$w_{1}=\{A{\,{=}\,}0,B{\,{=}\,}false{}\}$
•

$w_{2}=\{A{\,{=}\,}1,B{\,{=}\,}true{}\}$
•

$w_{3}=\{A{\,{=}\,}1,B{\,{=}\,}false{}\}$
•

$w_{4}=\{A{\,{=}\,}2,B{\,{=}\,}true{}\}$
•

$w_{5}=\{A{\,{=}\,}2,B{\,{=}\,}false{}\}$

If there are $n$ variables, each with domain size $d$ , there are $d^{n}$ total assignments.

One main advantage of reasoning in terms of variables is computational saving. Consider deciding whether to model in terms of states explicitly or to model the states in terms of binary variables. Many states can be described by a few variables:

•

10 binary variables can describe $2^{10}=1024$ states
•

20 binary variables can describe $2^{20}=1,048,576$ states
•

30 binary variables can describe $2^{30}=1,073,741,824$ states
•

100 binary variables can describe $2^{100}=1,267,650,600,228,229,401,496$ , $703,205,376$ states.

Reasoning in terms of thirty variables may be easier than reasoning in terms of more than a billion states. One hundred variables is not that many, but reasoning in terms of more than $2^{100}$ states explicitly is not possible. Many real-world problems have thousands, if not millions, of variables.

4.1.2 Constraints

In many applications, not all possible assignments of values to variables are permissible. A hard constraint, or simply constraint, specifies legal combinations of assignments of values to some of the variables. The set of variables involved in the constraint is the scope of the constraint. A constraint specifies a condition on these variables that is true or false for each assignment to the variables in the scope.

A unary constraint is a constraint on a single variable (e.g., $B\leq 3$ ). A binary constraint is a constraint over a pair of variables (e.g., $A\leq B$ ). In general, a $k$ -ary constraint has a scope of size $k$ . For example, $A+B=C$ is a 3-ary (ternary) constraint.

A constraint can be evaluated in an assignment that assigns a superset of the variables in the scope. The extra variables are ignored. For example, $A\leq B$ is true of the assignment $\{A=3,B=7,C=5\}$ .

Assignment $A$ satisfies constraint $c$ if $A$ assigns the variables in the scope of $c$ and the condition of $c$ evaluates to true for $A$ restricted to the scope of $c$ . Assignment $A$ violates constraint $c$ if $A$ assigns the variables in the scope of $c$ and the condition of $c$ evaluates to false for that assignment.

If an assignment $A$ satisfies a constraint, then any assignment that is a superset of $A$ also satisfies the constraint.

Example 4.6.

Suppose a robot needs to schedule a set of activities for a manufacturing process, involving casting, milling, drilling, and bolting. Each activity has a set of possible times at which it may start. The robot has to satisfy various constraints arising from prerequisite requirements and resource use limitations. For each activity there is a variable that represents the time that it starts. For example, it could use $D$ to represent the start time for the drilling, $B$ the start time of the bolting, and $C$ the start time for the casting. Drilling must start before bolting corresponds to the constraint $D<B$ . Casting and drilling must not start at the same time corresponds to the constraint $C\neq D$ . Bolting must start 3 time units after casting starts corresponds to the constraint $B=C+3$ .

Constraints are defined either by their intension, in terms of formulas, or by their extension, listing all the assignments that are true. Constraints defined extensionally can be seen as relations of legal assignments as in relational databases.

Example 4.7.

Consider a constraint on the possible dates for three activities. Let $A$ , $B$ , and $C$ be variables that represent the date of each activity. Suppose the domain of each variable is $\{1,2,3,4\}$ .

A constraint with scope $\{A,B,C\}$ could be described by its intension, using a logical formula to specify the legal assignments, such as

(A\leq B)\wedge(B<3)\wedge(B<C)\wedge\neg(A=B\wedge C\leq 3)

where $\wedge$ means and and $\neg$ means not. This formula says that $A$ is on the same date or before $B$ , and $B$ is before day $3$ , $B$ is before $C$ , and it cannot be that $A$ and $B$ are on the same date when $C$ is on or before day 3.

The extensional definition of this constraint is defined using the following table specifying the legal assignments:

$A$	$B$	$C$
2	2	4
1	1	4
1	2	3
1	2	4

The first assignment is $\{A{\,{=}\,}2,B{\,{=}\,}2,C{\,{=}\,}4\}$ , which assigns $A$ the value 2, $B$ the value 2, and $C$ the value 4. There are four legal assignments of the variables.

The assignment $\{A{\,{=}\,}1,B{\,{=}\,}2,C{\,{=}\,}3,D{\,{=}\,}3,E{\,{=}\,}1\}$ satisfies this constraint because when restricted to the scope of the relation, namely $\{A{\,{=}\,}1,B{\,{=}\,}2,C{\,{=}\,}3\}$ , it is one of the legal assignments in the table.

Example 4.8.

Consider the constraints for the two representations of crossword puzzles of Example 4.3:

•

For the representation in which the domains are words, the constraint is that the letters where a pair of words intersect must be the same.
•

For the representation in which the domains are letters, the constraint is that each contiguous sequence of letters must form a legal word.

4.1.3 Constraint Satisfaction Problems

A constraint satisfaction problem (CSP) consists of:

•

a set of variables
•

a domain for each variable
•

a set of constraints.

A solution is a total assignment that satisfies all of the constraints.

Example 4.9.

Suppose the delivery robot must carry out a number of delivery activities, $a$ , $b$ , $c$ , $d$ , and $e$ . Suppose that each activity happens at any of times $1$ , $2$ , $3$ , or $4$ . Let $A$ be the variable representing the time that activity $a$ will occur, and similarly for the other activities. The variable domains, which represent possible times for each of the deliveries, are

	$\displaystyle dom(A)=\{1,2,3,4\},~{}~{}dom(B)=\{1,2,3,4\},~{}~{}dom(C)=\{1,2,3% ,4\},$
	$\displaystyle dom(D)=\{1,2,3,4\},~{}~{}dom(E)=\{1,2,3,4\}.$

Suppose the following constraints must be satisfied:

	$\displaystyle\{$	$\displaystyle(B\neq 3),~{}(C\neq 2),~{}(A\neq B),~{}(B\neq C),~{}(C<D),~{}(A=D),$
		$\displaystyle(E<A),~{}(E<B),~{}(E<C),~{}(E<D),~{}(B\neq D).\}$

It is instructive for you to try to find a solution for this example; try to assign a value to each variable that satisfies these constraints.

Given a CSP, a number of tasks are useful:

•

determine whether or not there is a solution
•

find a solution when there is one
•

count the number of solutions
•

enumerate all of the solutions
•

find a best solution, given a measure of how good solutions are
•

determine whether some statement holds in all solutions.

The multidimensional aspect of CSPs, where each variable is a separate dimension, makes these tasks difficult to solve, but also provides structure that can be exploited.

CSPs are very common, so it is worth trying to find relatively efficient ways to solve them. Determining whether there is a solution for a CSP with finite domains is NP-complete (see box) and no known algorithms exist to solve such problems that do not use exponential time in the worst case. However, just because a problem is NP-complete does not mean that all instances are difficult to solve. Many instances have structure to exploit.

Artificial Intelligence 3E