DNNF-Based Belief State Estimation

Abstract

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 rea-soning over declarative models of the physical plant, repre-sented 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 Trajec-tory Enumeration (BFTE) algorithm. Two algorithms have since made improvements to the BFTE algorithm: 1) the Best-First Belief State Update (BFBSU) algorithm has im-proved 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 Esti-mation (DBSE) algorithm that merges the polynomial time bound of the MEXEC algorithm with the accuracy of the BF-BSU algorithm. This paper also presents an encoding of a PCCA as a CNF with probabilistic data, suitable for compi-lation into an sd-DNNF-based representation. The sd-DNNF representation supports computing k belief states from k pre-vious belief states in the DBSE algorithm.