Heuristics for planning with SAT

Jussi Rintanen

doi:10.1007/978-3-642-15396-9_34

Heuristics for planning with SAT

Jussi Rintanen^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

28 Citations (Scopus)

Abstract

Generic SAT solvers have been very successful in solving hard combinatorial problems in various application areas, including AI planning. There is potential for improved performance by making the SAT solving process more application-specific. In this paper we propose a variable selection strategy for AI planning. The strategy is based on generic principles about properties of plans, and its performance with standard planning benchmarks often substantially improves on generic variable selection heuristics used in SAT solving, such as the VSIDS strategy. These improvements lift the efficiency of SAT based planning to the same level as best planners that use other search methods.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming, CP 2010 - 16th International Conference, Proceedings
Publisher	Springer Verlag
Pages	414-428
Number of pages	15
ISBN (Print)	364215395X, 9783642153952
DOIs	https://doi.org/10.1007/978-3-642-15396-9_34
Publication status	Published - 2010
Event	16th International Conference on Principles and Practice of Constraint Programming, CP 2010 - St. Andrews, United Kingdom Duration: 6 Sept 2010 → 10 Sept 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6308 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Principles and Practice of Constraint Programming, CP 2010
Country/Territory	United Kingdom
City	St. Andrews
Period	6/09/10 → 10/09/10

Access to Document

10.1007/978-3-642-15396-9_34

Cite this

Rintanen, J. (2010). Heuristics for planning with SAT. In Principles and Practice of Constraint Programming, CP 2010 - 16th International Conference, Proceedings (pp. 414-428). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6308 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-15396-9_34

@inproceedings{c6fb3c518e9a446c929e16ec1b559f41,

title = "Heuristics for planning with SAT",

abstract = "Generic SAT solvers have been very successful in solving hard combinatorial problems in various application areas, including AI planning. There is potential for improved performance by making the SAT solving process more application-specific. In this paper we propose a variable selection strategy for AI planning. The strategy is based on generic principles about properties of plans, and its performance with standard planning benchmarks often substantially improves on generic variable selection heuristics used in SAT solving, such as the VSIDS strategy. These improvements lift the efficiency of SAT based planning to the same level as best planners that use other search methods.",

author = "Jussi Rintanen",

year = "2010",

doi = "10.1007/978-3-642-15396-9_34",

language = "English",

isbn = "364215395X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "414--428",

booktitle = "Principles and Practice of Constraint Programming, CP 2010 - 16th International Conference, Proceedings",

address = "Germany",

note = "16th International Conference on Principles and Practice of Constraint Programming, CP 2010 ; Conference date: 06-09-2010 Through 10-09-2010",

}

Rintanen, J 2010, Heuristics for planning with SAT. in Principles and Practice of Constraint Programming, CP 2010 - 16th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6308 LNCS, Springer Verlag, pp. 414-428, 16th International Conference on Principles and Practice of Constraint Programming, CP 2010, St. Andrews, United Kingdom, 6/09/10. https://doi.org/10.1007/978-3-642-15396-9_34

Heuristics for planning with SAT. / Rintanen, Jussi.
Principles and Practice of Constraint Programming, CP 2010 - 16th International Conference, Proceedings. Springer Verlag, 2010. p. 414-428 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6308 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Heuristics for planning with SAT

AU - Rintanen, Jussi

PY - 2010

Y1 - 2010

N2 - Generic SAT solvers have been very successful in solving hard combinatorial problems in various application areas, including AI planning. There is potential for improved performance by making the SAT solving process more application-specific. In this paper we propose a variable selection strategy for AI planning. The strategy is based on generic principles about properties of plans, and its performance with standard planning benchmarks often substantially improves on generic variable selection heuristics used in SAT solving, such as the VSIDS strategy. These improvements lift the efficiency of SAT based planning to the same level as best planners that use other search methods.

AB - Generic SAT solvers have been very successful in solving hard combinatorial problems in various application areas, including AI planning. There is potential for improved performance by making the SAT solving process more application-specific. In this paper we propose a variable selection strategy for AI planning. The strategy is based on generic principles about properties of plans, and its performance with standard planning benchmarks often substantially improves on generic variable selection heuristics used in SAT solving, such as the VSIDS strategy. These improvements lift the efficiency of SAT based planning to the same level as best planners that use other search methods.

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

U2 - 10.1007/978-3-642-15396-9_34

DO - 10.1007/978-3-642-15396-9_34

M3 - Conference contribution

SN - 364215395X

SN - 9783642153952

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

SP - 414

EP - 428

BT - Principles and Practice of Constraint Programming, CP 2010 - 16th International Conference, Proceedings

PB - Springer Verlag

T2 - 16th International Conference on Principles and Practice of Constraint Programming, CP 2010

Y2 - 6 September 2010 through 10 September 2010

ER -

Heuristics for planning with SAT

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this