Using automatic abstraction for problem-solving and learning

From Semantic Portal Wiki

{{#vardefine:category|Publication}}{{#vardefine:templatename|i.publication}}{{#vardefine:package|smwbp_instance_templates}}

Edit

Reference: {{#vardefine:pagename|using automatic abstraction for problem-solving and learning }}

1. [[]]

bibtex

{{#vardefine:pagename|Using automatic abstraction for problem-solving and learning }}{{#vardefine:key| }}

abstract: Abstraction has proven to be a powerful tool for controlling thecombinatorics of a problem-solving search. It is also of critical importancefor learning systems.This research develops a set of abstraction techniques which provide a problemsolver with a domain-independent {\em weak method} for abstraction. Themethod allows the problem solver to: (1) automatically determine when toabstract; (2) automatically determine what to abstract, and dynamicallycreate abstract problem spaces from the original domain spaces; and (3)provides the problem solver with an integrated model of abstractproblem-solving and learning.The abstraction method has been implemented and empirically evaluated.It has been shown to: reduce planning time, while still yieldingsolutions of acceptable quality; reduce learning time; and increasethe effectiveness of learned rules by enabling them to transfer to awider range of situations.The core idea underlying the abstraction techniques is that abstractioncan arise as an obviation response to impasses in planning. Thisbasic idea is used to reduce the amount of effort required to performlook-ahead searches during problem solving (searches performed inservice of a control decision, during which the available options areexplored and evaluated), by performing abstract search in problemspaces which are dynamically and automatically abstracted from theground spaces during search. New search control rules are learnedbased on the abstract searches; they constitute an abstract plan theproblem solver can use in future situations, and are used to producean emergent multi-level abstraction behavior.Although this basic abstraction method is broadly applicable, it is too weakand does not yield good performance in all of the domains to which it isapplied. In response to this, several domain-independent method incrementshave been developed to strengthen the method; added to the basic abstractionmethod, they have succeeded in making tractable a number of problems whichwere intractable with both non-abstract problem-solving and the simpler weakabstraction method. The two primary method increments are called {\emassumption counting} and {\em iterative abstraction}.Assumption counting involves adding a component to the plan evaluationfunction that counts the number of times the ground domain theory wasreformulated before a solution was reached. This is a measure -- though notan exact one -- of the amount of instantiation that will be required of theabstract plan, and enables abstract detection of interactions betweensubgoals.Iterative abstraction can be viewed as a search through a space of plans atvarying levels of abstraction. It uses a heuristic which suggests that inthe absence of more specific knowledge, a useful level of abstraction for agiven control decision during problem solving is that at which one of thechoices at the decision appears clearly the best. Implementation of thissituation-dependent heuristic enables a unique approach to abstractioncreation, during which the problem solver combines selection and synthesis byexperimenting with successively less abstract versions of a situationin an effort to estimate the most abstract (hence cheapest) level ofdescription at which useful decision-making can still occur for a situation.With the iterative abstraction method increment, more effort is spent insearching for the initial abstract plan, so as to increase the chances ofbeing able to effectively and efficiently implement it.Using iterative abstraction, upon making a decision about the level ofabstraction it considers appropriate for a particular situation, thesystem learns plan fragments for the situation at that level ofabstraction. Thus, the system accumulates plans containinginformation at multiple abstraction levels. In new situations, thecontext determines the level of abstraction of the plans used.

download:

• paper:
• slides: