Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning

Mauro Vallati, Ivan Serina, Alessandro Saetti, Alfonso Emilio Gerevini

Research output: Contribution to journalArticle

1 Citation (Scopus)

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.
Original languageEnglish
Pages (from-to)209-240
Number of pages32
JournalFundamenta Informaticae
Volume149
Issue number1-2
DOIs
Publication statusPublished - 24 Dec 2016
Event22nd RCRA International Workshop on "Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion" - Ferrara, Italy
Duration: 22 Sep 201522 Sep 2015

Fingerprint

Retrieval
Planning
Experimental Analysis
Search Space
Reuse
Encoding
Specifications
Specification

Cite this

Vallati, Mauro ; Serina, Ivan ; Saetti, Alessandro ; Gerevini, Alfonso Emilio. / Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning. In: Fundamenta Informaticae. 2016 ; Vol. 149, No. 1-2. pp. 209-240.
@article{6a084e685d8644548679bcc1ea6c0d0b,
title = "Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning",
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",
author = "Mauro Vallati and Ivan Serina and Alessandro Saetti and Gerevini, {Alfonso Emilio}",
note = "AAM deposited in ePrints within 3 months of acceptance; journal does not allow archiving of any version (see Sherpa)",
year = "2016",
month = "12",
day = "24",
doi = "10.3233/FI-2016-1447",
language = "English",
volume = "149",
pages = "209--240",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "1-2",

}

Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning. / Vallati, Mauro; Serina, Ivan; Saetti, Alessandro; Gerevini, Alfonso Emilio.

In: Fundamenta Informaticae, Vol. 149, No. 1-2, 24.12.2016, p. 209-240.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Identifying and Exploiting Features for Effective Plan Retrieval in Case-Based Planning

AU - Vallati, Mauro

AU - Serina, Ivan

AU - Saetti, Alessandro

AU - Gerevini, Alfonso Emilio

N1 - AAM deposited in ePrints within 3 months of acceptance; journal does not allow archiving of any version (see Sherpa)

PY - 2016/12/24

Y1 - 2016/12/24

N2 - 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.

AB - 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.

KW - Automated Planning

KW - case-based planning

KW - planning features

U2 - 10.3233/FI-2016-1447

DO - 10.3233/FI-2016-1447

M3 - Article

VL - 149

SP - 209

EP - 240

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-2

ER -