Graphplan : Graphplan Joe Souto
CSE 497: AI Planning
Sources:
Ch. 6
“Fast Planning through Planning Graph Analysis”, A. Blum & M. Furst
Classical Planning : Classical Planning Every node is a partial plan Initial plan complete
plan for
goals
Neoclassical Planning : Neoclassical Planning Every node in search space is a set of several partial plans
So not every action in a node appears in the solution
Planning Graph : Planning Graph State-space: plan is sequence of actions
Plan-space: plan is partially ordered set of actions
Planning graph: sequence of sets of parallel actions
ex: ( {a1, a2}, {a3, a4}, {a5, a6, a7} )
Veloso’s Rocket Problem : Veloso’s Rocket Problem St. Louis San Francisco Seattle R1 R2 R3 C1 C2 C3 Solution can be generalized in 3 steps
Veloso’s Rocket Problem : Veloso’s Rocket Problem St. Louis San Francisco Seattle R1 R2 R3 C1 C2 C3 Step 1: Load all rockets
Veloso’s Rocket Problem : Veloso’s Rocket Problem St. Louis San Francisco Seattle Step 2: Move all rockets
Veloso’s Rocket Problem : Veloso’s Rocket Problem St. Louis San Francisco Seattle Step 3: Launch all rockets
What does Graphplan do? : What does Graphplan do? Explores the problem with a “planning graph” before trying to find a solution plan
Uses STRIPS operators, except no negated literals allowed in preconditions or goals
Plan-space used ‘least commitment’, but Graphplan uses ‘strong commitments’
Requires reachability analysis: can a state be reached from a given state?
Requires disjunctive refinement: method of addressing flaws since multiple conflicting propositions can exist in each state
We’ll start with the reachability concept
Reachability : Reachability metric necessary since you have to know if a solution state can be reached from s0
Can be computed w/ reachability graphs, but computing them is intractable
Can be approximated w/ planning graph, but this is tractable
Reachability
Reachability Trees : Reachability Trees Consider a simple Blocks World Domain C B A Move(x, y, z)
Precond: On(y, x), Clear(x), Clear(z), etc.
Effects: On(z, x), ~On(y, x), Clear(y), etc. S0:
Reachability Trees : B C A B C A B C A Move(B,C,table) Move(A,table,B) B C A Move(A,B,table) A B C B C A Move(A,table,B) Move(B,table,A) C A B Move(C,table,A) etc… etc… Reachability Trees S0: Move(B,C,A) etc…
Reachability Trees : Reachability Trees Note that a reachability tree down to depth d solves all planning problems with s0 and A, for every goal that is reachable in d or fewer actions
This blows up into O(kd) nodes where k = # valid actions, thus we move on to finding reachability with planning graphs
Could be improved by making a graph rather than tree, but still intractable since #nodes = #states
Planning Graphs : Planning Graphs What if all the states reachable from s0 were modeled as a single state? B C A B C A Move(B,C,table) B C A Move(A,table,B) Move(B,C,A) B C A
Planning Graph Idea : Planning Graph Idea B C A B C A B C A B C A Move(B,C,table) Move(A,table,B) Move(B,C,A)
Planning Graphs : Planning Graphs Planning graph considers an inclusive disjunction of actions from one node to next that contains all the effects of these actions
Goal is considered reachable from s0 only if it appears in some node of the planning graph
Graph is of polynomial size and can be built in polynomial time in size of input
Since some actions in a disjunction may interfere, we must keep track of incompatible propositions for each set of propositions and incompatible actions for each disjunction of actions
Planning Graphs : Planning Graphs Planning graph = directed layered graph with alternating levels of propositions (P) and actions (A)
P0 = initial state
An = set of actions whose preconditions are in Pn
Pn = set of propositions that can be true after n actions have been performed ie: Pn-1 effects+(A1)
Planning Graphs : Planning Graphs Precondition arcs go from preconditions in Pn to associated actions in An
Add edges indicate positive effects of actions
Delete edges mark negative effects of actions
Also define a no-op operator p: precond(p) = effects+(p) = p and effects-(p) =
Note that negative effects are not removed, just marked.
Pn-1 Pn: “persistence principle” Precondition arcs Add edges Delete edges b2
Slide19 : Move(B,C,table) Move(A,table,B) Move(B,C,A) Clear(B)
On(B, C)
Clear(A)
On(A, table)
On(C,table) P0 B C A B C A B C A B C A Clear(C)
On(B, table)
On(B, C)
On(A, B)
On(A,table)
Clear(B)
On(B, A)
Clear(A)
On(C,table) A1 P1
Definitions : Definitions 1) Two actions(a,b) are independent iff:
effects-(a) [precond(b) effects+(b)] =
effects-(b) [precond(a) effects+(a)] = B C A B C A B C A Move(A,table,B) Move(B,C,table) Precond: clear(A), clear(B)
Effects+: on(B,A)
Effects-: clear(B) Precond: clear(B)
Effects+: on(table,B),
clear(C)
Effects-: none
Definitions : Definitions 2) A set of independent actions, , is applicable to a state iff precond() s
3) A layered plan is a sequence of sets of actions. A valid plan, = <1, … , n>, is solution to problem iff:
Each set i is independent
n is applicable to sn
g (…((s0, 1), 2) … n)
Note : Note Since planning graph explores results of all possible actions to level n:
If a valid plan exists within n steps, that plan is a subgraph of the planning graph
Allows you to find plan w/ min number of actions
Mutual Exclusion : Mutual Exclusion Can’t have 2 simultaneous actions in one level that are dependent
Two actions at a given level in planning graph are mutually exclusive (“mutex”) if no valid plan can contain both, or no plan could make both true, ie: they are dependent or they have incompatible preconditions
μAi = mutually exclusive actions in level i
μPi = mutually exclusive propositions in level i
Finding Mutex relationships : Finding Mutex relationships Two rules:
Interference: if one action deletes a precondition of another or deletes a positive effect
Competing Needs: if actions a and b have preconditions that are marked as mutex in previous proposition level
Mutex Example : Mutex Example B C A B C A B C A Move(A,table,B) Move(B,C,table) Precond: clear(A), clear(B)
Effects+: on(B,A)
Effects-: clear(B) Precond: clear(B)
Effects+: on(table,B),
clear(C)
Effects-: none Mutex by Interference
Mutex Example : Mutex Example Mutex by Competing Needs St. Louis R1 R2 A) Load(R1, C2, St Louis)
B) Load(R2, C2, Seattle)
Mutex because C2 cannot be in St Louis and Seattle at same time C2 Seattle
Slide27 :
Break
Graphplan Algorithm : Graphplan Algorithm Input: Proposition level P0 containing initial conditions
Output: valid plan or states no valid plan exists
Algorithm:
while (!done)
{
Expansion Phase: Expand planning graph to next action and proposition level;
Search/Extraction Phase: Search graph for a valid plan;
if (valid plan exists)
return successful plan;
else
continue;
}
Graphplan is sound and complete
Expanding Planning Graphs : Expanding Planning Graphs Create next Action level by iterating through each possible action for each possible instantiation given the preconditions in the previous proposition level, then insert no-ops and precondition edges
Create next Proposition level from the Add-Effects of the actions just generated
Associated with each action is a list of actions it is mutex with
Expansion Algorithm : Expansion Algorithm
Slide31 : Move(B,C,table) Move(A,table,B) Move(B,C,A) Clear(B)
On(B, C)
Clear(A)
On(A, table)
On(C,table) P0 B C A B C A B C A B C A Clear(C)
On(B, table)
On(B, C)
On(A, B)
On(A,table)
Clear(B)
On(B, A)
Clear(A)
On(C,table) A1 P1 Mutex list for Move(B,C,table):
-Move(A,table,B)
-Move(B,C,A) Mutex list for Move(A,table,B):
-Move(B,C,table)
-Move(B,C,A) Mutex list for Move(B,C,A):
-Move(B,C,table)
-Move(A,table,B)
Finding Graphplan Solution : Finding Graphplan Solution Solution found via backward chaining
Select one goal at time t, find an action at t – 1 achieving this goal
Continue recursively with next goal at time t
Preconditions of actions in At become the new goals
Repeat above steps until reaching P0
Performance improved w/ “forward checking”: after each action is considered, Graphplan checks that no goal becomes cut off by this action
Planning Graph Solution : Planning Graph Solution
Extraction Algorithm : Extraction Algorithm Optimization: Actions that failed to satisfy certain goals at certain levels are saved in “nogood” hash table (▼), indexed by level, so when you backtrack you can prevented wasting time examining actions that were not helpful earlier
Graphplan Algorithm : Graphplan Algorithm
Algorithm Example : Algorithm Example Initial state: B C A D E B C A D E Goal state: On(A, table)
On(B, A)
On(D, B)
Clear(D)
On(E, table)
On(C, E)
Clear(C)
Slide37 : Move(B,C,table) Clear(B)
On(B, C)
Clear(A)
On(A, table)
On(C,table)
On(E, table)
On(D,E)
Clear(D) P0 B C A Clear(A)
On(B, A)
Clear(C)
Clear(D)
On(C,table)
On(B, table)
On(B, C)
On(E,table)
On(A, B)
On(A,table)
Clear(B)
On(D,E)
Clear(E)
On(D,table) A1 P1 D E Move(B,C,A) Move(D,E,table) A2 P2 Move(D,table,B) Move(C,table,E) On(E,table)
On(B, A)
Clear(C)
On(C,E)
On(C,table)
On(B, table)
On(B, C)
Clear(D)
On(A, B)
On(A,table)
Clear(B)
On(D,E)
Clear(E)
On(D,table)
On(D,B) Move(B,C,D) Move(D,E,A) … … Solution: ({Move(B,C,A),Move(D,E,table)}, {(Move(C,table,E),Move(D,table,B)})
Monotonicity Property : Monotonicity Property Recall persistence principle: Since negative effects are never removed, and for : precond(p) = effects+(p) = p Pn-1 Pn, propositions monotonically increase
Similarly, An-1 An, actions monotonically increase
Unsolvable problems : Unsolvable problems Due to monotonic property of planning graphs, Pn-1 Pn, and An-1 An
At some point, all possible propositions will have been explored, thus Pn=Pn+k for all k>0
Graph has “leveled off” (also called “Fixedpoint” in book)
If you reach a proposition level that’s identical to the previous level, and all goal conditions are not present and non-mutex, problem is unsolvable
Thus Graphplan is complete
Graphplan Planning System : Graphplan Planning System Two files required to specify a domain
Facts file – describe objects in the problem, initial state, and goal state
Operations file – describe valid operations in that domain
Sample Facts File : Sample Facts File (blockA OBJECT)
(blockB OBJECT)
(blockC OBJECT)
(blockD OBJECT)
(preconds
(on-table blockA)
(on blockB blockA)
(on blockC blockB)
(on blockD blockC)
(clear blockD)
(arm-empty))
(effects
(on blockB blockA)
(on blockC blockB)
(on blockA blockD)) Things (operands)
in the domain Initial state Goal State (variable_name variable_type)
(…)
(preconds
(literal_name {variable_name1 variable_name2 …})
(…)
)
(effects
(literal_name {variable_name1 variable_name2 …})
(…)
) General Syntax
Sample Operations File : Sample Operations File
(operator
PICK-UP
(params ( OBJECT))
(preconds
(clear ) (on-table ) (arm-empty))
(effects
(holding )))
(operator
STACK
(params ( OBJECT) ( OBJECT))
(preconds
(clear ) (holding ))
(effects
(arm-empty) (clear ) (on )))
(operator
Operator_name
(params ( ))
(preconds
(literal { …}) (…)
)
(effects
(literal { …}) (…)
)
) General Syntax
More Samples: Rocket Facts : More Samples: Rocket Facts (London PLACE)
(Paris PLACE)
(JFK PLACE)
(r1 ROCKET)
(r2 ROCKET)
(alex CARGO)
(jason CARGO)
(pencil CARGO)
(paper CARGO)
(preconds
(at r1 London)
(at r2 London)
(at alex London)
(at jason London)
(at pencil London) (at paper London)
(has-fuel r1)
(has-fuel r2))
(effects
(at alex Paris)
(at jason JFK)
(at pencil Paris)
(at paper JFK))
More Samples: Rocket Ops : More Samples: Rocket Ops (operator
LOAD
(params
(