Acquiring search-control knowledge via static analysis (Q685544)

Explanation-Based Learning (EBL) is a widely-used technique for acquiring search-control knowledge. Recently, \textit{Prieditis}, \textit{van Harmelen} and \textit{Bundy} pointed to the similarity between Partial Evaluation (PE) and EBL. However, EBL utilizes training examples whereas PE does not. It is natural to inquire, therefore, whether PE can be used to acquire search-control knowledge, and if so at what cost? The paper answers these questions by means of a case study comparing PRODIGY/EBL, a state-of-the-art EBL system, and STATIC, a PE-based analyzer of problem-space definitions. When tested in PRODIGY/EBL's benchmark problem spaces, STATIC generated search-control knowledge that was up to three times as effective as the knowledge learned by PRODIGY /EBL, and did so from twenty-six to seventy-seven times faster. The paper describes STATIC's superior performance will scale up and when it will not. The paper concludes with several lessons for the design of EBL systems, suggesting hybrid PE/EBL systems as a promising direction for future research.