Home | | Artificial Intelligence | Partial Order Planning

Chapter: Artificial Intelligence

Partial Order Planning

Partial-Order Planning Algorithms

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

 


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Artificial Intelligence : Partial Order Planning |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.