Research map / Learning theory and algorithms / Combinatorial and search optimization

Automatic Selection of Macro-Events for Heuristic-Search Temporal Planning

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Classical and HTN planning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces macro-events (context-dependent event sequences) for heuristic-search temporal planning and a statistics-based ranking that selects macro-events from valid plans by estimating expanded states under four exploitation schemata.

Problem

Temporal planning with heuristic search is slow; macro-actions create shortcuts but enlarge the branching factor, so the set of macros must be chosen carefully. Classical macro-actions do not capture concurrent durative actions in temporal planning.

Approach

Defines macro-events as sequences of action IDs whose meaning depends on the current state (advance each action's next event), explores four exploitation schemata (fully/partially applicable, with/without intermediate nodes), and ranks candidate macros by an analytically estimated expanded-state count derived from plan-macro-event utilities.

Key results

• On MAJSP with hff, the PA+ macro-event approach solves 371 instances vs 342 without macros (4 folds, 123 test instances each).
• On Kitting with hadd, macro-event approaches solve up to 250 vs 207 for the baseline without macros, and with hff up to 206 vs 237 baseline for PA+ mixed results.
• Macro-based approaches are faster than the baseline in all cases according to the coverage tables and cactus plots.

Measured effects reported in the paper

Surprising findings

• On Kitting with hff, the baseline without macros (237 solved) outperforms all macro-event variants on total coverage in the reported table, contrary to the claim that macros always help.

Limitations

• Macro-events are ground (object-specific) and not lifted to generalize across instances.
• Selection relies on simplifying assumptions (blind search, all actions always applicable, fixed utilities).
• Evaluated on only two benchmark domains with a single planner (TAMER).

Experimental setup

Datasets: MAJSP Kitting

Benchmarks: MAJSP Kitting

Metrics: coverage (solved instances) number of instances faster than baseline expanded states estimate

Baselines: TAMER without macros De Bortoli et al. 2023 temporal macro-actions (FA- semantics)

Builds on: TAMER Crikey MACRO-FF Micheli and Valentini 2021 RL plan generation

Closest papers by meaning

• Synthesis of Search Heuristics for Temporal Planning via Reinforcement Learning (AAAI 2021 · similarity 0.88)
• Improving Domain-Independent Planning via Critical Section Macro-Operators (AAAI 2019 · similarity 0.88)
• Improving planning and MBRL with temporally-extended actions (NeurIPS 2025 · similarity 0.85)
• Optimizing the Optimization of Planning Domains by Automatic Action Schema Splitting (AAAI 2024 · similarity 0.85)
• Abstract Action Scheduling for Optimal Temporal Planning via OMT (AAAI 2024 · similarity 0.85)
• System 1.x: Learning to Balance Fast and Slow Planning with Language Models (ICLR 2025 · similarity 0.84)