Automatically Generating Abstractions for Planning
Abstract
This article presents a completely automated approach to generating abstractions for planning. The abstractions are generated using a tractable, domain-independent algorithm whose only input is the definition of a problem to be solved and whose output is an abstraction hierarchy that is tailored to the particular problem. The algorithm generates abstraction hierarchical dropping literals from the original problem definition. It forms abstractions that satisfy the ordered monotonicity property, which guarantees that the structure of an abstract solution is not changed in the process of refining it. The algorithm for generating abstractions is implemented in a system called ALPINE, which generates abstractions for a hierarchical version of the PRODIGY problem solver. The abstractions generated by ALPINE are tested in multiple domains on large problem sets and are shown to produce shorter solutions with significantly less search than planning without using abstraction. Artificial intelligence, Abstraction, planning, Hierarchical planning, Problem solving, problem reformulation, Learning, ALPINE.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1993
- Accession Number
- ADA269772
Entities
People
- Craig Knoblock
Organizations
- University of Southern California