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

Alessandro La Farciola, Alessandro Valentini, Andrea MicheliAAAI 2025 · DOI

Abstract

Temporal planning, which involves managing concurrent actions with durations, presents a significantly larger search space than classical planning. While macro-actions are a standard acceleration technique, they often struggle with the overlapping events characteristic of temporal domains. This paper introduces "macro-events"—flexible sequences of action progression instructions—and a statistical ranking function to identify high-impact shortcuts. Experimental results on complex benchmarks demonstrate that these macro-events substantially improve both coverage and solving speed for state-of-the-art temporal planners.

Introduction

Automated planning is a core area of AI, typically divided into classical planning (sequences of instantaneous steps) and temporal planning (actions with durations and concurrency). The latter is significantly more complex due to the explosion of the search space. To navigate this complexity, researchers often use "macro-actions" to jump ahead in the search. However, traditional macro-actions are rigid and fail to capture the interleaving of start and end events in temporal settings.

Methodology: Macro-Events and Selection

The authors propose three key innovations to address these challenges:

1. Macro-Events

Unlike standard macros, macro-events are defined as sequences of instructions to progress actions. For example, a macro might specify "advance action $a$, then advance action $b$." Depending on the current state, "advance" could mean starting an action or finishing it. This context-dependency allows the same macro to represent different physical behaviors, effectively handling concurrency.

2. Exploitation Schemata

The paper defines four ways a planner can utilize these macros based on applicability (Full vs. Partial) and the inclusion of intermediate states in the search queue. The "+" variants, which include intermediate nodes, often provide more "entry points" for the heuristic to find a path, preventing the planner from getting stuck.

3. Statistical Selection

To avoid the "utility problem"—where the cost of evaluating many macros outweighs their benefit—the authors developed a ranking function. It estimates the "Impact" of a macro by calculating how many states a "blind" planner would avoid expanding. This mathematical approach allows for the efficient pruning of thousands of candidate macros down to a small, high-impact set.

Experimental Evaluation

The approach was evaluated on the Multi-Agent Job Shop Scheduling (MAJSP) and Kitting domains.

Cactus plot showing the number of instances solved over time for the $h_{ff}$ heuristic. The macro-event schemata (such as PA+) significantly outperform the "no macros" baseline in terms of total coverage.

In the MAJSP domain using the $h_{ff}$ heuristic, the baseline planner solved 342 instances. The addition of macro-events (specifically the PA+ schema) boosted this to 371 instances.

Scatter plot comparing the solving time of the PA+ schema against the "no macros" baseline for the $h_{ff}$ heuristic. Points below the diagonal indicate instances where the macro-event approach was faster.

As shown in the scatter plot, the macro-enabled planner is significantly faster in the majority of cases. In the Kitting domain, macro-based approaches were faster than the baseline in 205 out of 250 instances for the FA+ schema.

Conclusion and Future Work

The introduction of macro-events and a robust statistical selection mechanism provides a powerful tool for temporal planning. By allowing for flexible action overlaps and efficiently identifying high-utility shortcuts, this method overcomes the limitations of traditional macro-actions. Future work will focus on "lifting" these macros into symbolic representations to improve generalization across different objects within a domain.

Summary updated

BibTeX
@inproceedings{farciola2025automatic,
  author = {Alessandro La Farciola and Alessandro Valentini and Andrea Micheli},
  title = {{Automatic Selection of Macro-Events for Heuristic-Search Temporal Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34859},
}
Figure