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