[ CogSci Summaries home | UP | email ]

C.A. Knoblock (1994), Automatically Generating Abstractions for Planning, Artificial Intelligence, 68(2).

Author of the summary: Patrawadee Prasangsit, 1999, pp@cc.gatech.edu

The actual paper is online.

Cite this paper for:

Introduction & Definitions

This paper presents a completely automated approach to generating abstractions for hierarchical planning.

While hierarchical planning is a widely used planning technique, there are only a few systems that automate the construction of abstraction hierarchies.  Some are generated by human.  An abstractiongenerated for an entire problem domain is not as good as one generated for a specific problem.

A hierarchical planner is one that, instead of solving problems in the original problem space, solves a problem in a simpler abstract space and then refines the abstract solution at successive levels of detail by inserting operators to achieve the conditions that were ignored in the more abstract spaces.

Hierarchical planning is used to reduce search.

Problem space is a triple (L,S,O) where L is a first-order language, S is set of states, O is a set of operators.

A state is a finite and consistent set of atomic sentences in L.

An operator consists of preconditions and effects.  Preconditions must be satisfied before an operator can be applied, and the effects describe the changes to the state in which the operator is applied.

A problem p consists of

Solution (or plan) is a sequence of operators that transforms the initial state S0 into some final state Sn that satisfies the goal Sg.

Abstraction space is formed by dropping certain terms from the language of a problem space.  An ordered sequence of abstraction spaces defines an abstraction hierarchy, where each successive abstraction space is an abstraction of the previous one.  The level i abstraction space is similar to the original problem space (aka ground space or base space), except operators and states will only refer to literals that have an abstraction level of i and higher.

Hierarchical planners start by solving problems at higher (more abstract) level first.  We want to make sure those in lower level can be solved without violating the conditions that were already achieved at higher levels in the abstraction hierarchy.  The property is called ordered monotonicity property.

Ordered Monotonicity Property: For all abstract plans, all refinements of those plans leave the literals established in the abstract space unchanged.

Sufficient conditions for Ordered Monotonicity

Restriction 1: Let O be the set of operators in a domain.  For all a in O, all p in Precondition(a), and all e and e' in Effect(a)
1. Level(e) = Level(e')
2. Level(e) >= Level(p)
Theorem 1: Every abstraction hierarchy satisfying Restriction 1 is an ordered monotonic hierarchy.

Restriction 2: Let p = (S0,Sg) be a problem instance and O be the set of operators in a domain.  For all a in O, all p in Precondition(a), and all e and e' in Effect(a), if e is Relevant(a,Sg) then

1. Level(e) >= Level(e')
2. Level(e) >= Level(p)
Theorem 2: Every abstraction hierarchy satisfying Restriction 2 with respect to a problem p is a problem-specific ordered monotonic hierarchy with respect to p.

Automatically Generating Abstraction Hierarchies

Determining the Constraints on a Hierarchy

Constraints are represented by directed graphs: a node corresponds to a literal and an edge to a constraint

Algorithms for finding constraints

1. Problem-Independent Constraints (Table 1) - Follows Restriction 1
2. Problem-Specific Constraints (Table 2) - Follows Restriction 2
Constructing a hierarchy
1. Find constraints (Figure 2) - Produces a set of constraints on the order of the literals.

2. Find strongly connected components (Figure 3) - Two nodes in a directed graph are in the same strongly connected component if there is a path from one node to the other and back again.

3. Construct reduced graph (Figure 4) - A node that comprises a connected component in the original graph corresponds to a single node in the reduced graph.

4. Sort in topological order (Figure 5) - Transforms the partial order into a total order.  There might be more than one possible total orders and one might be better than another.

The algorithm given in the paper is not the best; the output may still contain some unnecessary constraints.

Generating Abstractions in ALPINE

Implemented in ALPINE, the algorithm was tailored for this system by adding the followings

Empirical Results for ALPINE

Compares ALPINE's abstractions to the basic PRODIGY system and PRODIGY using hand-coded control knowledge.  Results: ALPINE reduces both solution time and length

Compares to the use of control knowledge acquired by EBL.  Results: comparable. BUT combination of both leads to better performance than any of the systems alone.

Compares to ABSTRIPS.  Results: produces significatly better abstractions than ABSTRIPS.

Summary author's notes:

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies ( jim@jimdavies.org )

Last modified: Mon Apr 12 08:38:28 EDT 1999