Selective Learning of Macro-operators with Perfect Causality

TL;DR

This paper introduces "Perfect Causality," a novel heuristic for selectively learning effective macro-operators in AI planning. By filtering out redundant or useless macro-operators, their system, PiL2, significantly improves problem-solving efficiency compared to non-selective learning or no learning at all, demonstrated in both robot planning and equation solving domains.

What Problem Does This Paper Address?

In AI planning, macro-operators are sequences of primitive actions that are learned and then used to speed up problem-solving by reducing the search space. However, a naive approach of learning all possible macro-operators from worked examples leads to an explosive increase in their number. This massive library of macro-operators can paradoxically make problem-solving less efficient due to the overhead of searching for the right one. The core problem this paper addresses is how to learn only the truly useful macro-operators to maintain and improve problem-solving efficiency.

Methods

The paper proposes a system called PiL2, which combines a STRIPS-like problem solver with a selective macro-operator learner. The key innovation is the "Perfect Causality" heuristic. This heuristic identifies a sub-sequence of operators as a potential macro-operator if:

  1. The last operator in the sub-sequence is not applicable to the initial state.
  2. After applying the preceding operators in the sub-sequence, the last operator becomes applicable.

This criterion ensures that the learned macro-operator represents a meaningful, causal step that wouldn't have been obvious or directly executable from the start. PiL2 uses this heuristic to extract candidate macro-operators from worked examples. These extracted sequences are then generalized using Explanation-Based Generalization (EBG) to create reusable macro-operators.

Datasets

The paper does not explicitly mention named datasets. Instead, it uses two domains for experimentation:

  1. Classical Robot Planning: This domain involves problems similar to those tackled by early AI planning systems like STRIPS, requiring robots to navigate, pick up objects, and move them. The "worked examples" are sequences of basic operator applications generated by a planner.
  2. Solving Algebraic Equations: This domain involves learning to solve various types of equations (first-degree, second-degree, fractional, logarithmic, exponential). The "worked examples" are sequences of basic algebraic manipulations that lead to a solution.

Key Insights and Ideas

  • The "Curse of Dimensionality" in Macro-Learning: Simply learning all possible macro-operators is counterproductive. The overhead of managing and searching a huge library outweighs the benefits.
  • Perfect Causality as a Filter: The core idea is that a useful macro-operator should represent a non-trivial causal step. If an operator is already applicable, it's less likely to be a valuable macro. If it becomes applicable only after a specific sequence of prior actions, that sequence is a strong candidate for a macro-operator.
  • Selective Learning is Crucial for Efficiency: The experiments strongly suggest that learning only a few, highly effective macro-operators is far better than learning many less effective ones.
  • EBG for Generalization: Combining the selective learning with EBG allows the system to generalize learned macro-operators, making them applicable to a wider range of similar problems.

Key Results

The paper presents experimental results in two domains:

  • Classical Robot Planning:
    • PiL2 (selective learning) significantly outperformed both a non-learning STRIPS and a non-selective macro-learning system (M-STRIPS).
  • For example, on problem P50, PiL2 evaluated 60 branches and expanded 54 nodes with a CPU time of 197 seconds, while STRIPS evaluated 756 branches and expanded 155 nodes in 1819 seconds. M-STRIPS failed due to stack overflow after solving only P12, having generated 202 macro-operators.
  • PiL2 learned very few macro-operators (e.g., 5 for P50) compared to what a non-selective learner would generate (potentially over 1000).
  • Solving Algebraic Equations:
    • PiL (a variant of PiL2) was able to solve problems it couldn't initially handle after learning macro-operators.
  • The system learned a reasonable number of macro-operators for different equation types (e.g., 13 for first-degree, 62 for second-degree).
  • The paper implies that PiL's selective learning approach leads to better efficiency than a non-selective approach would, though direct comparative results for non-selective learning in this domain are not explicitly detailed.

Limitations and Future Work

  • Domain Specificity: The authors acknowledge that the utility of Perfect Causality in domains other than robot planning and equation solving is unknown and requires further investigation.
  • Analytical Evaluation: An analytical evaluation of the limitations of their method is suggested as future work.
  • Operationality Criterion: While Perfect Causality is proposed as an operationality criterion in EBL, its broader applicability and formal definition are areas for continued research. The paper notes that while their macro-operators are "usable" by the performance system, proving their "utility" (i.e., guaranteed performance improvement) is a deeper challenge.

Summary updated

BibTeX
@inproceedings{1989selective,
  title = {{Selective Learning of Macro-operators with Perfect Causality}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure