Constrained symbolic search: On mutexes, BDD minimization and more

Álvaro Torralba, Vidal Alcázar

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

18 Citations (Scopus)


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 languageEnglish
Title of host publicationSixth Annual Symposium on Combinatorial Search
Number of pages9
PublisherAAAI Press
Publication date2013
Publication statusPublished - 2013
Externally publishedYes
Event6th Annual Symposium on Combinatorial Search, SoCS 2013 - Leavenworth, WA, United States
Duration: 11 Jul 201313 Jul 2013


Conference6th Annual Symposium on Combinatorial Search, SoCS 2013
Country/TerritoryUnited States
CityLeavenworth, WA

Bibliographical note

Copyright 2014 Elsevier B.V., All rights reserved.


  • Planning and scheduling
  • Artificial Intelligence (AI)


Dive into the research topics of 'Constrained symbolic search: On mutexes, BDD minimization and more'. Together they form a unique fingerprint.

Cite this