A statistical approach to adaptive problem solving

AbstractDomain independent general purpose problem solving techniques are desirable from the standpoints of software engineering and human computer interaction. They employ declarative and modular knowledge representations and present a constant homogeneous interface to the user, untainted by the peculiarities of the specific domain of interest. Unfortunately, this very insulation from domain details often precludes effective problem solving behavior. General approaches have proven successful in complex real-world situations only after a tedious cycle of manual experimentation and modification. Machine learning offers the prospect of automating this adaptation cycle, reducing the burden of domain specific tuning and reconciling the conflicting needs of generality and efficacy. A principal impediment to adaptive techniques is the utility problem: even if the acquired information is accurate and is helpful in isolated cases, it may degrade overall problem solving performance under difficult to predict circumstances. We develop a formal characterization of the utility problem and introduce COMPOSER, a statistically rigorous learning approach which avoids the utility problem. COMPOSER has been successfully applied to learning heuristics for planning and scheduling systems. This article includes theoretical results and an extensive empirical evaluation. The approach is shown to outperform significantly several other leading approaches to the utility problem