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

8.1.1 Explicit State-Space Representation

One possible representation of the effect and precondition of actions is to explicitly enumerate the states and, for each state, specify the actions that are possible in that state and, for each state-action pair, specify the state that results from carrying out the action in that state. This would require a table such as the following:

State Action Resulting State
s7 act47 s94
s7 act14 s83
s94 act5 s33
... ... ...

The first tuple in this relation specifies that it is possible to carry out action act47 in state s7 and, if it were to be carried out in state s7, the resulting state would be s94.

Thus, this is the explicit representation of the actions in terms of a graph. This is called a state-space graph. This is the sort of graph that was used in Chapter 3.

Example 8.2: In Example 8.1, the states are the quintuples specifying the robot's location, whether the robot has coffee, whether Sam wants coffee, whether mail is waiting, and whether the robot is carrying the mail. For example, the tuple
⟨lab, ¬rhc,swc, ¬mw,rhm⟩

represents the state where Rob is at the Lab, does not have coffee, Sam wants coffee, there is no mail waiting, and Rob has mail.

⟨lab,rhc,swc,mw, ¬rhm⟩

represents the state where Rob is at the Lab, carrying coffee, Sam wants coffee, there is mail waiting, and Rob is not holding any mail.

In this example, there are 4×2×2×2×2=64 states. Intuitively, all of them are possible, even if you would not expect that some of them would be reached by an intelligent robot.

There are six actions, not all of which are applicable in each state.

The actions can be defined in terms of the state transitions:

State Action Resulting State
⟨lab, ¬rhc,swc, ¬mw,rhm⟩ mc ⟨mr, ¬rhc,swc, ¬mw,rhm⟩
⟨lab, ¬rhc,swc, ¬mw,rhm⟩ mcc ⟨off, ¬rhc,swc, ¬mw,rhm⟩
⟨off, ¬rhc,swc, ¬mw,rhm⟩ dm ⟨off, ¬rhc,swc, ¬mw, ¬rhm⟩
⟨off, ¬rhc,swc, ¬mw,rhm⟩ mcc ⟨cs, ¬rhc,swc, ¬mw,rhm⟩
⟨off, ¬rhc,swc, ¬mw,rhm⟩ mc ⟨lab, ¬rhc,swc, ¬mw,rhm⟩
.........

This table shows the transitions for two of the states. The complete problem representation includes the transitions for the other 62 states.

This is not a good representation for three main reasons:

  • There are usually too many states to represent, to acquire, and to reason with.
  • Small changes to the model mean a large change to the representation. Modeling another feature means changing the whole representation. For example, to model the level of power in the robot, so that it can recharge itself in the Lab, every state has to change.
  • There is also usually much more structure and regularity in the effects of actions. This structure can make the specification of the preconditions and the effects of actions, and reasoning about them, more compact and efficient.

An alternative is to model the effects of actions in terms of how the actions affect the features.