Why is an ordering needed? Suppose the other order is allowed what happens At(HWS GO(SM) At(SM), not At(HWS) Link indicates protected time interval for the precondition AtISML G OfHome At(Home), not At(SM) At(SML Buy(Milk)
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)
Why is an ordering needed? The ordering resolves the threat At(HWS GO(SM) At(SM), not At(HWS) At(SM AtISML G OfHome 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 IFF every precondition of At(Home) Sells(HWS, Drill) Sells(SM, Milk) Sells(SM, Ban. every step is achieved a step s precondition is achieved iff At(HWS) Sells(HWS, Drill Buy(Drill) its the effect of some preceding step, HWS no possibly intervening step GO(SM can undo it At(SM) Sells(SM, Milk At(SM), Sells(SM, Ban. Buy(Ban) · Consistent plan Go(Home) Iff there is no contradiction Have(milk)At(Home)Have( Ban. Have( drill) in the ordering constraint ·ie. never s:<sand the plan graph is loop free
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 si < sj and sj < si . • 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 – Partial Order Planning Problem – Partial Order Plan Generation • Derivation from Completeness and Consistency • Backward Chaining • Threat Resolution • The POP algorithm – Plan Execution and Monitoring