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
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.
1. Level(e) = Level(e')Theorem 1: Every abstraction hierarchy satisfying Restriction 1 is an ordered monotonic hierarchy.
2. Level(e) >= Level(p)
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')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.
2. Level(e) >= Level(p)
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 1Constructing a hierarchy
2. Problem-Specific Constraints (Table 2) - Follows Restriction 2
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.
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.