Source-linked AI summary
Marvin: A Heuristic Search Planner with Online Macro-Action Learning
A. I. Coles, A. J. Smith
TL;DR
Plateau escape in Enforced Hill-Climbing can require expensive exhaustive search. Marvin learns action-sequence macro-actions during planning and uses them in search; reported benefits vary across domains, including reduced execution time and, sometimes, increased plan makespan.
Problem
Enforced Hill-Climbing can spend prolonged periods in exhaustive search when its heuristic cannot guide the planner off a plateau.
Source: §2.3 · p. 3Method
Results
Marvin substantially improves planner performance in Philosophers and improves execution time in Philosophers, Depots, Driverlog, Pipestankage-nontemporal, and Satellite, sometimes at the expense of makespan.
Source: §8 · p. 36Takeaways & Limitations
Reusing plateau-escaping sequences can avoid expensive exhaustive searches when similar plateaux recur.
Source: §1 · p. 1Learned sequences can be situation-specific, and unproductive macros can enlarge the search space; the reported competition evaluation used isolated problem instances without cross-problem learning.
Source: §3.4 · p. 12, §6 · p. 20
Abstract
from arXiv · showhide
This paper describes Marvin, a planner that competed in the Fourth International Planning Competition (IPC 4). Marvin uses action-sequence-memoisation techniques to generate macro-actions, which are then used during search for a solution plan. We provide an overview of its architecture and search behaviour, detailing the algorithms used. We also empirically demonstrate the effectiveness of its features in various planning domains; in particular, the effects on performance due to the use of macro-actions, the novel features of its search behaviour, and the native support of ADL and Derived Predicates.
1. Introduction
Marvin builds on Enforced Hill-Climbing search by memoising plateau-escaping action sequences as macro-actions, allowing similar later plateaux to be escaped without expensive exhaustive search. The paper presents its search algorithms, support for ADL and derived predicates, and evaluation in IPC 4 and additional domain studies.
1. Introduction
- Marvin memoises plateau-escaping action sequences as macro-actions that can help it escape similar later plateaux without expensive exhaustive search.These sequences are learned during planning.Source: §1 · p. 1
- Marvin supports STRIPS and ADL domains and handles PDDL2.2 derived predicates without first reducing domains to STRIPS.Source: §1 · p. 2
- The paper evaluates Marvin in IPC 4 and uses additional ablation studies to assess feature effects across selected domains.Source: §1 · p. 2
2. Background
The background introduces forward-chaining heuristic search and reviews FF’s approach, including Enforced Hill-Climbing, helpful actions, and macro-actions. It also outlines limitations of helpful-action search and the trade-off between useful macro-actions and increased branching.
2.1 Forward-Chaining Planning
- Heuristics guide forward-chaining search because unguided search is prohibitively expensive beyond the smallest problems.Forward search appends actions to the current plan, moving from one state-plan pair to successor pairs.Source: §2.1 · p. 2
2.2 Heuristics for Forward-Chaining Planning
- Relaxed-action heuristics ignore delete effects; FF instead counts actions in a relaxed plan extracted from a relaxed planning graph.The FF heuristic is inadmissible but is described as more informative in practice than earlier heuristics.Source: §2.2 · pp. 2–3
2.3 Enforced Hill Climbing Search
- FF’s Enforced Hill-Climbing uses breadth-first search to find a heuristically improving action sequence when none is available in the immediate neighborhood.EHC’s plateau search is a bottleneck because it can require prolonged exhaustive search.Source: §2.3 · p. 3
2.4 Exploiting the Structure of a Relaxed Plan
- Helpful actions are selected from the relaxed plan to reduce successor states evaluated, but restricting search to them further reduces EHC completeness.Observed failures with helpful actions correlate with cases where EHC using all applicable actions also fails to find a plan.Source: §2.4 · p. 4
2.5 Guaranteeing Completeness in FF
- When EHC reaches a dead end, FF switches to best-first search from the initial state, preserving completeness.Source: §2.5 · p. 4
2.6 Macro-Actions in Planning
- Macro-actions extend the successors visible from a state by applying a sequence of actions as one step; poor choices can increase branching and hurt performance.Earlier approaches commonly generated and filtered macros offline, including macros drawn from prior plans or domain preprocessing.Source: §2.6 · pp. 4–5
3. Marvin’s Search Behaviour
Marvin modifies FF-style search with least-bad-first plateau exploration, a greedy best-first fallback, and online plateau-escaping macros. The section explains how these mechanisms work, when macro reuse helps, and what can limit it.
3. Marvin’s Search Behaviour
- Marvin’s search differs from FF through least-bad-first plateau exploration, greedy best-first fallback, and learned plateau-escaping macro-actions.Its underlying search is forward-chaining heuristic search using the RPG heuristic.Source: §3 · p. 5
3.1 Least-Bad-First Search on Plateaux
- On a plateau, least-bad-first search expands the successor with the least negative heuristic impact, and can reach a better exit than breadth-first search.The paper reports that this strategy sometimes finds shorter plans than FF’s standard breadth-first plateau search.Source: §3.1 · p. 6
3.2 Greedy Best-First Search when EHC Fails
- When EHC fails, Marvin’s greedy best-first search expands the first strictly improving successor while retaining its parent for later, preserving completeness with a smaller queue.Unlike EHC, the fallback uses all applicable actions; the approach can reduce heuristic evaluations by considering fewer successors at a time.Source: §3.2 · p. 7
3.3 Plateau-Escaping Macro-Actions
- Marvin memoizes plateau-escape sequences as parameter-lifted macros and considers them during plateau escape, using helpful first-step actions to limit candidates.The macro’s steps use placeholders for distinct entities in the original sequence, and its applicability is checked across the resulting states.Source: §3.3 · pp. 9–10
3.4 Macro-Actions in Use
- Macro reuse is most rewarding in problem spaces with recurring similar plateaux, and Marvin gates macro use to plateau escape rather than effective single-step guidance.Their reuse depends on the search-space structure and heuristic profile.Source: §3.4 · pp. 10, 12, §3.3 · p. 10
- Unproductive or situation-specific macros can enlarge the search, and redundant sequences can increase plan makespan.Because macros are learned online without human intuition or a large test suite for identifying reusable ones, the planner must choose carefully when to apply them.Source: §3.4 · p. 12
- In IPC 4’s Dining Philosophers problem, learned 11-step and 3-step macros replaced repeated exhaustive rediscovery with single improving steps when reused.The repeated sequences would otherwise require repeated episodes of exhaustive search; later recurring plateaux can also be bypassed by macros, while new sequences still require search.Source: §3.4 · pp. 12–13
4. Handling ADL
Marvin handles ADL natively rather than relying on per-instance STRIPS compilations, adapting action processing and relaxed planning graphs to support ADL constructs. Its modified relaxed planning graph yields the same heuristic estimate as a precompiled STRIPS formulation.
4. Handling ADL
- Marvin reasons with original ADL domains, allowing it to abstract macro-actions from action sequences rather than using IPC 4's compiled STRIPS formulations.The automatic compilations replaced general action schemata with sets of specific action instances.Source: §4 · p. 14
4.1 The Preconditions of ADL Actions
- Quantified preconditions are enumerated and formulas translated into NNF, then satisfaction trees track which ground actions' preconditions hold in a state.The trees use and/or nodes and literal leaves; their counters are reset and updated as state propositions are considered.Source: §4.1 · pp. 14–15
4.2 The Effects of ADL Actions
- Conditional effects depending only on static predicates are resolved during grounding; dynamic conditions become sub-actions, recursively when effects are nested.Applicable sub-actions are applied alongside their parent action.Source: §4.2 · p. 15
4.3 Modifying the Relaxed Planning Graph
- Marvin extends relaxed planning graphs to handle all available ADL constructs while producing the same heuristic estimate as a precompiled STRIPS formulation.Cached proposition–action dependencies also make applicability testing and relaxed-graph extraction more efficient.Source: §4.3 · pp. 17–18
- Marvin adds a negative-fact spike to its relaxed planning graph, where delete effects mark facts as deleted while leaving the positive-fact spike unchanged.This lets the graph track when negative preconditions can be satisfied while preserving the relaxation.Source: §4.3 · p. 17
- For disjunctive preconditions, the graph selects the first satisfied alternative with an achiever, matching the heuristic estimate from compiled STRIPS.When a sub-action achieves a proposition, its parent action's preconditions are also added during plan extraction.Source: §4.3 · p. 18
5. Handling Derived Predicates
Derived predicates appeared in three IPC 4 domains, while compiling them can cause super-polynomial growth in domain and plan size. Marvin handles them natively by internally applying generated confirm actions to re-derive predicates after actions.
5. Handling Derived Predicates
- Flattening derived predicates can require super-polynomial growth in domain and plan size, while compiled instances are also constrained by file size and solving effort (Nebel, Hoffmann, & Thiebaux, 2003).Derived predicates were used in three IPC 4 domains.Source: §5 · pp. 18–19
- Marvin provides native support for derived predicates because compilation does not handle them efficiently.IPC 4 was the first planning competition to use derived predicates in its domains.Source: §5 · p. 19
confirm above ?x ?y
- Marvin machine-generates confirm actions, deletes derived predicates after each original action, then applies confirm actions to instantiate directly or recursively derivable propositions.This avoids an unwieldy compilation for domains with negative preconditions.Source: confirm above ?x ?y · p. 20
- Automatically applying confirm actions avoids searching or evaluating heuristics to discover them, and confirm actions used in relaxed plans do not contribute to the heuristic length.These are two performance benefits of handling confirm actions internally.Source: confirm above ?x ?y · p. 20
6. Results
The section assesses Marvin across planning domains, focusing on the effects of its search features and native domain support, with macro-actions generated during each problem-solving run rather than learned across problems. It covers results in Philosophers, PSR, and Optical Telegraph, including macro-action performance and native ADL versus compiled STRIPS encoding in Philosophers.
6.1 Plateau-Escaping Macro-Actions
- Macro-actions improved performance in Philosophers, Depots, Driverlog, and Pipestankage-nontemporal, worsened it in FreeCell, and had minimal impact in Airport, Pipesnotankage-nontemporal, and Satellite.Except in Driverlog and FreeCell, macro-actions did not significantly affect plan makespan.Source: Figure 7 · p. 21, Figure 8 · p. 22, §6.1 · p. 24
6.2 Greedy Best-First Search versus Best-First Search
- Greedy best-first and conventional best-first search had little impact on planner performance when EHC and macro-actions were disabled.The comparison isolated the effect of the greedy best-first search approach.Source: §6.2 · pp. 24–25
6.3 Least-Bad-First Search versus Breadth-First Search
- Least-bad-first solved all 48 Philosophers problems versus 14 with breadth-first, and solved 34 Pipestankage-nontemporal problems versus 30, generally faster but with longer plans.In the first 14 Philosophers problems, the two approaches found plans with identical makespans.Source: §6.3 · p. 28
- Least-bad-first search substantially helped Philosophers and generally reduced execution time in Satellite, Driverlog, and Pipestankage-nontemporal, with some plan-quality loss in the latter.Its impact was minimal in Airport and Depots, while performance degraded in FreeCell and Pipesnotankage-nontemporal.Source: §6.3 · p. 29
6.4 Handling Derived Predicates
- Native derived-predicate support raised PSR coverage from 12 to 23 problems and Philosophers coverage from nine to all 48 problems.In Optical Telegraph, the original domain enabled two larger problems and one additional problem overall, although smaller problems performed better without derived predicates.Source: §6.4 · p. 30
6.5 Native ADL Support
- Native ADL support offers a more efficient representation and preserves parameterized action sequences that ADL-to-STRIPS compilation loses, enabling reusable macro-actions.The paper identifies these as two benefits of using non-compiled domain formulations.Source: §6.5 · p. 31
6.5.1 THE EFFECTS OF USING A NON-COMPILED DOMAIN
- With macro-actions disabled, Airport, Optical Telegraph, and PSR performance was unaffected by choosing ADL rather than STRIPS encodings.The ADL encodings did not produce inefficient compiled STRIPS encodings.Source: §6.5.1 · p. 32
6.5.2 THE EFFECTS OF INFERRING MACRO-ACTIONS
- Macro-actions consistently improved Philosophers performance by avoiding exhaustive plateau search, while both configurations produced identical solution plans.The first five plan steps were found with heuristic guidance; the next eleven came from exhaustive search and formed macro-action A, with macro-action B formed later. The macros were reused across larger problems. Native ADL supports lifted macro-action schemata, whereas compilation to STRIPS leaves few or no parameters in plateau-escaping sequences, making those macros impractical to reuse.Source: §6.5.2 · pp. 32–33, Figure 17 · p. 34
6.5.1 THE EFFECTS OF USING A NON-COMPILED DOMAIN
- In Philosophers, ADL encoding reduced planning time relative to compiled STRIPS encoding and solved more problems within the 30 minute time-limit, even without macro-action improvements.Figure 17 shows the performance comparison across the two encodings, with and without macro-actions.Source: §6.5.1 · p. 32, Figure 17 · p. 34
6.5.2 THE EFFECTS OF INFERRING MACRO-ACTIONS
- 23 rather than 15 PSR problems were solved with macro-actions, which also found solutions faster in most cases solved by both configurations.Figure 18 compares the configurations with and without macro-actions.Source: §6.5.2 · p. 33, Figure 18 · p. 34
- Macro-actions enabled Marvin to solve a net of two additional problems in the promela/optical-telegraph domain, although it solved only a few of the first 10 problems.Figure 19 compares solution times with macro-actions enabled and disabled.Source: Figure 19 · p. 35, §6.5.2 · p. 35
7. Future Work
Future work would extend Marvin’s per-problem macro-action learning through cross-problem caching, test macro-actions with other heuristics, and broaden learning beyond plateau-escaping structures.
7. Future Work
- Caching learned macro-actions across a domain’s problem instances could make plateau-escaping knowledge reusable without rediscovering it through exhaustive search for each instance.The paper contrasts this proposed online learning with existing offline macro-action learning and notes that effective caching strategies and managing the resulting large macro set remain under investigation.Source: §7 · p. 35
- The authors are investigating plateau-escaping macro-actions with heuristics beyond the relaxed planning graph, including Fast Downward’s causal-graph heuristic.Source: §7 · p. 35
- Marvin’s current macro-actions are limited to escaping plateaux, while work is underway to learn more general macro-action structures.The paper cites Botea and Schaeffer as exploring such structures.Source: §7 · p. 36
8. Conclusions
Marvin combines learned plateau-escaping macro-actions with modified search strategies and native ADL and derived-predicate support. Their effects vary by domain: macro-actions improve execution time in four domains, while other features produce mixed or negligible differences.
8. Conclusions
- Marvin combines learned plateau-escaping macro-actions, least-bad-first plateau search, greedy best-first search when EHC fails, and native ADL and derived-predicate support.Source: §8 · p. 36
- Macro-actions improve execution time in Philosophers, Depots, Driverlog, and Pipestankage-nontemporal; elsewhere performance does not significantly degrade, except in FreeCell.Source: §8 · p. 36
- Least-bad-first search substantially improves performance in Philosophers, reduces execution time in Satellite, Driverlog, and Pipestankage-nontemporal sometimes with longer plans, and performs worse in FreeCell and Pipesnotankage-nontemporal.Source: §8 · p. 36
- Greedy best-first search does not perform significantly differently from best-first search in the evaluation domains considered.Source: §8 · p. 36
- Native ADL and derived-predicate support improves planner performance outside Airport, through more compact domain formulations or more effective inferred macro-actions.Source: §8 · p. 36