Planning in a Hierarchy of Abstraction Spaces

Earl D. Sacerdoti

article1974IJCAI1,331 citations

Introduces ABSTRIPS, an automated planning system that constructs a hierarchy of abstraction spaces by ranking operator preconditions, drastically reducing search complexity and demonstrating how hierarchical planning overcomes the combinatorial explosion in complex problem domains.

Listen

Automated problem solvers that rely on general search heuristics face severe computational bottlenecks when attempting to solve complex tasks. As the representation of an operational domain incorporates full real-world detail, the combinatorial explosion of potential action paths causes standard heuristic search to fail or become impractically slow.

The article evaluates a hierarchical planning approach designed to improve problem-solving efficiency by separating critical actions from minor operational details. It demonstrates how an automated planning system, designated ABSTRIPS, automatically establishes and utilizes a hierarchy of abstraction spaces to solve complex multi-step problems.

To demonstrate this method, the author implemented the system in the mobile robot domain from the Stanford Research Institute, which encompasses seven interconnected rooms, movable objects, and simulated door operations. Preconditions for operational actions were assigned numerical criticality ranks, either automatically or via a partial ordering of domain properties. The system executes a length-first recursive search strategy: it first solves the complete problem in the highest, least-detailed abstraction layer to establish a skeleton plan, and then systematically fills in lower-level subproblems at increasing levels of detail.

The evaluation produced several key findings regarding computational efficiency and search behavior. First, hierarchical abstraction dramatically reduced search space exploration; in a complex multi-room navigation and object manipulation task, the system generated only 60 total search nodes—with 54 residing on the final solution path—compared to 119 nodes explored by the baseline STRIPS system. Second, planning time for this complex task dropped from over 30 minutes down to 5 minutes and 28 seconds, representing a speedup of more than fivefold. Third, across a comparative suite of five test problems, the hierarchical approach consistently constrained planning time to a moderate range (under seven minutes) even on tasks where the baseline planner failed to find a solution within 20 minutes. Finally, the search strategy effectively deferred ambiguous operator choices and adjusted evaluation metrics dynamically based on abstraction depth, preventing premature commitment to suboptimal paths.

These findings indicate that distinguishing between core requirements and minor details fundamentally resolves the tension between representational completeness and search efficiency. In practical terms, this lowers computational overhead, accelerates response times, and makes complex robotic planning viable without requiring hand-coded, task-specific heuristics for every new environment. Unlike static macro-operators, hierarchical abstraction reduces exponential complexity by pruning unpromising branches early.

Based on these results, development teams should adopt hierarchical abstraction frameworks when designing autonomous planning and robotics architectures. The source suggests extending this architecture toward an interleaved planning and execution framework, where high-level plans absorb real-world uncertainties while low-level actions execute iteratively. When unexpected environmental deviations occur, systems should propagate failures only up to the level where the deviation constitutes an ignorable detail, rather than replanning from scratch.

A primary operational limitation of this approach is its dependence on producing sound plans at the highest abstraction level; if a subproblem fails at a lower level, the system must backtrack to higher spaces without retaining the specific failure context. Furthermore, the abstraction mechanism alters only preconditions rather than operator effects, meaning representational reformulations remain syntactically constrained. Confidence in the reported computational improvements is high within the modeled domain, though applying abstraction across non-deterministic actions with branching outcomes requires additional research into parameterized effects.

Artificial Intelligence Center SRI International hierarchical structures hierarchical planning abstraction spaces hierarchical representation

Sacerdoti (1974).pdf

Paper: STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving, Richard E. Fikes et al. (1971). This paper introduces the foundational STRIPS planning representation and means-ends analysis algorithm upon which ABSTRIPS directly builds by introducing hierarchical abstraction spaces.

