Symbolic search avoids (or at least lessens) the costs associated with the exponential memory requirement for the state set involved as problem sizes get bigger. Representing fixed-length state vectors (of finite domain) in binary is uncomplicated. For example, the Fifteen-Puzzle can be easily encoded in 64 bits, with 4 bits encoding the label of each tile. A more concise description is the binary code for the ordinal number of the permutation associated with the puzzle state yielding bits (see Ch. 3). For Sokoban we have different options; either we encode the position of the balls individually, or we encode their layout on the board. Similarly, for propositional planning, we can encode the valid propositions in a state by using the binary representation of their index, or we take the bitvector of all facts being true and false. More generally, a state vector can be represented by encoding the domains of the vector, or—assuming a perfect hash function of a state vector—using the binary representation of the hash address.

Given a fixed-length binary state vector for a search problem, characteristic functions represent state sets. A characteristic function evaluates to true for the binary representation of a given state vector if and only if the state is a member of that set. As the mapping is one-to-one, the characteristic function can be identified with the state set.

Let us consider the following Sliding-Token Puzzle as a running example. We are given a horizontal bar, partitioned into four locations (see Fig. 7.1) with one sliding token moving between adjacent locations. In the initial state, the token is found on the left-most position . In the goal state, the token has reached position . Since we only have four options, two variables and are sufficient to uniquely describe the position of the token and, therefore, each individual state. They refer to the bits for the states. The characteristic function of all states is provided in Table 7.1.

The characteristic function for combining two or more states is the disjunction of characteristic functions of the individual states. For example, the combined representation for the two positions and is . We observe that the representation for these two states is smaller than for the single ones. A symbolic representation for several states, however, is not always smaller than an explicit one. Consider the two states and . Their combined representation is . Given the offset for representing the term, in this case the explicit representation is actually the better one, but in general, the gain for sharing the encoding is big.

Actions are also formalized as relations; that is, as sets of state pairs, or alternatively, as the characteristic function of such sets. The transition relation has twice as many variables as the encoding of the state. The transition relation Trans is defined in a way such that if x is the binary encoding of a given position and if is the binary encoding of a successor state, will evaluate to true. To construct Trans, we observe that it is the disjunction of all individual state transitions. In our case we have the six actions , , , , , and , such thatTable 7.2 relates the concepts needed for explicit-state heuristic search to their symbolic counter-parts. As a feature, all algorithms in this chapter work for initial state sets, reporting a path from one member to the goal. For the sake of coherence, we nonetheless stick to singletons. Weighted transition relations include action cost values encoded in binary. Heuristic relations partition the state space according to the heuristic estimates encoded in value.

Binary Decision Diagrams (BDDs) are fundamental to various areas such as model checking and the synthesis of hardware circuits. In AI search, they are used to space-efficiently represent huge sets of states.

In the introduction, we informally characterized BDDs as deterministic finite automata. For a more formal treatment, a binary decision diagram is a data structure for representing Boolean functions f(acting on variables ). Assignments to the variables are mapped to either true or false.

For evaluating the represented function for a given input, a path is traced from the root node to one of the sinks, quite similar to the way Decision Trees are used. What distinguishes BDDs from Decision Trees is the use of two reduction rules, detecting unnecessary variable tests and isomorphisms in subgraphs, leading to a unique representation that is polynomial in the length of the bit strings for many interesting functions.

Figure 7.2 illustrates the application of these two rules. An unreduced and a reduced BDD for the goal state of the example problem is shown in Figure 7.3.

Throughout this chapter we write BDDs, although we always mean reduced and ordered BDDs. The reason that the reduced representation is unique is that each node in a BDD represents an essential subfunction. The uniqueness of BDD representation of a Boolean function implies that the satisfiability test is available in time. (If the BDD merely consists of a 0-sink, then it is unsatisfiable, otherwise it is satisfiable.) This is a clear benefit to a general satisfiability test of Boolean formulas, which by the virtue of Cook's theorem is an NP-hard problem. Some other operations on BDDs are:

