A statistical approach to adaptive problem solving

Jonathan Gratch, Gerald DeJong

Research output: Contribution to journalArticlepeer-review

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. 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.

Original languageEnglish (US)
Pages (from-to)101-142
Number of pages42
JournalArtificial Intelligence
Volume88
Issue number1-2
DOIs
StatePublished - Dec 1996

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A statistical approach to adaptive problem solving'. Together they form a unique fingerprint.

Cite this