Planning Graph Technique

Basic Ideas

Basic Ideas

• Constructs a structure called a planning graph
• Captures all possible solutions
• Proceeds to search planning graph for a solution
• Planning graph techniques extract plan of greater length than other techniques

State-Space vs Planning Graph

The proposition layer consists of the union of the propositions of all the states at a given depth

Proposition Layer

• State space search generates a successor state that will be selected for applying the next action
• In planning graph, all the states resulted applying

all the actions to the previous states are merged

• The resulting set of propositions forms the

proposition layer

Action Layer

Planning Graph

No-op Operation

The no-op action is always applicable

Every proposition is replicated in every proposition layer

Action Layer: Set of all Applicable Actions

Precondition Links

Positive Effects

Negative effects of the actions still persist in the propositional layer because of no-op operation

Action Layer: Set of all Applicable Actions

Precondition Links

Positive Effects

Hold(A)

Clear(B)

On(A,C)

OnT(A)

On(A,C)

OnT(C)

On(A,C)

Hold(C)

Stack(C,A)

Putdown(C)

Stack(C,B)

Stack(A,C)

Stack(A,B)

Putdown(A)

New applicable actions and their effects

Mutual Exclusion

Mutual Exclusion

Mutex Actions

Pickup(C) and Unstack(A,B) are mutext:

Case 4: both consume ArmE

Mutex Propositions

The Planning Graph

Growth in Planning Graph

Growing a Planning Graph

The Goals are Non-Mutex

Backward Search