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.
|Title of host publication||Sixth Annual Symposium on Combinatorial Search|
|Number of pages||9|
|Publication status||Published - 2013|
|Event||6th Annual Symposium on Combinatorial Search, SoCS 2013 - Leavenworth, WA, United States|
Duration: 11 Jul 2013 → 13 Jul 2013
|Conference||6th Annual Symposium on Combinatorial Search, SoCS 2013|
|Period||11/07/2013 → 13/07/2013|
Copyright 2014 Elsevier B.V., All rights reserved.
- Planning and scheduling
- Artificial Intelligence (AI)
FingerprintDive into the research topics of 'Constrained symbolic search: On mutexes, BDD minimization and more'. Together they form a unique fingerprint.
Torralba, Alvaro (Recipient), 2013
Prize: Conference prizes