STATIC: A Problem-Space Compiler for PRODIGY

Oren EtzioniAAAI 1991

Abstract

STATIC is a problem-space compiler that uses static analysis to generate search control rules for the PRODIGY planner. Unlike Explanation-Based Learning (EBL), which relies on training examples and execution traces, STATIC performs partial evaluation on the problem space definition to identify necessary goal interactions and potential search failures. Experimental results across several classic AI planning domains demonstrate that STATIC generates control knowledge significantly faster than EBL while producing rules that are more efficient to execute and robust across different problem instances.

Introduction

In the early 1990s, Explanation-Based Learning (EBL) was the dominant paradigm for improving the performance of automated planners. Systems like PRODIGY/EBL would solve a problem, analyze the resulting trace, and derive general rules to avoid future mistakes. However, EBL faced three significant challenges: the utility problem (where rule-checking overhead outweighs savings), training dependency (performance hinges on the quality of examples), and slow learning (the system must solve difficult problems slowly before it can learn how to solve them quickly).

Oren Etzioni's research presented at AAAI-91 challenged this paradigm by asking whether the benefits of EBL could be achieved without training examples. The resulting system, STATIC, treats problem-space definitions as code to be compiled rather than experiences to be learned from.

The STATIC Approach

STATIC performs a proactive "static analysis" of the problem space through four primary phases. The core of this process is the construction of Problem Space Graphs (PSGs) using Partial Evaluation (PE). By symbolically back-chaining from goals to operators without a specific initial state, STATIC maps out the logical structure of the domain.

Figure 1: A Problem Space Graph (PSG) for the Blocksworld domain, illustrating the partial evaluation of subgoals.
  1. PSG Construction: STATIC builds AND/OR graphs for potential subgoals, employing repetition detection to prevent infinite loops during symbolic analysis.
  2. Node Labeling: Nodes in the PSG are labeled as success, failure, or unknown. This allows the solver to identify and avoid "dead ends" in the search tree before they are encountered.
  3. Rule Generation: These labels are translated into PRODIGY control rules (e.g., rejecting an operator that leads to a known failure node).
  4. Goal Interaction Analysis: STATIC identifies "goal clobbering"—instances where achieving one goal necessarily undoes another—and creates rules to enforce correct goal ordering.

Experimental Evaluation

STATIC was evaluated against PRODIGY/EBL using four benchmark domains: Blocksworld, Stripsworld, Schedworld, and ABworld. The results demonstrated a clear advantage for static analysis over example-based learning.

Table 1: Total problem-solving time (CPU seconds) for PRODIGY without learning, PRODIGY/EBL, and STATIC.

As shown in Table 1, STATIC consistently achieved the lowest total problem-solving times. In the Blocksworld domain, STATIC reduced solving time to 47 seconds, compared to 139 seconds for EBL and 2,182 seconds for the baseline solver. Furthermore, STATIC generated its control knowledge 26 to 77 times faster than EBL, as it did not need to solve complex training problems to derive its rules.

Key Insights

  • Nonrecursive Explanations: A counter-intuitive finding was that STATIC's focus on nonrecursive structures provided better speedups than the complex recursive rules often favored by EBL. Simpler rules proved cheaper to match and more effective in practice.
  • Proactive vs. Reactive: While EBL is reactive, learning from specific experiences, STATIC is proactive. It analyzes the "map" of the problem space before the journey begins, ensuring its rules are robust and not over-specialized to specific training instances.
  • Necessary Interactions: By focusing on interactions that must occur regardless of the state, STATIC avoids the pitfalls of learning rules that only apply to specific, possibly rare, scenarios.

Limitations and Future Work

Despite its success, STATIC has several limitations. It currently only analyzes interactions between pairs of goals, potentially missing complex N-ary conflicts. Because it ignores training distributions, it cannot optimize for specific subsets of common problems as EBL might. Additionally, by excluding recursive knowledge to maintain efficiency, it may miss sophisticated control strategies. Future work aims to extend these techniques to more complex problem solvers and broader classes of goal interactions.

Summary updated

BibTeX
@inproceedings{etzioni1991static,
  author = {Oren Etzioni},
  title = {{STATIC: A Problem-Space Compiler for PRODIGY}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure