Partial Order Planning

PARTIAL ORDER PLANNING

Partial-Order Planning Algorithms

Partially Ordered Plan

c)                 Plan

d)                Steps

e)                 Ordering constraints

f)                  Variable binding constraints

g)                 Causal links

h)                POP Algorithm

i)                   Make initial plan

j)                   Loop until plan is a complete

– Select a subgoal

– Choose an operator

– Resolve threats

Choose Operator

k)                Choose operator(c, Sneeds)

Choose a step S from the plan or a new step S by instantiating an operator that has c as an effect

If there’s no such step, Fail

•                     Add causal link S _c Sneeds

•                     Add ordering constraint S < Sneeds

•                     Add variable binding constraints if necessary

•                     Add S to steps if necessary Nondeterministic choice

•                   Choose – pick one of the options arbitrarily

•                      Fail – go back to most recent non-deterministic_∈ choice and try a different one that has not been tried before Resolve Threats

•                        A step S threatens a causal link Si c Sj iff ¬ c effects(S) and it’s possible that Si < S < Sj

•                       For each threat  Choose

–Promote S : S < Si < Sj

–Demote S : Si < Sj < S

If resulting plan is inconsistent, then Fail

Threats with Variables If c has_∈ variables in it, things are kind of tricky.

• S is a threat if there is any    instantiation of the variables that makes ¬ c effects(S)

•We could possibly resolve the threat by adding a negative variable binding constraint, saying that two variables or a variable and a constant cannot be bound to one another

• Another strategy is to ignore such threats until the very end, hoping that the variables will become bound and make things easier to deal with

Sells(SM, Banana) Sells(HW,

Shopping problem

sta rt At (Hom e)

Buy (Drill) Buy

At (x2)

GO (HDW)

At(x1)

¬At(x1) start At (Home)

Buy (Drill) Buy (Bananas)

At(HDW) Sells (HDW,D)

Buy (Milk)

At (SM) Sells(SM,M)

finish

Have(D) Have(M) Have(B)

At(SM) Sells(SM,B)

NB: Causal links imply ordering

¬At(x1)

of steps ¬At(x2) GO (SM) At (x2) GO (HDW) At(x1)

start At (Home)

Buy (Drill) Buy (Bananas)

At(HDW) Sells (HDW,D)

Buy (Milk)

At (SM) Sells(SM,M) finish

Have(D) Have(M)

Have(B) At(SM) Sells(SM,B) x1=Home x2=Home NB: Causal links imply ordering of steps

¬At(x2) GO (SM) At (x2) GO (HDW)

At(x1)

¬At(x1) start At (Home)

Buy (Drill) Buy (Bananas)

At(HDW) Sells (HDW,D)

Buy (Milk)

At (SM) Sells(SM,M)

finish

Have(D) Have(M) Have(B) At(SM) Sells(SM,B) x1=Home x2=Home

NB: Causal links imply ordering

of steps ¬At(x2)

GO (SM)

At (x2)

GO (HDW)

At(x1)

¬At(x1)

start

Buy (Drill) Buy (Bananas) At(HDW) Sells (HDW,D)

Buy (Milk)

At (SM) Sells(SM,M) finish

Have(D) Have(M) Have(B) At(SM) Sells(SM,B) x1=Home x2=Home

NB: Causal links imply ordering of steps

start At (Home)

Buy (Drill) Buy (Bananas) At(HDW) Sells (HDW,D)

¬At(x2) GO (SM) At (x2) Buy (Milk)

At (SM) Sells(SM,M)

finish

Have(D) Have(M) Have(B)

At(SM) Sells(SM,B)

GO (HDW)

At(x1)

¬At(x1) x1=Home x2=Home

3 start

At (Home)

Buy (Drill) Buy (Bananas) At(HDW) Sells (HDW,D)

¬At(x2) GO (SM)

GO (HDW)

At (x2)

Buy (Milk)

At (SM) Sells(SM,M)

finish

Have(D) Have(M) Have(B)

At(SM) Sells(SM,B)

At(x1) ¬At(x1) x1=Home x2=Home x2=HDW

start At (Home)

Buy (Drill) Buy (Bananas)

At(HDW) Sells (HDW,D)

¬At(x2)

GO    (SM)

At      (x2)

Buy (Milk)

At (SM) Sells(SM,M)

finish

Have(D) Have(M) Have(B)

At(SM) Sells(SM,B)

GO (HDW)

At(x1)

¬At(x1)

x1=Home x2=Home x2=HDW

start At (Home)

Buy (Drill) Buy (Bananas)

At(HDW) Sells (HDW,D)

¬At(x2)

GO    (SM)

At      (x2)

Buy (Milk)

At (SM) Sells(SM,M)

finish Have(D) Have(M) Have(B).

At(SM) Sells(SM,B)

At(x1)

¬At(x1) x1=Home x2=Home x2=HDW

PLANNING GRAPHS

·                    Levels  

·                    Mutex between actions  

·                    Mutex holds between luents  

·  Graph plan algorithm  

PLANNING AND ACTING IN THE REAL WORLD

•            Conditional planning Or Contingency Planning

•            Execution monitoring and replanning Continuous planning

Multiagent planning

•            Times, schedules, and resources

Critical path method

• Hierarchical task network planning