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*.