Session 23

Plan-Space Planning


Artificial Intelligence

today's slides in PDF

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:

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)."


"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 plan, whether partial or complete, consists of:

Wrap Up

Eugene Wallingford ==== ==== November 29, 2001