Symbolic search allows researchers to navigate state spaces that are far too large to explore one state at a time. By using data structures like Binary Decision Diagrams (BDDs), algorithms can represent sets of states as compact directed acyclic graphs. However, the efficiency of this approach rests on a fragile foundation: the sequence in which variables are processed.
The Power of Symbolic Representation
In traditional search, the "state explosion" problem occurs because the number of possible configurations grows exponentially with the number of variables. Symbolic search, as exemplified by the SetA* algorithm proposed by Jensen et al., attempts to bypass this by performing operations on entire sets of states simultaneously.
This works because many states share common properties. BDDs and their derivatives, such as Algebraic Decision Diagrams (ADDs) used in the SPUDD algorithm by Hoey et al., exploit these redundancies by merging identical sub-graphs. When successful, a BDD can represent millions of states using only a few thousand nodes. As Edelkamp et al. demonstrated with the SYMBA* planner, this symbolic approach can dominate cost-optimal planning benchmarks where explicit-state search fails.
The Ordering Bottleneck
The primary challenge of these symbolic structures is their extreme sensitivity to variable ordering. A BDD is a canonical representation, meaning that for a fixed variable order, there is exactly one way to represent a specific Boolean function. However, changing that order can change the size of the graph from linear to exponential.
As Madre and Coudert noted in their work on truth maintenance systems, finding the absolute optimal variable ordering is an NP-complete problem. Without a near-optimal sequence, the spatial efficiency of the graph is lost. A poor ordering prevents the system from identifying and merging redundant sub-structures, leading to a "memory explosion" that can exhaust available RAM even for relatively simple problems.
This sensitivity is a recurring theme across diverse domains:
- Stochastic Games: Kwiatkowska et al. found that the efficiency of Multi-Terminal BDDs (MTBDDs) for strategy synthesis is heavily dependent on the Boolean variable sequence.
- Embedded Systems: Hansen and Tiedemann highlighted that for memory-constrained devices, a suboptimal ordering can make it impossible to store the logic required for interactive configuration.
- Automated Reasoning: Benedetti observed that extracting certificates for Quantified Boolean Formulas (QBF) becomes computationally infeasible if the symbolic representation grows uncontrollably due to ordering issues.
Why Ordering Dictates Size
To understand why ordering matters, consider how a decision diagram is constructed. Each level of the graph corresponds to a variable. If a variable that "decides" many things is placed at the top, it may allow the lower levels of the graph to be highly unified. Conversely, if a variable that creates many distinct, non-redundant branches is placed early, the graph must maintain all those branches separately for the remainder of the structure.
Hoey et al. explain that the goal is to maximize the merging of redundant sub-graphs. When the ordering is poor, the structure is forced to represent similar information multiple times in different branches. Mattmüller et al. encountered this when using Edge-Valued Multi-valued Decision Diagrams (EVMDDs) to unify state-dependent costs and conditional effects; a suboptimal sequence makes evaluating these functions computationally expensive because the diagram size explodes.
Heuristics and Alternative Structures
Because finding the optimal order is intractable, researchers rely on heuristics. Kissmann and Edelkamp introduced automated strategies based on causal graphs, which analyze the dependencies between variables in a planning domain to suggest a linear arrangement. Despite these advances, Behnke and Speck argue that identifying optimal orderings remains a critical open challenge in fields like Hierarchical Task Network (HTN) planning.
Some researchers have looked beyond standard BDDs to mitigate this sensitivity:
- Sentential Decision Diagrams (SDDs): Xue et al. proposed SDDs as a generalization of BDDs that offer more flexibility in how they decompose Boolean functions, potentially easing the ordering bottleneck.
- And-Or Belief States (AOBS): Safronov and Colledanchise introduced the AOBS structure for robot task planning, arguing that it scales better than BDDs by utilizing Cartesian products to maintain compactness even when variable evaluation orders are not ideal.
- d-DNNF: Muise noted that while BDDs are powerful, they often lack the domain-specific heuristics available to more robust formats like Decomposable Deterministic Negation Normal Forms (d-DNNF).
Ultimately, the success of symbolic search depends on the ability to keep the representation compact. As Torralba et al. emphasize in their work on Stackelberg planning, the computational advantages of the symbolic approach are only realized when the variable ordering prevents the exponential growth of the underlying data structures.
Key Foundational Work
A Logically Complete Reasoning Maintenance System Based on a Logical Constraint Solver (1991) — contributed 2 concept elements to this direction.
SetA*: An Efficient BDD-Based Heuristic Search Algorithm (2002) — contributed 1 concept elements to this direction.