Acquiring search-control knowledge via static analysis

摘要

Explanation-based learning (EBL) is a widely-used technique for acquiring search-control knowledge. Prieditis, van Harmelen, and 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? This 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 algorithms, compares its performance to prodigy/ebl's, noting when 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.