State Space Planning

Planning as Search

• It is natural to model planning as a search problem
• Definition of state is natural
• Operators define the state transition
• Goal test: Whether the current state satisfies the goal or not
• Different planning procedure has different search spaces
• State-space planning: Each node represents the state of the world
• Plan-space-planning: Each node is a partial plan

Outline: State-space Planning

• Forward Search
• Backward Search
• Lifting
• STRIPS
• Domain-specific Planning
• Block-stacking

Forward Search

Forward Search

take c3

move r1

take c2

…

…

Forward Search Properties

Forward Search: Pruning

• Forward-search’s state-space is much larger
• Modify algorithm to prune branches of the search space
• Cut off search below these branches
• Safe pruning is guaranteed not to prune every solution
• To maintain the completeness of the algorithm
• Strongly safe pruning guarantee not pruning at least one optimal solution

Forward Search Pruning Strategy

Deterministic Implementation

• Some deterministic implementations of forward search:
• breadth-first search
• depth-first search
• best-first search (e.g., A*)
• greedy search
• Breadth-first and best-first search are sound and complete
• But they usually aren’t practical because they require too much memory
• Memory requirement is exponential in the length of the solution

​

​

Deterministic Implementation

• In practice, more likely to use depth-first search or greedy search
• Worst-case memory requirement is linear in the length of the solution
• In general, sound but not complete
• But classical planning has only finitely many states
• Thus, can make depth-first search complete by doing loop-checking

​

Branching Factor of Forward Search

• Many applicable actions that don’t progress toward goal
• Deterministic implementations can waste time trying lots of irrelevant actions

​

​

a₃

a₁

…

a₁

a₂

a₅₀

a₃

initial state

goal

a₂

Backward Search

Backward Search Algorithm

Backward Search Algorithm

Initial State

Goal

At first iteration choose

Backward Search Algorithm

At second iteration choose

Backward Search Algorithm

Satisfies

Efficiency of Backward Search

• Backward search can also have a very large branching factor
• an operator o that is relevant for g may have many ground instances a₁, a₂, …, a_n such that each a_i’s input state might be unreachable from the initial state
• As before, deterministic implementations can waste lots of time trying all of them

​

b₁

…

b₁

b₂

b₅₀

b₃

initial state

goal

Lifted Backward Search

• Lifting: Can reduce the branching factor of backward search if we partially instantiate the operators

​

holding(b₁)

. . .

ontable(b₁)

on(b₁,b₁)

on(b₁,b₂)

on(b₁,b₅₀)

pickup(b₁)

unstack(b₁,b₁)

unstack(b₁,b₂)

unstack(b₁,b₅₀)

holding(b₁)

ontable(b₁)

on(b₁,y)

pickup(b₁)

unstack(b₁,y)

Lifted Backward Search

The Search Space is Still Large

• Suppose actions a, b, and c are independent, action d must precede all of them, and there’s no path from s₀ to d’s input state
• We’ll try all possible orderings of a, b, and c before realizing there is no solution

​

c

b

a

goal

a

b

b

a

b

a

a

c

b

c

c

b

d

d

d

d

d

d

s₀

STRIPS

• Similar to Backward-search with following difference
• Only the preconditions of the last operators added to the plan are treated as the subgoals
• Reduces the branching factor
• If current state satisfies all of an operator’s preconditions, STRIPS commits to the execution of the operator and will not backtrack

G

Efficient but Incomplete

Sussman Anomaly

Two relevant operators at top level: “put A onto B” and “put B onto C”

Sussman Anomaly (Case: put A onto B)

• Achieve on(A,B)
• put C from A onto Table
• put A onto B
• sub-plan complete from initial state; commit to it
• Achieve on(B,C)
• put A from B onto Table
• put B onto C
• sub-plan complete from new state (un-achieves first sub-goal); commit to it
• Re-achieve on(A,B)
• put A onto B

​

Length 5 plan

Sussman Anomaly (Case: put B onto C)

• Achieve on(B,C)
• put B onto C
• sub-plan complete from initial state; commit to it
• Achieve on(A,B)
• put B from C onto Table
• put C from A onto Table
• put A onto B
• Re-achieve on(B,C)
• put A from B onto Table
• put B on C
• Re-achieve on(A,B)
• put A onto B

​

​

Length 7 plan

Sussman Anomaly

• Interleave plans
• Shortest solution for achieving on(A,B)
• put C from A onto Table
• put A onto B
• Shortest solution for achieving on(B,C)
• put B onto C
• Optimal solution – Interleave two solutions
• put C from A onto Table
• put B onto C
• put A onto B

​

​

Sussman Anomaly

STRIPS Does not always find the best solution

Sussman Anomaly

Sussman Anomaly

Shortest plan for achieving on(c1,c2)

Shortest plan for achieving on(c2,c3)

Interleaved plan