DNNF-based Belief State Estimation

Paul Elliott, Brian C. WilliamsAAAI 2006

Introduction

As embedded systems on satellites and rovers grow in complexity, the need for robust "mode estimators" becomes critical. These software components interpret sensor data and commands to determine the system's internal state—for instance, distinguishing between a stuck valve and a faulty sensor. Historically, diagnostic algorithms have struggled with a trade-off between accuracy and worst-case performance. While some methods are fast but inaccurate, others are accurate but risk exponential execution times, which is unacceptable for time-critical missions like a Mars landing.

Researchers from MIT have addressed this challenge with the DBSE (DNNF-based Belief State Estimation) algorithm. DBSE provides high diagnostic accuracy while guaranteeing polynomial time and memory usage, making it ideal for embedded flight systems.

Methodology: PCCA and sd-DNNF

The DBSE algorithm bridges the gap between accuracy and efficiency by utilizing two key frameworks: Probabilistic Concurrent Constraint Automata (PCCA) and Smooth Deterministic Decomposable Negation Normal Form (sd-DNNF).

Probabilistic Concurrent Constraint Automata (PCCA)

The system is modeled as a set of concurrent components. Each component transitions between various modes (e.g., "nominal," "failed," "stuck") based on probabilistic rules and control commands. This modeling approach allows for a granular representation of component behavior under different conditions.

Example of a PCCA model for a solenoid valve, showing transitions between open, closed, and stuck states with associated probabilities.

sd-DNNF Compilation

To achieve efficiency, the system's logic is compiled into an sd-DNNF format. This specific logic representation allows complex probabilistic queries—typically computationally expensive—to be solved in a single pass through the graph. DBSE conditions this graph on current sensor observations to extract the $k$ most likely belief states. Unlike previous methods, DBSE ensures it finds the best candidates, maintaining high accuracy without searching the entire global state space.

Evaluation and Key Results

The researchers evaluated DBSE using a complex model of a Mars Entry, Descent, and Landing (EDL) subsystem, featuring 42 variables. The performance was benchmarked by varying the number of tracked belief states ($k$) from 1 to 30.

Linear Scaling and Performance Guarantees

A pivotal finding was that the size of the compiled sd-DNNF representation grows linearly with the number of belief states tracked. This linear relationship is essential for real-time systems with strict memory constraints.

Empirical results showing the linear growth of nodes and edges in the sd-DNNF representation as the number of tracked belief states (k) increases.

The algorithm's space complexity is $O(ke)$ and time complexity is $O(k^2e)$, where $e$ is the number of edges in the graph. This provides the "hard" performance bounds required for mission-critical aerospace applications. Furthermore, the use of sd-DNNF allows for exact model counting, making the estimator highly resilient to noisy or ambiguous sensor data.

Conclusion

DBSE represents a significant advancement in autonomous spacecraft diagnostics. By combining the modeling power of PCCA with the computational efficiency of sd-DNNF, it provides a reliable, fast, and accurate tool for state estimation. Future work aims to extend DBSE to include N-step time window estimation and to optimize the offline compilation process to further reduce the size of the resulting logic graphs.

Summary updated

BibTeX
@inproceedings{elliott2006dnnf,
  author = {Paul Elliott and Brian C. Williams},
  title = {{DNNF-based Belief State Estimation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure