Session 24

Partial-Order 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.

Goal-stack planning (Session 22) is simple to implement and execute, but it doesn't satisfy our needs.

So we are exploring the idea of plan-space planning (Session 23).

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:

How to Plan in a Space of (Partial) Plans

The new algorithm looks something like this:

  1. P := empty-plan(I, G)
  2. Loop:

This algorithm introduces some new concepts.

The Modal Truth Criterion

The interesting new ideas here are:

In order to define these, we need a way to talk about possible problems in a plan. The modal truth criterion (MTC) does that. "Modal" means that it deals with possibility and necessity (a term from logic), and "truth criterion" means that we can apply it to an assertion about a plan and determine its truth value.

The modal truth criterion states:

A proposition a is necessarily true before the execution of step s in plan p if both of the following are true:

Now, we can define flaws and methods in terms of the MTC.

What new data do we need to keep track of in our plans? Causal links that connect steps that necessarily follow or precede other steps to their partners. Note that this can be treated as a distinguished form of ordering that cannot be changed.

Partial Order Planning

Plan-space planning is usually called partial-order planning (POP), since it enables a planner to construct plans that are only partially order and only complete enough to accomplish the goal. Such a plan leaves the agent that will use it as much flexibility as possible at "execution time".

The POP algorithm using the MTC and causal links is the culmination of a progression of increasingly more sophisticated planning algorithms. POP satisfies our initial criteria -- but it comes up short in practice.

Wrap Up

Eugene Wallingford ==== ==== December 4, 2001