4.1 Possible Worlds, Variables, and Constraints

4.1.1 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.

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. 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 meaning outside of the program (as opposed to variables in the program), but without a predefined meaning in the language, can be defined in many programming languages. In Java they are called enumeration types. Lisp refers to them as atoms. Python 3.4 introduced a symbol type called enum, 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 a user of a computer, symbols 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. He or she associates a symbol with some concept or object in the world. For example, the variable SamsHeight, to the computer, is just a sequence of bits. It has no relationship to SamsWeight or AlsHeight. 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 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 can 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 {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.

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 {X1,X2,,Xk} as {X1=v1,X2=v2,,Xk=vk}, where vi is in dom(Xi). This assignment specifies that, for each i, variable Xi is assigned value vi. A variable can only be assigned one value in an assignment. A total assignment assigns all of the variables. Assignments do not have to be total, but may be partial.

A possible world is defined to be a total assignment. That is, it is a function from variables into values that assigns a value to every variable. If world w is the assignment {X1=v1,X2=v2,,Xk=vk}, we say that variable Xi has value vi in world w.

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:

𝑑𝑜𝑚(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 random variable with domain {𝑡𝑟𝑢𝑒, 𝑓𝑎𝑙𝑠𝑒}, which has value true if it is raining at a particular time.

The assignment {Class_time=11,Height_joe=165,𝑅𝑎𝑖𝑛𝑖𝑛𝑔=𝑓𝑎𝑙𝑠𝑒} specifies that the class starts at 11, Joe is 165cm tall and it is not raining.

Example 4.2.

In the electrical environment of Figure 1.8, 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:

  • S1_𝑝𝑜𝑠 is a binary variable denoting the position of switch s1 with domain {𝑢𝑝, 𝑑𝑜𝑤𝑛}, where S1_𝑝𝑜𝑠=𝑢𝑝 means switch s1 is up, and S1_𝑝𝑜𝑠=𝑑𝑜𝑤𝑛 means switch s1 is down.

  • S1_𝑠𝑡 is a discrete variable denoting the status of switch s1 with domain {𝑜𝑘, upside_down, 𝑠ℎ𝑜𝑟𝑡, 𝑖𝑛𝑡𝑒𝑟𝑚𝑖𝑡𝑡𝑒𝑛𝑡, 𝑏𝑟𝑜𝑘𝑒𝑛}, where S1_𝑠𝑡=𝑜𝑘 means switch s1 is working normally, S1_𝑠𝑡=upside_down means it is installed upside down, S1_𝑠𝑡=𝑠ℎ𝑜𝑟𝑡 means it is shorted and it allows electricity to flow whether it is up or down, S1_𝑠𝑡=𝑖𝑛𝑡𝑒𝑟𝑚𝑖𝑡𝑡𝑒𝑛𝑡 means it is working intermittently, and S1_𝑠𝑡=𝑏𝑟𝑜𝑘𝑒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_w1 is a real-valued variable denoting the current, in amps, flowing through wire w1. Current_w1=1.3 means there are 1.3 amps flowing through wire w1. We also allow inequalities between variables and constants; for example, Current_w11.3 is true when there are at least 1.3 amps flowing through wire w1.

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

Example 4.3.

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 used. For example, one_across could be a variable with domain {’ant’, ’big’, ’bus’, ’car’, ’has’}. 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. For example, the top-left square could be a variable p00 with domain {a,,z}. A possible world corresponds to an assignment of 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 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.

An alternative representation may have the days as the variables, with domains the set of possible activity–location pairs.

The number of worlds 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 {𝑡𝑟𝑢𝑒,𝑓𝑎𝑙𝑠𝑒}, there are six possible worlds, which we name w0,,w5 as follows

  • w0={A=0,B=𝑡𝑟𝑢𝑒}

  • w1={A=0,B=𝑓𝑎𝑙𝑠𝑒}

  • w2={A=1,B=𝑡𝑟𝑢𝑒}

  • w3={A=1,B=𝑓𝑎𝑙𝑠𝑒}

  • w4={A=2,B=𝑡𝑟𝑢𝑒}

  • w5={A=2,B=𝑓𝑎𝑙𝑠𝑒}

If there are n variables, each with domain size d, there are dn possible worlds.

One main advantage of reasoning in terms of variables is the computational savings. Many worlds can be described by a few variables:

  • 10 binary variables can describe 210=1,024 worlds

  • 20 binary variables can describe 220=1,048,576 worlds

  • 30 binary variables can describe 230=1,073,741,824 worlds

  • 100 binary variables can describe 2100=1,267,650,600,228,229,401,496, 703,205,376 worlds.

Reasoning in terms of thirty variables may be easier than reasoning in terms of more than a billion worlds. One hundred variables is not that many, but reasoning in terms of more than 2100 worlds explicitly is not possible. Many real-world problems have thousands, if not millions, of variables.