Abstract
Symbolic search allows saving large amounts of memory compared to regular explicit-state search algorithms. This is crucial in optimal settings, in which common search algorithms often exhaust the available memory. So far, the most successful uses of symbolic search have been bidirectional blind search and the generation of abstraction heuristics like Pattern Databases. Despite its usefulness, several common techniques in explicit-state search have not been employed in symbolic search. In particular, mutexes and other constraining invariants, techniques that have been proven essential when doing regression, are yet to be exploited in conjunction with BDDs. In this paper we analyze the use of such constraints in symbolic search and its combination with minimization techniques common in BDD manipulation. Experimental results show a significant increase in performance, considerably above the current state of the art in optimal planning.
Original language | English |
---|---|
Title of host publication | Sixth Annual Symposium on Combinatorial Search |
Number of pages | 9 |
Publisher | AAAI Press |
Publication date | 2013 |
Pages | 175-183 |
Publication status | Published - 2013 |
Externally published | Yes |
Event | 6th Annual Symposium on Combinatorial Search, SoCS 2013 - Leavenworth, WA, United States Duration: 11 Jul 2013 → 13 Jul 2013 |
Conference
Conference | 6th Annual Symposium on Combinatorial Search, SoCS 2013 |
---|---|
Country/Territory | United States |
City | Leavenworth, WA |
Period | 11/07/2013 → 13/07/2013 |
Bibliographical note
Copyright:Copyright 2014 Elsevier B.V., All rights reserved.
Keywords
- Planning and scheduling
- Artificial Intelligence (AI)
Fingerprint
Dive into the research topics of 'Constrained symbolic search: On mutexes, BDD minimization and more'. Together they form a unique fingerprint.Prizes
-
Best Paper Award at the 6th Symposium on Combinatorial Search
Torralba, Alvaro (Recipient), 2013
Prize: Conference prizes