Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators

Adi Botea, Markus Enzenberger, Martin Müller, Jonathan SchaefferJAIR 2005 · DOI · OpenReview

TL;DR

This paper introduces MACRO-FF, a system that automatically learns and utilizes "macro-operators" to significantly improve AI planning performance. By analyzing domain structure and past solutions, MACRO-FF creates shortcuts that drastically reduce search effort in complex planning problems, leading to first-place finishes in the IPC-4 competition.

What Problem Does This Paper Address?

Automated AI planning systems have made great strides, but many complex domains and problem instances remain challenging. The authors argue that a key to improving planner performance lies in exploiting "domain structure" – implicit information about how actions and objects relate that isn't explicitly encoded in the standard PDDL (Planning Domain Definition Language) formulation. This implicit knowledge, often obvious to humans, can dramatically simplify planning. For example, a human knows that fueling a truck and assigning a driver are prerequisites for driving, even if the PDDL only defines a single "drive" action. The challenge is to automatically discover and leverage this structural information.

Methods

The paper presents two main approaches for learning and using macro-operators, both following a four-step strategy:

  1. Analysis: Extract structural information from the domain.
  2. Generation: Create macro-operators based on this structure.
  3. Filtering: Select the most useful macro-operators.
  4. Planning: Use the selected macros to speed up future searches.

The two methods differ in how they achieve steps 1-3:

  • CA-ED (Component Abstraction – Enhanced Domain): This method focuses on identifying "abstract components" by analyzing static relationships between objects in the domain. It then generates macro-operators that represent sequences of actions within these components. These macros are then added directly to the domain's operator set, creating an "enhanced domain" that any standard planner can use. This approach is limited to domains with static facts and STRIPS-style PDDL.
  • SOL-EP (Solution – Enhanced Planner): This more general approach extracts macros from successful "solution plans" of training problems. Instead of modifying the domain definition, SOL-EP creates macros as sequences of actions that are then handled by a specialized planner. This method is applicable to more complex PDDL subsets like ADL and doesn't require static facts.

The system MACRO-FF integrates these ideas with enhancements to the state-of-the-art FF planner (version 2.3), including optimizations to the open queue and state hashing.

Datasets

The experiments were conducted on benchmarks from the International Planning Competition (IPC-4), including:

  • Promela Dining Philosophers - ADL
  • Promela Optical Telegraph - ADL
  • Satellite - STRIPS
  • PSR Middle Compiled - ADL
  • Pipesworld Notankage Nontemporal – STRIPS
  • Pipesworld Tankage Nontemporal STRIPS
  • Airport - ADL
  • Rovers (IPC-3)
  • Depots (IPC-3)

These datasets represent a variety of domains with different complexities and PDDL formulations.

Key Insights and Ideas

  • Domain Structure is Key: The paper strongly advocates that exploiting implicit domain structure is crucial for achieving significant performance gains in AI planning, especially in complex domains.
  • Two Paths to Macros: The CA-ED and SOL-EP approaches offer complementary ways to learn macros. CA-ED leverages static relationships for domain enhancement, while SOL-EP learns from successful plans, offering broader applicability.
  • Macros as Shortcuts: Macro-operators act as "shortcuts" by collapsing sequences of actions into single, more powerful operations, thereby reducing the search space and the number of nodes expanded.
  • Trade-offs in Macro Integration: Adding macros can increase preprocessing costs and the cost per node in search (especially for CA-ED), but the benefits in reduced search effort often outweigh these costs. SOL-EP's approach of handling macros dynamically mitigates some of these overheads.
  • Ranking is Crucial: Simply generating many macros isn't enough; a robust ranking and filtering mechanism is needed to select the most effective ones, as poor macros can degrade performance (the "utility problem").

Key Results

  • MACRO-FF achieved first place in the classical part of the fourth International Planning Competition (IPC-4) in three domains: Promela Optical Telegraph, PSR, and Satellite.
  • In domains where structural information could be inferred, MACRO-FF demonstrated significant reductions in search effort, with speedups reaching a factor of 10 in some cases (e.g., Pipesworld domains).
  • The SOL-EP approach, used in the competition system, showed substantial improvements, allowing MACRO-FF to solve 12 additional problems in Promela Optical Telegraph and one more problem in Promela Dining Philosophers.
  • Combining CA-ED and SOL-EP often yielded better results than using either method alone, particularly in domains like Depots.
  • CA-ED macros were shown to improve the accuracy of heuristic state evaluation and reduce the depth of goal states.

Limitations and Future Work

  • CA-ED Limitations: CA-ED is limited to domains with static facts and STRIPS-style PDDL. Adding macros to the domain can significantly increase preprocessing costs and the cost per node in search.
  • SOL-EP Limitations: While more general, SOL-EP's current implementation doesn't directly affect the heuristic state evaluation computation, which is an area for future work.
  • Determining Optimal Number of Macros: The paper acknowledges that deciding the optimal number of macros to use for a domain is still an open problem.
  • Generalizing to More Complex Structures: The authors plan to generalize their learning method to more complex structures like Hierarchical Task Networks (HTNs).
  • Improving Heuristic Evaluation with Macros: Further research is planned to explore how macros can improve heuristic evaluation, especially for non-STRIPS domains where macros cannot be directly added to the domain definition.
  • Automatic Domain Reformulation: A long-term goal is to develop methods for automatically reformulating planning domains based on their structure.

Summary updated

Abstract

Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present and compare two automated methods that learn relevant information from previous experience in a domain and use it to solve new problem instances. Our methods share a common four-step strategy. First, a domain is analyzed and structural information is extracted, then macro-operators are generated based on the previously discovered structure. A filtering and ranking procedure selects the most useful macro-operators. Finally, the selected macros are used to speed up future searches. We have successfully used such an approach in the fourth international planning competition IPC-4. Our system, Macro-FF, extends Hoffmanns state-of-the-art planner FF 2.3 with support for two kinds of macro-operators, and with engineering enhancements. We demonstrate the effectiveness of our ideas on benchmarks from international planning competitions. Our results indicate a large reduction in search effort in those complex domains where structural information can be inferred.
BibTeX
@article{botea2005macro,
  author = {Adi Botea and Markus Enzenberger and Martin Müller and Jonathan Schaeffer},
  title = {{Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators}},
  journal = {J. Artif. Intell. Res.},
  year = {2005},
  doi = {10.1613/jair.1696},
}
Figure