6 Planning with Certainty

6.1 Representing States, Actions, and Goals

To reason about what to do, assume an agent has goals, a model of the environment, and a model of its actions.

A deterministic action is a partial function from states to states. It is partial because not every action is able to be carried out in every state. For example, a robot cannot pick up a particular object if it is nowhere near the object. The precondition of an action specifies when the action can be carried out. The effect of an action specifies the resulting state.

Example 6.1.

Consider a delivery robot with mail and coffee to deliver. Assume a simplified problem domain with four locations as shown in Figure 6.1.

Features to describe states RLoc – Rob’s location RHC – Rob has coffee SWC – Sam wants coffee MW – Mail is waiting RHM – Rob has mail Actions mc – move clockwise mcc – move counterclockwise puc – pickup coffee dc – deliver coffee pum – pickup mail dm – deliver mail
Figure 6.1: The delivery robot domain

The robot, called Rob, can buy coffee at the coffee shop, pick up mail in the mail room, move, and deliver coffee and/or mail. Delivering the coffee to Sam’s office will stop Sam from wanting coffee. There could be mail waiting at the mail room to be delivered to Sam’s office. This domain is quite simple, yet it is rich enough to demonstrate many of the issues in representing actions and in planning.

The state is described in terms of the following features.

  • RLoc, the robot’s location, which is one of the coffee shop (cs), Sam’s office (off), the mail room (mr), or the laboratory (lab).

  • RHC, whether the robot has coffee. The atom rhc means Rob has coffee (i.e., RHC=true) and ¬rhc means Rob does not have coffee (i.e., RHC=false).

  • SWC, whether Sam wants coffee. The atom swc means Sam wants coffee and ¬swc means Sam does not want coffee.

  • MW, whether mail is waiting at the mail room. The atom mw means there is mail waiting and ¬mw means there is no mail waiting.

  • RHM, whether the robot is carrying the mail. The atom rhm means Rob has mail, and ¬rhm means Rob does not have mail.

Rob has six actions.

  • Rob can move clockwise (mc).

  • Rob can move counterclockwise (mcc).

  • Rob can pick up coffee if Rob is at the coffee shop. Let puc mean that Rob picks up coffee. The precondition of puc is ¬rhcRLoc=cs; that is, Rob can pick up coffee in any state where its location is cs, and it is not already holding coffee. The effect of this action is to make RHC true. It does not affect the other features.

  • Rob can deliver coffee if Rob is carrying coffee and is at Sam’s office. Let dc mean that Rob delivers coffee. The precondition of dc is rhcRLoc=off. The effect of this action is to make RHC false and make SWC false. Note that Rob can deliver coffee whether or not Sam wants it.

  • Rob can pick up mail if Rob is at the mail room and there is mail waiting there. Let pum mean Rob picks up the mail.

  • Rob can deliver mail if Rob is carrying mail and at Sam’s office. Let dm mean Rob delivers mail.

Assume that it is only possible for Rob to do one action at a time. We assume that a lower-level controller is able to implement these actions, as described in Chapter 2.