Stratified Case-Based Reasoning in Non-Refinable Abstraction Hierarchies

Papers

Stratified case-based reasoning (ScBR) is a technique in which case abstractions are used to assist case retrieval, matching, and adaptation. Previous work showed that SCBR can significantly decrease the computational expense required for retrieval, matching, and adaptation in a route-finding domain characterized by abstraction hierarchies with the downward refinement property. This work explores the effectiveness of SCBR in hierarchies without the downward refinement property. In an experimental evaluation using such hierarchies (1) SCBR significantly decreased search cost in hierarchies without the downward refinement property, although the speedup over groundlevel A* was not as great as in refinable hierarchies, (2) little difference was observed in SCBR search costs between case libraries created top-down in the process of P~EFINEMENT and those created bottom-up from a valid ground solution, and (3) the most important factor in determining speedup appeared to be a priori likelihood that a previous solution can be usefully applied to a new problem.