Abstract
The success of heuristic search in AI planning largely depends on the design of the heuristic. On the other hand, previous experience contains potential domain information that can assist the planning process. In this context, we have studied dynamic macro-based heuristic planning through action relationship analysis. We present an approach for analyzing the action relationship and design an algorithm that learns macros in solved cases. We then propose a dynamic macro-based heuristic that appropriately reuses the macros rather than immediately assigning them to domains. The above ideas are incorporated into a working planning system called Dynamic Macro-based Fast Forward planner (DM-FF). Finally, we evaluate our method in a series of experiments. Our method effectively optimizes planning since it reduces the result length by an average of 10% relative to the FF, in a time-economic manner. The efficiency is especially improved when invoking an action consumes time.
Introduction
Classical AI planning involves searching through a massive state space to find a sequence of actions that leads from an initial state to a goal. To navigate this space efficiently, modern planners rely on heuristics—mathematical rules of thumb—to estimate the distance to the goal. While effective, these domain-independent heuristics often ignore the "latent knowledge" hidden in previously solved problems.
A common approach to utilizing this knowledge is through macros, which treat a sequence of actions (e.g., "pick up wrench" followed by "tighten bolt") as a single unit. While macros can theoretically speed up search by allowing for larger steps, they often lead to a "branching factor explosion." Adding too many macros increases the number of choices at every step, which can paradoxically slow down the search process. This research introduces DM-FF to address this "utility problem" through intelligent macro selection and dynamic weighting.
Methodology
The DM-FF system introduces three key innovations to integrate macros effectively without degrading search performance:
- Action Relationship Analysis: The system analyzes dependencies between actions rather than just co-occurrence. It distinguishes between "straightly dependent" actions (where one provides a precondition for another) and "independent" actions. This ensures learned macros are logically coherent units.
- LMLF Algorithm: The "Learning Macros with Length and Frequency" algorithm scans solved plans to identify candidates. It utilizes a length threshold ($l^*$) and a frequency threshold ($s^*$) to filter out macros that are either too complex or too rare to be beneficial.
- Dynamic Weighting: Instead of treating a macro as a single step (weight of 1), DM-FF assigns a dynamic weight based on the macro's length, historical frequency, and real-time success during the search. This allows the planner to prioritize high-value macros while penalizing those that do not contribute to progress.
As shown in Figure 2, the choice of macro length ($l^*$) is critical. While longer macros can potentially cover more ground, they also increase the computational overhead. The researchers found a "sweet spot" (typically around $l^*=4$ in the Depots domain) where the benefits of macro-guided search outweigh the costs of analysis.
Experimental Evaluation
The researchers evaluated DM-FF using four representative domains from the IPC2002 benchmarks: Depots, ZenoTravel, Satellite, and Rovers. The system was trained on 20 problems per domain and tested on 50.
Key Results
- Plan Quality: DM-FF consistently produced shorter plans than the standard Fast-Forward (FF) planner. Across all domains, the resulting plan length was reduced by an average of 10% (see Figure 3).
- Search Efficiency: By integrating macros into the heuristic function itself rather than the domain description, DM-FF avoids the branching factor explosion typical of macro-based systems. The system proved particularly effective in scenarios where action invocation is time-consuming.
- Heuristic vs. Domain Bloat: Comparisons showed that DM-FF outperformed "FF with enhanced domain" (simply adding macros to the domain file), validating the necessity of the dynamic weighting scheme.
Conclusion
DM-FF demonstrates that learning from experience through action relationship analysis can significantly improve planning quality. By using dynamic weighting to manage the utility of macros, the planner achieves shorter plans without the typical performance penalties associated with increased branching factors. Future work will explore extending this methodology to numeric domains with continuous variables and conformant planning under uncertainty.
Summary updated