DNNF-based Belief State Estimation

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Constraint Satisfaction and Satisfiability

As embedded systems grow increasingly complex, there is a pressing need for diagnosing and monitoring capabilities that estimate the system state robustly. This paper is based on approaches that address the problem of robustness by reasoning over declarative models of the physical plant, represented as a variant of factored Hidden Markov Models, called Probabilistic Concurrent Constraint Automata. Prior work on Mode Estimation of PCCAs is based on a Best-First Trajectory Enumeration (BFTE) algorithm. Two algorithms have since made improvements to the BFTE algorithm: 1) the Best-First Belief State Update (BFBSU) algorithm has improved the accuracy of BFTE and 2) the MEXEC algorithm has introduced a polynomial-time bounded algorithm using a smooth deterministic decomposable negation normal form (sd-DNNF) representation. This paper introduces a new DNNF-based Belief State Estimation (DBSE) algorithm that merges the polynomial time bound of the MEXEC algorithm with the accuracy of the BFBSU algorithm. This paper also presents an encoding of a PCCA as a CNF with probabilistic data, suitable for compilation into an sd-DNNF-based representation. The sd-DNNF representation supports computing k belief states from k previous belief states in the DBSE algorithm.