Partial Order planning and execution Brian c williams 16410/13 Slides with help from October 15th. 2003 Dan Weld Stuart russell Peter norvig
Partial Order Planning and Execution 1 Brian C. Williams 16.410/13 October 15th Slides with help from: , 2003 Dan Weld Stuart Russell & Peter Norvig
autonomous Agents Self-commanding Self-diagnosing Self-repairing RECOVERY Commanded at Mission level Engineering level Monitors Command dispatch Fault protection Attitude control Mission goal scenario
Monitors Autonomous Agents Command dispatch Fault protection Attitude control Mission Goal Scenario Self-commanding commanding Self-diagnosing diagnosing Self-repairing repairing RECOVERY PLANNING EXECUTION Commanded at: • Mission level • Engineering level
STRIPS Operator Representation initial state nortel (block a)(block b) (block c)(on-table a) (on-table b)(clear a) (clear b)(clear c) (arm-empty) precond: (and(agent-at 11) (agent-facing north) e goal(partial state, Nortel ((on a b) effect: (and(agent-at 1 2 (on b c)) (not(agent-at 1 1) Available actions Effects specify how to Strips operators change the set of propositions
STRIPS Operator Representation • Effects specify how to change the set of propositions. a a north11 W 0 W 1 • 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 Instead of defining pickup-A and pickup -B and Define a schema ?var denotes a free variable (: operator pick-up parameters(block ?obl) precondition (and(clear?obl) (on-table obl) (arm-empty) effect(and(not(clear ? obl) (not(on-table ?ob1) (not(arm-empty) Holding ?ob))
(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: Note: strips doesn ’t allow derived effects; you must be complete! } ?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
Partial Order Planning – Partial Order Planning Problem • Problem Encoding • Partial Order Plans • Plan Correctness – Partial Order Plan Generation – Plan Execution and Monitoring
Example problem Initial State: At(Home)Sells(hws, Drill) Sells(SM, Milk) Sells( SM, Ban Goal: Have(Milk) At(Home) Have( Ban ) Have drill) erators At(SM), Sells(SM, Ban. At(Hws GO(SM) Buy(Ba At(SM) Have( Ban) At(hWS) Sells(hws, Drill) At (home) Go(HWS Buv di At(HWS Have drill At(sm) At(SM), Sells(SM Milk Go(Home) Buy(Milk) At(Home) Havel milk)
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 Start At(Home) Sells(Hws, Drill) Sells(SM,Milk) Sells(SM, Ban. Why encode as operators? Dont need to introduce(partial )states as separate objects Keeps theory minimal Have milk) at(Home) Havel Ban )Have drill) Finish
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
Partial Order plan Start At(Home) Sells(hws, Drill)Sells(SM, Milk) Sells(SM, Ban. At(Home Go(HWS At(HWS) Sells(hws, Drill) Buy(Drill At(Hws GO(SM) At(SM), Sells(SM, Milk) At(SM), Sells(SM, Ban. Buy( Milk Buy(Ban) AtISML Go(Home) Have milk) at(Home) Havel Ban ) Have(drill) Finish
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 At(HWS) Go(SM) Go(Home) At(SM) Go(HWS) At(Home)
Partial Order plan Start At(Home) Sells(hws, Drill)Sells(SM, Milk) Sells(SM, Ban. At(Home Go(HWS At(HWS) Sells(hws, Drill) Buy(Drill, At(Hws GO(SM) At(SM), Sells(SM, Milk) At(SM), Sells(SM, Ban. Buy(Milk, Buy(Ban) AtISML Go(Home) Have milk) at(Home) Havel Ban ) Have(drill) Finish
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 At(HWS) Go(SM) Go(Home) At(SM) Go(HWS) At(Home)
Partial Order plan Start At(Home) sells(hws Drill) Sells(SM, Milk) Sells(SM, Ban. At(Home Go(HWS At(HWS) Sells(hwS, Drill Buy(Drill At(HWs GO(SM) At(SM), Sells(SM, Milk At(SM), Sells(SM, Ban. Buy(Milk, Buy(Ban) AtISML Go(Home) Have milk) at(Home) Havel Ban ) Have(drill) Finish
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 Go(HWS) At(Home)