http://www.jimdavies.org/summaries/

Author of the summary: Jake Auxier, 1999, jauxier1@cc.gatech.edu

The actual paper is online.

Cite this paper for:

- Progression: searching forward from the initial world-state in the state space until a state is found that satisfies the goal specification
- Regression: searching backward from the goal world-state in the state space until a state is found that satisfies the initial state specification
- Least Commitment Planning: planning where plans are represented as a partially ordered sequence of actions and only the essential ordering decisions are recorded
- Ordering constraints are used to provide for least commitment
- The POP algorithm
- Converting explicit actions to operators by adding variables provides for least commitment
- Conditional effects will also provide for more least commitment
- Disjunctive preconditions and universal quantification will also provide for more least commitment
- The UCPOP algorithm

This paper is about mechanisms to create a least commitment planner.

The Planning Problem

A planning problem has three inputs: a description of the world, a description of the agent's goal, and a description of the possible actions that can be performed

Assumptions made in building a planner:

- Atomic Time
- Deterministic Effects
- Omniscience
- Sole Cause of Change

Search through World Space

Progression is used to search forward through the world space. A search algorithm is used when choosing an action.

Regression is used to search backward through the world space. A search algorithm is used when choosing an action.

Search through the Space of Plans

A regression planner can be viewed as a plan-space planner that returns a total order plan.

Partial order planning uses the concept of least commitment where ordering decisions are deferred as much as possible.

Ordering constraints are used in the simplest of partial order planners to provide for least commitment. To make sure that different actions introduced for different goals do not interfere with each other, causal links are used.

The POP algorithm uses ordering constraints and causal links to create a partial order planner.

Providing for Further Least Commitment

Instead of having explicit actions for every possible action, you can generalize an action by introducing variables. The resulting actions are then converted to operators. Once this is done, the bindings for the variables must be stored so that there is no confusion.

To further make operators more abstract, conditional effects can be introduced. If this is done, then a threatening effect that is conditional must be fixed by confrontation where the negation of the conditional effect's antecedent is added.

Disjunctive preconditions can be used but only in moderation or the search space will explode.

Universal quantification is useful for more expressive actions that allow a lot of objects' states to be changed at once. To use universal quantification it is important to have types for each object. That way, when a universal quantification clause is encountered, the objects' can be changed.

The UCPOP algorithm uses the above techniques along with the techniques provided in POP.

- none

Back to the Cognitive Science Summaries homepage

Cognitive Science Summaries Webmaster: JimDavies ( jim@jimdavies.org ) Last modified: Mon Apr 12 08:34:05 EDT 1999