Introduction
Automated planning systems often face a significant hurdle known as the "utility problem." While "macro-operators"—sequences of primitive actions bundled into a single unit—can potentially accelerate the search for a solution, an uncontrolled accumulation of these macros can lead to a "macro-operator explosion." This overhead often results in a system that is slower than one using only basic primitives. In "Selective Learning of Macro-operators with Perfect Causality," Yamada and Tsuji propose a novel heuristic filter to address this challenge.
The PiL2 System Architecture
The authors introduce PiL2 (Perfectly-causal Macro-operator Learner), a system designed to selectively learn only the most useful macro-operators. The architecture integrates a problem solver with a learning component that analyzes worked examples to generate new macro-operators.
Methods: Perfect Causality and EBG
The core innovation of PiL2 is the Perfect Causality heuristic. The authors argue that while many macros are usable, only perfectly causal ones have high utility. A sequence of operators is considered perfectly causal only if each operator (except the first) becomes applicable solely due to the effects of its immediate predecessor. This ensures that the learned macros represent tight, logical chains of dependency rather than arbitrary or independent actions—independence being the primary cause of search overhead in other systems.
Once a perfectly causal sequence is identified in a specific "worked example," PiL2 employs Explanation-Based Generalization (EBG). This process transforms specific instances into generalized rules.
By using set operations to collapse these generalized sequences, PiL2 creates structured macro-operators that the solver can treat as primitive actions.
Experimental Evaluation
The effectiveness of PiL2 was evaluated in two domains: classical robot planning (STRIPS-based) and algebraic equation solving.
Key Results
- Efficiency in Robotics: In a complex 28-step planning problem, PiL2 expanded only 54 nodes, compared to 155 nodes for the standard STRIPS solver. This resulted in a nearly 10x speedup in execution time (197 seconds vs. 1,819 seconds).
- Avoiding Performance Degradation: While non-selective learners (like M-STRIPS) suffered from stack overflows due to generating hundreds of useless macros, PiL2 remained stable by learning only high-utility sequences.
- Algebraic Problem Solving: PiL2 successfully learned 75 macros across various equation types, enabling it to solve complex problems that were previously unsolvable within time limits.
Conclusion and Future Work
PiL2 demonstrates that "Perfect Causality" is a powerful operationality criterion for selective learning. By focusing on logical dependency, it avoids the pitfalls of the utility problem. While highly effective in robotics and algebra, future research is needed to explore its applicability in more abstract domains and to provide formal analytical bounds for the heuristic's performance.
Summary updated