Paper: The Fast Downward Planning System, Malte Helmert (2006). This work develops the Fast Downward planning system, extending the classical STRIPS paradigm through causal graph analysis and hierarchical dependency decomposition for efficient heuristic search.
Paper: The FF Planning System: Fast Plan Generation Through Heuristic Search, Jörg Hoffmann et al. (2011). This paper advances classical domain-independent planning beyond early hierarchy techniques by introducing relaxed-plan distance heuristics and enforced hill-climbing.
Paper: PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains, Maria Fox et al. (2003). This paper standardizes temporal and numeric extensions to STRIPS-based planning domain definition languages, modernizing the formalism used in early hierarchical planners.
Paper: Classical Planning in Deep Latent Space, Masataro Asai et al. (2022). This work bridges classical STRIPS action modeling with deep learning by automatically inducing discrete symbolic planning models from raw image observations.
Paper: Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition, Thomas G. Dietterich (1999). This work generalizes hierarchical decomposition and state abstraction principles into reinforcement learning through the MAXQ value function decomposition.
Paper: Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning, Richard S. Sutton et al. (1999). This seminal paper introduces temporal abstraction and options to formalize multi-level hierarchical action choices in stochastic environments.

Abstract

A problem domain can be represented as a hierarchy of abstraction spaces in which successively finer levels of detail are introduced. The problem solver ABSTRIPS, a modification of STRIPS, can define an abstraction space hierarchy from the STRIPS representation of a problem domain, and it can utilize the hierarchy in solving problems. Examples of the system's performance are presented that demonstrate the significant increases in problem-solving power that this approach provides. Then some further implications of the hierarchical planning approach are explored.

Topics

hierarchical structures

Keywords

hierarchical planning abstraction spaces hierarchical representation search heuristics skeleton plan heuristic adequacy search space operator descriptions task-specific knowledge

I Introduction
II The Motivation for Using Abstraction Spaces in Problem Solving
III Automated Definition of Abstraction Spaces
Abstraction Spaces in the STRIPS Context
Assigning Criticality to the Literals of a Precondition
IV Utilization of Abstraction Spaces in Planning
V Examples of ABSTRIPS' Performance
Definition of Abstraction Spaces
A Detailed Sample Problem
Other Examples
VI Further Implications of the Use of Abstraction Spaces in Planning
Learning Task-Specific Knowledge
Planning with Multiple Outcome Operators
An Integrated Robot System
Acknowledgements
References

Knowls

Knowl 1 — Representation of Abstraction Spaces via Precondition Criticality
model/method
In STRIPS-style planning, a world state is represented as a set of well-formed formulas (wffs) in first-order predicate calculus, and actions are represented as operators with precondition wffs, add lists, and delete lists. ABSTRIPS defines a hierarchy of abstraction spaces by varying only the level of detail specified in operator precondition wffs, keeping the world model representation, operator add lists, and operator delete lists completely unchanged across all abstraction levels.

Each literal in an operator's precondition is assigned an integer criticality value. In an abstraction space of criticality level $k$ , only precondition literals with a criticality value $c \ge k$ are considered by the planner; literals with criticality $c < k$ are temporarily ignored as details to be resolved in lower abstraction spaces. At the highest abstraction level, only the most critical preconditions must be satisfied to produce a plan skeleton. Planning then descends through lower abstraction levels, incrementally enforcing less critical preconditions until all preconditions are satisfied in the ground space. Preserving identical add and delete lists across all levels guarantees that the effect of an operator on the world model is uniform throughout the hierarchy, eliminating the need for state-mapping transformations across abstraction levels.
Knowl 2 — Automated Criticality Assignment for Precondition Literals
algorithm
Criticality values determine the abstraction level at which an operator precondition literal is enforced. ABSTRIPS assigns criticality values using a domain-specific partial ordering of predicate names combined with automated short-plan generation.
Input: Set of domain operators $O$ , partial ordering of domain predicates $P_{ord}$
Output: Criticality value $c(l)$ for every literal $l$ in the precondition of each operator $op \in O$
for each operator $op \in O$ do
    for each literal $l$ in the precondition wff of $op$ do
        if the truth value of $l$ cannot be modified by any operator in $O$ then
            Assign $c(l) \leftarrow \text{MaxCriticality}$
        end if
    end for
end for
for each operator $op \in O$ do
    for each remaining unassigned literal $l$ in the precondition wff of $op$ , in decreasing rank according to $P_{ord}$ do
        Assume all previously processed literals in the precondition are true
        Attempt to generate a short plan to achieve $l$ from a state where those previously processed literals hold
        if a short plan to achieve $l$ is successfully found then
            Assign $c(l) \leftarrow \text{rank}(l, P_{ord})$
        else
            Assign $c(l) \leftarrow \text{rank}(l, P_{ord}) + \text{HighestRank}(P_{ord})$
        end if
    end for
