1.5.2 Representation Scheme
The representation scheme dimension concerns how the world is described.
The different ways the world
could be to affect what an agent should do are called states. We can factor the state of the world into the
agent's internal state (its belief state) and the
environment state.
At the simplest level, an agent can reason explicitly in terms of
individually identified states.
Example 1.4:
A thermostat for a heater
may have two belief states: off and heating. The environment may have three
states: cold, comfortable, and hot. There are thus six states corresponding
to the different combinations of belief and environment states. These
states may not fully describe the world, but they are adequate to describe
what a thermostat should do. The thermostat should move to, or stay in,
heating if the environment is cold and move to, or stay in,
off if the environment is hot. If the
environment is comfortable, the thermostat should stay in its
current state. The agent heats in the
heating state and does not heat in the off state.
Instead of enumerating states, it is often easier to reason in terms
of the state's features or propositions that are true or false of the
state.
A state may be described in terms of
features, where a feature has a value in each state (see Section 4.1).
Example 1.5:
An agent that has to look after a house may have to reason about
whether light bulbs are broken. It may
have features for the position of each switch, the status of each
switch (whether it is working okay, whether it is shorted, or whether
it is broken), and whether each
light works. The feature
pos_s2 may be a feature that
has value
up when switch
s2 is up and has value
down when the
switch is down. The state of the house's lighting may be
described in terms of values for each of these features.
A proposition is a Boolean feature, which
means that its value is either true or false. Thirty propositions can encode 230=
1,073,741,824 states. It may be easier to specify and reason with the
thirty propositions than with more than a billion states. Moreover, having
a compact representation of the states indicates understanding, because
it means that an agent has captured some regularities in the domain.
Example 1.6:
Consider an agent that has to recognize letters of the
alphabet. Suppose the agent observes a binary
image, a 30×30 grid of pixels, where each of the 900
grid points is either on or off (i.e., it is not using any color or
gray scale information). The action is to determine which of the
letters {a,...,z} is drawn in the image. There are 2900
different states of the image, and so 262900 different
functions from the image state into the characters
{a,...,z}. We cannot even represent such functions in terms
of the state space. Instead, we define features of the image,
such as line segments, and define
the function from images to characters in terms of these features.
When describing a complex world, the features can depend on relations
and individuals. A relation on a single individual is a property. There is a feature for each possible relationship
among the individuals.
Example 1.7:
The agent that looks after a house in
Example 1.5
could have the lights and switches as individuals, and
relations
position and
connected_to. Instead of the feature
position_s1=up, it could use the relation
position(s1,up). This
relation enables the agent to reason about all switches or for an agent to have knowledge
about switches that can be used when the agent encounters a switch.
Example 1.8:
If an agent is enrolling
students in courses, there could be a feature that gives the grade of a
student in a course, for every student-course
pair where the student took the course. There would be a passed feature for every student-course pair, which
depends on the grade feature for that pair. It may be easier to
reason in terms of individual students, courses and grades, and the relations
grade and passed. By defining how passed depends on grade
once, the agent can apply the definition for each student and course. Moreover, this can be
done before the agent knows of any of the individuals and so before it knows
any of the features.
Thus, instead of dealing with features or propositions, it is often
more convenient to have relational descriptions in terms of individuals and
relations among them. For example, one binary relation and 100 individuals
can represent 1002=10,000 propositions and 210000 states. By
reasoning in terms of relations and individuals, an agent can specify reason about whole classes of individuals without ever
enumerating the features or propositions, let alone the states. An
agent may have to reason about infinite sets of individuals, such as the set of all numbers or the set of all sentences. To reason
about an unbounded or infinite number of individuals, an agent cannot reason in terms of
states or features; it must reason at the relational level.
In the representation scheme dimension, the agent reasons in terms of
- states,
- features, or
- relational descriptions, in terms of individuals and relations.
Some of the frameworks will be developed in terms of states, some in
terms of features and some relationally.
Reasoning in terms of states is introduced in
Chapter 3. Reasoning in terms of features is
introduced in Chapter 4. We
consider relational reasoning starting in
Chapter 12.
