CSCE 420 Lecture 27

« previous | Thursday, April 25, 2013 | next »

What makes planning hard?

In State-Space search,

• high branching factor: operator instantiated with different variables, e.g. pickup(A,B), pickup(B,C), pickup(C, table)
• depth of solution = length of plan

Famous Planning Algorithms

• GraphPlan
• SatPlan
• #Partial Order Planning (POP)
• Ordered Binary Decision Diagrams (OBDD)
• etc.

Subgoal Interactions

Key issue of complexity

• prevent divide-and-conquer approach
• can't decompose problems and solve subgoals separately
• solutions require interleaving steps

This interference is called the Sussman Anomaly The following blocks-world problem is easy to solve because the sub-goals (on(A,table) and on(B,table)) do not relate to each other:

Init:
    [C][B][A]
Goal:
    [C]
    [B]
    [A]

Classic example of interference

Init:
    [A][C]
    [B]
Goal:
    [A][B][C]
Subgoals:
    on(A,B)
    on(B,C)

Solving the first subgoal gives

[A][B]
[C]

Then solving the second subgoal gives

[B][C]
[A]

Solution for above problem is:

pickup(C,A)
puton(C,table)
picup(B,table)
puton(B,C)
pickup(A,table)
puton(A,B)

The first two and last two actions are for solving the first subgoal, but the middle two solve the second subgoal.

Computational Complexity of Plonning (with PDDL operators)

• NP-hard: negative preconditions but not negative effects
• PSPACE-hard: negatives in both preconditions and effects
• P: no negative literals

Partial Order Planning (POP)

Data structure: plan graph

• actions are nodes
• add'l nodes: start & goal
• edges can be ordering constraints or causal constraints

Define search of space of plan graphs

Algorithm

1. draw start node and goal node
   • goal node includes open pre-conditions (incomplete in-edges)
   • preconditions usually written to the left of nodes
   • postconditions usually written to right of nodes
2. try to connect open precondition to out-edge of existing node
3. or add action that provides it as an effect
   • add in-edges for pre-conditions, out-edge for effects
   • connect with causal constraints ("protection interval")
4. add ordering constraints so that action does not violate other protection interval ("conflict")
   • this resolves conflict by forcing action to come before or after an action that would be violated
   • creates choice point which could lead to backtracking

Figure 1

Linearization of Figure 1(topological sort):

Lsock Lsock Lsock Rsock Rsock Rsock
Lshoe Rsock Rsock Lsock Lsock Rshoe
Rsock Lshoe Rshoe Lshoe Rshoe Lsock
Rshoe Rshoe Lshoe Rshoe Lshoe Lshoe

Simple Example

Init:
    clear(a)
    on(a,b)
    on(b,table)
    gripper_empty
Goal:
    on(a,table)
    on(b,table)

Figure 2: POP graph of sample block problem

Sussman Anomaly

Init:
    gripper_empty
    on(c,a)
    on(b,table)
    clear(c)
    clear(b)
    on(a,table)
Goal:
    on(a,b)
    on(b,c)

Figure 3: POP graph of Sussman Anomaly