Automatic Discovery of Heuristics for Non-Deterministic Programs.
Abstract
During the last few years a number of relatively effective AI programs have been written incorporating considerable amounts of problem specific knowledge. Consequently, the problem of encoding such knowledge in a useful form has emerged as one of the central problems of AI. In particular, Declarative representations of knowledge have attracted much attention partly because of the relative ease with which knowledge can be communicated in this form. Unfortunately, implementation of Declaratively specified knowledge corresponds to a non-deterministic program which incurs enormous computational costs. This paper discusses one way to limit this cost. The approach we take is to develop control heuristics for a family of problems from traces of sample solutions generated during a training session with a human expert. Algorithms have been developed which recognize a predefined set of patterns in the sequence of 'knowledge applications' and which compile descriptions of these patterns in a control language, called CRAPS. More specifically, patterns of repeating, parallel and common sequences are considered in the analysis. The CRAPS descriptions generated are then used for guidance in solving subsequent problems. We discusss the utility of such an approach and give an example of a generated CRAPS description. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1979
- Accession Number
- ADA067546
Entities
People
- Malcolm C. Harrison
- Salvatore J. Stolfo
Organizations
- New York University