Session 24

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

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 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

How to Plan in a Space of (Partial) Plans

The new algorithm looks something like this:

1. P := empty-plan(I, G)
2. Loop:
   • If P is a solution, return P.
   • Choose F := a flaw in P.
   • Choose M := a method for fixing F in P.
   • If there is no such method, return failure.
   • P := fix-flaw(P, F, M).

This algorithm introduces some new concepts.

• The empty plan, one with no actions. This is merely the trivial plan that says, "yeah, I plan to get from A to B" without specifying how.

• A solution plan. This corresponds to a goal test, since any plan that achieve the I -> G transformation is a solution plan.

• A flaw in a plan. A flaw is typically defined as something that is left undone, such as "no action achieves this part of the goal" or "no action achieves this precondition of an action in the plan". More generally, one could allow for planning to be internally inconsistent for a while, in which case a flaw might be the fact that the preconditions of one action are undone by an earlier action.

• A method for fixing a flaw. In the typical case, a flaw is a hole in the plan, and so a method for fixing it would be to choose an operator that fills the gap. More generally, though, fix methods could be arbitrarily complex, since they may have to analyze the flaw, determine what needs to be done or undone, and do something to fix it. That may involve operator selection, but it could also involve changing the orderings of steps, removing a step altogether, changing a variable binding constraint, and so on.

The Modal Truth Criterion

The interesting new ideas here are:

• What's a flaw in a plan? How do I identify one?

• What's a method for fixing a flaw? How do I identify one?

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:

• There is a step s_p in p such that s_p necessarily comes before s and s_p adds a.

• For every step s_d in p that may delete a, either s_d necessarily comes before s_p or s_d necessarily comes after s.

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

• A flaw is any precondition a of a step s that is not necessarily true before executing s.

• To fix a flaw,

  • Make sure that a is made true before executing s. You can add a new step s_p and make it necessarily prior to s. Or you can choose an s_p that is already in the plan and add an ordering constraint.

  • Make sure that a is not clobbered by some s_d. This can be done by changing the variable bindings on some s_d so that it necessarily does not delete a. Or this can be done by adding an ordering so that s_d must either come before s_p or come after s.

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

• Reading -- None new.
• Homework -- Homework 4 will be available one week from today (Tuesday) and be due the next session (Thursday). It is a short couple of questions about your reading assignment during that period

• Exams -- Exam 2 is next session. It covers material since the last exam.