Why PRODIGY/EBL Works

Abstract

Explanation-Based Learning (EBL) fails to accelerate problem solving in some problem spaces. How do these problem spaces differ from the ones in Minton's experiments [1988b]? Can minute modifications to problem space encoding drastically alter EBL's performance? Will PRODIGY/EBL'S success scale to real-world domains? This paper presents a formal theory of problem space structure that answers these questions. The central observation is that PRODIGY/EBL relies on finding nonrecursive explanations of PRODIGY'S problem-solving behavior. The theory explains and predicts PRODIGY/EBL'S performance in a wide range of problem spaces. The theory also predicts that a static program transformer, called STATIC, can match PRODIGY/EBL'S performance in some cases. The paper reports on an array of experiments that confirms this prediction. STATIC matches PRODIGY/EBL'S performance in each of Minton's problem spaces.