end for
Literals whose truth values cannot be changed by any domain operator (such as static type predicates) receive the maximum criticality value. A modifiable literal is evaluated in the context of higher-ranked preconditions: if achieving it is a minor subproblem (a short plan exists), it receives a criticality equal to its predicate rank; if it cannot be achieved by a short plan, it is elevated to a higher criticality level above the predicate hierarchy.
Knowl 3 — ABSTRIPS Hierarchical Planning Executive
algorithm
ABSTRIPS constructs plans using a recursive, length-first search procedure across abstraction spaces. It completes an abstract plan from initial state to goal at the highest abstraction level before descending to refine subproblems at lower abstraction levels.
Input: Initial world model $M_0$ , Goal wff $G$ , Criticality level $k$ , Skeleton plan $S$
Output: Fully instantiated ground-level plan achieving $G$
procedure ABSTRIPS_Executive( $M_0$ , $k$ , $S$ )
    CurrentState $\leftarrow M_0$
    PlanSteps $\leftarrow [\ ]$
    for each Step in $S$ do
         $P_{op} \leftarrow$ Preconditions of the operator in Step (filtered to literals with criticality $\ge k$ )
        PlanToStep $\leftarrow$ Plan in abstraction space $k$ to achieve $P_{op}$ from CurrentState
        if PlanToStep is unsuccessful then
            Backtrack to higher abstraction space, forbid the choice that created Step, and re-plan
        end if
        CurrentState $\leftarrow$ Apply operator of Step to state resulting from PlanToStep
        PlanSteps $\leftarrow \text{Append}(PlanSteps, \text{steps of } PlanToStep, Step)
    end for
    if $k$ is the minimum (ground) criticality level then
        return PlanSteps
    else
         $k_{next} \leftarrow \text{NextLowerCriticality}(k)$
         $S_{new} \leftarrow PlanSteps$
        return ABSTRIPS_Executive( $M_0$ , $k_{next}$ , $S_{new}$ )
    end if
end procedure
Planning begins by setting $k$ to the maximum criticality level and initializing $S$ as a dummy operator whose precondition is $G$ . Each recursive invocation refines the skeleton plan $S$ by inserting operators that satisfy the newly considered precondition literals at criticality $k$ . If any subproblem cannot be solved in the current space, control backtracks to the caller in the higher abstraction space to select an alternative operator instance.
Knowl 4 — Evaluation Function Scaling and Deferred Operator Instantiation in ABSTRIPS
model/method
ABSTRIPS adapts heuristic search for hierarchical planning through two key modifications to the STRIPS search algorithm:
1. Abstraction-Dependent Evaluation Function: In STRIPS, the heuristic node evaluation function emphasizes the estimated cost of reaching the goal from the current node while deemphasizing the cost from the initial state, biasing search toward finding longer plans quickly. In ABSTRIPS, an additional operator step at an abstract level may expand into many operations in the ground problem space. Therefore, at the highest abstraction level, ABSTRIPS gives equal weight to the cost from the initial state and the estimated cost to the goal. As planning descends through lower abstraction levels, the evaluation function shifts incrementally toward the standard STRIPS weighting, matching STRIPS at the ground level.
2. Deferred Operator Parameter Instantiation: When multiple instantiations of an operator are equally valid in reducing a difference at an abstract level (e.g., choosing which door to traverse between two rooms), committing arbitrarily to one instance can lead to failure at lower levels. ABSTRIPS leaves free parameters uninstantiated when multiple equivalent choices exist, passing partially instantiated operators down into the skeleton plan. When refinement at lower abstraction spaces reveals specific local constraints, the preferred instantiation is selected; if it fails, backtracking explores the alternative parameter bindings.
Knowl 5 — SRI Robot World Experimental Setup
experimental setup
ABSTRIPS and comparison planners were evaluated in a simulated robot environment based on the Stanford Research Institute (SRI) mobile robot domain:
- Environment layout: A world consisting of 7 interconnected rooms with doorways, connectable or blockable by boxes, with doors that can be open or closed.
- Axiomatic representation: A world model initialized with 167 first-order predicate calculus well-formed formulas (wffs) defining axioms and facts about rooms, doors, boxes, and robot locations.
- Operator set: Eight primitive robot operators (GOTOB, GOTOD, GOTOL, PUSHB, PUSHD, PUSHL, GOTHRUDR, PUSHTHRUDR) and two domain environment operators (OPEN, CLOSE) for door state manipulation.
- Criticality levels: Six criticality levels ranging from 1 (lowest detail, e.g., Nextto(Robot, Object)) to 6 (static type predicates, e.g., Type(Object, Box)).
- Hardware/Software: Implemented in compiled BBN-LISP running on a PDP-10 computer.

