{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22285"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22285","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"On efficient approaches to the utility problem in adaptive problem solving","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Gratch, Jonathan Matthew"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["DeJong, Gerald F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:35:00Z","date_published":"2011-05-07T13:35:00Z","updated_at":"2026-07-22T22:25:19Z","subjects":["Operations Research","Artificial Intelligence","Computer Science"],"languages":["eng"],"rights":["Copyright 1995 Gratch, Jonathan Matthew"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624352","(UMI)AAI9624352"],"render_values":[{"text":"AAI9624352","href":null,"code":true},{"text":"(UMI)AAI9624352","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22285","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["DeJong, Gerald F."]},{"key":"dc:creator","label":"Author","values":["Gratch, Jonathan Matthew"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:35:00Z","10000-01-01","1995"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Operations Research","Artificial Intelligence","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1995 Gratch, Jonathan Matthew"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9624352","(UMI)AAI9624352","http://hdl.handle.net/2142/22285"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T13:35:00Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624352.pdf: 10100524 bytes, checksum: f78a4863cc1d4297bb25fc45a2381703 (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:56:35Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:26:28-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["On efficient approaches to the utility problem in adaptive problem solving"]}]}],"canonical_facts":{"dc:contributor":["DeJong, Gerald F."],"dc:creator":["Gratch, Jonathan Matthew"],"dc:date":["2011-05-07T13:35:00Z","10000-01-01","1995"],"dc:description":["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.","Made available in DSpace on 2011-05-07T13:35:00Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9624352.pdf: 10100524 bytes, checksum: f78a4863cc1d4297bb25fc45a2381703 (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:56:35Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:26:28-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9624352","(UMI)AAI9624352","http://hdl.handle.net/2142/22285"],"dc:language":["eng"],"dc:rights":["Copyright 1995 Gratch, Jonathan Matthew"],"dc:subject":["Operations Research","Artificial Intelligence","Computer Science"],"dc:title":["On efficient approaches to the utility problem in adaptive problem solving"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:19Z"}