In fields like automated planning, formal verification, and reactive synthesis, researchers face a common enemy: the "state space explosion." As systems grow in complexity—adding more variables, agents, or possible actions—the number of possible configurations grows exponentially. Traditional "explicit" methods, which track and visit states one by one, quickly exhaust memory and time.
To overcome this, a broad research direction has emerged around symbolic representation. Instead of enumerating individual states, these methods represent entire sets of states and transition relations as compact mathematical structures, most notably Binary Decision Diagrams (BDDs). By treating state sets as boolean functions, researchers can manipulate billions of states simultaneously.
From Individual States to Boolean Functions
The core intuition behind symbolic methods is that many states in a system share structural similarities. In an explicit search, if two states differ by only one variable, they are still stored as two distinct entries. In a symbolic representation, these states are grouped.
As Alessandro Cimatti, Marco Roveri, and Paolo Traverso demonstrated in Automatic OBDD-Based Generation of Universal Plans in Non-Deterministic Domains, we can encode a set of states as a boolean formula. A Binary Decision Diagram then serves as a canonical, compressed representation of that formula. This allows for "planning via model checking," where the search for a solution becomes an operation on logic gates rather than a traversal of a graph.
Jussi Rintanen further applied this to Conditional Planning in the Discrete Belief Space, showing that BDDs can bypass the exponential branching typical of forward-search planners by performing backward search over sets of belief states.
Scaling to Billions of States
The power of symbolic representation is most evident in verification. Marta Kwiatkowska and David Parker have shown in Advances in Probabilistic Model Checking that symbolic data structures enable the exhaustive verification of models containing billions of states.
This is achieved through several specialized variants of the decision diagram:
- Multi-Terminal BDDs (MTBDDs): Used to represent transition matrices and state vectors for probabilistic systems, as seen in the verification of randomized consensus protocols by Marta Z. Kwiatkowska and Gethin Norman in Automated Verification of a Randomized Distributed Consensus Protocol Using Cadence SMV and PRISM.
- Algebraic Decision Diagrams (ADDs): These map sets of states to numerical values, allowing planners like SYM-OSP to identify maximum utility within specific cost layers without evaluating states individually.
- Edge-Valued Multi-valued Decision Diagrams (EVMDDs): These manage state-dependent action costs by exploiting the internal logic of cost functions, a technique detailed in Delete Relaxations for Planning with State-Dependent Action Costs.
Synthesis and Reactive Systems
Beyond just checking if a system works, symbolic methods are used to build systems that are correct by construction. This is known as reactive synthesis. In the The Reactive Synthesis Competition (SYNTCOMP), researchers like Guillermo Perez and Michaël Cadilhac have tracked the dominance of BDD-based solvers.
Tools like Strix and LISA use symbolic representations to handle the high theoretical complexity of Linear Temporal Logic (LTL) synthesis. For example, LISA employs a hybrid approach, using explicit-state representations for small components and switching to symbolic BDDs once a state-space threshold is reached. This allows the tool to minimize small automata efficiently while still scaling to massive systems.
Beyond Boolean Logic: Continuous and Infinite Systems
The reach of symbolic representation extends into continuous and infinite-state domains. Majid Zamani and Alessandro Abate demonstrated in Symbolic Models for Networked Control Systems that BDDs can encode transition relations for high-dimensional physical models, making formal controller synthesis practical for systems previously limited by the "curse of dimensionality."
Similarly, in Parameterized Verification of Infinite-State Processes with Global Conditions, Parosh Aziz Abdulla and colleagues showed that symbolic grouping can verify distributed algorithms with an unbounded number of processes in seconds, proving that structural redundancy is the key to taming even infinite state spaces.