Knowl 6 — Planning Performance Comparison Across Problem Complexities

data/table

ABSTRIPS was evaluated against standard non-hierarchical STRIPS and STRIPS augmented with macro-operators (MACROPs) across five benchmark robot problems of increasing difficulty on a PDP-10 computer.

Planner / Metric	Problem 1	Problem 2	Problem 3	Problem 4	Problem 5
ABSTRIPS
Time to find plan (min:sec)	1:54	2:55	2:24	2:30	6:41
Total nodes in search trees	25	34	30	33	63
– Nodes by space	5, 5, 5, 10	5, 7, 7, 15	3, 4, 11, 12	5, 7, 7, 14	5, 17, 16, 25
Nodes on solution path	24	32	28	32	54
– Nodes on path by space	5, 5, 5, 9	5, 7, 7, 13	3, 4, 10, 11	5, 7, 7, 13	5, 11, 15, 23
Operators in final plan	4	6	5	6	11
STRIPS
Time to find plan (min:sec)	1:40	5:44	4:34	9:47	> 20:00 (failed)
Total nodes in search tree	10	33	22	51	–
Nodes on solution path	9	13	11	15	–
Operators in final plan	4	6	5	7	–
STRIPS with MACROPs
Time to find plan (min:sec)	1:40	2:06	5:18	3:00	5:49
Total nodes in search tree	10	9	14	9	14
Nodes on solution path	9	9	9	9	14
Operators in final plan	4	6	5	6	11

While non-hierarchical STRIPS is faster on small plans (Problem 1, 4 operators: 1:40 vs 1:54), its search tree size and runtime grow exponentially with plan length, failing to solve Problem 5 (11 operators) within 20 minutes. ABSTRIPS scales gracefully: total search nodes generated remain close to the number of nodes on the solution path (54 path nodes out of 63 total in Problem 5), showing that hierarchical abstraction avoids expanding unproductive search branches.

Knowl 7 — Growth of Planning Time as a Function of Plan Length
empirical result
In experimental trials in the SRI robot domain on a PDP-10, the planning time for standard non-hierarchical STRIPS exhibits steep exponential growth with respect to plan length, increasing from 1:40 (minutes:seconds) for a 4-operator plan to 9:47 for a 7-operator plan, and exceeding 20:00 without finding a solution for an 11-operator plan (Problem 5).

In contrast, ABSTRIPS exhibits near-linear planning time growth with respect to plan length across the same domain, completing a 4-operator plan in 1:54, a 7-operator plan in 2:30, and an 11-operator plan in 6:41. In extended testing on Problem 5, non-hierarchical STRIPS generated over 119 search tree nodes (with only 23 on the successful path) requiring over 30 minutes of compute time, whereas ABSTRIPS generated only 60 search nodes across all abstraction spaces (54 on the successful path) in 5:28, achieving more than a five-fold speedup.
Knowl 8 — Representation of Multiple Outcome and Conditional Operators in Abstraction Spaces
model/method
Hierarchical abstraction spaces facilitate planning with operators that have uncertain or conditional outcomes without requiring exhaustive search over branching execution trees. In a higher abstraction space, an action with multiple possible outcomes (such as parking a vehicle in one of several available lots) is represented as an abstract operator with a single simplified effect that abstracts away specific outcome parameters (for example, asserting $\text{Parked-in-lot}(\text{Car}, \text{Parameter37})$ rather than branching over specific lots).

Planning proceeds at the higher abstraction level under this generalized outcome. Branching case analysis and contingency handling are deferred to lower abstraction spaces or execution time, where sensor feedback or refined preconditions resolve which specific outcome branch must be traversed.

