Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

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.
  • S1_pos may be a discrete binary variable denoting the position of switch s1 with domain {up, down}, where S1_pos=up means switch s1 is up, and S1_pos=down means switch s1 is down.
  • S1_st may be a variable denoting the status of switch s1 with domain {ok, upside_down, short, intermittent, broken}, where S1_st=ok means switch s1 is working normally, S1_st=upside_down means switch s1 is installed upside down, S1_st=short means switch s1 is shorted and acting as a wire, S1_st=intermittent means switch S1 is working intermittently, and S1_st=broken means switch s1 is broken and does not allow electricity to flow.
  • Number_of_broken_switches may be an integer-valued variable denoting the number of switches that are broken.
  • Current_w1 may be 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 as Boolean features; for example, Current_w1 ≥ 1.3 is true when there are at least 1.3 amps flowing through wire w1.
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:
  1. 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.
  2. 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 w0,..., w5. One possible arrangement of variables and possible worlds is
  • w0: A=0 and B=true
  • w1: A=0 and B=false
  • w2: A=1 and B=true
  • w3: A=1 and B=false
  • w4: A=2 and B=true
  • w5: A=2 and 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.