The variable ordering has a huge influence on the size (the space complexity in terms of the number of nodes to be stored) of a BDD. For example, the function has linear size ( nodes) if the ordering matches the permutation , and exponential size ( nodes) if the ordering matches the permutation . Unfortunately, the problem of finding the best ordering (the one that minimized the size of the BDD) for a given function f is NP-hard. The worst case are functions that have exponential size for all orderings (see Exercises) and, therefore, do not suggest the use of BDDs.

For transition relations, the variable ordering is also important. The standard variable ordering simply appends the variables according to the binary representation of a state; for example, . The interleaved variable ordering alternates x and variables; for example, .

The BDD for the transition relation for a noninterleaved variable ordering is shown in Figure 7.4. (Drawing the BDD for the interleaved ordering is left as an exercise.)

There are many different possibilities to come up with an encoding of states for a problem and a suitable ordering among the state variables. The more obvious ones often waste a lot of space. So it is worthwhile to spend efforts in finding a good ordering. Many applications select orderings based upon an approximate analysis of available input information. One approach is a conflict analysis, which determines how strong a state variable assignment depends on another. Variables that are dependent of each other appear as close as possible in the variable encoding.

Alternatively, advanced variable ordering techniques have been developed, such as the sifting algorithm. It is roughly characterized as follows. Because a BDD has to respect the variable ordering on each path, it is possible to partition it according to levels of nodes with the same variable index. Let be the level of nodes with variable index i, . The sifting algorithm repeatedly seaks a better position in the variable ordering for a variable (or an entire group of variables) by moving it up (or down) in the current order, and evaluating the result by measuring the resulting BDD size. In fact, variables are selected, for which the levels in the BDDs are at their widest; that is, for which is maximal. Interestingly, the reordering technique can be invoked dynamically during the course of computations.

Performing arithmetics is essential for many BDD-based algorithms. In the following we illustrate how to perform addition with finite-domain variables using BDDs (multiplication is dealt with analogously). Since most BDD packages support finite-domain variables, we abstract from the binary representation. Because it is not difficult to shift a domain from [min, max] to [0, max − min], without loss of generality, in the following we assume all variable domains start with value 0 and end with value max.

First, the BDD that encodes the binary relation can be constructed by enumerating all possible assignments of the form , ,assuming that the binary relation , written as , is provided by the underlying BDD package.

BDD represents the ternary relation . For the construction, we might enumerate all possible assignments to the variables a, b, and c. For large domains, however, the following recursive computation should be preferred:Hence, Add is the result of a fixpoint computation. Starting with the base case , which unifies all cases in which the according relation is true, the closure of Add is computed by applying the second part of the equation until the BDD representation no longer changes. The pseudo code is shown in Algorithm 7.1. To allow multiple quantification, in each iteration the sets of variables (for the parameters b and c) are swapped (denoted by ). The BDDs From and New denote the same set, but are kept as separate concepts: one is used for termination detecting and the other for initiating the next iteration.

What have we achieved so far? We are able to reformulate the initial and final states in a state space problem as BDDs. As an end in itself, this does not help much. We are interested in a sequence of actions that transforms an initial state into one that satisfies the goal.

By conjoining the transition relation with a formula describing a set of states, and quantifying the predecessor variables, we compute the representation of all states that can be reached in one step from some state in the input set. This is the relational product operator. Hence, what we are really interested in is the image of a state set S with respect to a transition relation Trans, which is equal to applying the operationwhere denotes the characteristic function of set S. The result is a characteristic function of all states reachable from the states in S in one step. For the running example, the image of the state set represented by is given byand represents the state set .

More generally, the relational product of a vector of Boolean variables x and two Boolean functions f and g combines quantification and conjunction in one step and is defined as . Since existential quantification of a Boolean variable in the Boolean function f is equal to , the quantification of the entire vector x results in a sequence of subproblem disjunctions. Although computing the relational product (for the entire vector) is NP-hard in general, specialized algorithms have been developed leading to an efficient determination of the image for many practical applications.

First, we turn to undirected search algorithms that originate in symbolic model checking.

To uncover the causes for good and bad BDD performance we aim at lower and upper bounds for BDD growth in various domains.

We have seen that in heuristic search, with every state in the search space we associate a lower-bound estimate h on the optimal solutions cost. Further, at least for consistent heuristics by reweighting the edges, the algorithm of A* reduces to Dijkstra's algorithm. The rank of a node is the combined value of the generating path length g and the estimate h.

