Abstract
This paper presents a novel hybrid model checking framework designed to navigate the exponential state space of powerset automata. By integrating symbolic Binary Decision Diagram (BDD) representations for individual sets of states with explicit-state hashing for frontier management, the proposed method effectively addresses the "exponential blow-up" inherent in planning under uncertainty and circuit synchronization. Experimental results demonstrate significant performance improvements over existing conformant planners and traditional symbolic methods.
Introduction
In domains such as AI planning for sensorless robotics and hardware circuit testing, systems often operate under significant uncertainty. Whether due to unknown initial conditions or nondeterministic transitions, these problems are mathematically modeled as searches within the powerset of the system's state space. For a system with $N$ states, the powerset contains $2^N$ potential "uncertainty states."
Traditional approaches struggle with this complexity. Explicit-state methods fail due to the sheer number of subsets, while purely symbolic methods often require an exponential number of variables to represent the powerset, leading to memory exhaustion. This paper introduces a hybrid approach that leverages the strengths of both paradigms to search these massive spaces without full explicit construction.
Hybrid Representation and Search Paradigms
The core innovation lies in a dual-layer representation. An "uncertainty state" (Us), representing a set of indistinguishable system states, is stored as a BDD. To manage the search frontier, an explicit-state hash table stores pointers to these canonical BDD structures. This allows for constant-time comparison of state sets via pointer equality.
The authors propose two primary search styles:
- Semi-symbolic Search: Operates like a traditional explicit search (e.g., BFS or DFS), where each node is a symbolically represented uncertainty state.
- Fully-symbolic Search: Encodes sequence variables directly into the BDD to represent the entire search frontier and the input sequences as a single symbolic structure.
A critical optimization is the PruneUsSTable operation, which identifies and removes redundant uncertainty states, preventing the search from revisiting explored regions of the powerset automaton.
Evaluation and Results
The hybrid tool was evaluated on two benchmark suites:
- Conformant Planning: Problems like the "Blind Robot" and "Faulty Device" (FIXi), where agents must reach a goal without sensors.
- Circuit Synchronization: Standard ISCAS’89 and MCNC’91 benchmarks, aiming to find input sequences that force a circuit into a known state regardless of initial flip-flop values.
The hybrid approach demonstrated remarkable efficiency. Many complex planning problems were solved in under a second, outperforming state-of-the-art planners like FSB. In circuit synchronization, the tool successfully handled large circuits; for instance, the s1196 circuit was synchronized in approximately 0.28 seconds using the fully-symbolic approach.
Key Insights
The success of this method stems from the realization that while BDDs are excellent at representing sets of states, they are less efficient at representing sets of sets. By delegating the "outer" set management to a hash table and the "inner" set representation to BDDs, the system achieves a balance of memory efficiency and search speed. Furthermore, the study found that backward search is often more effective for these specific reachability problems, and that the two search paradigms are complementary: semi-symbolic search is faster for finding any solution, while fully-symbolic search is better for proving unsolvability or finding optimal (shortest) sequences.
Conclusion and Future Work
The hybrid search of powerset automata provides a robust solution for model checking under uncertainty. Future research directions include addressing the "monolithic relation" bottleneck through partitioning techniques, extending the framework to handle Linear Temporal Logic (LTL) for safety and liveness properties, and incorporating partial observability to model systems that receive feedback during execution.
Summary updated