Author of the summary: Jake Auxier, 1999,
jauxier1@cc.gatech.edu The actual paper is online.
Cite this paper for:
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:
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.