Searching for Plans Using a Hierarchy of Learned Macros and Selective Reuse
Abstract
This research presents a new approach to improving the performance of a macro planner: selective reuse. In macro planning, reuse can result in poorer performance than when planning with only primitive operators, a phenomenon that has been called the utility problem. The utility problem arises because the benefits of reuse are outweighed by the cost of retrieving a macro to reuse and the cost of searching through the larger search space caused by considering reuse candidates. Selective reuse contains the expansion of the search space by limiting the number of reuse candidates considered and limits the search required by considering only those reuse candidates that entail no additional work. Previously, performance improvement in a macro planner has been possible only by selective learning. Unlike selective learning, selective reuse never overlooks a learning opportunity that might have value in future problem solving. This research developed a polynomial-order retrieval method which reduces the cost of retrieving a reuse candidate likely to save search. A macro planner (HINGE) was implemented to explore selective reuse. To improve the probability of beneficial reuse. HINGE searches in a space of plans using a hierarchically-structured search method that provides multiple opportunities for reuse.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1994
- Accession Number
- ADA280594
Entities
People
- Douglas E. Dyer
Organizations
- Air Force Institute of Technology