Abstract
OMA (Online MAcro generation) is a novel method designed to accelerate AI planning by generating "shortcut" actions, known as macro-operators, on-the-fly. Unlike traditional methods that require extensive offline training, OMA identifies high-value action sequences by analyzing domain structures and "outer entanglements." This approach significantly improves the performance of various state-of-the-art planning engines across standard benchmarks without the overhead of a dedicated training phase.
Introduction
In automated planning, macro-operators (macros) are sequences of actions treated as a single step, effectively acting as shortcuts in the search space. Traditionally, these are learned offline through a dedicated training phase on simpler problems. However, offline learning suffers from expensive setup costs, potential bias toward training data, and the "utility problem"—where adding too many macros increases the branching factor and slows down the planner.
Existing online methods, which learn during the task, are often tied to specific planning algorithms. This paper introduces OMA, a planner-independent online method that generates effective macros by analyzing domain and problem descriptions directly, avoiding the pitfalls of offline training and planner dependency.
Methodology
The OMA system follows a three-step process to generate useful macro-operators:
- Identifying Outer Entanglements: OMA identifies relationships between actions and the initial or goal states (e.g., a
pickupaction entangled with an object's starting location). It uses a heuristic formula to find these without requiring example plans. - Generating Connected Macros: The system focuses on "connected macros"—sequences that transform an object from its initial state toward its goal (e.g.,
Pick-Move-Drop). A "chaining rule" ensures logical continuity between actions. - Filtering for Utility: To mitigate the utility problem, OMA applies six strict filters, checking for soundness, mutual exclusions (mutexes), and the potential increase in branching factor using Argument Matching Graphs.
Evaluation and Results
The researchers evaluated OMA using standard benchmarks from the International Planning Competition (IPC), specifically the IPC-8 Agile Track and the IPC-7 Learning Track.
Performance Gains
OMA demonstrated significant improvements in IPC scores—a metric combining speed and success rate—across various domains and planners. By keeping the macro set small (typically 1 to 3 macros per problem), OMA avoids search-space explosion.
As shown in Table 1, OMA improved the performance of seven different state-of-the-art planners, including Yahsp3, Cedalion, and Probe. Notably, the time OMA takes to generate these macros is negligible, usually requiring less than 0.1 seconds.
Comparison with Existing Methods
OMA was also compared against existing macro-learning techniques. It outperformed Marvin, a well-known online learner, and in several domains, it even surpassed MUM, a state-of-the-art offline learner. This is attributed to OMA's lack of bias from potentially low-quality training plans.
Discussion and Conclusion
While OMA shows strong performance, it faces challenges in "Logistics-like" domains where entanglements are less obvious, sometimes failing to find useful macros or generating counter-intuitive ones. Additionally, the current implementation lacks support for complex PDDL features like conditional effects.
Future work involves integrating machine learning predictive models to better characterize planning problems and refine macro selection beyond simple heuristics. Overall, OMA represents a significant step toward efficient, planner-independent online macro generation that leverages problem structure over statistical training.
Summary updated