SPEEDING-UP PROBLEM-SOLVING BY ABSTRACTION - A GRAPH ORIENTED APPROACH

This paper presents a new perspective on the traditional AI task of pr oblem solving and the techniques of abstraction and refinement. The ne w perspective is based on the well-known, but little exploited, relati on between problem solving and the task of finding a path in a graph b etween two given nodes. The graph oriented view of abstraction suggest s two new families of abstraction techniques, algebraic abstraction an d STAR abstraction. The first is shown to be extremely sensitive to th e 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 te chniques as graph algorithms suggests several enhancements, including an optimal refinement algorithm, and one radically new technique: alte rnating 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.