Speeding Up Problem Solving by Abstraction: A Graph Oriented Approach
- Robert Holte, Department of Computing Science, University of Alberta
- T. Mkadmi, Computer Science Department, University of Ottawa
- Robert Zimmer
- Alan J. MacDonald
This paper presents a new perspective on the traditional AI task of problem solving and the techniques of abstraction and refinement. The new perspective is based on the well known, but little exploited, relation between problem solving and the task of finding a path in a graph between two given nodes. The graph oriented view of abstraction suggests two new families of abstraction techniques, algebraic abstraction and STAR abstraction. The first is shown to be extremely sensitive to the exact manner in which problems are represented. STAR abstraction, by contrast, is very widely applicable and leads to significant speedup in all our experiments. The reformulation of traditional refinement techniques as graph algorithms suggests several enhancements, including an optimal refinement algorithm, and one radically new technique: alternating search direction. Experiments comparing these techniques on a variety of problems show that alternating opportunism (AltO) a variant of the new technique, is uniformly superior to all the others.
Citation
R. Holte, T. Mkadmi, R. Zimmer, A. MacDonald. "Speeding Up Problem Solving by Abstraction: A Graph Oriented Approach". Artificial Intelligence (AIJ), 85, pp 321-361, July 1996.Keywords: | speeding up, abstraction, machine learning |
Category: | In Journal |
BibTeX
@article{Holte+al:AIJ96, author = {Robert Holte and T. Mkadmi and Robert Zimmer and Alan J. MacDonald}, title = {Speeding Up Problem Solving by Abstraction: A Graph Oriented Approach}, Volume = "85", Pages = {321-361}, journal = {Artificial Intelligence (AIJ)}, year = 1996, }Last Updated: June 04, 2007
Submitted by Staurt H. Johnson