Besides forward set simplification there are several improvement tricks that can be played to improve the performance of the BDD exploration.

Symbolic search approaches are also under theoretical and empirical investigation for classic graph algorithms, like Topological Sorting, Strongly Connected Component, Single-Source Shortest Path, All-Pairs Shortest Path, and Maximum Flow. The difference from the earlier implicit setting is that the graph is now supposed to be an input of the algorithms. In other words, we are given a graph with source represented in the form of a Boolean function or BDD , such that if and only if and for all u and v.

For the encoding of the nodes, a bit string of length is used, so that edges are represented by a relation with 2k variables. To perform an equality check in linear time an interleaved ordering is preferred to a sequential ordering .

Since the maximum accumulated weight on a path can be , the fixed size of the encoding of the weight function should be of size . It is well known that the BDD size for a Boolean function on l variables is bounded by nodes, since given the reduced structure, the deepest levels have to converge to the two sinks. Using a binary encoding for V and weights in nd we have that the worst-case size of the BDD Graph is of order , and the hope is that many structured graphs have a sublinear BDD with size . Since we cannot expect a gain for general graphs in the worst case, symbolic versions for explicit-graph algorithms are designed for sublinear runtime on special graphs and acceptable average-case behavior.

The symbolic Single-Source Shortest Path algorithm maintains distance function in the form of a BDD Dist such that if and only if . As we have discussed before, Dijkstra's algorithm considers nodes in the set Closed that already have a shortest path, selects nodes with minimum , and adds u to Closed. Then it updates f for neighbors v of u according to . With BDD operations and n being the number of nodes in the graph, one iteration can be performed with BDD operations. Having at most iterations, we have at most BDD operations in total.

For the Bellman-Ford algorithm we relax every node with followed by an update of . This can be achieved using a BDD representation for Relax on the variables for u, v, and d that evaluates to true if . In other words, the relation Relax is defined byIn total, we have BDD operations. The observation is that Dijkstra's algorithm leads to many fast operations, since the symbolic sets are fairly structured, whereas the algorithm of Bellman and Ford relaxes edges in parallel, which leads to fewer operations, but each operation is considerably slow. Experiments on random graphs show that even though Dijkstra needs space almost linear in the size of the BDD representation of the input graph, Bellman-Ford is usually faster.

Symbolic search algorithms use a functional representation to express large but finite sets of states based on a finite-domain state encoding. We have chosen binary decision diagrams (BDDs) for the space-efficient unique representation of these functions. Other representations for Boolean functions (e.g., Algebraic Decision Diagrams (ADDs), And Inverter Graphs, and Decomposable Negational Normal Forms (DNNFs)) do not change the exploration algorithms. Other symbolic data structures (e.g., Presburger automata and difference bound matrices) can cover infinite state sets, but follow similar algorithmic principles.

The advantages of symbolic search with BDDs for representing state sets include

During the exploration, a minimized binary variable encoding (e.g., for ) outperforms a unary encoding of predicates (e.g., for ). Using an appropriate relevance measure on the dependency of variables, good orderings can be obtained that lead to smaller BDDs. As an immediate consequence, precondition and effect variables should be interleaved. Permutation games are likely to be hard for BDDs, whereas games that are based on selecting indistinguishable objects appear to be easier.

Symbolic search relies on a transition relation that takes twice the number of state variables. The relation features both forward and backward search and can be extended to include action costs. If possible, the transition relation should be kept partitioned to keep the most expensive image operation tractable for larger problems. As enumerating all problem graph edges is out of reach for an implicit graph search, we have introduced partitions by individual actions (disjunctive partitioning), by abstract distance values (pattern database partitioning), by hash differences (branching partitioning), and by discrete action costs (cost value partitioning). Using a discretization into buckets, BDD arithmetics can be avoided. Duplicate detection with respect to previous exploration sets is not necessarily an advantage, as it may complicate the BDD representation, but as a trade-off, we can detect a nonsolvable search problem due to a complete exploration. Even though it is difficult to formalize by the series of subproblem disjunctions, the number of represented states seems to have some influence on the hardness of computing the image of a state set. The number of previous levels that need to be maintained in the RAM to preserve full duplicate detection has been introduced in previous chapters (e.g., Ch. 6).

