Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning
Issue title: Special issue of the 22nd RCRA International Workshop on “Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion”
Guest editors: Stefano Bistarelli, Andrea Formisano, Marco Maratea and Paolo Torroni
Affiliations: [a] School of Computing and Engineering University of Huddersfield Huddersfield, United Kingdom m.vallati@hud.ac.uk | [b] Dipartimento d’Ingegneria dell’Informazione Università degli Studi di Brescia Brescia, Italy {ivan.serina,alessandro.saetti,alfonso.gerevini}@unibs.it
Correspondence:
[*]
Address for correspondence: School of Computing and Engineering, University of Huddersfield, Huddersfield, United Kingdom
Abstract: Case-based planning can fruitfully exploit knowledge gained by solving a large number
of problems, storing the corresponding solutions in a plan library and reusing them for solving
similar planning problems in the future. Case-based planning is very effective when similar reuse
candidates can be efficiently and effectively chosen. In this paper, we study an innovative technique based on planning problem features for efficiently retrieving solved planning problems (and relative plans) from large plan libraries. A problem feature is a characteristic –usually provided under the form of a number– of the instance that can be automatically derived from the problem specification, domain and search space analyses, or different problem encodings. Given a planning problem to solve, its features are extracted and compared to those of problems stored in the case base, in order to identify most similar problems. Since the use of existing planning features is not always able to effectively distinguish between problems within the same planning domain, we introduce a large number of new features. An experimental analysis in this paper investigates the best set of features to be exploited for retrieving plans in case-based planning, and shows that our feature-based retrieval approach can significantly improve the performance of a state-of-the-art case-based planning system.
Keywords: Automated Planning, Case-based Planning, Planning Features
