## 4.2 Possible Worlds, Variables, and Constraints

To keep the formalism simple and general, we develop the notion of features without considering time explicitly. Constraint satisfaction problems will be described in terms of possible worlds.

When we are not modeling change, there is a direct one-to-one correspondence between
features and variables, and between states and possible worlds.
A **possible world** is a possible way the world (the real
world or some imaginary world) could be.
For example, when representing a
crossword puzzle, the possible worlds correspond to the ways the
crossword could be filled out. In the electrical environment, a
possible world specifies the position of every switch and the status
of every component.

Possible worlds are described by algebraic variables. An
**algebraic variable** is a symbol used to denote features of
possible worlds. Algebraic variables will be written starting with an
upper-case letter. Each algebraic variable *V* has an associated
**domain**, *dom(V)*, which is the set of values the variable
can take on.

For this chapter, we refer to an algebraic variable simply as a
**variable**. These algebraic variables are different
from the variables used
in logic, which are discussed in Chapter 12. Algebraic
variables are the same as the random variables used in
probability theory, which are discussed in Chapter 6.

**Symbols and Semantics**

Algebraic variables are symbols.

Internal to a computer, a **symbol**
is just a sequence of bits that can be distinguished from other
symbols. Some symbols have a fixed interpretation, for example, symbols that
represent numbers and symbols that represent characters. Symbols that
do not have fixed meaning appear in many programming languages. In Java,
starting from Java 1.5, they are called *enumeration types*. Lisp refers to
them as *atoms*. Usually, they 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 if two symbols are the same or not.

To a **user** of a computer, symbols have meanings. A person
who inputs constraints or interprets the output associates
meanings with the symbols that make up the constraints or the outputs. He or she
associates a symbol with some concept or object in the world. For
example, the variable *HarrysHeight*, to the computer, is just a
sequence of bits. It has no relationship to *HarrysWeight* or
*SuesHeight*. 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 satisfy
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 Harry* 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, we may want to reason about the height, in
centimeters, of Harry Potter at the start of the second movie of
J. K. Rowling's book. This is different from the height, in inches, of
Harry Potter at the end of the same movie (although they are, of course,
related). If you want to refer to Harry's height at two different
times, you must have two different variables.

You should have a consistent meaning. 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 can have meanings because we give them meanings. For this chapter, assume that the computer does not know what the symbols mean. A computer can only know what a symbol means if it can perceive and manipulate the environment.

A **discrete variable** is one whose domain is finite or
countably infinite. One particular case of a discrete variable is a
**Boolean variable**, which is a variable
with domain *{true*, *false}*. If *X* is a Boolean variable, we write
*X=true* as its lower-case equivalent, *x*, and write *X=false* as
* ¬x*. We can also have variables that are not discrete;
for example, a variable whose domain corresponds to a subset of the real line is a
**continuous variable**.

**Example 4.2:**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
at a particular time
and have as its domain the set of real numbers, in some range, that
represent the height in centimeters. *Raining* may be a Boolean random
variable with value *true* if it is raining at a particular time.

**Example 4.3:**Consider the electrical domain depicted in Figure 1.8.

*S*may be a discrete binary variable denoting the position of switch_{1}_pos*s*with domain_{1}*{up*,*down}*, where*S*means switch_{1}_pos=up*s*is up, and_{1}*S*means switch_{1}_pos=down*s*is down._{1}*S*may be a variable denoting the status of switch_{1}_st*s*with domain_{1}*{ok,**upside_down,**short,**intermittent,**broken}*, where*S*means switch_{1}_st=ok*s*is working normally,_{1}*S*means switch_{1}_st=upside_down*s*is installed upside down,_{1}*S*means switch_{1}_st=short*s*is shorted and acting as a wire,_{1}*S*means switch_{1}_st=intermittent*S*is working intermittently, and_{1}*S*means switch_{1}_st=broken*s*is broken and does not allow electricity to flow._{1}*Number_of_broken_switches*may be an integer-valued variable denoting the number of switches that are broken.*Current_w*may be a real-valued variable denoting the current, in amps, flowing through wire_{1}*w*._{1}*Current_w*means there are_{1}=1.3*1.3*amps flowing through wire*w*. We also allow inequalities between variables and constants as Boolean features; for example,_{1}*Current_w*is true when there are at least_{1}≥ 1.3*1.3*amps flowing through wire*w*._{1}

**Example 4.4:**A classic example of a constraint satisfaction problem is a crossword puzzle. 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 put in. A possible world corresponds to an assignment of 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. A possible world corresponds to an assignment of a letter to each square.

Possible worlds can be defined in terms of variables or variables can be defined in terms of possible worlds:

- Variables can be primitive and a
**possible world**corresponds to a**total assignment**of a value to each variable. - Worlds can be primitive and a variable is a function from possible worlds into the domain of the variable; given a possible world, the function returns the value of that variable in that possible world.

**Example 4.5:**If there are two variables,

*A*with domain

*{0,1,2}*and

*B*with domain

*{true,false}*, there are six possible worlds, which you can name

*w*. One possible arrangement of variables and possible worlds is

_{0},..., w_{5}*w*and_{0}: A=0*B=true**w*and_{1}: A=0*B=false**w*and_{2}: A=1*B=true**w*and_{3}: A=1*B=false**w*and_{4}: A=2*B=true**w*and_{5}: A=2*B=false*

**Example 4.6:**The trading agent, in planning a trip for a group of tourists, may be required to schedule a given set of activities. There can be two variables for each activity: one for the date, for which the domain is the set of possible days for the activity, and one for the location, for which the domain is the set of possible towns where it may occur. A possible world corresponds to an assignment of a date and a town for each activity.