foundations of computational agents
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, $\text{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 $\colorbox[rgb]{1,1,0.701960784313725}{$e$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$n$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$u$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$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 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 $\colorbox[rgb]{1,1,0.701960784313725}{$S$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$a$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$m$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$s$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$H$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$e$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$i$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$g$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$h$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$t$}$, to the computer, is just a sequence of bits. It has no relationship to $\colorbox[rgb]{1,1,0.701960784313725}{$S$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$a$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$m$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$s$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$W$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$e$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$i$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$g$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$h$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$t$}$ or $\colorbox[rgb]{1,1,0.701960784313725}{$A$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$l$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$s$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$H$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$e$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$i$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$g$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$h$}\colorbox[rgb]{1,1,0.701960784313725}{$$}\colorbox[rgb]{1,1,0.701960784313725}{$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 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 $\{\text{true}$, $\text{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 $\{{X}_{1},{X}_{2},\mathrm{\dots},{X}_{k}\}$ as $\{{X}_{1}={v}_{1},{X}_{2}={v}_{2},\mathrm{\dots},{X}_{k}={v}_{k}\}$, where ${v}_{i}$ is in $\text{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 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 $\{{X}_{1}={v}_{1},{X}_{2}={v}_{2},\mathrm{\dots},{X}_{k}={v}_{k}\}$, we say that variable ${X}_{i}$ has value ${v}_{i}$ in world $w$.
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:
$${\text{\mathit{d}\mathit{o}\mathit{m}}}{}{(}{\mathit{\text{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 ${\mathrm{\{}}{\text{\mathit{t}\mathit{r}\mathit{u}\mathit{e}}}$, ${\text{\mathit{f}\mathit{a}\mathit{l}\mathit{s}\mathit{e}}}{\mathrm{\}}}$, which has value true if it is raining at a particular time.
The assignment ${\mathrm{\{}}{\mathit{\text{Class\_time}}}{\mathrm{=}}{\mathrm{11}}{\mathrm{,}}{\mathit{\text{Height\_joe}}}{\mathrm{=}}{\mathrm{165}}{\mathrm{,}}{\text{\mathit{R}\mathit{a}\mathit{i}\mathit{n}\mathit{i}\mathit{n}\mathit{g}}}{\mathrm{=}}{\text{\mathit{f}\mathit{a}\mathit{l}\mathit{s}\mathit{e}}}{\mathrm{\}}}$ specifies that the class starts at 11, Joe is 165cm tall and it is not raining.
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:
${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{p}\mathit{o}\mathit{s}}}$ is a binary variable denoting the position of switch ${{s}}_{{1}}$ with domain ${\{}{\text{\mathit{u}\mathit{p}}}$, ${\text{\mathit{d}\mathit{o}\mathit{w}\mathit{n}}}{\}}$, where ${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{p}\mathit{o}\mathit{s}}}{=}{\text{\mathit{u}\mathit{p}}}$ means switch ${{s}}_{{1}}$ is up, and ${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{p}\mathit{o}\mathit{s}}}{=}{\text{\mathit{d}\mathit{o}\mathit{w}\mathit{n}}}$ means switch ${{s}}_{{1}}$ is down.
${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{s}\mathit{t}}}$ is a discrete variable denoting the status of switch ${{s}}_{{1}}$ with domain ${\{}{\text{\mathit{o}\mathit{k}}}{,}$ ${\mathit{\text{upside\_down}}}{,}$ ${\text{\mathit{s}\u210e\mathit{o}\mathit{r}\mathit{t}}}{,}$ ${\text{\mathit{i}\mathit{n}\mathit{t}\mathit{e}\mathit{r}\mathit{m}\mathit{i}\mathit{t}\mathit{t}\mathit{e}\mathit{n}\mathit{t}}}{,}$ ${\text{\mathit{b}\mathit{r}\mathit{o}\mathit{k}\mathit{e}\mathit{n}}}{\}}$, where ${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{s}\mathit{t}}}{=}{\text{\mathit{o}\mathit{k}}}$ means switch ${{s}}_{{1}}$ is working normally, ${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{s}\mathit{t}}}{=}{\mathit{\text{upside\_down}}}$ means it is installed upside down, ${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{s}\mathit{t}}}{=}{\text{\mathit{s}\u210e\mathit{o}\mathit{r}\mathit{t}}}$ means it is shorted and it allows electricity to flow whether it is up or down, ${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{s}\mathit{t}}}{=}{\text{\mathit{i}\mathit{n}\mathit{t}\mathit{e}\mathit{r}\mathit{m}\mathit{i}\mathit{t}\mathit{t}\mathit{e}\mathit{n}\mathit{t}}}$ means it is working intermittently, and ${{S}}_{{1}}{}{\mathrm{\_}}{}{\text{\mathit{s}\mathit{t}}}{=}{\text{\mathit{b}\mathit{r}\mathit{o}\mathit{k}\mathit{e}}}{}{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.
${{\mathit{\text{Current\_w}}}}_{{1}}$ is a real-valued variable denoting the current, in amps, flowing through wire ${{w}}_{{1}}$. ${{\mathit{\text{Current\_w}}}}_{{1}}{=}{1.3}$ means there are ${1.3}$ amps flowing through wire ${{w}}_{{1}}$. We also allow inequalities between variables and constants; for example, ${{\mathit{\text{Current\_w}}}}_{{1}}{\ge}{1.3}$ is true when there are at least ${1.3}$ amps flowing through wire ${{w}}_{{1}}$.
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.
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 ${p}{}{00}$ with domain ${\{}{a}{,}{\mathrm{\dots}}{,}{z}{\}}$. A possible world corresponds to an assignment of a letter to each square.
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.
If there are two variables, ${A}$ with domain ${\mathrm{\{}}{\mathrm{0}}{\mathrm{,}}{\mathrm{1}}{\mathrm{,}}{\mathrm{2}}{\mathrm{\}}}$ and ${B}$ with domain ${\mathrm{\{}}{\text{\mathit{t}\mathit{r}\mathit{u}\mathit{e}}}{\mathrm{,}}{\text{\mathit{f}\mathit{a}\mathit{l}\mathit{s}\mathit{e}}}{\mathrm{\}}}$, there are six possible worlds, which we name ${{w}}_{{\mathrm{0}}}{\mathrm{,}}{\mathrm{\dots}}{\mathrm{,}}{{w}}_{{\mathrm{5}}}$ as follows
${{w}}_{{0}}{=}{\{}{A}{=}{0}{,}{B}{=}{\text{\mathit{t}\mathit{r}\mathit{u}\mathit{e}}}{\}}$
${{w}}_{{1}}{=}{\{}{A}{=}{0}{,}{B}{=}{\text{\mathit{f}\mathit{a}\mathit{l}\mathit{s}\mathit{e}}}{\}}$
${{w}}_{{2}}{=}{\{}{A}{=}{1}{,}{B}{=}{\text{\mathit{t}\mathit{r}\mathit{u}\mathit{e}}}{\}}$
${{w}}_{{3}}{=}{\{}{A}{=}{1}{,}{B}{=}{\text{\mathit{f}\mathit{a}\mathit{l}\mathit{s}\mathit{e}}}{\}}$
${{w}}_{{4}}{=}{\{}{A}{=}{2}{,}{B}{=}{\text{\mathit{t}\mathit{r}\mathit{u}\mathit{e}}}{\}}$
${{w}}_{{5}}{=}{\{}{A}{=}{2}{,}{B}{=}{\text{\mathit{f}\mathit{a}\mathit{l}\mathit{s}\mathit{e}}}{\}}$
If there are $n$ variables, each with domain size $d$, there are ${d}^{n}$ 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 ${2}^{10}=1,024$ worlds
20 binary variables can describe ${2}^{20}=1,048,576$ worlds
30 binary variables can describe ${2}^{30}=1,073,741,824$ worlds
100 binary variables can describe ${2}^{100}=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 ${2}^{100}$ worlds explicitly is not possible. Many real-world problems have thousands, if not millions, of variables.