Chapter: Artificial Intelligence

| Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

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


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