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
AN - SCOPUS:84892748612
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
T2 - 13th International Conference of the Italian Association for Artificial Intelligence
Y2 - 4 December 2013 through 6 December 2013
ER -