Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

4.1 Features and States

For any practical problem, an agent cannot reason in terms of states; there are simply too many of them. Moreover, most problems do not come with an explicit list of states; the states are typically described implicitly in terms of features. When describing a real state space, it is usually more natural to describe the features that make up the state rather than explicitly enumerating the states.

The definitions of states and features are intertwined; we can describe either in terms of the other.

  • States can be defined in terms of features: features can be primitive and a state corresponds to an assignment of a value to each feature.
  • Features can be defined in terms of states: the states can be primitive and a feature is a function of the states. Given a state, the function returns the value of the feature on that state.

Each feature has a domain that is the set of values that it can take on. The domain of the feature is the range of the function on the states.

Example 4.1: In the electrical environment of Figure 1.8, there may be a feature for the position of each switch that specifies whether the switch is up or down. There may be a feature for each light that specifies whether the light is lit or not. There may be a feature for each component specifying whether it is working properly or if it is broken. A state consists of the position of every switch, the status of every device, and so on.

If the features are primitive, a state is an assignment of a value to each feature. For example, a state may be described as switch 1 is up, switch 2 is down, fuse 1 is okay, wire 3 is broken, and so on.

If the states are primitive, the functions may be, for example, the position of switch 1. The position is a function of the state, and it may be up in some states and down in other states.

One main advantage of reasoning in terms of features is the computational savings. For a binary feature the domain has two values. Many states can be described by a few features:

  • 10 binary features can describe 210=1,024 states.
  • 20 binary features can describe 220=1,048,576 states.
  • 30 binary features can describe 230=1,073,741,824 states.
  • 100 binary features can describe 2100=1,267,650,600,228,229,401,496,703,205,376 states.

Reasoning in terms of thirty features may be easier than reasoning in terms of more than a billion states. One hundred features is not that many, but reasoning in terms of more than 2100 states explicitly is not possible. Many problems have thousands if not millions of features.

Typically the features are not independent, in that there may be constraints on the values of different features. One problem is to determine what states are possible given the features and the constraints.