Example

 

We now present a detailed example of how PRODIGY4.0, ROGUE and Xavier interact in a two goal problem: (has-item mitchell delivermail) and (has-item jhm deliverfax). The second (higher priority) goal arrives while ROGUE is executing the first action for the first goal.

Figure 7 shows the planning graph generated by PRODIGY4.0. We describe below the details of how it is generated. This example shows:

• how PRODIGY4.0 expands tasks,
• how search control rules affect PRODIGY4.0's selections, and
• how an asynchronous task request affects the plan.

 

Figure 7: Plan for a two-task problem; goal nodes are in ovals, required actions are in rectangles.

We assume for the purposes of this example that no failures occur during execution. The example is perhaps overly detailed for a reader familiar with back-chaining planners; those readers could skip to the next section without loss of continuity.

We show the algorithmic sequence of steps of PRODIGY4.0. At each step, we show the lists of pending goals, PG, applicable operators, Applicable-Ops, and executed operators, Executed-Ops.

1. Request (has-item mitchell delivermail) arrives. ROGUE adds this goal to PRODIGY4.0's pending goals list, PG, and adds the following knowledge to PRODIGY4.0's state information:

       (needs-item mitchell delivermail)
       (pickup-loc mitchell r-5303)
       (deliver-loc mitchell r-5313)
   

       PG   is (has-item mitchell delivermail)
       Applicable-Ops is nil 
       Executed-Ops is nil
   
   

2.   PRODIGY4.0 fires its goal-selection search control rules, which selects this goal (node 5 of Figure 7) as the highest priority goal (since it is the only choice). PRODIGY4.0 examines this goal to find an appropriate operator. It finds (DELIVER-ITEM <user> <room> <object>), and instantiates the variables: <user> := mitchell, <room> := r-5313 and <object> := delivermail, yielding the instantiated operator shown in node 7 of Figure 7. Using means-ends analysis, PRODIGY4.0 identifies two preconditions not satisfied in the state: (robot-has-item mitchell delivermail) and (robot-in-room r-5313). PRODIGY4.0 adds these preconditions to the pending goals list.

       PG  is (and (robot-has-item mitchell delivermail) (robot-in-room r-5313))
       Applicable-Ops  is nil 
       Executed-Ops is nil
   
   

3.   PRODIGY4.0 continues expanding the plan for this task, yielding nodes 5 through 16. At this moment, two operators in the plan have all their preconditions met in the current state.

       PG is nil
       Applicable-Ops is (and (GOTO-DELIVER-LOC mitchell r-5313) (GOTO-PICKUP-LOC mitchell r-5303))
       Executed-Ops is nil
   
   

4. PRODIGY4.0 examines the set of Applicable-Ops, and based on ordering constraints (goal clobbering), selects (GOTO-PICKUP-LOC mitchell r-5303) to apply. ROGUE takes the applied operator, (GOTO-PICKUP-LOC mitchell r-5303) (node 17), and sends it to the robot for execution. (It does not need to verify preconditions in the real world since none can be changed by exogenous events.)

       PG  is nil
       Applicable-Ops is (GOTO-DELIVER-LOC mitchell r-5313)
       Executed-Ops is nil
   
   

5. Request (has-item jhm deliverfax) arrives. ROGUE adds this goal to PG.

   ROGUE does not interfere with the currently executing action, namely (GOTO-PICKUP-LOC mitchell r-5303). Goodwin [1994] discusses methods to decide when to interfere.

       PG  is (has-item jhm deliverfax)
       Applicable-Opsis (GOTO-DELIVER-LOC mitchell r-5313)
       Executed-Ops is nil
   
   

6.   The navigation module finally indicates completion of the action. ROGUE verifies the outcome (post-conditions) of the action, i.e., that it has arrived at the location r-5313 (see Section 3 for a description). Now the action (ACQUIRE-ITEM r-5303 mitchell delivermail) is applicable.

       PG  is (has-item jhm deliverfax)
       Applicable-Ops is (and (GOTO-DELIVER-LOC mitchell r-5313) (ACQUIRE-ITEM r-5303 mitchell delivermail))
       Executed-Ops is (GOTO-PICKUP-LOC mitchell r-5303)
   
   

7. PRODIGY4.0 fires ROGUE's search control rules, which select the new goal (since it is higher priority than the current task) (node 18). It expands the plan as above, except that instead of selecting a new operator to achieve the goal (robot-in-room r-5313), it notices that the operator (GOTO-DELIVER-LOC mitchell r-5313) has the same effect, and does not redundantly add a new operator.

       PG  is nil
       Applicable-Ops  is (and (GOTO-DELIVER-LOC mitchell r-5313) 
                            (ACQUIRE-ITEM r-5303 mitchell delivermail)
                            (GOTO-PICKUP-LOC jhm r-5311))
       Executed-Ops is (GOTO-PICKUP-LOC mitchell r-5303)
   
   

8. PRODIGY4.0 selects (ACQUIRE-ITEM r-5303 mitchell delivermail) to apply (node 27); ROGUE verifies its preconditions and then sends it to the robot for execution. When the action is complete, ROGUE verifies the postconditions (i.e. that it now has mitchell's mail).

       PG   is nil
       Applicable-Ops  is (and (GOTO-DELIVER-LOC mitchell r-5313) (GOTO-PICKUP-LOC jhm r-5311))
       Executed-Ops is (GOTO-PICKUP-LOC mitchell r-5303) 
                         		 (ACQUIRE-ITEM r-5303 mitchell deliver-mail)
   
   

9.   The execution constraint control rule now selects (GOTO-PICKUP-LOC jhm r-5311) as the next applicable operator (node 28). ROGUE sends it to Xavier for execution and monitors its outcome.

       PG   is nil
       Applicable-Ops  is (and (GOTO-DELIVER-LOC mitchell r-5313) (ACQUIRE-ITEM r-5311 jhm deliverfax))
       Executed-Ops is (GOTO-PICKUP-LOC mitchell r-5303) 
                    (ACQUIRE-ITEM r-5303 mitchell deliver-mail)
                    (GOTO-PICKUP-LOC jhm r-5311)
   
   

10. ROGUE then acquires the fax.
11. ROGUE then goes to room 5313.
12. ROGUE delivers both items.

The final execution order described in this example is shown in Figure 8. This example illustrates the asynchronous handling of goals in ROGUE.

 
Figure 8: Final execution sequence.