SciXa AI Systems Series · Cluster Article
Macro-Actions and Temporal Abstraction in Sequential Plans: In Practice
Bigger steps buy shorter searches — and new distortions. This is the practical theory of macro-actions: why they help, when they hurt, where they come from, and where full hierarchy begins.
SciXa Research Desk · SciXa.com
Published October 15, 2026 · Estimated reading time: about 82 minutes
Cluster 45 of 100 · Hierarchy and Time · 52 cited sources · 5 original figures
Part of the pillar guide AI Planning Under Uncertainty: Decision-Making for Autonomous Systems, which situates this subtopic in the full landscape of planning under uncertainty. This cluster article is a secondary synthesis of published research; figure bases are stated in every caption.
Section 1 · Hierarchy and Time
Orientation: Bigger Steps, New Distortions
Every sequential planner faces the same arithmetic. Search effort in a flat state space grows exponentially with the length of the solution it must find, so a planner that has to assemble a two-hundred-step plan one primitive action at a time is fighting the exponent directly (Bellman, 1957; Korf, 1985). The oldest counter-move in the book is to make the steps bigger. A macro-action — a macro-operator, a temporally extended action, a skill, a behavior, a procedure, depending on which literature you grew up in — bundles several primitive actions into a single decision that a planner or a learning agent can choose, execute, and reason about as one unit. Choose fetch-and-deliver rather than load, then drive, then drive, then unload. The plan gets shorter, the search tree gets shallower, and the decision granularity moves closer to the level at which the domain actually makes sense to a human operator or a mission engineer.
That is the promise, and it is real. But bigger steps are not free, and the price is paid in a currency that this article takes seriously: distortion. A macro is a commitment device. By bundling actions it fixes an internal sequence that a flat search would have been free to revisit, reorder, or abandon mid-course; it inflates the branching factor by adding itself to the action set; it hides intermediate states from the heuristic functions that were designed to evaluate them; and it can quietly lengthen the plans it was supposed to shorten, because the optimal route through a problem rarely decomposes exactly along macro boundaries. Macro-actions therefore do not sit on a simple good axis. They sit on a trade-off axis, and the trade has to be evaluated — which is why this article is organized around a utility analysis rather than a cheerleading session.
The scope needs one boundary drawn early. Macro-actions are the lightest form of temporal abstraction: a bundle of actions, added to an otherwise flat planner or learner, with no commitment to a full hierarchical control regime. The heavier machinery — hierarchical task networks with their decomposition methods, goal networks, and closed-loop options with internal policies — is treated in dedicated sibling articles, and we point to them throughout: Hierarchical Task Networks as Domain-Knowledge Encodings: The Long View for method-based decomposition, and Options as Search Primitives for Hierarchical Planning: The Expert View for the stochastic, closed-loop generalization of everything here. What this article owns is the practical middle: the analysis that tells you whether a given macro set helps a given planner on a given class of instances, the machinery for deciding where macros come from, and the interface between macros and the heuristic search that consumes them (Bonet & Geffner, 2001).
A note on evidence discipline before the route map. Established results carry citations: the semi-Markov formalism into which macro-actions fall in stochastic settings is due to Sutton, Precup, and Singh's framework for temporal abstraction (Sutton, Precup, & Singh, 1999); the value-function decomposition that made hierarchical reinforcement learning analyzable is Dietterich's MAXQ work (Dietterich, 2000); the compilability lens through which we ask what macros formally buy is Nebel's (Nebel, 2000). Where we assemble our own stylized models — the compression-versus-inflation arithmetic of Section 4, the worked corridor of Section 6 — they are labeled as our synthesis, with every number derived from a stated formula so a reader can re-derive it. Open problems are labeled open. This is a secondary synthesis; no firsthand experiments or deployment claims are made anywhere in it.
What you will learn
- What macro-actions are in both classical (deterministic, symbolic) and Markovian (stochastic) planning, and why the two formalisms meet in the same design space.
- A compression-versus-inflation utility analysis: when bundling actions into macros reduces expected search effort, and when it makes the tree bigger and the plans worse.
- Two fully worked illustrative examples — a courier domain for deterministic heuristic search, and a discounted corridor for semi-Markov option evaluation — with numbers you can check.
- Where macros come from: plan mining from STRIPS' MACROPs onward, domain analysis, hand encoding in deployed systems, and learned options in modern reinforcement learning.
- How macros interact with heuristics — applicability, cost accounting, guidance loss, and the safeguards that keep optimality guarantees intact.
- A failure-mode catalogue, a comparison with HTN methods, options, and durative actions, and a deployer's guide with concrete decision rules.
In the coordinate system of the pillar guide — uncertainty representation × objective × computation budget — macro-actions are primarily a budget-axis instrument: they change how much computation a plan of given quality costs. But their side effects reach the other two axes. They change what a policy can express about time and interruption, which matters under uncertainty; and by committing to bundles they change which objectives a planner can honor at fine grain, which matters whenever plan quality is defined by deadlines, risk measures, or resource envelopes rather than by step counts. That three-axes framing returns in the FAQ, and readers who want the full map should start from the pillar; readers who want the sampling-based use of macro-actions inside tree search can continue to Monte-Carlo Tree Search Architecture and Its Design Dimensions.
The route is as follows. Sections 2 and 3 build the foundation: the rationale for bigger steps and a working formalism that spans classical and Markovian planning. Sections 4 through 6 are the analytical core — the utility theory of macros, then two worked examples, deterministic and stochastic, that turn the theory into numbers. Sections 7 through 9 cover supply and interaction: where macros come from, how heuristics consume them, and the failure modes that result when things go wrong. Sections 10 through 13 widen out: the boundary with full hierarchical methods, engineering practice, the history of the idea from MACROPs to option-critic-style learning, and the open problems. The reader who wants only the decision-relevant heart can jump to Sections 4, 9, and 11.
Section 2 · Hierarchy and Time
Why Bigger Steps? The Rationale for Macro-Actions
The exponent problem
The founding observation is Bellman's: sequential decision problems solved by exhaustive look-ahead suffer from what he called the curse of dimensionality, and even in discrete, deterministic planning the practical face of that curse is depth (Bellman, 1957). A breadth-first or iterative-deepening search over a state space with branching factor b must, in the worst case, entertain on the order of bd candidate action sequences before it reaches a goal at depth d; Korf's analysis of iterative deepening made the depth term explicit and showed that even optimal admissible tree search cannot escape paying for it (Korf, 1985). Planning compounds the problem because solutions are long. Classical benchmarks are measured in tens to hundreds of primitive steps; robot missions, logistics schedules, and scientific workflows are measured in thousands. When d grows from 20 to 200, the flat search is not ten times more expensive — it is astronomically more expensive, and no constant-factor engineering closes an exponential gap.
Macro-actions attack d itself. If a planner can treat a useful length-L sequence of primitive actions as a single choosable action, then a solution that needed d primitive decisions needs, in the idealized limit where every part of the solution is covered by a macro, only about d/L decisions. The tree that would have grown to depth d grows to depth d/L, and the node count falls from roughly bd to roughly (b + k)d/L, where k is the number of macros added. This is the single clean sentence of the macro promise, and everything else in the article is about the asterisks attached to it: the (b + k) term grows, the division by L is only as good as the coverage of the macro set, and the plans found may no longer be the short ones the flat search would have found. Section 4 turns the asterisks into arithmetic. But the promise itself is sound, and it is the reason macros keep reappearing, under different names, in every generation of the field (Fikes & Nilsson, 1971; Sutton, Precup, & Singh, 1999).
Granularity as a modeling decision
There is a second, less arithmetic rationale: the primitive actions of a formal model are themselves a modeling choice, and they are frequently the wrong granularity for the decisions an agent actually faces. The General Problem Solver already organized behavior into methods — packaged procedures applied by means-ends analysis — precisely because human problem-solving knowledge arrives packaged (Newell, Shaw, & Simon, 1959). A mission engineer does not think in wheel torques and gripper closes; she thinks in traverse to site, sample the outcrop, uplink the results. The activity vocabulary of the Mars Exploration Rover planning system operated exactly at that level: rover operations were specified, scheduled, and interactively adjusted as temporally extended activities with durations and resource profiles, not as primitive commands (Ai-Chang et al., 2004). When the decision granularity of the planner matches the granularity at which domain knowledge and human oversight are expressed, three things get easier at once: encoding expert guidance, producing legible plans, and interfacing with mixed-initiative refinement by people.
This rationale has a formal shadow. In the decision-theoretic tradition, structural assumptions about a domain — factored states, limited interactions between variables, reusable subtasks — are exactly what convert intractable sequential decision problems into tractable ones; Boutilier, Dean, and Hanks called this the exchange of structural assumptions for computational leverage (Boutilier, Dean, & Hanks, 1999). A macro is one of the cheapest structural assumptions available: it asserts that a particular bundle of actions is worth treating as a unit. Unlike a full hierarchical model it requires no new solver, no new semantics for decomposition, and no revision of the objective. It is a lever that a practitioner can pull incrementally, which is precisely why it is the most common first move in practice — and why it deserves the sober utility analysis that follows.
Two currencies: depth reduction and path duplication
It is worth being precise, early, about what a macro does and does not change in the underlying state space: nothing. Adding macros to a planning domain leaves the set of reachable states and the set of achievable goals exactly as they were, because every macro is executable as its constituent sequence. What changes is the path structure of the search space — the graph the search algorithm actually walks. That graph gains shortcut edges, one per macro, each skipping L levels. A search over that graph buys depth reduction with two currencies. The first is branching: every macro added to the action set is one more child generated at every expanded node where it is applicable. The second is duplication: because base operators remain available, the same state is now reachable through more distinct action sequences, so duplicate-detection work grows and, in searches without perfect duplicate elimination, wasted expansions grow with it. The two currencies are paid at every node and recouped only along the macro-covered fraction of the solution. This is the entire macro gamble in one sentence, and Figure 1 draws it.
What macro-actions are not
Three boundary clarifications keep the rest of the article honest. First, macros are not abstractions in the refinement sense: Sacerdoti's hierarchy of abstraction spaces suppressed problem detail at coarse levels and re-introduced it during refinement, changing which facts the planner could even see (Sacerdoti, 1974). A macro suppresses no facts; it fixes an internal control sequence over the full-fidelity state space. Second, macros are not durative actions: in temporal planning languages such as PDDL2.1 an action genuinely occupies time, with conditions checked over an interval and effects at its end (Fox & Long, 2003). A macro occupies no time of its own — its duration is the sum of its constituents' durations — though the two ideas meet at the boundary discussed in Section 10, and the dedicated treatment of time lives in Temporal Planning With Durative Actions and Deadline Goals: What to Do. Third, macros are not methods: an HTN method replaces an abstract task with a context-shaped network of subtasks, conditioned on the state in which it is invoked (Erol, Hendler, & Nau, 1994). A classical macro is context-blind — one fixed sequence, applicable wherever its combined precondition holds. The progression from context-blind bundle to conditioned method to closed-loop policy is exactly the spectrum along which Section 10 arranges the hierarchical landscape, and the Markovian substrate that the stochastic end of that spectrum presupposes is laid out in Markov Decision Processes as Modeling Substrates for Planners.
Section 3 · Hierarchy and Time
A Working Formalism: Macros in Classical and Markovian Planning
The macro idea lives in two formal worlds that rarely share a room, and both are needed for practice. In classical, deterministic planning, a macro is a derived operator — a compiled shortcut through the operator graph. In Markovian planning, a macro is a temporally extended action whose internal behavior is a policy and whose duration is a random variable — the option of Sutton, Precup, and Singh, formalized over the semi-Markov decision process (Sutton, Precup, & Singh, 1999). This section defines both, proves the one small lemma that makes derived macros safe, and then exhibits the shared skeleton that makes them the same design object despite the different mathematics. Notation is fixed in Table 1 and used consistently for the rest of the article.
Macro-operators over deterministic actions
Work in the STRIPS tradition: states are sets of ground atoms, and each operator o has a precondition pre(o), an add set add(o), and a delete set del(o) (Fikes & Nilsson, 1971; McDermott et al., 1998). A macro-operator μ = o1;o2;…;oL is an ordered sequence of L ground operators. Its filter construction derives the macro's own precondition and effect without human annotation:
- Precondition. pre(μ) collects every precondition literal of every oi that is not established (made true and still true) by o1;…;oi−1 earlier in the sequence. Literals that the earlier steps produce are omitted — the macro supplies them internally.
- Effect. eff(μ) is the sequential composition of the add and delete sets, applied in order: a literal's final truth value is determined by the last constituent that touches it.
- Cost. The macro's cost is the sum of its constituents' costs; under unit-cost conventions, cost(μ) = L. This accounting choice is what preserves admissibility downstream, and Section 8 returns to it with teeth.
The construction carries a small guarantee worth stating precisely, because it is the difference between macros that behave and macros that crash mid-execution. Say the sequence was observed to execute in some state s — it came from a plan that actually ran. Then whenever the filter construction puts a literal p into pre(μ), either p held in s or some oj, j < i, added it. Suppose, for contradiction, that at some state s′ satisfying pre(μ) the macro becomes inapplicable at step i: some literal q needed by oi is false when oi's turn arrives. That q was either false in s′ initially or deleted by an earlier oj. If it was deleted by an earlier oj and not re-added, then the same deletion would have broken the observed execution in s — contradiction, unless q was restored, in which case the restoring operator is inside the macro and the restoration happens in s′ too. If q was false in s′ initially, then q is a precondition of oi not established by earlier steps, so q ∈ pre(μ) by the filter — contradicting s′ satisfying pre(μ). The upshot: plan-derived macros with the filter construction are internally executable wherever they are applicable. The caveat is equally important: the guarantee is about executability, not usefulness — a macro can be perfectly executable and still lead the search somewhere it did not want to go.
Ground macros transfer to almost no other problem instance, so practice lifts them: constants that happened to appear in the source plan are replaced by variables, with the substitutions constrained so the internal data flow of the sequence is preserved (Fikes & Nilsson, 1971; Korf, 1983). A lifted macro haul(p, x, y) ≡ load(p, x); drive(x, y); unload(p, y) applies at any package p and any connected locations x, y. Lifting is where the learning risk enters: a constant generalized away may have been load-bearing (the plan drove via y because of a bridge that only exists there), and the lifted macro silently assumes the world is more uniform than it is. The standard texts treat this construction and its hazards as part of the basic vocabulary of domain-independent planning (Ghallab, Nau, & Traverso, 2004).
Macro-actions in Markovian domains: options and semi-MDPs
Deterministic bundles are too rigid for stochastic settings: a fixed open-loop sequence cannot react to a surprising observation. The Markovian side of the formalism therefore closes the loop. An option o is a triple ⟨Io, πo, βoo of states where o may be started; an internal policy πo mapping states to primitive actions (or to distributions over them); and a termination function βo giving the probability that o terminates upon arriving in each state (Sutton, Precup, & Singh, 1999). Executing an option means following πo until termination, which occurs after a random number τ of primitive steps. A deterministic macro is the degenerate special case: πo is a fixed sequence and βo = 1 exactly at the L-th step of it. The generality is not free decoration — it is what lets temporally abstract actions remain valid in worlds where the L-th step is not always reachable in L steps.
The correct substrate for choosing among temporally extended actions is the semi-Markov decision process, in which decisions occur at the timescale of option terminations while rewards and dynamics run at the primitive timescale. The Bellman equations adapt by integrating over durations. Writing V for the state value function and Q for the option-value function:
V(s) = maxo ∋ s Q(s, o)
Q(s, o) = Σs′, τ p(s′, τ | s, o) [ Σk=1τ γk−1 rk + γτ V(s′) ]
The inner sum is the discounted reward accumulated while the option runs; γτ is the discount applied to the value of the state where it stops. When reward accrues at a constant rate r̄ while o runs, the inner sum collapses to the geometric closed form (1 − γτ)/(1 − γ) · r̄, which is the form the worked example of Section 6 evaluates numerically. Two classical facts frame these equations. First, the contraction arguments that make value iteration converge for Markov decision processes extend to the semi-Markov setting, so planning over options is principled in the same sense flat planning is (Puterman, 1994; Sutton, Precup, & Singh, 1999). Second, the framework is deliberately agnostic about where options come from: they may be designed, learned end to end, or discovered, and the thesis that first systematized this — that learning and planning benefit from acting at multiple timescales simultaneously — traces to the temporal-abstraction line running from Precup's formulation of the problem through the MAXQ decomposition of task value functions (Precup, 2000; Dietterich, 2000).
One design object, two formalizations
Set the two formalisms side by side and a common skeleton appears, which is why practitioners can move between them without relearning the design questions. Both attach to each temporally abstract action an availability condition (combined precondition; initiation set), an body (operator sequence; internal policy), a termination rule (sequence end; β function), and a cost or reward profile inherited from the primitives (sum of costs; accumulated discounted reward). Both change the search or learning problem only through the path structure, not through the reachable states. And both import the same commitment semantics: while the body runs, the outer planner has no authority. In the deterministic case the commitment is absolute for L steps; in the option case it is softened only insofar as β and πo themselves encode exits. Everything the utility analysis of the next section says about branching, depth, and quality applies to both, with one stochastic amendment — random durations — that Section 6 shows is more consequential than it looks.
| Symbol | Meaning | Notes and first use |
|---|---|---|
| b, d | Branching factor and flat solution depth of the base search | Stylized model, Section 4; d is measured in primitive actions. |
| k, L | Number of macros added; length (constituent count) of a macro | L = 3 in the running example; cost(μ) = L under unit costs. |
| d′ | Solution depth in the macro-augmented action space | Between d/L (full coverage) and d (no coverage). |
| c, i | Compression ratio c = d/d′; inflation factor i = logb(b + k) | Macros pay when c > i; Section 4's central inequality. |
| μ = o1;…;oL | A macro-operator over primitive operators oi | Filter construction defined in this section. |
| o = ⟨Io, πo, βo | An option: initiation set, internal policy, termination function | Semi-MDP setting, Sections 3 and 6. |
| τ, γ | Random duration of an option; discount factor per primitive step | The pair whose interaction Section 6 computes. |
| V, Q | State value and option-value functions in the semi-MDP | Defined above; evaluated numerically in Section 6. |
Table 1. Notation used throughout the article. Basis: symbols defined in this section and in Section 4; no external data are tabulated.
Section 4 · Hierarchy and Time
The Utility Theory of Macros: Speedup Versus Branching Distortion
Practice needs a rule for when bigger steps help, and the field's honest answer is a small model with sharp edges. This section builds that model — stylized, ours, and labeled as such — and pushes it until it yields the decision rule that governs everything downstream. The claim it defends is the article's central one: macro-utility is not a property of macros but a property of the match between a macro set and a solution distribution, and the two terms of the match pull in opposite directions.
The stylized cost model
Fix a flat search over a domain whose solutions run about d primitive actions deep, with effective branching factor b — the average number of applicable successors per expanded node, the quantity that A*-style analyses of exponential search actually feel (Hart, Nilsson, & Raphael, 1968). In the worst case, and to first order in the exponent, such a search explores nodes proportional to bd. Now augment the action set with k macros of length L and keep every base operator. Write d′ for the depth of the solution as measured in the augmented action space: a plan of d primitive actions in which a fraction of the actions is covered by macros appears as roughly d/L decisions where covered and single actions where not. The augmented search explores, to the same first order, (b + k)d′ nodes. Define the compression ratio and the inflation factor:
c = d / d′ (how much shorter solutions become)
i = logb(b + k) (how much bigger each level becomes)
Taking logarithms of both node counts, the macro-augmented search visits fewer nodes exactly when d·log b > d′·log(b + k), which rearranges to the cleanest sentence in the subject:
Key result · the macro-utility inequality
Macros reduce expected search effort exactly when the compression ratio exceeds the inflation factor, c > i = logb(b + k). Everything else in macro practice is a commentary on this inequality: coverage raises c, macro count raises i, and the two are coupled because more macros are needed to raise coverage. Our model, stated in the stylized terms above; the node-count convention follows standard exponential-search accounting (Hart, Nilsson, & Raphael, 1968; Korf, 1985).
The inequality deserves a slow reading because it corrects two folklore errors at once. The first folklore error is that macros help because they make steps bigger — true only if the compression they induce survives the branching they add. With b = 4 and k = 6, the inflation factor is log410 ≈ 1.66: each level of depth saved must be bought by compressing the solution by more than 1.66 times, so a family of length-2 macros that only manages to halve the solution (c = 2, i = 1.66) barely pays, while length-3 macros achieving the same halving pay comfortably. The second folklore error is that more macros are monotonically better. Inflation is concave in k at first and then punishing: going from k = 6 to k = 12 at b = 4 raises i from 1.66 to 2.00, and the extra macros had better raise coverage by another factor of 1.2 in compression terms just to break even. Under full coverage, where d′ = d/L, adding the seventh through twelfth macro buys nothing in depth and costs a factor of 100.34 per level — the model's way of saying that a small, well-chosen macro set beats a large, redundant one.
Reading the curves
Figure 2 evaluates the model at the running parameters — b = 4, d = 24 — across macro lengths L from 2 to 8 and three set sizes, plus the case that practice actually lives in: partial coverage. Three regimes fall out of the picture. In the full-coverage regime (solid curves), every macro length shown beats the flat baseline, and longer macros dominate because d′ = d/L shrinks faster than the branching grows; at L = 8 even the k = 12 set, branching 16, needs only 163 ≈ 4.1×103 nodes against the flat 424 ≈ 2.8×1014. In the no-coverage regime, d′ = d and macros are pure loss: every added action inflates branching without shortening anything, the mirror image of the first regime. The instructive middle is the half-coverage curve (dashed), where only half the solution is macro-coverable and the residual half must still be assembled one primitive action at a time, so d′ = d/2 + d/(2L). At L = 2 the augmented search needs 1018 nodes — more than a million times worse than flat search at 1014.45; only at L ≥ 6 does the macro set claw back to parity. The dashed curve is the one practitioners should tattoo somewhere visible: under partial coverage, short macros are actively harmful and only long ones pay, because a short macro saves a little depth while its branching tax is charged on the entire uncovered remainder of the search.
The quality ledger
The inequality governs effort, not plan quality, and the quality ledger is kept separately. When the optimal solution decomposes along macro boundaries, a macro-augmented optimal search — base operators retained, macro costs summed, admissible heuristic — still returns an optimal plan, because every macro plan unfolds into a primitive plan of exactly the summed cost, and every primitive plan remains available. The quality risk enters through two side doors. The first is forced detours: a macro body is a fixed sequence, so using it where a shorter interleaving exists pins the plan to the macro's route. The canonical damage is small but real and adds up — the worked example of the next section exhibits a 12.5 percent lengthening from a single badly shaped macro, and the number is the rule, not the exception, whenever macro boundaries cut across goal interactions. The second is satisficing interaction: greedy and weighted searches, which already trade optimality for speed, magnify macro-induced distortion, because the inflated branching gives the greedy criterion more ways to be misled — the same interaction that the bounded-suboptimal literature documents from the other side (Zilberstein, 1996; Hansen & Zhou, 2007). Under a bounded-suboptimality contract with bound w, macro detours eat the budget that w was supposed to spend on search speed.
A subtler accounting note belongs on the same ledger. Anytime search returns improving incumbents under a deadline, and macros change the shape of that improvement curve rather than its limit: the first macro-flavored incumbent arrives fast (short depth), while the closing phase — where the last few percent of quality live — can stall, because the inflated branching slows the exhaustion of the remaining search space (Hansen & Zhou, 2007). Deployments that read only the fast first incumbent conclude macros are pure win; deployments that read the full anytime trajectory see the crossover. This is one instance of a pattern the article returns to repeatedly: macro evaluations are horizon-of-observation sensitive, and the honest experiment reports the whole curve.
What the model cannot see
Four real-world effects sit outside the model and all point the same direction: the model is optimistic about macros. First, applicability gates: the model charges the branching tax (b + k) at every node, but macros apply only where their combined preconditions hold, so effective inflation is often below the model's; this is the model's one systematic pessimism, and it is why hand-written macros with tight preconditions behave better than the raw inequality predicts. Second, duplicate detection: state hashing turns path duplication into a hash lookup, so the bd counting overstates both sides; macro gains shrink under strong duplicate elimination, because the flat search's revisited states were already cheap. Third, heuristic interplay: node count is a proxy for time only if per-node cost is constant, and Section 8 shows macro nodes are cheaper to generate in bulk but evaluated with coarser information. Fourth, the coverage distribution: c is not a property of the domain but of the joint distribution of instances and the macro set — the same macros that compress one instance class stretch another, and the field's hardest open problem, taken up in Section 13, is estimating c before deployment rather than after.
One more framing deserves record, because it explains why the theory can be this simple and the practice still this hard. In the compilability framework, adding macro-operators to a planning formalism is a conservative extension: macro plans unfold to primitive plans of polynomially related length, so nothing changes in expressive power or worst-case complexity — propositional planning stays PSPACE-complete with or without macros (Bylander, 1994; Nebel, 2000). Macros therefore cannot buy anything at the level of what is computable; everything they buy is at the level of what is computed first. That is exactly the territory where the exponent model, with all its stylization, is the right kind of theory: it does not describe the problem, it describes the order in which the search meets it. Metareasoning makes the same point from the decision-theory side — if computations are actions, a macro set is a policy over computations, and choosing it is a metalevel decision to be evaluated by its expected value (Russell & Wefald, 1991; Barto, Bradtke, & Singh, 1995, for the value of focusing computation on visited regions). The bounded-rationality framing of that decision is developed in Bounded Rationality as a Constraint on Practical Planner Design.
Read more about Greedy Best-First Search and the Abandonment of Optimality: Beyond the Benchmark and Weighted A* and Bounded-Suboptimal Planning Guarantees: A Reality Check — the cluster articles that treat the satisficing searches whose distortion budgets macros consume.
Section 5 · Hierarchy and Time
Worked Example I: A Courier Domain, Four Macro Configurations
The utility theory needs numbers attached, so this section invents a small courier family and evaluates it honestly: every figure is computed from the stated model and labeled illustrative, because the point is the structure of the arithmetic, not a benchmark claim. The family runs on a road line of five depots A–B–C–D–E with a single truck of capacity one package. Primitive operators: drive(x, y) for adjacent depots, load(p, x), unload(p, x). A typical instance asks for three deliveries — p1 from A to D, p2 from B to E, p3 from D back to C, say — and an optimal plan has a characteristic shape: load, a run of drives, unload, then a repositioning drive, then the next leg. Across the family these plans run about 24 primitive actions: eighteen drives and six load/unload operations, arranged in three legs of eight actions. Effective branching at a typical state is about b = 4 — two drive directions, load, unload, minus whichever are inapplicable. This is deliberately the running parameter set of Section 4, so the model applies directly.
Four configurations, evaluated
Configuration A is the flat planner. The model estimates 424 ≈ 2.8×1014 leaf-equivalent paths before goal depth, the number that makes depth-first, breadth-first, and A*-alike all blanch equally (Korf, 1985). Configuration B adds a single parameterized macro, convoy(x, y) ≡ drive;drive;drive along the line — length L = 3, tight precondition (three connected depots ahead), k = 1. Since the eighteen drives decompose exactly into six convoys and the six load/unload actions must remain primitive, the plan compresses to d′ = 12 decisions, and the search estimate becomes 512 ≈ 2.4×108 — a reduction of about a million-fold in the model's path count, at the price of one extra child per node. The compression ratio c = 24/12 = 2 exceeds the inflation i = log45 ≈ 1.16, so the inequality is satisfied with room to spare: this is the macro success story, and it is success precisely because the domain has a long, boring, repeated fragment — driving — that the macro swallows whole.
Configuration C adds a second, more aggressive family: haul(p, x, y) ≡ load(p, x); drive(x→y); unload(p, y) for the delivery legs — length L = 3 counting each leg's spine, k rises to 6 with the depot-pair instances retained abstractly. Under the model's full-coverage assumption the estimate is 108, worse than B's 2.4×108 but still far better than flat. Configuration D is where the story turns: the same macro set on an interrupted instance — one delivery requires an en-route pickup that splits a leg, so only half the plan decomposes along macro boundaries. Now d′ = 12 + 6 = 16 at branching 10, and the estimate is 1016: thirty-six times worse than the flat planner it was supposed to beat. Nothing about the macros changed; the instance distribution did. That is the entire pedagogical point of configuration D, and Table 2 lines the four cases up side by side.
| Configuration | Action set | Branching | Depth d′ | Est. paths | c vs i |
|---|---|---|---|---|---|
| A · flat | base operators only | 4 | 24 | 424 ≈ 2.8×1014 | — (baseline) |
| B · convoy macro | + convoy(x,y), L = 3, k = 1 | 5 | 12 | 512 ≈ 2.4×108 | c = 2.0 > i = 1.16 · wins ~106-fold |
| C · full macro set | + haul(p,x,y) family, k = 6 | 10 | 8 | 108 | c = 3.0 > i = 1.66 · wins, but worse than B |
| D · interrupted instance | same as C, half coverage | 10 | 16 | 1016 | c = 1.5 < i = 1.66 · loses 36-fold |
| E · detour-prone macro | C, with unload-at-y forced | 10 | 8 | 108 | plan lengthens 24 → 27 (+12.5%) |
Table 2. The courier-family configurations under the stylized model of Section 4. Basis: illustrative values computed from N = (b + k)d′ with b = 4, d = 24, L = 3; no planner was run, and the model omits duplicate detection and applicability gating as stated.
The forced-detour macro
Configuration E exhibits the quality distortion with the same domain. Suppose the haul(p, x, y) macro is written to unload at its destination y — the natural encoding — but the optimal plan for one instance carries p1 past D toward E to collect p2 en route, because the truck was going there anyway. A flat planner interleaves: load p1, drive, drive, drive, drive, load p2, drive, unload p1, unload p2. The macro planner faces a choice: use haul(p1, A, D) and then re-drive D→E empty for p2 — two extra drives — or use haul(p1, A, E) and backtrack E→D empty — also two extra drives — or fall back to primitives for that leg and keep the other two legs compressed. The macro-optimal plan under the macro-only action set runs 27 primitive actions against the flat optimum of 24: a 12.5 percent quality loss from a single boundary misalignment. Under the safe configuration — base operators retained, macro costs summed — the planner can still reach 24 by falling back to primitives, but the inflated branching of configuration C is now purchased for a leg where it bought nothing. Three lessons line up.
- Boundary alignment is worth more than macro count. The single convoy macro, aligned with the domain's dominant repeated fragment, beat the six-macro haul family that cut across leg interactions. Macro design is less "find frequent sequences" than "find fragments whose boundaries the optimal solutions respect."
- Coverage is distributional. Configuration D did not fail because its macros were wrong for the domain; it failed because the instance distribution included interrupted legs. A macro set is a bet on a solution distribution, and the bet's payoff varies instance by instance.
- Never remove the base operators. Every configuration above stayed complete and optimal-capable only because primitives remained available at summed costs. The moment macros replace rather than augment, completeness needs a proof and optimality usually dies quietly (Section 9's distortion four).
A closing observation transfers from toy to practice. The courier family rewarded the macro that encoded the boring part of solutions — driving — and punished the macro that tried to encode the interesting part, where goals interacted. Deployed macro libraries tend to show the same signature: the macros that earn their keep wrap routine, low-variability, high-frequency fragments; the macros that cause incidents wrap decision points where the flat planner needed its freedom. That signature is also, not coincidentally, what human domain experts can articulate most reliably — which is the bridge to the macro-supply question of Section 7, and to the mixed-initiative practice in which people and planners co-design the action vocabulary (Ai-Chang et al., 2004; Ghallab, Nau, & Traverso, 2016).
Section 6 · Hierarchy and Time
Worked Example II: Macro-Actions as Options in a Semi-Markov Corridor
The deterministic example showed macros trading search effort. The stochastic example shows something subtler: what macro-actions can and cannot change about the value of a policy, and where the accounting traps hide. The setting is deliberately the smallest one that exhibits all of it. A corridor of thirteen states, indexed 0 through 12, with state 12 absorbing and terminal. Every primitive step costs reward −1 until termination; the discount factor is γ = 0.9 per primitive step. The primitive action set is {step-right}; with one action, the flat optimal policy is forced, and its value can be written in closed form. This is an illustrative computation from the stated formulas, in the spirit of the small gridworlds the reinforcement-learning literature uses to make definitions concrete (Sutton & Barto, 2018).
The flat value, exactly
Under the flat policy, reaching the goal from state 0 takes twelve steps of reward −1, discounted as they accrue, so the value is the negative of a finite geometric series:
V∗(0) = −(1 − γ12)/(1 − γ) = −(1 − 0.912)/0.1 = −7.176
Seven decimal places are not decoration; they are the point. The flat optimum is the yardstick against which every temporally abstract accounting scheme must reconcile exactly, and any implementation whose option values disagree with −7.176 by more than rounding error contains a bug. Now introduce the macro-action dash: an option that moves right deterministically for up to four steps and then terminates (or terminates early on reaching state 12). In option notation, Io = {0, …, 11}, πo = step-right everywhere, and βo = 1 at states 4, 8, and 12 — or, viewed from the option's internal clock, termination at τ = 4 with probability one. The semi-MDP recursion from Section 3, with the constant-rate closed form for the running cost, evaluates the two-action set {step, dash}:
Q(s, dash) = −(1 − γ4)/(1 − γ) + γ4 V(s + 4) = −3.439 + 0.6561 · V(s + 4)
Working backward from V(12) = 0: V(8) = −3.439, then V(4) = −3.439 + 0.6561 × (−3.439) = −5.695, then V(0) = −3.439 + 0.6561 × (−5.695) = −7.175. To the last digit the discount permits, the option-augmented value equals the flat value. This is not a coincidence of the corridor, and it deserves its own box.
Key result · value neutrality under exact accounting
In a deterministic environment, a macro-action whose rewards and duration are accounted exactly — per-step rewards discounted per step, γτ applied to the true terminal state — changes nothing about the optimal value function. Bundling is value-neutral; every gain from macro-actions in such settings is computational, not decision-theoretic. The corollary cuts both ways: any reported value difference is either an accounting artifact or evidence of stochastic structure, never a free lunch.
The corollary is the more useful half. Value neutrality gives practitioners a debugging invariant — option-level value iteration must reproduce flat values on deterministic instances — and it disciplines claims: a system that "improves the policy" by adding macros in a deterministic domain has, on inspection, always either changed the objective, changed the model, or misaccounted the discount. The interesting regimes begin where the accounting stops being exact, and there are exactly two such regimes: stochastic durations and approximate value functions. The corridor exhibits the first, and it is where the trap lives.
Stochastic durations and the Jensen gap
Give dash a flaky termination: after each primitive step, the option halts prematurely with probability 0.2, independently, and halts for certain at four steps. The duration τ now has distribution P(τ = 1) = 0.2, P(τ = 2) = 0.16, P(τ = 3) = 0.128, P(τ = 4) = 0.512, with mean E[τ] = 2.952. A tempting implementation evaluates the option as if it ran for its mean duration — γE[τ] times the terminal value — and that temptation is a bug factory, because the discount interacts multiplicatively with a random exponent. The correct term is E[γτ], the expectation over the duration distribution, and since γτ is a convex function of τ for γ < 1, Jensen's inequality fixes the ordering:
E[γτ] ≥ γE[τ]
E[γτ] = 0.2·0.9 + 0.16·0.81 + 0.128·0.729 + 0.512·0.6561 = 0.7388
γE[τ] = 0.92.952 = 0.7327
At γ = 0.9 the gap is 0.0061 — small enough to hide in a noisy learning curve and large enough to shift action choices in a close comparison. At γ = 0.6 the same computation gives E[γτ] = 0.2716 against γE[τ] = 0.2214, a gap of 0.050: the mean-duration approximation undervalues every stochastic-duration option by roughly a fifth of its continuation discount, and the undervaluation worsens as the discount tightens. The pattern generalizes into a design rule with two horns. First, option value functions must carry the duration distribution, not a point estimate of duration — the semi-MDP equations of Section 3 are not optional formality, they are the difference between 0.7388 and 0.7327, compounding at every decision. Second, the discount factor itself is a macro-relevant design decision: the conventions and distortions of discounting in long-horizon choice — how a small γ quietly starves temporally extended behavior whose payoffs arrive late — are treated in Discounting Conventions and Their Distortion of Long-Horizon Choice, and the interaction seen here in miniature is that article's subject at scale.
What the stochastic example adds to the deterministic one
Three transfers. First, the computational gain survives the stochastic setting, but it moves. A flat lookahead over twelve steps of a branching tree is exactly the regime where sparse-sampling and tree-search costs are exponential in horizon (Kearns, Mansour, & Ng, 2002), and macro-actions shrink the horizon axis directly: choosing among {step, dash} for three decisions instead of twelve replaces a depth-12 tree with a depth-3 one. This is why macro-actions appear throughout sampling-based search — in bandit-based tree search and its descendants, temporally extended moves reduce the depth that the tree must grow before its statistics mean anything (Kocsis & Szepesvári, 2006; Browne et al., 2012). The branching distortion of Section 4 reappears here with the same arithmetic, plus a stochastic term: an option's internal policy multiplies the paths behind each macro edge, so the effective branching under an option is the branching of its policy, not of a single action.
Second, termination design is where option craft concentrates. In the corridor, dash's value neutrality held because termination was pinned to state structure — stop at 4, 8, or 12. The flaky-termination variant showed what happens when termination decouples from structure: the option's value changed not because the world changed but because the exit times did. Option termination conditions are, in effect, a second policy — a policy over when to return control — and the option-critic line of work made exactly this point by learning termination functions end to end, with the durations and the internal policies co-adapting (Bacon, Harb, & Precup, 2017). Practitioners who hand-write options usually hand-write β as an afterthought; the arithmetic above says it is half the value function.
Third, the complexity boundary does not move. Semi-MDPs inherit the decision-theoretic landscape of their flat cousins: Markovian decision problems are already polynomial in the explicit case (Papadimitriou & Tsitsiklis, 1987), and partially observable, infinite-horizon probabilistic planning is undecidable with or without temporal abstraction (Madani, Hanks, & Condon, 1999). What options buy in the stochastic world is the same thing macros buy in the deterministic one — a restructured search space whose first solutions arrive sooner — plus one genuinely new ingredient: a compact representation of behavior that a learner can fill in, which is the door through which reinforcement learning at scale entered the subject (Sutton, Precup, & Singh, 1999; Dietterich, 2000).
Section 7 · Hierarchy and Time
Where Macros Come From: Fragments, Domain Analyses, and Learning
If macros are a bet on a solution distribution, the obvious next question is who places the bet and with what information. The field has accumulated four supply channels, and they differ exactly where it matters: what evidence they use, what failure they are prone to, and how their output interacts with the utility inequality of Section 4. Figure 4 shows the four channels converging on a macro library; this section walks them in historical order, which happens to be the order of increasing automation.
Channel one: watching yourself solve
The oldest channel is plan mining, and it is older than the term. STRIPS itself learned macro-operators: after solving a problem, the system could generalize the solution — replacing the constants that happened to appear with variables, subject to consistency constraints — and store the result, a MACROP, for reuse (Fikes & Nilsson, 1971). The mechanism is worth spelling out because every modern descendant still uses its skeleton. A solved plan is a trace of operators that worked together; generalization by lifting constants asks which of those bindings were incidental and which were structural; and storage adds the trace, as one composite operator, to the action set. The filter construction of Section 3 supplies the combined precondition automatically. What STRIPS' designers learned early, and what Korf later systematized in his analysis of macro-operators as a weak method for learning, is the transfer problem: a macro extracted from one solution encodes the regularities of that solution, and domains reward the macros whose regularities recur (Korf, 1983). Rote learning of sequences is weak precisely because nothing in the extraction procedure checks recurrence, boundary alignment, or coverage — the three properties the utility inequality rewards.
Modern plan mining fixes exactly those gaps, and the Macro-FF system is the canonical study: macros are mined from plans that a baseline planner produced on training instances, candidate fragments are filtered for redundancy against macros already accepted, and the surviving library is validated by re-solving the training corpus, so that only macros that demonstrably helped survive into deployment (Botea, Enzenberger, Müller, & Schaeffer, 2005). Built on the FF planner's heuristic machinery (Hoffmann & Nebel, 2001), that pipeline established the template — mine, filter, validate — that the more recent mining literature follows. The residual risk is the one Section 5's configuration D exhibited: a library validated on one instance distribution can fail on another, because validation measures coverage on the training world, not on the deployment world. The deeper treatment of that specific failure mode — what frequent-sequence mining actually does and does not establish about a domain — is the subject of its own cluster article, listed at the end of this section.
Channel two: reading the domain's structure
The second channel derives macros from the domain description itself, without solving anything. The reasoning is that a compiled domain — its causal structure, its variable dependencies, its transition graphs — already declares which operator sequences are structurally coupled, and structurally coupled sequences are candidates for bundling regardless of any particular instance. Fast Downward made automatic macro generation part of a competition-grade preprocessing pipeline, deriving macros from the compiled domain structure before search begins (Helmert, 2006). The epistemic profile is the mirror image of plan mining's: domain analysis cannot overfit an instance distribution, because it never saw one, but it can misread the domain's own structure, and its macros are unselective about coverage because coverage is a property of instances, not domains. In the terms of the utility inequality, mining has good estimates of c on the training distribution and no guarantee off it; analysis has weak estimates of c everywhere but no distribution to overfit. Systems that ship both — and modern domain-independent planners ship a surprising amount of derived structure — are hedging that epistemic difference.
Channel three: asking the expert
The third channel is authorship, and it remains the workhorse of deployed systems. A domain engineer writes the macro vocabulary by hand, guided by the operational semantics the organization already uses: the rover activity vocabulary that operations teams manipulate is a hand-authored macro layer, with durations, resources, and constraints, refined interactively in mixed-initiative sessions between people and the planner (Ai-Chang et al., 2004). The acting literature has largely absorbed this channel into its main line: when plans are executed as procedures, the procedure library is the macro library, and acting engines select among procedures the way planners select among operators (Ghallab, Nau, & Traverso, 2016). Hand authorship has the best boundary alignment of any channel — experts know where the boring parts of their domain live — and the tightest preconditions, which Section 4 identified as the one systematic source of model pessimism working in macros' favor. Its costs are the familiar knowledge-engineering ones: acquisition effort, maintenance drift as the domain changes, and brittleness when an authored macro's implicit assumptions stop holding. The mixed-initiative article in this cluster treats the human-loop craft in detail.
Channel four: learning behavior end to end
The fourth channel arrives from reinforcement learning, where the question inverts: instead of bundling known operators, learn the bundle itself. The MAXQ decomposition showed that a task hierarchy's value function decomposes into per-subtask value functions that could be learned separately, with state abstraction shrinking each subtask's effective problem (Dietterich, 2000); the options framework supplied the substrate-neutral formal object (Sutton, Precup, & Singh, 1999; Precup, 2000); and the option-critic architecture closed the loop, learning internal policies and termination functions jointly by gradient descent through the option structure (Bacon, Harb, & Precup, 2017). At deep-learning scale, temporally extended behavior emerges implicitly — hierarchical controllers and latent-model planners learn to act at coarse granularity because doing so compresses what they must represent (Mnih et al., 2015; Schrittwieser et al., 2020) — with the trade that learned macros are opaque: no combined precondition to inspect, no boundary alignment to audit, and the utility inequality's terms measurable only empirically. The newest wrinkle is that large language models emit macro-shaped behavior directly — plausible multi-step procedures in natural language — which makes them a proposal source for macro libraries, though a proposal source whose output requires exactly the validate-and-filter stage that channel one learned to insist on, and whose failure modes under grounding are now well documented (Huang, Abbeel, Pathak, & Mordatch, 2022; Kambhampati et al., 2024). The LLM-as-proposer pattern, and the verifier loops that discipline it, are treated in Large Language Models as Plan Proposers and Their Failure Modes.
One property cuts across all four channels and deserves the last word: provenance. A macro library that records, for each entry, where it came from — which solutions, which structural analysis, which expert session, which training run — supports exactly the audits that Sections 9 and 11 argue for: when a macro-containing plan fails, the first diagnostic question is which channel produced the macro and what its evidence base was. Libraries that lose provenance inherit the worst epistemics of all four channels simultaneously, and the failure-mode catalogue that follows repeatedly reduces to that single omission.
Read more about Macro-Operator Discovery From Frequent Action Sequences: The Real Story and Heuristic-Function Learning From Solved Instance Corpora: The Long View — the cluster articles that treat mining solved instances for reusable structure, on both the action side and the guidance side.
Section 8 · Hierarchy and Time
Macros Meet Heuristics: Guidance at Coarser Granularity
Modern planners are heuristic-search machines — the framing is due to Bonet and Geffner's demonstration that planning could be cast as heuristic search and solved competitively that way (Bonet & Geffner, 2001) — and a macro set is only as useful as the guidance function that steers the search through the augmented space. The interaction runs in both directions: macros change what the heuristic is asked to evaluate, and the heuristic determines whether macro-induced shortcuts are taken well or badly. This section works the interface in four moves: admissibility, visibility, guidance sources, and a design recipe.
Admissibility under summed costs
The bookkeeping question first, because it is the one with a clean answer. An admissible heuristic never overestimates true remaining cost; A* with such a heuristic returns optimal plans (Hart, Nilsson, & Raphael, 1968). Augment the action set with macros while (a) keeping all base operators, (b) assigning each macro the sum of its constituents' costs, and (c) evaluating the same heuristic on macro-successor states — and optimality survives intact. The reason is almost embarrassingly simple: the macro-augmented space contains, as a subgraph, the original search graph with the original costs, plus shortcut edges whose costs equal the lengths of the paths they abbreviate; no path through the augmented graph is cheaper than the best primitive path, so the heuristic's admissibility carries over unchanged, and the optimal macro plan unfolds to an optimal primitive plan. The trap is equally simple, and it is called the unit-cost trap: if macros are counted as single steps in a unit-cost regime — "the plan has eight actions" where four were macros of length three — the objective itself has been silently redefined, the heuristic's scale no longer matches the objective's scale, and guarantees evaporate. Deployed systems hit this trap most often in reporting: an eight-macro-step plan sounds twice as good as a sixteen-primitive-step plan until someone multiplies by three. The rule that keeps everything aligned is one sentence: macros shorten the decision sequence, never the cost accounting.
What the heuristic cannot see
Heuristic functions evaluate states, and macros change which states the search visits — that is the whole point — so the subtle interaction is about which evaluations are skipped. Three effects are worth separating. First, the milestone effect, usually favorable: heuristic error is per-state, and by jumping from macro start to macro end, the search never consults h at the intermediate states, where an unlucky over- or underestimate could have steered it astray. When macros span genuinely routine passages — the convoy macro over three boring drives — skipping the intermediate evaluations removes noise without removing signal. Second, the visibility effect, usually unfavorable: delete-relaxation heuristics and their relatives estimate distance from the current state's literals, so a state deep inside a macro body, where some literal has been transiently deleted, can look pathologically far to a relaxed computation even though the macro is about to restore it; conversely, pruning machinery that reasons about operator structure — FF's helpful-action filtering, which restricts successors to operators on the relaxed plan (Hoffmann & Nebel, 2001) — has to decide whether a macro counts as helpful when only its third constituent lies on the relaxed plan. Implementations that treat a macro as all-or-nothing for pruning purposes throw away base operators the flat planner would have kept, an accident with the same shape as removing base operators outright. Third, the compounding effect, neutral on average but variance-increasing: heuristic error per macro edge is charged once but spans L primitive steps, so per-unit-distance error is neither amplified nor damped — what changes is that the search has fewer opportunities to notice it is wrong. Under greedy search this couples macros to the satisficing distortions of Section 4: fewer checkpoints mean a wrong macro choice is discovered later, after more committed search.
A useful mental model, and it is ours: think of a heuristic as a measurement instrument with per-state error, and of macros as a change in the sampling schedule. Macro-augmented search samples the state trajectory at macro boundaries instead of every step. Fewer samples of the same biased instrument cannot remove bias — the relaxed-heuristic's optimism survives bundling — but they do change which decisions the bias contaminates. The empirical question for any macro set is therefore not "does the heuristic stay accurate?" but "does the heuristic's error, sampled at macro boundaries, still rank the alternatives correctly?" — a question about ranking, not estimation, and one reason small heuristic degradations coexist with large macro speedups in practice.
Guidance sources and the knowledge-injection comparison
Landmark-based guidance interacts with macros in a particularly instructive way. A landmark is a fact or action that must occur in every plan, and landmark orderings — achieve this before that — are among the most reliable signals a domain-independent planner has (Helmert & Domshlak, 2009). A macro body that spans a landmark boundary makes the landmark invisible to a search that only consults states at macro endpoints: the fact is achieved and consumed entirely inside the bundle. The plan remains correct, but the guidance that the landmark would have provided — the ordering constraint that prunes wrong orderings early — is spent on nothing. The design corollary is one of the most actionable sentences in macro practice: prefer macros whose boundaries coincide with landmark boundaries. A macro that achieves a landmark at its end and requires none in its middle is aligned with the domain's causal structure in exactly the way both the utility inequality and the guidance machinery reward.
It is worth setting macros against the other knowledge-injection routes at this point, because they compete for the same engineering attention. Pattern databases inject knowledge by abstracting the state space and precomputing exact distances in the abstraction, yielding admissible, composable heuristics — an inside-the-heuristic intervention, leaving the search graph untouched (Culberson & Schaeffer, 1998; Felner, Korf, & Hanan, 2004; Haslum et al., 2007). Macros inject knowledge by restructuring the search graph, leaving the heuristic untouched. The routes are orthogonal and compose: a macro-augmented search can be driven by a pattern-database heuristic with summed macro costs, and nothing in either technique conflicts. The deep symmetry is that both are answers to the same question — "where in this problem is the structure that flat search wastes?" — with PDBs answering "inside the state representation" and macros answering "inside the action sequences." A practitioner choosing between them is not choosing between competing methods but choosing where to spend knowledge-engineering effort, and the honest comparison is budget-allocation, not ideology. The landmark-extraction craft that the boundary-alignment rule leans on has its own dedicated treatment in the cluster.
Practitioner's checklist · heuristic-aware macro design
- Keep every base operator; assign macro costs as the sum of constituents; never let unit-cost bookkeeping redefine the objective.
- Align macro boundaries with landmarks and with other "milestone" states the heuristic evaluates well; avoid bodies that transiently delete goal-relevant literals.
- Make helpful-action and successor pruning macro-aware: a macro is helpful if any constituent is, and its base constituents remain individually selectable.
- When pairing with relaxed heuristics, spot-check macro endpoints against intermediate states for ranking inversions before trusting speedups.
- Budget knowledge-engineering across macros and heuristic sources jointly — they compose, so compare marginal gains, not philosophies.
One closing observation ties this section back to the utility theory. The compression-versus-inflation inequality counted nodes as if guidance were absent, and guidance is precisely what changes the effective branching factor below its structural value: a strong heuristic makes the flat search's effective b small, which shrinks the space in which macros can pay. This is the quietest and most practically important negative result in the area, and the experiments that motivated it are exactly the ones where adding a strong heuristic to a macro-accelerated planner erodes the macro speedup: macros and heuristics draw their benefit from the same underlying structure, and when the heuristic already exploits it, the macros arrive as redundant branching. Search-cost accounting of the kind collected in the heuristic-search literature makes the same point from the measurement side (Edelkamp & Schrödl, 2012). The engineering conclusion is not to choose one but to measure marginal utility in combination: the fourth macro added to a heuristic-guided planner is usually worth less than the first, and the only honest ledger is an ablation over both dimensions.
Read more about Delete-Relaxation Heuristics and Their Accuracy Bounds: A Balanced View and A Practical Guide to Landmark Extraction Methods for Guiding Heuristic Search — the cluster articles that treat the guidance functions whose blind spots and boundary alignments macro design must respect.
Section 9 · Hierarchy and Time
A Failure-Mode Catalogue: The Four Distortions
Failure modes deserve their own section because each of the four has a distinct signature in logs and field reports, and because each is routinely misdiagnosed as something else. The catalogue is our synthesis — the organizing frame is ours, though every underlying mechanism traces to the cited literature — and it is deliberately stated as a diagnostic manual: what the distortion is, how it shows up, and what contains it.
Distortion one: branching inflation
The first distortion is the branching tax, and its signature is nodes per solution depth creeping up while per-instance solve times creep up with them — the opposite of what the macro deployment promised. The dashed curve of Figure 2 is its theory: whenever real coverage falls below the inflation threshold, the tax exceeds the rebate. In deployed libraries the usual mechanism is library bloat: macros accumulated from multiple channels, or from multiple versions of the domain, that overlap heavily — several macros whose bodies differ only in irrelevant bindings, each generating successors in the same states. The containment is dominance analysis among macros: if μ′s body can be simulated by μ followed by base operators at no greater cost, μ′ adds branching without adding reachability, and the machinery of dominance pruning that the search community built for state spaces applies to the macro layer directly — the general techniques are treated in Symmetry Breaking and Dominance Pruning in State Spaces: Beyond the Benchmark. The operational rule is an audit, not a theorem: periodically re-derive the effective branching factor with and without each macro, and retire macros whose removal does not degrade the training corpus.
Distortion two: locked-body commitment
The second distortion is the commitment semantics, and its signature is late, clustered deviation reports during execution. A deterministic macro executes as an open-loop sequence: once chosen, its body runs to completion regardless of what the world does en route, so every disturbance inside the body is discovered at the boundary, bundled with whatever else went wrong in those L steps. Execution monitors anchored in predicted state trajectories see exactly this pattern — predictions and observations diverge at macro boundaries because the interior was never predicted stepwise — and repair machinery then faces a multi-step deviation with a compound cause instead of the single-step deviation the flat policy would have produced. The craft of monitoring and repairing around such deviations has its own cluster treatment in Plan Repair Techniques After Execution Deviations: What the Field Knows; the macro-relevant point is upstream of repair: a macro trades the frequency of replanning decisions for the severity of each replanning episode. Domains with cheap, routine replanning should bundle aggressively; domains where each replan is expensive or operationally disruptive should keep bodies short and boundaries dense. The options formalism softens this distortion by design — termination β is precisely a hook for early exit — which is the single strongest argument for closing the loop once disturbance is the norm rather than the exception (Sutton, Precup, & Singh, 1999).
Distortion three: quality drift
The third distortion is the quality gap, and its signature is the quietest of all: plans that are valid, executable, and several percent worse than the plans the system used to produce. Section 5 computed the canonical instance — a 12.5 percent lengthening from one misaligned boundary — and the important property of that number is that it is invisible without a baseline. A macro-augmented satisficing planner under deadline pressure will still return plans; nothing in the output flags that the primitive-only planner would have interleaved the deliveries more tightly. Under a bounded-suboptimality contract, the drift is doubly sneaky, because the guarantee — cost within w of optimal — is typically proven against the macro-augmented model whose optimal cost is itself inflated by detours, so the certificate reads "within w of a worse number" (Zilberstein, 1996; Hansen & Zhou, 2007). The containment is measurement discipline: regression suites that periodically solve a fixed instance sample with macros disabled, and quality dashboards that report primitive-cost plans, not macro-step counts — the unit-cost trap of Section 8 in its operational costume. Our reading of the field evidence is that quality drift is the most under-reported distortion in practice, precisely because it fails silently while every other distortion fails loudly.
Distortion four: silent replacement
The fourth distortion is the only one that breaks correctness rather than performance, and its signature is unsolvable instances that used to solve. It occurs when macros replace base operators instead of augmenting them. Removal is sometimes motivated innocently — search-space hygiene, execution efficiency, a learned policy that "no longer needs" primitives — and it changes the reachable state space for the first time in the entire story. Two sub-mechanisms follow. Reachability loss: states and goals only reachable through interleavings that the macro set cannot express become unreachable, and completeness dies without an error message. Invariant smuggling: a lifted macro carries assumptions from its source — the bridge that existed on the training road, the corridor wide enough for the maneuver — and when the assumption fails, the macro's combined precondition holds, the body executes, and the plan walks through a world feature that does not exist. Korf's diagnosis of rote-learned macros as a weak method was, at bottom, a warning about this distortion: sequences learned by observation encode observed worlds, not the world (Korf, 1983). The containment is categorical, not incremental: base operators are never removed; if a macro-only interface is required for execution or safety reasons, it is built as a layer above a complete planner, not inside the action set — and any learned macro's preconditions are treated as claims to be verified against the domain model, a discipline that modern LLM-proposed macros make mandatory rather than optional (Kambhampati et al., 2024).
Myth vs. evidence
Myth: macro-actions make planners faster in a general, monotone way. Evidence: speedup is conditional on the compression ratio exceeding the inflation factor, holds only over the instance distribution the macros were matched to, and shrinks as heuristic guidance strengthens (Sections 4, 5, 8). Myth: a macro-augmented optimal search is still optimal, so plan quality is unaffected. Evidence: optimality survives only under the full safeguard stack — base operators retained, costs summed, admissible heuristic — and even then the safeguarded system pays the branching tax without reaping depth on badly matched instances, while any deviation from the stack silently redefines the objective or the reachable space.
The four distortions share one saving grace: all of them are measurable before deployment, on a held-out corpus, with the same instruments the utility analysis prescribes — node counts per depth, solution lengths in primitive cost, deviation-cluster statistics from simulation, and reachability checks against the macro-only action set. A deployment that instruments those four signals has, in effect, continuous coverage of the entire failure-mode catalogue; a deployment that instruments none of them is flying on folklore. The next section turns from what can go wrong to where this whole design space borders its heavier relatives — the hierarchical methods that absorb the same distortions into richer machinery.
Section 10 · Hierarchy and Time
The Boundary With Full Hierarchical Methods
Macro-actions sit at the light end of a design space whose heavy end is full hierarchy, and the boundary is best drawn with two axes rather than one. The first axis is context conditioning: does the temporally abstract action know anything about the state in which it is invoked beyond a Boolean precondition? The second is closed-loop control: once started, can the action's body observe and react? Plain macros score zero on both — one fixed sequence, one precondition, no internal sensing. Everything richer in the hierarchical toolbox is a way of raising one or the other score, and the four major stations along the way are worth walking in order.
HTN methods: context-conditioned bundles
A hierarchical task network replaces an abstract task with a network of subtasks by applying a method — a recipe whose applicability is conditioned on the current state, and whose expansion can be a partial order with inserted constraints rather than a fixed linear sequence (Erol, Hendler, & Nau, 1994). In macro terms, a method is a family of context-conditioned macros with a selection rule: the planner commits not to one body but to a decomposition chosen from the bodies the method offers for the state at hand. SHOP2 made this operational at scale by decomposing in forward state-space order — the method applied is always chosen against the state that will actually hold when its subtasks run, which eliminates a whole class of decomposition-soundness bugs and made the approach the engine of choice for knowledge-rich applications (Nau et al., 2003). The expressiveness bill arrives with the conditioning: HTN methods can encode behaviors that flat planning cannot express compactly at all, and the complexity landscape shifts accordingly — where flat propositional planning is PSPACE-complete (Bylander, 1994), the general HTN planning problem crosses into undecidability, because method sets can simulate arbitrary computation in their decomposition structure (Erol, Hendler, & Nau, 1994). Practical HTN use stays well inside the decidable region, but the boundary is real, and it is the formal signature of what conditioning buys and costs. The dedicated long view of HTN practice — authoring, brittleness, the knowledge-engineering bargain — is Hierarchical Task Networks as Domain-Knowledge Encodings: The Long View.
Options: closed-loop bundles
Options raise the other axis. An option's body is a policy — a reactive program — so the bundle observes and adapts while it runs, and its termination condition is itself state-dependent (Sutton, Precup, & Singh, 1999). Two consequences matter for the boundary. First, the locked-body distortion of Section 9 dissolves: an option can exit early when the world surprises it, which is why the options framework is the natural home for macro-like behavior in stochastic domains. Second, the value machinery changes character: with closed-loop bodies, the semi-MDP equations of Section 3 are not just bookkeeping but the substrate for a family of learning algorithms — intra-option methods that credit the option's internal policy, and decompositions like MAXQ that expose per-subtask value functions and the state abstractions they license (Dietterich, 2000; Precup, 2000). The expert-level treatment of options as search primitives — how they enter sampling-based search, what their guarantees are, where they fail — is Options as Search Primitives for Hierarchical Planning: The Expert View.
Angelic bounds: knowing when to trust the bundle
The boundary's most intellectually interesting crossing is neither conditioning nor looping but certification. The idea, developed in the hierarchical-planning literature and presented in standard texts as the angelic-semantics treatment of hierarchical look-ahead, is to annotate each temporally abstract action with sound bounds on what it can achieve — an optimistic and a pessimistic reachable-outcome set (Russell & Norvig, 2020). With such bounds, a planner can reason about a macro's consequences without unfolding its body, and — the striking part — can sometimes prove that a plan containing macros is optimal, because the optimistic bound certifies that no unfolding could do better. Angelic annotation inverts the usual epistemics of this article: instead of measuring macro utility empirically and worrying about distortion, the designer supplies guarantees that make the distortion impossible. The price is that bounds must be sound, which is exactly the kind of claim that requires either a tractable body semantics or human care — and the reason the technique is standard in expositions but rare in automatically constructed macro libraries. Our reading is that angelic semantics is the concept practitioners should reach for whenever they find themselves wanting to trust a macro set in a safety-relevant loop: it converts the trust question from an empirical correlation into a checkable proof obligation.
Neighbors on the time axis
Two further neighbors complete the map, both treated elsewhere in the cluster. Durative actions occupy time as a first-class quantity: PDDL2.1 actions have durations, conditions checked over intervals, and effects at interval endpoints, so the "bundle" is not a sequence of instantaneous steps but a genuinely temporal object, and concurrency between overlapping actions becomes the central planning question (Fox & Long, 2003). Macros over instantaneous actions are the discretized shadow of this idea, and the full treatment of deadlines and temporal goals lives in Temporal Planning With Durative Actions and Deadline Goals: What to Do. Goal networks organize decomposition around goal achievement rather than task recipes — the planner maintains a network of open goals and selects decomposition strategies against it — and the strategic questions that arise there are covered in Goal-Network Decomposition Strategies in Hierarchical Search. Table 3 fixes the whole neighborhood side by side, and Figure 5 places the stations on the two axes.
| Approach | Body | Context condition | Loop | Dominant risk |
|---|---|---|---|---|
| Ground macro | fixed operator sequence | combined precondition only | open | branching tax; boundary misalignment |
| Parameterized macro | lifted sequence over variables | precondition schema | open | invariant smuggling from the source plan |
| HTN method | task network, possibly partial order | state-conditioned method selection | mostly open | authoring brittleness; undecidability at full power |
| Option | internal policy πo with termination βo | initiation set Io | closed | duration-accounting errors; opaque learned bodies |
| Durative action | interval with duration, conditions, end effects | conditions over the interval | open (sensing modeled separately) | concurrency and resource interactions |
Table 3. The neighborhood of temporally abstract actions. Basis: qualitative synthesis of the cited formal treatments (Erol, Hendler, & Nau, 1994; Sutton, Precup, & Singh, 1999; Dietterich, 2000; Fox & Long, 2003; Nau et al., 2003); no empirical quantities are compared.
The boundary view also settles a question practitioners ask constantly: when should a macro project graduate to a hierarchy project? The two-axis map gives a two-signal answer. Graduate on the conditioning axis when the macro library starts accreting selection logic — wrappers that inspect state and pick among variants, guard conditions multiplying at call sites — because that is a method set reinvented badly, and HTN machinery manages it properly (Erol, Hendler, & Nau, 1994; Nau et al., 2003). Graduate on the control axis when the locked-body distortion dominates field reports — deviations clustering at bundle boundaries, repair episodes growing severe — because that is the symptom the option's closed loop exists to cure (Sutton, Precup, & Singh, 1999). And stay at the macro layer, deliberately, when neither signal appears: full hierarchy buys expressiveness and resilience at the price of authoring burden and analysis opacity, and a well-audited macro library on a flat planner remains one of the best cost-to-benefit trades in the field.
Read more about Hierarchical Task Networks as Domain-Knowledge Encodings: The Long View and Options as Search Primitives for Hierarchical Planning: The Expert View — the cluster articles that develop both heavy ends of this boundary.
Section 11 · Hierarchy and Time
Engineering Practice: A Deployer's Guide
The analysis of the preceding sections compresses into practice as a sequence of decisions, and this section states them as a guide: when to bundle, what safeguards to install, what to measure, and how to budget. The guide is our synthesis — the field's results, arranged as deployment decisions — and where a rule rests on a cited result rather than on our judgment, the citation travels with it.
Deciding to bundle at all
Bundle when at least one of four signals is present, and treat the absence of all four as a decision against macros. The first signal is long mandatory fragments: passages of the domain that every solution must traverse in nearly fixed form, like the courier family's driving. These raise compression at minimal risk because the flat planner's freedom inside them is freedom it never uses. The second is an operational vocabulary: if the humans around the system already speak in multi-step units — rover activities, surgical phases, warehouse pick-waves — then aligning the action set with that vocabulary buys interface value that no speedup measurement captures (Ai-Chang et al., 2004). The third is a tick budget: when decisions must arrive within a wall-clock or cycle budget, the depth axis is the binding constraint, and macros attack it directly — this is the anytime-search regime, where solution quality is traded against deliberation time and the trade is managed explicitly (Dean & Boddy, 1988; Zilberstein, 1996). The fourth is learning pressure: if the system learns its behavior from data, temporally extended actions are the representation through which sample-efficient credit assignment across long horizons arrives at all (Dietterich, 2000; Sutton, Precup, & Singh, 1999). Against these, weigh the counter-signals: strong heuristic guidance already exploiting the same structure, cheap routine replanning that penalizes locked bodies, and safety cases that cannot tolerate uncertified bundles.
The safeguard stack
Every failure mode in Section 9 maps to a safeguard, and the safeguards compose into a stack worth stating once, in order:
- Augment, never replace. Base operators stay in the action set; macro-only interfaces are built above the planner, not inside it. This single rule contains reachability loss, the only correctness-breaking distortion.
- Sum the costs. Macro cost equals the sum of constituents; objectives, reports, and dashboards count primitive cost. This preserves admissibility and kills the unit-cost trap (Hart, Nilsson, & Raphael, 1968).
- Label provenance. Every macro records its channel, evidence, and validation history, so post-incident audits can ask what a failing macro was believed to encode and why.
- Verify learned preconditions. Macros from mining, lifting, or language-model proposals have assumptions, not facts; treat their preconditions as claims against the domain model (Korf, 1983; Kambhampati et al., 2024).
- Account durations exactly. In stochastic deployments, carry the duration distribution — E[γτ], never γE[τ] — and pin termination to state structure wherever the domain permits (Sutton, Precup, & Singh, 1999).
Measuring: the four-signal dashboard
The instrumentation follows the distortion catalogue one-for-one. Nodes per depth level, compared with the macro-free baseline on a fixed corpus, tracks branching inflation; it should be computed periodically because library accretion shifts it silently. Plan cost in primitive units, again against the primitive-only baseline, tracks quality drift; the comparison must run on instances the macro set covers well and on instances it covers badly, because Section 5's configuration D is invisible on friendly instances alone. Deviation cluster statistics from simulation — the spacing and severity of execution deviations — tracks the locked-body distortion, and a shift of deviations from isolated single steps to clustered multi-step bundles is the direct observable of over-bundling. Coverage ratio — the fraction of corpus solution steps absorbed by macros — is the leading indicator for all of the above, because compression c is the quantity every other signal depends on. Deployments that can afford only one instrument should instrument coverage, on a held-out corpus, refreshed as the instance distribution drifts. The metareasoning frame gives the budgeting principle behind all four: measurement spends computation to buy information about which computations to spend on, and the same value-of-computation logic that justifies metareasoning justifies the dashboard (Russell & Wefald, 1991).
Sizing the library
Sizing follows the marginal-utility principle that the utility inequality makes precise: each additional macro must raise expected compression by more than the inflation its branching adds, over the deployment distribution, in combination with the heuristic actually in use. Three operational rules fall out. First, run the ablation grid — macro subsets crossed with heuristic settings — on the training corpus at least once per library revision; the interaction documented in Section 8 means single-factor evaluations misprice macros systematically. Second, prefer few long, boundary-aligned macros to many short ones: under any coverage below roughly two-thirds, short macros are net negative in the stylized model, and the model's pessimism about applicability gating is the only force that can save them. Third, prune by dominance regularly: a macro whose body is simulated at equal cost by an existing macro plus base operators is pure branching tax, and the dominance machinery of state-space search transfers directly to this audit. In sampling-based deployments, the same sizing logic appears as the widening schedule — how many macro children to expand per node — and that knob has its own dedicated field guide in Progressive Widening for Enormous Branching Factors: The State of the Play.
Deployment archetypes
Four archetypes cover most real deployments, and each pairs the macro decision with its characteristic discipline. The mixed-initiative operations desk — the rover pattern — treats the macro vocabulary as shared human-machine interface: domain experts and planners co-refine it, so the discipline is version control and review of vocabulary changes, and the payoff is legibility as much as speed (Ai-Chang et al., 2004). The embedded real-time controller treats macros as a depth-budget device: the discipline is worst-case tick timing, and the risk concentration is the locked-body distortion under disturbance, which argues for short bodies with dense boundaries and for closed-loop options once sensing is available (Dean & Boddy, 1988; Zilberstein, 1996). The learning stack treats options as representation: the discipline is exact duration accounting and termination design, with value-neutrality checks on deterministic probes as a regression test (Bacon, Harb, & Precup, 2017). And the procedure-execution engine treats the macro library as an acting vocabulary of procedures, where selection among procedures replaces plan synthesis for routine work, and planning proper is invoked only for the residual (Ghallab, Nau, & Traverso, 2016). The archetypes are not exclusive — a deployed system often contains all four — but naming them keeps the safeguards attached to the risks that actually materialize in each.
A final word on people. Every archetype above involves humans who read, adjust, approve, or repair plans, and the macro layer is where those humans meet the machine. The craft of that meeting — how refinement responsibility is divided, how vocabulary changes are negotiated, how trust in bundles is calibrated and earned — is its own discipline, treated in Mixed-Initiative Plan Refinement Between People and Planners, and the time-budget side of the same deployments is covered in Online Replanning Budgets in Time-Constrained Deployments: In Practice. Our reading of the deployment literature is unambiguous on one point: the macro layer's greatest production value has usually been interface alignment, with search speedup as the bonus — a conclusion that the benchmarking tradition, which measures only the bonus, systematically underprices.
Read more about Goal-Network Decomposition Strategies in Hierarchical Search and Temporal Planning With Durative Actions and Deadline Goals: What to Do — the cluster articles covering the two directions in which macro layers most often grow.
Section 12 · Hierarchy and Time
A Short History: From MACROPs to Options and Back
The history of macro-actions is a history of one idea being rediscovered roughly once a decade, in a formalism suited to whatever the decade's dominant problem happened to be. Telling it straight is useful precisely because the rediscoveries are not redundant: each pass added a mechanism — lifting, then conditioning, then closing the loop, then learning the bundle itself — and the additions accumulate into the design space of Section 10.
The symbolic decades
The prehistory is the General Problem Solver, whose methods — packaged procedures selected by means-ends analysis — already embodied the claim that problem solving proceeds at the granularity of reusable routines rather than atomic moves (Newell, Shaw, & Simon, 1959). The first true macro-action arrived with STRIPS: its designers, having watched the system labor through long primitive sequences, gave it the ability to generalize its own solutions into stored MACROPs — the first learned macros, and the origin of the filter construction this article formalized in Section 3 (Fikes & Nilsson, 1971). The 1970s took the opposite fork: rather than bundling actions, Sacerdoti's hierarchy of abstraction spaces suppressed problem detail at coarse levels and refined it back in, and his NOAH system along with Tate's NONLIN developed the plan-structure view of hierarchy — partial-order networks of steps with explicit interactions — that still underlies HTN practice (Sacerdoti, 1974, 1975; Tate, 1977). The fork mattered: the macro line kept flat planners and changed the action set; the hierarchy line changed the planner and kept, in effect, an open action space. Every later development, including the options synthesis, is a negotiation between those two inheritances.
The 1980s belong to Korf, twice. His macro-operator analysis gave the learning question its first sober answer — macros are a weak method, rote-acquired and weakly transferring — and thereby set the epistemic standard every later macro-learning system had to meet (Korf, 1983). And his analysis of iterative deepening made the depth term of search cost explicit, giving the macro rationale its quantitative footing: if effort grows exponentially in depth, then shortening depth is the game (Korf, 1985). The 1990s formalized the hierarchy fork: Erol, Hendler, and Nau's complexity results gave HTN planning its expressiveness theory, including the undecidability boundary that conditioning eventually crosses (Erol, Hendler, & Nau, 1994), and the decision-theoretic planning survey of the decade reframed the whole enterprise — hierarchy included — as the exchange of structural assumptions for computational leverage (Boutilier, Dean, & Hanks, 1999). Meanwhile the time-pressure line matured in parallel: time-dependent planning and anytime computation established the quality-versus-time frontier on which macros later traded (Dean & Boddy, 1988; Zilberstein, 1996).
The stochastic synthesis and the heuristic-search era
The turn of the millennium produced the synthesis this article's formalism rests on. Casting temporally extended actions as options over semi-Markov decision processes, Sutton, Precup, and Singh unified the deterministic macro and the stochastic skill under one Bellman discipline, with termination conditions and intra-option credit assignment as first-class objects (Sutton, Precup, & Singh, 1999; Precup, 2000). Dietterich's MAXQ decomposition demonstrated the same machinery from the value-function side, showing that hierarchy could be analyzed as a decomposition of value rather than merely a compilation of behavior (Dietterich, 2000). At the same moment, the deterministic side was being transformed by heuristic search — planning-as-heuristic-search, FF's relaxed-plan machinery — and the two threads met in the macro-learning systems of the mid-2000s: Macro-FF's mine-filter-validate pipeline (Botea, Enzenberger, Müller, & Schaeffer, 2005), and the automatic macro generation that entered mainstream domain-independent pipelines with Fast Downward (Helmert, 2006). It is worth pausing on the simultaneity: the same decade produced the formal object (the option), the value theory (MAXQ), and the deployed tooling (macro-augmented heuristic planners) — and the three communities barely cited each other at first. Much of this article's argument is that they were solving the same inequality.
The learning decades and the return of proposals
The 2010s moved the frontier from searching with macros to learning them. Deep reinforcement learning at scale demonstrated control from pixels, and its hardest practical problem was exactly the timescale problem — credit assignment across hundreds of primitive decisions — which the options and MAXQ machinery had been built to address (Mnih et al., 2015; Sutton & Barto, 2018). The option-critic architecture delivered the missing differentiable path, learning policies and terminations jointly (Bacon, Harb, & Precup, 2017), and latent-model planners demonstrated that planning itself could run at a learned, coarse granularity inside a representation rather than over an engineered state space (Schrittwieser et al., 2020). The 2020s closed the loop back to proposals: large language models emit macro-shaped behavior in natural language — plausible procedures, plausible orderings — reviving, at civilization scale, exactly the question STRIPS faced in 1971: what does it take to trust a bundled sequence you did not verify? The answer the field has converged on — treat proposals as candidates, verify against a model, keep the base actions available — is the LLM-Modulo pattern, and its planning-side evidence and failure modes are documented in the citation base of this series (Huang, Abbeel, Pathak, & Mordatch, 2022; Kambhampati et al., 2024).
The arc, compressed: 1959 packaged human routines; 1971 learned them; 1974 suppressed detail instead; 1983 measured their transfer; 1999 closed their loop; 2005 mined them at scale; 2017 learned their bodies end to end; 2022 received them as proposals from a language model. Each step answered a question the previous step exposed, and none of them changed the underlying arithmetic — depth is exponential, bundling trades depth for branching, and the trade is only as good as its match to the solution distribution. That persistence is the strongest evidence that the subject is not a chapter of planning history but a permanent design dimension of sequential decision-making.
Read more about Large Language Models as Plan Proposers and Their Failure Modes and Unifying Learning and Symbolic Planning at Scale: The Nuance That Counts — the cluster articles covering the proposal sources and the learning–symbolic synthesis that define the current frontier of the macro story.
Section 13 · Hierarchy and Time
Open Problems and the Road Ahead
The article closes with the questions the preceding sections leave genuinely open — labeled as open, not smuggled toward a verdict. Six of them, in our ordering of practical weight.
Estimating compression before deployment
The deepest gap between theory and practice is that the utility inequality's key quantity — the compression ratio c over the deployment distribution — is measurable only after solving instances, which is to say only after the computation the macros were supposed to save. An ex-ante estimator of c, even a conservative one, would convert macro-set selection from empirical loop into a calculation. The bandit literature offers one promising frame — selecting which macros to activate as an exploration problem with finite-time guarantees on the cost of learning (Auer, Cesa-Bianchi, & Fischer, 2002) — and the focused-sweep insight of real-time dynamic programming offers another: estimate c only along the solution distribution the current policy actually visits, not across the whole state space (Barto, Bradtke, & Singh, 1995). Both are frames, not solutions; the open problem is an estimator with a stated error bound, and it is open.
Certification for constructed macros
Angelic bounds make macros trustworthy when a human supplies sound annotations; automatic libraries have no equivalent. The natural research program — derive optimistic and pessimistic outcome bounds from the macro body's operator semantics automatically, then search against the bounds — is easy to state and hard to execute, because the bounds must remain sound under lifting and under learned, stochastic bodies. The verifier-loop perspective, in which machine-generated candidates are checked against a trusted model before use, is the operational version of the same demand, and its trade-offs have their own treatment in Verifier Loops Around Machine-Generated Candidate Plans: Key Trade-offs (Kambhampati et al., 2024). Open, and newly urgent as language-model proposals flood the candidate space.
The structural theory gap
Compilability results establish that macros change nothing in expressive power or worst-case complexity (Bylander, 1994; Nebel, 2000). What no theorem establishes is a structural characterization of the domains and macro families for which macro-augmented search is provably polynomially cheaper — the qualitative folklore says "domains with long mandatory sequences," and nothing formal replaces the folklore. A characterization would tell macro-mining systems what to look for, the way the landmark theory tells heuristic extraction what to look for (Helmert & Domshlak, 2009). Until it exists, macro practice runs on measurement where it would prefer to run on mathematics.
Adaptive macro activation
Deployed libraries are static: every macro is available everywhere, paying its branching tax at every applicable node whether or not the current instance will use it. Search-time adaptation — activating macros by predicted relevance, gating on learned coverage estimates, widening the action set only where compression is likely — would concentrate the benefit and dilute the tax. The sampling community already manages branching adaptively through widening schedules; transferring that discipline to deterministic and semi-Markov search, with guarantees, is open (Kocsis & Szepesvári, 2006; Browne et al., 2012).
Risk, duration, and objective design
Almost everything in this article assumed expected discounted return as the objective, and macros interact with every alternative. Risk-sensitive objectives concentrate value nonlinearly over trajectories, and a macro that spans a risk event changes when the risk is even observed — the classical risk-sensitive MDP formalism exists, but its interaction with temporal abstraction is barely mapped (Howard & Matheson, 1972; Chow & Ghavamzadeh, 2014). Chance constraints and deadlines similarly bind at bundle boundaries rather than inside them. The open problem is a design theory that treats the macro set, the discount, the termination conditions, and the objective as one joint object rather than four separate dial-turns (Sutton, Precup, & Singh, 1999).
Valuing the interface
The quietest open problem is measurement-theoretic: the deployment evidence suggests macro layers create much of their value as human interfaces — legibility, auditability, mixed-initiative negotiability — and the evaluation tradition measures only solve-time and plan length, neither of which prices those properties (Ai-Chang et al., 2004). Quality metrics beyond path length are being developed elsewhere in this cluster, notably in Plan-Quality Metrics Beyond Path Length and Action Cost: A Careful Read, but a measurement standard for interface value — the worth of a plan a human can actually read and correct — remains open, and until it exists, the field will keep systematically underpricing its own most successful tool.
Section 14 · Hierarchy and Time
Frequently Asked Questions
What exactly is a macro-action, and how does it differ from an HTN method or an option?
A macro-action is a bundle of primitive actions treated as a single choosable action. In its plainest form it is a fixed operator sequence with a derived combined precondition, added to the planner's action set (Fikes & Nilsson, 1971). An HTN method generalizes the idea along the context axis: it replaces an abstract task with a network of subtasks, selected by the state in which decomposition happens, which is why HTNs can express more and cost more — up to undecidability of general plan existence (Erol, Hendler, & Nau, 1994). An option generalizes along the control axis: its body is an internal policy with a termination condition, so it senses and reacts while running, and its evaluation runs over the semi-Markov decision process (Sutton, Precup, & Singh, 1999). A plain macro is the degenerate option with a deterministic body and fixed-length termination. In practice: macros augment a flat planner; methods build a hierarchical one; options close the loop in stochastic settings.
Do macro-actions ever make plans worse?
Yes, through two mechanisms. First, forced detours: a macro body is a fixed sequence, so using it where a shorter interleaving exists pins the plan to the macro's route — our illustrative courier computation showed one misaligned boundary lengthening a plan from 24 to 27 primitive actions, a 12.5 percent loss. Second, silent objective redefinition: if macro steps are counted as single actions under unit costs, the objective itself changes scale and optimality guarantees evaporate. Under the safeguard stack — base operators retained, macro costs summed, admissible heuristic — optimality is preserved, but the planner then pays the branching tax on instances where macros buy no depth, so it can be slower without ever being wrong. Quality drift is the failure mode to watch precisely because it is silent: plans remain valid while becoming several percent worse than the primitive-only baseline, which is why Section 11 prescribes periodic macro-free regression runs.
Where do macro-actions sit in the pillar's three-axes frame of uncertainty representation × objective × computation budget?
Macros are primarily a computation-budget instrument: they change how much computation a plan of given quality costs, by trading search depth for branching factor. Their side effects reach the other two axes. On the uncertainty axis, an open-loop macro bundle cannot react to disturbances inside its body, so the representation of uncertainty effectively coarsens to bundle boundaries — the closed-loop option exists precisely to repair this (Sutton, Precup, & Singh, 1999). On the objective axis, macros change when costs and risk events are observed: a risk event spanned by a bundle is observed only at its end, so risk-sensitive objectives, deadlines, and chance constraints bind at macro boundaries rather than inside them (Howard & Matheson, 1972). A designer who moves along the budget axis alone should therefore expect consequences on the other two — the frame's point is that the three move together.
Can macro-actions be learned automatically, and can the results be trusted?
They can be learned, with channel-dependent trust. Plan mining extracts frequent fragments from solved corpora and validates candidates by re-solving the training set, the Macro-FF pattern (Botea, Enzenberger, Müller, & Schaeffer, 2005); its blind spot is distribution shift, since validation measures coverage on the training world only. Domain analysis derives macros from compiled domain structure without seeing any instance (Helmert, 2006); it cannot overfit instances but can misread structure. Reinforcement learning can learn option bodies and termination functions end to end (Bacon, Harb, & Precup, 2017), but learned macros are opaque — no inspectable precondition, no auditable boundary alignment. Language models add a proposal channel whose output requires explicit verification against a domain model (Kambhampati et al., 2024). Trust protocol regardless of channel: keep base operators available, treat learned preconditions as claims, and record provenance so failures can be traced to evidence.
How do macro-actions interact with heuristic functions?
Three interactions dominate. Admissibility survives intact if macro costs are the sum of constituents and base operators remain available, because the augmented search graph merely adds shortcut edges of honestly accounted cost (Hart, Nilsson, & Raphael, 1968). Visibility changes: heuristics are evaluated only at macro endpoints, so intermediate states — where relaxed heuristics can be pathologically wrong and where helpful-action pruning operates (Hoffmann & Nebel, 2001) — are never consulted, which removes some noise but also hides transient deletes and landmark structure (Helmert & Domshlak, 2009). And guidance competes: a strong heuristic already exploits the structure macros encode, shrinking the room in which macros pay — which is why macro evaluations must be run as ablations over the macro set and the heuristic jointly, not one factor at a time. The design rule with the best return: align macro boundaries with landmark boundaries, so the bundle's milestones coincide with the guidance machinery's.
Should macros replace the base action set once they prove their worth?
No, and the reasons are structural rather than cautious. Removing base operators changes the reachable state space — the only macro decision that does — so states reachable solely through interleavings the macro set cannot express become unreachable, and completeness fails silently. Lifted macros additionally carry assumptions from their source plans, so a removed primitive can hide behind a macro whose precondition still holds while its world assumption does not, the invariant-smuggling failure (Korf, 1983). Everything else in macro practice — branching taxes, detours, locked bodies — degrades performance; replacement degrades correctness. If an execution interface must expose only composite actions, build it as a layer above a complete planner rather than inside the action set, and verify any learned macro's preconditions against the domain model before it enters the loop (Kambhampati et al., 2024). Augment, never replace, is the categorical rule.
How do macro-actions relate to durative actions in temporal planning?
They are cousins on the time axis with different ontologies. A macro occupies no time of its own: its duration is exactly the sum of its constituents' durations, and its internal structure is a discrete sequence of instantaneous events. A durative action in PDDL2.1 genuinely occupies an interval, with conditions checked over the interval's span and effects at its endpoints, so overlapping executions, concurrency, and resource profiles become first-class planning concerns (Fox & Long, 2003). A macro over instantaneous actions is best read as the discretized shadow of a durative activity: bundling approximates what duration represents exactly. In deployments the two compose — a temporal planner can carry macros over durative actions, with costs summed over the constituent durations — but the accounting discipline carries over unchanged: durations and costs are summed, never averaged, and deadlines attach to the primitive timeline rather than the macro-step count.
What is the honest evidence that macro-actions speed up search in practice?
Conditional and distribution-bound, which is the honest summary. Automated macro pipelines of the Macro-FF type validated their libraries by re-solving training corpora with and without macros, demonstrating gains on matched distributions (Botea, Enzenberger, Müller, & Schaeffer, 2005), and automatic macro generation entered competition-grade systems (Helmert, 2006). The theory explains both the gains and their fragility: speedup requires the compression ratio to exceed the inflation factor over the instance distribution actually encountered, so half-covered or shifted distributions flip the sign, as our worked configuration D exhibits. Two further qualifications matter. Gains shrink as heuristic guidance strengthens, because both exploit the same structure. And solve-time benchmarks underprice the interface value that deployments report as the macro layer's main production benefit — legibility and mixed-initiative negotiability (Ai-Chang et al., 2004). Evidence supports macros as a matched-distribution tool with human-interface upside, not a universal accelerant.
Section 15 · Hierarchy and Time
Conclusion: Macros as a Search-Space Instrument
This article set out to treat macro-actions as an engineering instrument rather than a slogan, and the treatment reduces to a small set of load-bearing statements. As fact: bundling actions into composite choices shortens decision sequences and lengthens branching, leaves reachable states and worst-case complexity untouched, and — under exact accounting in deterministic settings — leaves the optimal value function unchanged, so every flat-to-macro gain is computational, not decision-theoretic (Sutton, Precup, & Singh, 1999; Nebel, 2000). As interpretation, ours and labeled as such: the utility inequality c > i organizes when bigger steps pay; the four distortions name how they hurt when they do not; and the supply channels differ mainly in the evidence they carry and the failure they invite. As open problems: ex-ante compression estimation, automatic certification, a structural theory of macro-friendly domains, adaptive activation, joint objective-duration design, and the measurement of interface value all remain genuinely unsettled.
Two claims deserve restatement because they run against the field's folklore. The first is that macros and heuristics compete for the same underlying structure, so their benefits are not additive in general — the most common silent disappointment in macro deployments is a strong heuristic quietly absorbing the structure the macros were counting on. The second is that the heaviest measured value of macro layers in deployed systems has been interface alignment with human operators, a benefit the benchmarking tradition prices at zero (Ai-Chang et al., 2004; Ghallab, Nau, & Traverso, 2016). Both claims are readings of the cited evidence rather than theorems, and both are testable by the dashboard of Section 11 — which is the posture this series prefers: strong claims, attached instruments.
The boundary picture is the article's final gift to a practitioner deciding where to invest. Macro-actions are the lightest form of temporal abstraction; HTN conditioning, option looping, and angelic certification each add capability and cost in a specific direction, and the two-axis map of Section 10 turns "should we go hierarchical?" from an identity question into a coordinate question. The graduation signals — selection logic accreting around macros, deviations clustering at bundle boundaries — are observable in production telemetry before they become incidents. Between the courier arithmetic of Section 5 and the design space of Section 10, the practical middle of temporal abstraction is, we contend, now mapped: bigger steps are a permanent, budget-axis instrument of sequential decision-making, and the craft lies in paying for them only where the solution distribution is willing to sell depth.
About this article · research transparency
This cluster article is a secondary synthesis of published research; no original experiments were run and no firsthand deployment claims are made. All worked numbers are labeled illustrative and computed from stated formulas, with figure bases declared in every caption. The compression-versus-inflation model, the four-distortion catalogue, the two-axis boundary map, and the deployer's guide are editorial syntheses owned by the SciXa Research Desk. Limitations: coverage privileges the classical-planning and reinforcement-learning literatures over game-playing and control-theory treatments of temporal abstraction; option-discovery research beyond the option-critic line is cited only qualitatively; the Fast Downward and Macro-FF descriptions compress system details; and two moving subfields — learned planners and language-model proposal loops — were current only to the series' editorial date.
Section 16 · References
References
Citations follow an APA-style condensed format, alphabetized by first author; where page ranges or DOIs could not be verified, they are omitted rather than approximated.
Ai-Chang, M., et al. (2004). MAPGEN: Mixed-initiative planning and scheduling for the Mars Exploration Rovers. IEEE Intelligent Systems, 19(1).
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3), 235–256.
Bacon, P.-L., Harb, J., & Precup, D. (2017). The option-critic architecture. In Proceedings of the Sixteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017).
Barto, A. G., Bradtke, S. J., & Singh, S. P. (1995). Learning to act using real-time dynamic programming. Artificial Intelligence, 72(1–2), 81–138.
Bellman, R. (1957). Dynamic programming. Princeton University Press.
Bonet, B., & Geffner, H. (2001). Planning as heuristic search. Artificial Intelligence, 129(1–2), 5–33.
Botea, A., Enzenberger, M., Müller, M., & Schaeffer, J. (2005). Macro-FF: Improving AI planners with automated macros. Journal of Artificial Intelligence Research.
Boutilier, C., Dean, T., & Hanks, S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11, 1–94.
Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., & Colton, S. (2012). A survey of Monte Carlo tree search algorithms. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1–43.
Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1–2), 165–204.
Chow, Y., & Ghavamzadeh, M. (2014). Algorithms for CVaR optimization in Markov decision processes. In Advances in Neural Information Processing Systems 27 (NIPS 2014).
Culberson, J. C., & Schaeffer, J. (1998). Pattern databases. Computational Intelligence, 14(4), 318–334.
Dean, T., & Boddy, M. (1988). An analysis of time-dependent planning. In Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI-88).
Dietterich, T. G. (2000). Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13, 227–303.
Edelkamp, S., & Schrödl, S. (2012). Heuristic search: Theory and applications. Morgan Kaufmann / Elsevier.
Erol, K., Hendler, J., & Nau, D. S. (1994). HTN planning: Complexity and expressivity. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94).
Felner, A., Korf, R. E., & Hanan, S. (2004). Additive pattern database heuristics. Journal of Artificial Intelligence Research, 22.
Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3–4), 189–208.
Fox, M., & Long, D. (2003). PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 20, 61–124.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated planning: Theory and practice. Morgan Kaufmann.
Ghallab, M., Nau, D., & Traverso, P. (2016). Automated planning and acting. Cambridge University Press.
Hansen, E. A., & Zhou, R. (2007). Anytime heuristic search. Journal of Artificial Intelligence Research, 28, 267–297.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
Haslum, P., Botea, A., Helmert, M., Bonet, B., & Koenig, S. (2007). Domain-independent construction of pattern database heuristics for cost-optimal planning. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07).
Helmert, M. (2006). The Fast Downward planning system. Journal of Artificial Intelligence Research, 26, 191–246.
Helmert, M., & Domshlak, C. (2009). Landmarks, critical paths and abstractions: What's the difference anyway? In Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS 2009).
Hoffmann, J., & Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14, 253–302.
Howard, R. A., & Matheson, J. E. (1972). Risk-sensitive Markov decision processes. Management Science, 18(7), 356–369.
Huang, W., Abbeel, P., Pathak, D., & Mordatch, I. (2022). Language models as zero-shot planners. arXiv preprint.
Kambhampati, S., Valmeekam, K., Bhatt, V., et al. (2024). LLMs can't plan, but can help planning in LLM-Modulo frameworks. In Proceedings of the 41st International Conference on Machine Learning (ICML 2024).
Kearns, M., Mansour, Y., & Ng, A. Y. (2002). A sparse sampling algorithm for near-optimal control in large Markov decision processes. Machine Learning, 49(2–3), 193–208.
Kocsis, L., & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In Proceedings of the 17th European Conference on Machine Learning (ECML 2006).
Korf, R. E. (1983). Macro-operators: A weak method for learning. In Proceedings of the Third National Conference on Artificial Intelligence (AAAI-83).
Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97–109.
Madani, O., Hanks, S., & Condon, A. (1999). On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems. In Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99).
McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D., & Wilkins, D. (1998). PDDL — The Planning Problem Domain Language (Version 1.2). Technical Report CVC TR-98-003, Yale Center for Computational Vision and Control.
Mnih, V., Kavukcuoglu, K., Silver, D., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529–533.
Nau, D., Au, T.-C., Ilghami, O., Kuter, U., Murdock, W., Wu, D., & Yaman, F. (2003). SHOP2: An HTN planning system. Journal of Artificial Intelligence Research, 20, 379–404.
Nebel, B. (2000). On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence Research, 12.
Newell, A., Shaw, J. C., & Simon, H. A. (1959). Report on a general problem solving program. In Proceedings of the International Conference on Information Processing (ICIP 1959).
Papadimitriou, C. H., & Tsitsiklis, J. N. (1987). The complexity of Markov decision processes. Mathematics of Operations Research, 12(3), 441–450.
Precup, D. (2000). Temporal abstraction in reinforcement learning. Doctoral dissertation, University of Massachusetts Amherst.
Puterman, M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons.
Russell, S., & Norvig, P. (2020). Artificial intelligence: A modern approach (4th ed.). Pearson.
Russell, S., & Wefald, E. (1991). Principles of metareasoning. Artificial Intelligence, 49(1–3), 361–395.
Sacerdoti, E. D. (1974). Planning in a hierarchy of abstraction spaces. Artificial Intelligence, 5(2), 115–135.
Sacerdoti, E. D. (1975). The nonlinear nature of plans. In Proceedings of the Fourth International Joint Conference on Artificial Intelligence (IJCAI-75).
Schrittwieser, J., Antonoglou, I., Hubert, T., et al. (2020). Mastering Atari, Go, chess and shogi by planning in a latent model. Nature, 588(7839), 604–609.
Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). MIT Press.
Sutton, R. S., Precup, D., & Singh, S. (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1–2), 181–211.
Tate, A. (1977). Generating project networks. In Proceedings of the Fifth International Joint Conference on Artificial Intelligence (IJCAI-77).
Zilberstein, S. (1996). Using anytime algorithms in intelligent systems. AI Magazine, 17(3), 73–83.