Session 23

Plan-Space Planning

810:161

Artificial Intelligence

Context: The Planning Problem

The planning problem is this:

Given an initial state description I, a goal state description G, and a set of operators O, produce a plan P such that executing P in a state described by I results in state described by G.

For more, see our intro to planning.

Applications of Goal-Stack Planning in the Blocks World

An Opening Exercise: Stack B on A from an initial state of A on B.

A Thorny Problem (Sussman's Anomaly): Stack A on B on C from an initial state of C on A and B on the table.

Analysis of goal-stack planning:

• nondeterministic
• backward chaining
• generates total-order plans
• non-interleaving
• "most commitment"
• incomplete
• state-based (the problem space = space of world states)

But what alternative do we have?

Plan-Space Planning

Goal-stack planning, exemplified in the STRIPS representation and algorithm, is an example of state-space planning: The states in our search are possible world states. Most of the negative features of STRIPS result from searching through a space of world states; the rest result from using a stack to control the search.

Instead of searching through a space of world states, we could search through a space of potential plans and sub-plans. (Go "meta"!) This sort of problem transformation comes to mind because we know what is wrong with state-space planning. (Analogy to theory of computation and problem transformations.)

So: let's changed our view of planning from:

"Searching in a space of world states for a goal state (and returning an operator sequence that will take us from the initial state to there)."

To:

"Searching in a space of (partial) plans for a plan that takes us from initial state to a goal state (and returning the plan)."

Plan-Space Planning

In plan-space planning, we search through a space of potential partial plans. On this view,

• A state is a plan.

  • The plan may be incomplete, or partial. In a partial plan, steps are given with a partial ordering and may contain unbound variables.

  • A complete plan has all steps related by a total ordering, and all of its variables are bound.

• An operator creates a new plan from an old plan. There are two possible kinds of operator:

  • A refinement operator takes a partial plan and adds a constraint to it. That is, it makes the plan more specific and makes one or more decisions left open in the partial plan. Refinement operators allow "progression" planning, since they move (we hope) toward the goal.

  • A modification operator does anything else. It might change the plan by making some decisions and undoing others, or it may just undo an earlier decision. Modification operators thus allow "regression" in the planning process.

• The goal state is thus a plan that achieves the goals for which we are planning.

A plan, whether partial or complete, consists of:

• a specification of its precondition state and its postcondition state
• a set of actions, or "steps", S_i
• a set of orderings on the steps, { (S_i < S_j), ... }
• a set of variable-binding constraints that unify variables across the steps,
  such as v_i = v_j, or v_i not equal K

Wrap Up

• Homework -- Homework 3 is available and due tomorrow.
• Exams -- Exam 2 is one week from today.