6.4 Planning as a CSP

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 PUC be a Boolean variable that is true when Rob picks up coffee.

  • whether it will deliver coffee. Let DelC be a Boolean variable that is true when Rob delivers coffee.

  • whether it will pick up mail. Let PUM be a Boolean variable that is true when Rob picks up mail.

  • whether it will deliver mail. Let DelM be a Boolean variable that is true when Rob delivers mail.

  • whether it moves. Let Move be a variable with domain {mc,mcc,nm} that specifies whether Rob moves clockwise, moves counterclockwise, or does not move (nm 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.

RLoci – Rob’s location RHCi – Rob has coffee SWCi – Sam wants coffee MWi – Mail is waiting RHMi – Rob has mail Movei – Rob’s move action PUCi – Rob picks up coffee DelC – Rob delivers coffee PUMi – Rob picks up mail DelMi – 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: SWC0=true and on RHC0=false. The goal is that Sam no longer wants coffee, SWCk=false.

With a planning horizon of 2, the CSP is shown in Figure 6.5. The goal is represented as the domain constraint SWC2=false, there is a solution RLoc0=cs (the robot has to start in the coffee shop), PUC0=true (the robot has to pick up coffee initially), Move0=mc (the robot has to move to the office), and DC1=true (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.