6.4 Planning as a CSP

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

6.4.1 Action Features

So far we have assumed that actions are atomic and that an agent can only do one action at any time. For the CSP representation, it can be useful to describe the actions in terms of features – to have a factored representation of actions as well as a factored representation of states. The features representing actions are called action features and the features representing states are called state features. The action features can be considered as actions in themselves that are carried out in the same time step.

In this case, there can be an extra set of constraints called action constraints to specify which action features cannot co-occur. These are sometimes called mutual exclusion or mutex constraints.

Example 6.15.

Another way to model the actions of Example 6.1 is that, at each step, Rob gets to choose

  • •

    whether it will pick up coffee. Let P⁢U⁢C be a Boolean variable that is true when Rob picks up coffee.

  • •

    whether it will deliver coffee. Let D⁢e⁢l⁢C be a Boolean variable that is true when Rob delivers coffee.

  • •

    whether it will pick up mail. Let P⁢U⁢M be a Boolean variable that is true when Rob picks up mail.

  • •

    whether it will deliver mail. Let D⁢e⁢l⁢M be a Boolean variable that is true when Rob delivers mail.

  • •

    whether it moves. Let M⁢o⁢v⁢e be a variable with domain {m⁢c,m⁢c⁢c,n⁢m} that specifies whether Rob moves clockwise, moves counterclockwise, or does not move (n⁢m means “not move”).

Thus the agent can be seen as doing more than one action in a single stage. For some of the actions at the same stage, the robot can do them in any order, such as delivering coffee and delivering mail. Some of the actions at the same stage need to be carried out in a particular order, for example, the agent must move after the other actions.

R⁢L⁢o⁢ci – Rob’s location R⁢H⁢Ci – Rob has coffee S⁢W⁢Ci – Sam wants coffee M⁢Wi – Mail is waiting R⁢H⁢Mi – Rob has mail M⁢o⁢v⁢ei – Rob’s move action P⁢U⁢Ci – Rob picks up coffee D⁢e⁢l⁢C – Rob delivers coffee P⁢U⁢Mi – Rob picks up mail D⁢e⁢l⁢Mi – Rob delivers mail
Figure 6.5: The delivery robot CSP planner with factored actions
Example 6.16.

Consider finding a plan to get Sam coffee, where initially, Sam wants coffee but the robot does not have coffee. The initial state can be represented as two domain constraints: S⁢W⁢C0=t⁢r⁢u⁢e and on R⁢H⁢C0=f⁢a⁢l⁢s⁢e. The goal is that Sam no longer wants coffee, S⁢W⁢Ck=f⁢a⁢l⁢s⁢e.

With a planning horizon of 2, the CSP is shown in Figure 6.5. The goal is represented as the domain constraint S⁢W⁢C2=f⁢a⁢l⁢s⁢e, there is a solution R⁢L⁢o⁢c0=c⁢s (the robot has to start in the coffee shop), P⁢U⁢C0=t⁢r⁢u⁢e (the robot has to pick up coffee initially), M⁢o⁢v⁢e0=m⁢c (the robot has to move to the office), and D⁢C1=t⁢r⁢u⁢e (the robot has to deliver coffee at time 1).

Note that in the representation without factored actions, the problem cannot be solved with a horizon of 2; it requires a horizon of 3, as there are no concurrent actions.