麻省理工学院：《自制决策制造原则》英文版 Partial Order Planning and execution

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)