STATIC: A Problem-Space Compiler for PRODIGY

Oren Etzioni

Explanation-Based Learning (EBL) can be used to significantly speed up problem solving. Is there sufficient structure in the definition of a problem space to enable a static analyzer, using EBL-style optimizations, to speed up problem solving without utilizing training examples? If so, will such an analyzer run in reasonable time? This paper demonstrates that for a wide range of problem spaces the answer to both questions is "yes." The STATIC program speeds up problem solving for the PRODIGY problem solver without utilizing training examples. In Minton’s problem spaces [1988], STATIC acquires control knowledge from twenty six to seventy seven times faster, and speeds up PRODIGY up to three times as much as PRODIGY/EBL. This paper presents STATIC'S algorithms, derives a condition under which STATIC is guaranteed to achieve polynomial-time problem solving, and contrasts STATIC with PRODIGY/EBL.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.