On efficient approaches to the utility problem in adaptive problem solving.

摘要

Domain 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. To date, however, the utility problem--the realization that adaptive strategies that were intended to improve problem solving performance would actually degrade performance under difficult to predict circumstances--has impeded the development of adaptive problem solving techniques. Even systems designed to address the utility problem can seriously impair problem solving behavior, as they have incompletely accounted for the subtleties of the problem. In order to develop a more rigorous approach to adaptive problem solving, this thesis details a formal framework that highlights these prior shortcomings, and presents a statistically rigorous solution to the utility problem. Based on clearly articulated and well-motivated assumptions, this statistical method is applied successfully to learning heuristics for several artificial and a real-world problem solving applications. Although the focus of this work is on adaptive planning and scheduling, the results of this research have wider implications for operations research, software simulation, and decision-tree learning.