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.