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.
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.
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