Learning Rewrite Rules to Improve Plan Quality

AAAI 1999

TL;DR

This paper introduces REWRITE, a system that automatically learns "rewrite rules" to improve the quality of plans generated by AI planners. By analyzing the differences between a planner's output and a higher-quality "better plan," REWRITE identifies and codifies decision points that lead to suboptimal plans, enabling future planning to avoid these pitfalls. This work is significant because it automates a crucial aspect of plan refinement, moving beyond hand-coded rules and offering a more scalable approach to generating high-quality plans.

What Problem Does This Paper Address?

Traditional AI planning often focuses on finding any valid plan, not necessarily the best one. While some research has explored learning search control rules to improve planning efficiency, these methods are typically limited to "state-space planners." Newer planning approaches, like "plan refinement," operate on partial plans and lack the global state information needed to evaluate complex quality metrics. This makes it difficult to directly learn rules that improve plan quality in these systems. The paper addresses this gap by proposing a method to learn "rewrite rules" that operate on complete plans, transforming them into higher-quality versions. These rules are defined on the space of complete plans, making them applicable to plan refinement techniques.

Methods

REWRITE has three core components:

  1. Partial-Order Causal-Link Planner (POP): This component generates an initial plan. The paper mentions using a speed-up version called DerPOP for generating initial plans along with causal-link and ordering constraints.
  2. Analytic Component: This is the heart of the learning process. It takes as input:
  3. The problem description (initial state and goals).
  4. The plan and its trace generated by the POP.
  5. A "better plan" for the same problem, which has a higher quality rating (e.g., better resource utilization) than the POP's plan. This "better plan" can come from an oracle, user, or another planner.

    The analytic component works by:

  6. Reconstructing causal links and ordering constraints from the better plan.

  7. Retracing the POP's planning trace to identify "conflicting choice points" – decisions made by POP that introduced constraints not present in the better plan.
  8. For each conflicting choice point, it compares the plan-refinement decisions made by POP (leading to a lower-quality plan) with those inferred from the better plan (leading to a higher-quality plan).
  9. It then identifies the "to-be-replaced action sequence" (from the worse plan) and the "replacing action sequence" (from the better plan), along with their preconditions and effects.
  10. Case Library of Plan-Rewrite Rules: The information extracted by the analytic component is stored as a rewrite rule. These rules are then applied to future plans generated by the POP.

Datasets

Not discussed in the paper. The paper focuses on a general methodology and does not refer to specific benchmark datasets for training or evaluation. The "better plan" is assumed to be provided externally.

Key Insights and Ideas

  • Learning on Complete Plans: The core innovation is learning rules that operate on complete plans, rather than just search control rules on partial plans. This makes the learned rules more applicable to plan refinement systems.
  • Leveraging "Better Plans": The system effectively learns by comparing a planner's output to a known superior solution. This "supervised" learning approach allows it to pinpoint specific decision points that lead to suboptimal outcomes.
  • Identifying "Conflicting Choice Points": The concept of a "conflicting choice point" is crucial. It's where the planner made a decision that deviates from the path to a higher-quality plan, highlighting an area where the planner's knowledge is deficient.
  • Automating Rule Creation: REWRITE automates the creation of these quality-improving rules, eliminating the need for manual, labor-intensive rule engineering.

Key Results

The paper presents preliminary evaluation results indicating that the overhead for applying these techniques (identifying, storing, and using rewrite rules) is not large. The primary benefit highlighted is that these rewrite rules do not have to be hand-coded, suggesting a significant improvement in scalability and practicality for generating high-quality plans. Specific quantitative metrics (e.g., percentage improvement in plan quality, speedup) are not detailed in this abstract.

Limitations and Future Work

  • Source of "Better Plan": The system relies on the availability of a "better plan." The paper acknowledges this can be provided by an oracle, a user, or another planner, but the process of obtaining this better plan is not detailed.
  • Rule Application: The paper mentions that rules are retrieved and applied if their "to-be-replaced action sequence is a subset of P" (where P is the initial plan). The exact criteria and effectiveness of this retrieval and application process are not fully elaborated.
  • Rule Complexity: While the paper describes the components of a rule (action sequences, preconditions, effects), the complexity and expressiveness of the learned rules are not deeply explored.

Future work is implied by the methodology itself: further evaluation of the learned rules' effectiveness, exploring different methods for obtaining "better plans," and potentially extending the rule learning to handle more complex planning domains or quality metrics.

Summary updated

BibTeX
@inproceedings{1999learning,
  title = {{Learning Rewrite Rules to Improve Plan Quality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}

Loading related content...

Figure