An Efficient BDD-based A* Algorithm

    Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

    Abstract

    In this paper we combine the goal directed search of A* with the ability of BDDs to traverse an exponential number of states in polynomial time. We introduce a new algorithm, SetA*, that generalizes A* to expand sets of states in each iteration. SetA* has substantial advantages over BDDA*, the only previous BDD-based A* implementation we are aware of. Our experimental evaluation proves SetA* to be a powerful search paradigm. For some of the studied problems it outperforms BDDA*, A*, and BDD-based breadth-first search by several orders of magnitude. We believe exploring sets of states to be essential when the heuristic function is weak. For problems with strong heuristics, SetA* efficiently specializes to single-state search and consequently challenges single-state heuristic search in general.
    Original languageEnglish
    Title of host publicationProceedings of the International Conference on Artificial Intelligence Planning Systems (AIPS-02) Workshop on Planning via Model Checking
    Number of pages9
    PublisherAAAI Press
    Publication date2002
    Pages72-80
    Publication statusPublished - 2002

    Keywords

    • Algorithmic Search
    • Set Expansion
    • Heuristic Function
    • BDD-Based Methods
    • State Space Traversal

    Fingerprint

    Dive into the research topics of 'An Efficient BDD-based A* Algorithm'. Together they form a unique fingerprint.

    Cite this