State-Set Branching: Leveraging OBDDs for Heuristic Search

In this paper, we introduce a framework called state-set branching that combines symbolic search based on the reduced Ordered Binary Decision Diagram (OBDD) with classical heuristic search, such as A* and best-first search. The framework relies on an extension of these algorithms from expanding a single state in each iteration to expanding a set of states. We prove that it is generally sound and optimal for two A* implementations and show how a new OBDD technique called branching partitioning can be used to efficiently expand sets of states. The framework is general. It applies to any heuristic function, any evaluation function, and any transition cost function. Moreover, branching partitioning applies to both disjunctive and conjunctive transition relation partitioning, An extensive experimental evaluation involving several new and classical domains proves state-set branching to be a powerful framework. It consistently outperforms single-state A*, except when the heuristic is very strong. In addition, we show that it can improve the complexity of single-state search exponentially and that it often dominates both single-state A* and blind OBDD-based search by several orders of magnitude. Moreover, it has substantially better performance than BDDA*, the only previous OBDD-based implementation of A*.