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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Gratch, Jonathan Matthew

Contributors dc:contributor

• DeJong, Gerald F.

• Operations Research
• Artificial Intelligence
• Computer Science

Statement dc:rights

• Copyright 1995 Gratch, Jonathan Matthew

Language dc:language

eng

Identifier

AAI9624352
(UMI)AAI9624352

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/22285