Searching Powerset Automata by Combining Explicit-State and Symbolic Model Checking

Alessandro Cimatti, Marco Roveri, Piergiorgio Bertoli

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.

Hybrid representation using a hash table for uncertainty states and BDD-based pruning.

The authors propose two primary search styles:

  1. Semi-symbolic Search: Operates like a traditional explicit search (e.g., BFS or DFS), where each node is a symbolically represented uncertainty state.
  2. 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.
Search tree of uncertainty states across levels during a reachability analysis.

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

Abstract

The ability to analyze a digital system under conditions of uncertainty is important in several application domains. The problem is naturally described in terms of search in the powerset of the automaton representing the system. However, the associated exponential blow-up prevents the application of traditional model checking techniques. This work describes a new approach to searching powerset automata, which does not require the explicit powerset construction. We present an efficient representation of the search space based on the combination of symbolic and explicit-state model checking techniques. We describe several search algorithms, based on two different, complementary search paradigms, and we experimentally evaluate the approach.
BibTeX
@inproceedings{cimatti2001searching,
  author = {Alessandro Cimatti and Marco Roveri and Piergiorgio Bertoli},
  title = {{Searching Powerset Automata by Combining Explicit-State and Symbolic Model Checking}},
  booktitle = {Tacas},
  year = {2001},
  doi = {10.1007/3-540-45319-9\_22},
}
Figure