Reference: Unruh, A. Using Automatic Abstraction for Problem-Solving and Learning. Ph.D Thesis, Stanford University, 1995.
Abstract: Abstraction has proven to be a powerful tool for controlling the combinatorics of a problem-solving search. It is also of critical importance for learning systems. This research develops a set of abstraction techniques which provide a problem solver with a domain-independent {\em weak method} for abstraction. The method allows the problem solver to: (1) automatically determine when to abstract; (2) automatically determine what to abstract, and dynamically create abstract problem spaces from the original domain spaces; and (3) provides the problem solver with an integrated model of abstract problem-solving and learning. The abstraction method has been implemented and empirically evaluated. It has been shown to: reduce planning time, while still yielding solutions of acceptable quality; reduce learning time; and increase the effectiveness of learned rules by enabling them to transfer to a wider range of situations. The core idea underlying the abstraction techniques is that abstraction can arise as an obviation response to impasses in planning. This basic idea is used to reduce the amount of effort required to perform look-ahead searches during problem solving (searches performed in service of a control decision, during which the available options are explored and evaluated), by performing abstract search in problem spaces which are dynamically and automatically abstracted from the ground spaces during search. New search control rules are learned based on the abstract searches; they constitute an abstract plan the problem solver can use in future situations, and are used to produce an emergent multi-level abstraction behavior. Although this basic abstraction method is broadly applicable, it is too weak and does not yield good performance in all of the domains to which it is applied. In response to this, several domain-independent method increments have been developed to strengthen the method; added to the basic abstraction method, they have succeeded in making tractable a number of problems which were intractable with both non-abstract problem-solving and the simpler weak abstraction method. The two primary method increments are called {\em assumption counting} and {\em iterative abstraction}. Assumption counting involves adding a component to the plan evaluation function that counts the number of times the ground domain theory was reformulated before a solution was reached. This is a measure -- though not an exact one -- of the amount of instantiation that will be required of the abstract plan, and enables abstract detection of interactions between subgoals. Iterative abstraction can be viewed as a search through a space of plans at varying levels of abstraction. It uses a heuristic which suggests that in the absence of more specific knowledge, a useful level of abstraction for a given control decision during problem solving is that at which one of the choices at the decision appears clearly the best. Implementation of this situation-dependent heuristic enables a unique approach to abstraction creation, during which the problem solver combines selection and synthesis by experimenting with successively less abstract versions of a situation in an effort to estimate the most abstract (hence cheapest) level of description at which useful decision-making can still occur for a situation. With the iterative abstraction method increment, more effort is spent in searching for the initial abstract plan, so as to increase the chances of being able to effectively and efficiently implement it. Using iterative abstraction, upon making a decision about the level of abstraction it considers appropriate for a particular situation, the system learns plan fragments for the situation at that level of abstraction. Thus, the system accumulates plans containing information at multiple abstraction levels. In new situations, the context determines the level of abstraction of the plans used.
Full paper available as ps.