1.5 Agent Design Space

1.5.3 Representation

The representation dimension concerns how the world is described.

The different ways the world could be are called states. A state of the world specifies 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.5.

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 thermostat agent keeps the heater on in the heating state and keeps the heater off in the off state.

Instead of enumerating states, it is often easier to reason in terms of features of the state 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.6.

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 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛_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. These features depend on each other, but not in arbitrarily complex ways; for example, whether a light is on may just depend on whether it is okay, whether the switch is turned on, and whether there is electricity.

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

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 black or white. The action is to determine which of the letters {a,,z} is drawn in the image. There are 2900 different possible 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, handwriting recognition systems define features of the image, such as line segments, and define the function from images to characters in terms of these features. Modern implementations learn the features that are useful.

When describing a complex world, the features can depend on relations and individuals. What we call an individual could also be called a thing, an object or an entity. A relation on a single individual is a property. There is a feature for each possible relationship among the individuals.

Example 1.8.

The agent that looks after a house in Example 1.6 could have the lights and switches as individuals, and relations position and connected_to. Instead of the feature 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛_s2=𝑢𝑝, it could use the relation 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛(s2,𝑢𝑝). This relation enables the agent to reason about all switches or for an agent to have general knowledge about switches that can be used when the agent encounters a switch.

Example 1.9.

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.

The two-argument relation passed, with 1000 students and 100 courses can represent 1000*100=100000 propositions and so 2100000 states.

By reasoning in terms of relations and individuals, an agent can 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 dimension, the agent reasons in terms of

  • states

  • features, or

  • individuals and relations (often called relational representations).

Some of the frameworks will be developed in terms of states, some in terms of features and some in terms of individuals and relations.

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