Exploiting macro-actions and predicting plan length in planning as satisfiability

Alfonso E. Gerevini, Alessandro Saetti, Mauro Vallati

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The use of automatically learned knowledge for a planning domain can significantly improve the performance of a generic planner when solving a problem in this domain. In this work, we focus on the well-known SAT-based approach to planning and investigate two types of learned knowledge: macro-actions and planning horizon. Macro-actions are sequences of actions that typically occur in the solution plans, while a planning horizon of a problem is the length of a (possibly optimal) plan solving it. We propose a method that uses a machine learning tool for building a predictive model of the optimal planning horizon, and variants of the well-known planner SatPlan and solver MiniSat that can exploit macro actions and learned planning horizons to improve their performance. An experimental analysis illustrates the effectiveness of the proposed techniques demonstrating that significant speedups can be obtained.
LanguageEnglish
Pages323-344
Number of pages22
JournalAI Communications
Volume28
Issue number2
DOIs
Publication statusPublished - Apr 2015
Event19th RCRA International Workshop on "Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion" - Sapienza University, Rome, Italy
Duration: 14 Jun 201215 Jun 2012
http://rcra.aixia.it/rcra2012/workshop-programme (Link to Workshop Programme)

Fingerprint

Macros
Planning
Learning systems

Cite this

Gerevini, Alfonso E. ; Saetti, Alessandro ; Vallati, Mauro. / Exploiting macro-actions and predicting plan length in planning as satisfiability. In: AI Communications. 2015 ; Vol. 28, No. 2. pp. 323-344.
@article{c2f82977aa644ebfb10f5143a11b8604,
title = "Exploiting macro-actions and predicting plan length in planning as satisfiability",
abstract = "The use of automatically learned knowledge for a planning domain can significantly improve the performance of a generic planner when solving a problem in this domain. In this work, we focus on the well-known SAT-based approach to planning and investigate two types of learned knowledge: macro-actions and planning horizon. Macro-actions are sequences of actions that typically occur in the solution plans, while a planning horizon of a problem is the length of a (possibly optimal) plan solving it. We propose a method that uses a machine learning tool for building a predictive model of the optimal planning horizon, and variants of the well-known planner SatPlan and solver MiniSat that can exploit macro actions and learned planning horizons to improve their performance. An experimental analysis illustrates the effectiveness of the proposed techniques demonstrating that significant speedups can be obtained.",
keywords = "planning, satisfiability, Machine learning",
author = "Gerevini, {Alfonso E.} and Alessandro Saetti and Mauro Vallati",
year = "2015",
month = "4",
doi = "10.3233/AIC-140641",
language = "English",
volume = "28",
pages = "323--344",
journal = "AI Communications",
issn = "0921-7126",
publisher = "IOS Press",
number = "2",

}

Exploiting macro-actions and predicting plan length in planning as satisfiability. / Gerevini, Alfonso E.; Saetti, Alessandro; Vallati, Mauro.

In: AI Communications, Vol. 28, No. 2, 04.2015, p. 323-344.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Exploiting macro-actions and predicting plan length in planning as satisfiability

AU - Gerevini, Alfonso E.

AU - Saetti, Alessandro

AU - Vallati, Mauro

PY - 2015/4

Y1 - 2015/4

N2 - The use of automatically learned knowledge for a planning domain can significantly improve the performance of a generic planner when solving a problem in this domain. In this work, we focus on the well-known SAT-based approach to planning and investigate two types of learned knowledge: macro-actions and planning horizon. Macro-actions are sequences of actions that typically occur in the solution plans, while a planning horizon of a problem is the length of a (possibly optimal) plan solving it. We propose a method that uses a machine learning tool for building a predictive model of the optimal planning horizon, and variants of the well-known planner SatPlan and solver MiniSat that can exploit macro actions and learned planning horizons to improve their performance. An experimental analysis illustrates the effectiveness of the proposed techniques demonstrating that significant speedups can be obtained.

AB - The use of automatically learned knowledge for a planning domain can significantly improve the performance of a generic planner when solving a problem in this domain. In this work, we focus on the well-known SAT-based approach to planning and investigate two types of learned knowledge: macro-actions and planning horizon. Macro-actions are sequences of actions that typically occur in the solution plans, while a planning horizon of a problem is the length of a (possibly optimal) plan solving it. We propose a method that uses a machine learning tool for building a predictive model of the optimal planning horizon, and variants of the well-known planner SatPlan and solver MiniSat that can exploit macro actions and learned planning horizons to improve their performance. An experimental analysis illustrates the effectiveness of the proposed techniques demonstrating that significant speedups can be obtained.

KW - planning

KW - satisfiability

KW - Machine learning

UR - http://content.iospress.com/articles/ai-communications/aic641

U2 - 10.3233/AIC-140641

DO - 10.3233/AIC-140641

M3 - Article

VL - 28

SP - 323

EP - 344

JO - AI Communications

T2 - AI Communications

JF - AI Communications

SN - 0921-7126

IS - 2

ER -