Accession Number:

ADA597663

Title:

Automatic Representation Changes in Problem Solving

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1999-06-01

Pagination or Media Count:

498.0

Abstract:

The purpose of our research is to enhance the efficiency of AI problem solvers by automating representation changes. We have developed a system that improves description of input problems and selects an appropriate search algorithm for each given problem. Researchers have accumulated much evidence of the importance of appropriate representations for the efficiency of AI systems. The same problem may be easy or difficult, depending on the way we describe it and on the search algorithm we use. Previous work on automatic improvement of problem description has mostly been limited to the design of individual learning algorithms. The user has traditionally been responsible for the choice of algorithms appropriate for a given problem. We present a system that integrates multiple description-changing and problem-solving algorithms. The purpose of our work is to formalize the concept of representation, explore its role in problem solving, and confirm the following general hypothesis An effective representation-changing system can be constructed out of three parts a library of problem-solving algorithms a library of algorithms that improve problem description by static analysis and learning and a top-level control module that selects appropriate algorithms for each given problem. We have supported this hypothesis by building a system that improves representations in the prodigy problem-solving architecture. The library of problem solvers consists of several search engines available in the prodigy architecture. The library of description changers comprises novel algorithms for selecting primary effects generating abstractions, and discarding irrelevant elements of a problem encoding. The control module chooses and applies appropriate description changers, stores and reuses new descriptions, and selects problem solvers. We define a space of possible representations of a given problem, and view the task of changing representation as search in this space.

Subject Categories:

  • Operations Research
  • Cybernetics
  • Manufacturing and Industrial Engineering and Control of Production Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE