Underestimation vs. overestimation in SAT-based planning

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Planning as satisfiability is one of the main approaches to finding parallel optimal solution plans for classical planning problems. Existing high performance SAT-based planners are able to exploit either forward or backward search strategy; starting from an underestimation or overestimation of the optimal plan length, they keep increasing or decreasing the estimated plan length and, for each fixed length, they either find a solution or prove the unsatisfiability of the corresponding SAT instance. In this paper we will discuss advantages and disadvantages of the underestimating and overestimating techniques, and we will propose an effective online decision system for selecting the most appropriate technique for solving a given planning problem. Finally, we will experimentally show that the exploitation of such a decision system improves the performance of the well known SAT-based planner SatPlan.

Original languageEnglish
Title of host publicationAI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings
Pages276-287
Number of pages12
Volume8249 LNAI
DOIs
Publication statusPublished - 2013
Event13th International Conference of the Italian Association for Artificial Intelligence - Turin, Italy
Duration: 4 Dec 20136 Dec 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8249 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference13th International Conference of the Italian Association for Artificial Intelligence
Abbreviated titleAI*IA 2013
CountryItaly
CityTurin
Period4/12/136/12/13

Fingerprint

Decision System
Planning
Search Strategy
Exploitation
High Performance
Optimal Solution

Cite this

Vallati, M., Chrpa, L., & Crampton, A. (2013). Underestimation vs. overestimation in SAT-based planning. In AI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings (Vol. 8249 LNAI, pp. 276-287). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8249 LNAI). https://doi.org/10.1007/978-3-319-03524-6_24
Vallati, Mauro ; Chrpa, Lukáš ; Crampton, Andrew. / Underestimation vs. overestimation in SAT-based planning. AI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings. Vol. 8249 LNAI 2013. pp. 276-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{7c25f9737e384e58a56f481465e7b01a,
title = "Underestimation vs. overestimation in SAT-based planning",
abstract = "Planning as satisfiability is one of the main approaches to finding parallel optimal solution plans for classical planning problems. Existing high performance SAT-based planners are able to exploit either forward or backward search strategy; starting from an underestimation or overestimation of the optimal plan length, they keep increasing or decreasing the estimated plan length and, for each fixed length, they either find a solution or prove the unsatisfiability of the corresponding SAT instance. In this paper we will discuss advantages and disadvantages of the underestimating and overestimating techniques, and we will propose an effective online decision system for selecting the most appropriate technique for solving a given planning problem. Finally, we will experimentally show that the exploitation of such a decision system improves the performance of the well known SAT-based planner SatPlan.",
author = "Mauro Vallati and Luk{\'a}š Chrpa and Andrew Crampton",
year = "2013",
doi = "10.1007/978-3-319-03524-6_24",
language = "English",
isbn = "9783319035239",
volume = "8249 LNAI",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "276--287",
booktitle = "AI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings",

}

Vallati, M, Chrpa, L & Crampton, A 2013, Underestimation vs. overestimation in SAT-based planning. in AI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings. vol. 8249 LNAI, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8249 LNAI, pp. 276-287, 13th International Conference of the Italian Association for Artificial Intelligence, Turin, Italy, 4/12/13. https://doi.org/10.1007/978-3-319-03524-6_24

Underestimation vs. overestimation in SAT-based planning. / Vallati, Mauro; Chrpa, Lukáš; Crampton, Andrew.

AI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings. Vol. 8249 LNAI 2013. p. 276-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8249 LNAI).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Underestimation vs. overestimation in SAT-based planning

AU - Vallati, Mauro

AU - Chrpa, Lukáš

AU - Crampton, Andrew

PY - 2013

Y1 - 2013

N2 - Planning as satisfiability is one of the main approaches to finding parallel optimal solution plans for classical planning problems. Existing high performance SAT-based planners are able to exploit either forward or backward search strategy; starting from an underestimation or overestimation of the optimal plan length, they keep increasing or decreasing the estimated plan length and, for each fixed length, they either find a solution or prove the unsatisfiability of the corresponding SAT instance. In this paper we will discuss advantages and disadvantages of the underestimating and overestimating techniques, and we will propose an effective online decision system for selecting the most appropriate technique for solving a given planning problem. Finally, we will experimentally show that the exploitation of such a decision system improves the performance of the well known SAT-based planner SatPlan.

AB - Planning as satisfiability is one of the main approaches to finding parallel optimal solution plans for classical planning problems. Existing high performance SAT-based planners are able to exploit either forward or backward search strategy; starting from an underestimation or overestimation of the optimal plan length, they keep increasing or decreasing the estimated plan length and, for each fixed length, they either find a solution or prove the unsatisfiability of the corresponding SAT instance. In this paper we will discuss advantages and disadvantages of the underestimating and overestimating techniques, and we will propose an effective online decision system for selecting the most appropriate technique for solving a given planning problem. Finally, we will experimentally show that the exploitation of such a decision system improves the performance of the well known SAT-based planner SatPlan.

UR - http://www.scopus.com/inward/record.url?scp=84892748612&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-03524-6_24

DO - 10.1007/978-3-319-03524-6_24

M3 - Conference contribution

SN - 9783319035239

VL - 8249 LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 276

EP - 287

BT - AI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings

ER -

Vallati M, Chrpa L, Crampton A. Underestimation vs. overestimation in SAT-based planning. In AI*IA 2013: Advances in Artificial Intelligence - XIIIth International Conference of the Italian Association for Artificial Intelligence, Proceedings. Vol. 8249 LNAI. 2013. p. 276-287. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-03524-6_24