Coverage note — No substantial contributed material was omitted. High-level qualitative discussions of robot execution architectures and MACROP caching proposals from Section VI were condensed or excluded as conceptual extensions rather than core technical contributions.

References

1.R. E. Fikes and N. J. Nilsson, "STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving," Artificial Intelligence, Vol. 2, Nos. 3/4, pp. 189-208 (1971).
2.R. E. Fikes, P. E. Hart, and N. J. Nilsson, "Learning and Executing Generalized Robot Plans," Artificial Intelligence, Vol. 3, pp. 251-288 (1972).
3.G. Ernst and A. Newell, GPS: A Case Study in Generality and Problem Solving, ACM Monograph Series (Academic Press, New York, New York, 1969).
4.J. McCarthy and P. Hayes, "Some Philosophical Problems from the Standpoint of Artificial Intelligence," in Machine Intelligence 4, B. Meltzer and D. Michie, eds., pp. 463-502 (American Elsevier Publishing Company, New York, New York, 1969.
5.G. Polya, How to Solve It, p. 8 (Princeton University Press, Princeton, New Jersey, 1945).
6.A. Newell, J. C. Shaw, and H. A. Simon, "Report on a General Problem Solving Program," Proceedings of the International Conference on Information Processing, UNESCO, Paris, pp. 256-264 (1960).
7.M. D. Kelly, "Edge Detection in Pictures by Computer Using Planning," in Machine Intelligence 6, B. Meltzer and D. Michie, eds., pp. 397-409 (American Elsevier Publishing Company, New York, New York, 1971).
8.C. Hewitt, "Description and Theoretical Analysis (Using Schemata) of PLANNER: A Language for Proving Theorems and Manipulating Models in a Robot," Ph.D. Thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts (1972).
9.B. Buchanan, G. Sutherland, and E. Feigenbaum, "HEURISTIC DENDRAL: A Program for Generating Explanatory Hypotheses in Organic Chemistry," in Machine Intelligence 4, B. Meltzer and D. Michie, eds., pp. 209-254 (American Elsevier Publishing Company, New York, New York, 1969.

Citation

MLA

Sacerdoti, E. D. “Planning in a Hierarchy of Abstraction Spaces”. Artificial Intelligence, vol. 5, no. 2, 1974, pp. 115–35, https://doi.org/10.1016/0004-3702(74)90026-5.

APA

Sacerdoti, E. D. (1974). Planning in a hierarchy of abstraction spaces. Artificial Intelligence, 5(2), 115–135. https://doi.org/10.1016/0004-3702(74)90026-5

Chicago

Sacerdoti, E. D. 1974. “Planning in a Hierarchy of Abstraction Spaces”. Artificial Intelligence 5 (2): 115–35. https://doi.org/10.1016/0004-3702(74)90026-5.

Harvard

Sacerdoti, E.D. (1974) “Planning in a hierarchy of abstraction spaces”, Artificial Intelligence, 5(2), pp. 115–135. Available at: https://doi.org/10.1016/0004-3702(74)90026-5.

Vancouver

1. Sacerdoti ED (1974) Planning in a hierarchy of abstraction spaces. Artificial Intelligence 5:115–135

BibTeX

@article{Sacerdoti_1974, title={Planning in a hierarchy of abstraction spaces}, volume={5}, ISSN={0004-3702}, url={http://dx.doi.org/10.1016/0004-3702(74)90026-5}, DOI={10.1016/0004-3702(74)90026-5}, number={2}, journal={Artificial Intelligence}, publisher={Elsevier BV}, author={Sacerdoti, Earl D.}, year={1974}, pages={115–135} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Planning in a Hierarchy of Abstraction Spaces

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Representation of Abstraction Spaces via Precondition Criticality

Knowl 2 — Automated Criticality Assignment for Precondition Literals

Knowl 3 — ABSTRIPS Hierarchical Planning Executive

Knowl 4 — Evaluation Function Scaling and Deferred Operator Instantiation in ABSTRIPS

Knowl 5 — SRI Robot World Experimental Setup

Knowl 6 — Planning Performance Comparison Across Problem Complexities

Knowl 7 — Growth of Planning Time as a Function of Plan Length

Knowl 8 — Representation of Multiple Outcome and Conditional Operators in Abstraction Spaces

References

Citation

BibTeX

Access the Paper