Partial Order Planning and Execution 1 Brian C. Williams 16.410/13 October 15 th , 2003Slides with help from: Dan Weld Stuart Russell & Peter Norvig Monitors Autonomous Agents Command dispatch Fault protection Attitude control Mission Goal Scenario Self-commanding Self-diagnosing Self-repairing RECOVERY P L A N N I N G E X E C U T ION Commanded at: ? Mission level Engineering level STRIPS Operator Representation Effects specify how to change the set of propositions. a a north11 W0 W1 ? Initial state: ((block a) (block b) (block c) (on-table a) (on-table b) (clear a) (clear b) (clear c) (arm-empty)) goal (partial state): ((on a b) (on b c))) Available actions Strips operators precond: (and (agent-at 1 1) (agent-facing north)) effect: (and (agent-at 1 2) (not (agent-at 1 1))) North11 (Parameterized) Operator Schemata (:operator pick-up :parameters ((block ?ob1)) :precondition (and (clear ?ob1) (on-table ?ob1) (arm-empty)) :effect (and (not (clear ?ob1)) (not (on-table ?ob1)) (not (arm-empty)) (holding ?ob1))) Instead of defining: pickup-A and pickup-B and … Define a schema: N o te : s tr ip s d o e s n ’ t a l l o w d e r iv e d e f f e c ts ; y o u m u s t b e c o m p le t e ! } ?var denotes a free variable Partial Order Planning – Partial Order Planning Problem Problem Encoding Partial Order Plans Plan Correctness – Partial Order Plan Generation – Plan Execution and Monitoring Example Problem Go(HWS) Go(Home) Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) Have(Milk) Have(Drill) Have(Ban) At(Home) At(HWS) At(SM) Goal: Have(Milk) At(Home) Have(Ban.) Have(Drill) Initial State: At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Operators: Initial And Goal States Encoded As Operators Have(Milk) At(Home) Have(Ban.) Have(Drill) Finish Start At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Why encode as operators? Don’t need to introduce (partial) states as separate objects. Keeps theory minimal. Start Finish Have(Milk) At(Home) Have(Ban.) Have(Drill) Buy(Milk) At(SM), Sells(SM,Milk) Buy(Ban.) At(SM), Sells(SM,Ban.) Buy(Drill) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Partial Order Plan <Actions,Orderings,Links> At(HWS) Go(SM) Go(Home) At(SM) Go(HWS) At(Home) Start Finish Buy(Drill) Buy(Milk) Buy(Ban.) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Ban.) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Partial Order Plan <Actions,Orderings,Links> At(HWS) Go(SM) Go(Home) At(SM) Go(HWS) At(Home) Start Finish Buy(Drill) Buy(Milk) Buy(Ban.) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Ban.) At(HWS) Sells(HWS,Drill) Go(Home) At(HWS) Go(SM) At(SM) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Partial Order Plan <Actions,Orderings,Links> Go(HWS) At(Home) Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Partial Order Plan <Actions,Orderings,Links> Partial Order Planning – Partial Order Planning Problem Problem Encoding Partial Order Plans Plan Correctness – Partial Order Plan Generation – Plan Execution and Monitoring What Constitutes a Correct Plan? Complete Plan – Achieves all Goals Achieves all preconditions … No actions intervenes to undo needed precondition Consistent Plan – There exists an execution sequence that is consistent with the ordering Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Why is an ordering needed? Go(Home) Buy(Milk) Go(SM) At(Home), not At(SM) At(SM) At(SM) At(HWS) At(SM), not At(HWS) Why is an ordering needed? Go(Home) At(Home), not At(SM) At(SM) Buy(Milk) At(SM) Suppose the other order is allowed, what happens? “Threatened Precondition” Go(SM) At(HWS) At(SM), not At(HWS) Why is an ordering needed? Go(Home) At(SM) Buy(Milk) At(SM) Suppose the other order is allowed, what happens? Link indicates protected time interval for the precondition. Go(SM) At(HWS) At(SM), not At(HWS) At(Home), not At(SM) The ordering resolves the threat. Go(Home) Buy(Milk) At(SM) At(SM) Go(SM) At(HWS) At(SM), not At(HWS) At(Home), not At(SM) Why is an ordering needed? Solution: A Complete and Consistent Plan Complete Plan Consistent Plan IFF every precondition of every step is achieved A step’s precondition is achieved iff its the effect of some preceding step, no possibly intervening step can undo it. IFF there is no contradiction in the ordering constraint i.e., never s i < s j and s j < s i . the plan graph is loop free Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Partial Order Planning – Partial Order Planning Problem – Partial Order Plan Generation Derivation from Completeness and Consistency Backward Chaining Threat Resolution The POP algorithm – Plan Execution and Monitoring Partial Order Planning Algorithm The algorithm falls out of Consistency and Completeness Completeness: Must achieve all preconditions :Backward chain from goals to initial state by inserting actions and causal links. Must avoid intervening actions that threaten :After each action is inserted, search for any action that threatens its effects, and impose ordering to resolve. Consistent: Ordering must be consistent :After each causal link and ordering is inserted, check for loops. Partial Order Planning – Partial Order Planning Problem – Partial Order Plan Generation Derivation from Completeness and Consistency Backward Chaining Threat Resolution The POP algorithm – Plan Execution and Monitoring Start Finish Have(Drill) Have(Milk) Have(Ban.) at(Home) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Start Finish Have(Drill) Have(Milk) Have(Ban.) at(Home) Buy(Drill) At(HWS) Sells(HWS,Drill) Buy(Ban.) At(SM), Sells(SM,Ban.) Buy(Milk) At(SM), Sells(SM,Milk) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Start Finish Buy(Drill) Buy(Milk) Buy(Ban.) Have(Drill) Have(Milk) Have(Ban.) at(Home) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Ban.)At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Start Finish Buy(Drill) Buy(Milk) Buy(Ban.) Have(Drill) Have(Milk) Have(Ban.) at(Home) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Ban.)At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Go(HWS) At(x) Go(SM) At(x) Partial Order Planning – Partial Order Planning Problem – Partial Order Plan Generation Derivation from Completeness and Consistency Backward Chaining Threat Resolution The POP algorithm – Plan Execution and Monitoring Go(Home) At(SM) Buy(Milk) At(SM) Go(SM) At(HWS) At(SM), not At(HWS) At(Home), not At(SM) To remove threats… Go(Home) Buy(Milk) At(SM) At(SM) Go(SM) At(HWS) At(SM), not At(HWS) At(Home), not At(SM) To remove threats… promote the threat or… But only allow demotion/promotion if schedulable consistent = loop free no action precedes initial state To remove threats… promote the threat or demote the threat Buy(Milk) At(SM) Go(Home) At(Home), not At(SM) At(SM) Go(SM) At(HWS) At(SM), not At(HWS) Start Go(HWS) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Drill) Have(Milk) Have(Ban.) at(Home) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Ban.) At(Home) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) At(Home) Start Go(HWS) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Drill) Have(Milk) Have(Ban.) at(Home) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Ban.) At(Home) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) At(Home) Start Go(HWS) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Drill) Have(Milk) Have(Ban.) at(Home) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Ban.) At(Home) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) At(x) Go(Home) At(SM) Partial Order Planning – Partial Order Planning Problem – Partial Order Plan Generation Derivation from Completeness and Consistency Backward Chaining Threat Resolution The POP algorithm – Plan Execution and Monitoring POP(<A,O,L>, agenda, actions) <A,O,L>, A partial plan to expand Agenda: A queue of open conditions still to be satisfied: <p, a need > Actions: A set of actions that may be introduced to meet needs. a add : an action that produces the needed condition p for a need a threat : an action that might threaten a causal link from a producer to a consumer POP(<A,O,L>, agenda, actions) 1. Termination: If agenda is empty, return plan <A,O,L>. 2. Goal Selection: select and remove open condition <p, a need > from agenda. 3. Action Selection: Choose new or existing action a add that can precede a need and whose effects include p. Link and order actions. 4. Update Agenda: If a add is new, add its preconditions to agenda. 5. Threat Detection: For every action a threat that might threaten some causal link from a produce to a consume , choose a consistent ordering: a) Demotion: Add a threat <a produce b) Promotion: Add a consume <a threat 6. Recurse: on modified plan and agenda Choose is nondeterministic Select is deterministic Partial Order Planning – Partial Order Planning Problem – Partial Order Plan Generation Derivation from Completeness and Consistency Backward Chaining Threat Resolution The POP algorithm – Plan Execution and Monitoring Execution Monitoring Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Execution Can perform a step when all predecessors have been executed. Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Execution Can perform a step when all predecessors have been executed. Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Can perform a step when all predecessors have been executed. Execution Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Can perform a step when all predecessors have been executed. Execution Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Can perform a step when all predecessors have been executed. Execution Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Can perform a step when all predecessors have been executed. Execution Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Can perform a step when all predecessors have been executed. Execution Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Can perform a step when all predecessors have been executed. Execution Plan Execution Initialize the agenda, called Ready, with action Start Mark all actions as not executed. Loop If Ready is empty then terminate. Dequeue action a from Ready and execute When completed, mark a as executed. For each action b such that a < b or linked(a,b,p). – If every action c is marked executed, such that c < b or linked(c,b,p’) – Then queue b on Ready. Partial Order Planning – Partial Order Planning Problem – Partial Order Plan Generation Derivation from Completeness and Consistency Backward Chaining Threat Resolution The POP algorithm – Plan Execution and Monitoring Execution Monitoring – Actions – Causal links Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Fail if preconditions of ready action are not satisfied. Action Monitoring Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Action Monitoring Fail if preconditions of ready action are not satisfied. Plan Execution with Action Monitoring Initialize the agenda, called Ready, with action Start Mark all actions as not executed. Loop If Ready is empty then terminate. Dequeue action a from ready If preconditions of action are satisfied – Then execute – Else return failure When completed, mark a as executed. For each action b such that a < b or linked(a,b,p). – If every action c has been executed, such that c < b or linked(c,b,p’) – Then queue b on Ready. Partial Order Planning – Partial Order Planning Problem – Partial Order Plan Generation Derivation from Completeness and Consistency Backward Chaining Threat Resolution The POP algorithm – Plan Execution and Monitoring Execution Monitoring – Actions – Causal links Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Execution Monitoring Check if precondition of remaining plan is violated. Check if causal link crossing current time is violated. Start Go(HWS) Go(Home) Finish Buy(Drill) Buy(Milk) Buy(Ban.) Go(SM) Have(Milk) At(Home) Have(Ban.) Have(Drill) At(SM), Sells(SM,Milk) At(SM) At(SM), Sells(SM,Ban.) At(Home) At(HWS) At(HWS) Sells(HWS,Drill) At(Home) Sells(HWS,Drill) Sells(SM,Milk) Sells(SM,Ban.) Execution Monitoring Check if precondition of remaining plan is violated. Check if causal link crossing current time is violated. Plan Execution with Execution Monitoring Initialize agenda Ready with action Start Initialize agenda ActiveLinks to empty Mark all actions as not executed. Loop If Ready is empty then terminate. For each link on ActiveLinks – If the condition of link doesn’t hold, Then return failure Dequeue action a from Ready If preconditions of action are satisfied – Then execute – Else return failure … Plan Execution with Execution Monitoring (cont). Loop … Mark a as executed. For each action c such that linked(c,a,p). – dequeue <c,a,p> from ActiveLinks. For each action d such that linked(a,d,p). – queue <a,d,p> on ActiveLinks. For each action b such that a < b or linked(a,b,p). – If every action c has been executed, such that c <b or linked(c,b,p’) – Then queue b on Ready. Monitors Autonomous Agents: What is missing? Command dispatch Fault protection Attitude control Mission Goal Scenario Self-commanding Self-diagnosing Self-repairing RECOVERY P L A N N I N G E X E C U T ION Many Action Representations: (Many Studied In This Course) Tractable Expressive STRIPS MDPs POMDPs Situation Calculus SADL ADL, UWL Probabilistic Concurrent Constraint Automata Hierarchical Hybrid Constraint Automata DS1 DDL TPNs