We have emphasized the similarities to other implicit graph search algorithms, and propose symbolic search variants for breadth-first search, Dijkstra search, and A*. The two blind search algorithms were used to construct pattern databases in suitable abstract spaces. The advantages with respect to explicit-state pattern databases have been made visible in time and space.

Symbolic heuristic and branch-and-bound search is an apparent integration of compaction (using BDDs) and pruning (using pruning by the f-cost). In difference to symbolic A*, symbolic versions of branch-and-bound take the solution bound as an additional input parameter. For problems with exponentially increasing state set sizes, iterative deepening applies.

Table 7.6 summarizes the presented approaches. We indicate if disjunctive transition function splitting can be used to compute the image. We also denote whether or not the provided implementations use a visited list for duplicate detection (DDD). The table also shows whether BDD arithmetic is used, if the search is guided by a heuristic relation, and if the result is optimal.

Additionally, we have seen an alternative application for symbolic search methods. We have discussed a symbolic algorithm for solving the Single-Source Shortest Path problem in explicit but symbolically represented graphs.

BDDs together with efficient operations on them have been made prominent by Bryant (1992), but binary decision diagrams go back to Lee (1959) and Akers (1978). Minato, Ishiura, and Yajima (1990) have shown how to store several BDDs in a joint structure. One of the best libraries is CUDD, maintained by Fabio Somenzi. Improved implementation issues are found in Yang et al. (1998). The authors have shown that the number of subproblem disjunctions is a good platform-independent measure of the work to be performed in computing the image. Lower bounds and some generalized BDD structures have been studied by Sieling (1994). A survey on theory and applications of BDDs has been given by Wegener (2000).

The use of BDDs for model checking, known as symbolic model checking, has been introduced by McMillan (1993). Implementations for symbolic model checkers based on BDDs include nuSMV by Cimatti, Giunchiglia, Giunchiglia, and Traverso (1997) and μcke by Biere (1997). Alternatives for symbolic exploration with BDDs are bounded model checkers introduced by Biere, Cimatti, Clarke, and Zhu (1999) that base on thresholded Sat solving as in the Satplan system by Kautz and Selman (1996). The rise of heuristic search procedures for explicit and symbolic model checking tools (e.g., by Edelkamp, Leue, and Lluch-Lafuente, 2004b and by Qian and Nymeyer, 2004) indicate that synergies between the disciplines are many-fold.

Symbolic A* (alias BDDA*) has been invented by Edelkamp and Reffel (1998) in the context of solving the (n²−1)-Puzzle and Sokoban. The work estimated the maximum number of iterations. The algorithm has been ported to hardware verification problems (Reffel and Edelkamp, 1999) and has been integrated in the presented planning context by Edelkamp and Helmert (2001). ADDA* developed by Hansen, Zhou, and Feng (2002) is an alternative implementation of symbolic A* with ADDs. Jensen, Bryant, and Veloso (2002) have refined the partitioning in symbolic A*. The authors also have exploited on a matrix representation of g-values and h-values. An extensive treatment, including applications in nondeterministic and adversarial domains, has been provided by Jensen (2003). Symbolic branch-and-bound search has been proposed by Jensen, Hansen, Richards, and Zhou (2006).

In an experimental study, Qian and Nymeyer (2003) indicated that for BDD exploration with heuristics with smaller range and inducing a simpler BDD structure, sometimes to speedup the overall search process better than more complex heuristics (having more involved BDDs). However, this has not been shown to be a general trend.

Different symbolic approaches are under theoretical and empirical investigation for classic graph algorithms. The used upper bound O(2ⁿ/n) for the BDD size on n variables is due to the work of Breitbart, Hunt, and Rosenkrantz (1995). In fact, Breitbart, Hunt, and Rosenkrantz (1992) already have determined this lower bound and a matching upper bound function. The presented study for Topological Sorting has been proposed by Woelfel (2006). Maximum Flow has been studied by Hachtel and Somenzi (1992), with an improvement given by Sawatzki (2004b). A treatment for shortest paths based on a symbolical representation of the entire state space is also subject to current research; for example, the All-Pairs Shortest Path problem has been considered by Sawatzki (2004a).