
Research
Abstracts  2007 
Efficient Mode Estimation through Compiled ModelsPaul Elliott & Brian WilliamsThe purpose of estimation is to determine the current state of the system. An estimator infers the current state by reasoning over a model of the system dynamics, along with the commands that have been executed and the resulting sensory observations. Many deployed estimators are handcoded from the models developed by the system engineers. These estimators generally estimate the state locally, using only a limited amount of information about other components. Any systemlevel diagnostic rules are specified separately by engineers, who generate the specifications by reasoning manually about systemwide interactions. This handcoding of diagnostic rules is error prone in both steps: the specification of the systemwide interactions and the process of hardcoding the rules. The systemwide diagnosis rules are errorprone because they require having humans reason over a large set of systemwide interactions and manually inferring the system state from lowlevel sensory measurements. The handcoding of the rules is also errorprone because the software produced is very specific to each system, and thus always new and untested. ProblemA modelbased approach to diagnosis frees the system engineer from needing to do manual translation; however, before these techniques will be adopted, they must be both very efficient and transparent. Current Optimal Constraint Satisfaction Problem (OCSP) based techniques are transparent but frequently inefficient, as solving OCSPs is computationally expensive. ApproachWe propose a technique for compiling the estimation problem into a smooth deterministic decomposable negation normal form (sdDNNF) [4] to replace the potentially exponential OCSP solver with a new solver that is polynomial in the size of the sdDNNF. An sdDNNF is maximally exponential in the size of the tree width of the estimation problem, which we believe will in general be tractably small for more systems. This new representation requires a new estimation algorithm capable of estimating belief states while using a compact sdDNNF coding. We build upon [5] and [6]. This technique improves the efficiency of any algorithm that repeatedly solves Projected Optimal Constraint Satisfaction Problems (POCSPs), such as Sherlock [1], Livingstone [2] or Titan [3] and the accuracy of existing sdDNNF estimation algorithms [6]. InnovationWe propose an optimal sdDNNF solver capable of computing belief states. A belief state captures all methods of attaining the current state given a distribution over the previous state. [6] has shown that an sdDNNF can be used to create a polynomialtime algorithm for estimating state trajectories, which can be formulated as a pure OCSP. Belief states require precomputing an a prior distribution over possible states and then can be formulated as an OCSP. We present an encoding of the belief state estimation algorithm capable of being encoded as an sdDNNF, where the precomputation is included in the sdDNNF, and the precomputation required is naturally decomposed. In a single pass of the sdDNNF, we can compute the total preprocessing step. We can then run a modified OCSP algorithm on the remaining sdDNNF and get the kbest belief states. ResultsPreliminary results in [7] suggest that given a natural sdDNNF size of w, we are able to generate an estimation algorithm that takes O(w k^2) space and O(w k^3) time to generate k belief states given k previous belief states. The term w is the tree width of the constraint network. We have since been able to reduce this bound to O(w k) space and O(w k log k) time. References:[1] Johan de Kleer and Brian C. Williams. Diagnosis with Behavioral Modes. In The Proceedings of the IJCAI , pp. 13241330, 1989. [2] Douglas E. Bernard, Gregory A. Dorais, Chuck Fry, Edward B. Gamble Jr., Bob Kanefsky, James Kurien, William Millar, Nicola Muscettola, P. Pandurang Nayak, Barney Pell, Kanna Rajan, Nicolas Rouquette, Benjamin Smith and Brian C. Williams. Design of the Remote Agent Experiment for Spacecraft Autonomy. In The Proceedings of the IEEE Aerospace Conference, Snomass, CO, USA, 1998. [3] Brian C. Williams, Michel Ingham, Seung H. Chung and Paul H. Elliott. Modelbased Programming of Intelligent Embedded Systems and Robotic Space Explorers. In Proceedings of the IEEE , vol. 9, pp. 212237, Jan 2003. [4] Adnan Darwiche. Decomposable Negation Normal Form. J. ACM , 48(4):608647, 2001. [5] Oliver Martin. Accurate belief state update for probabilistic constraint automata. Master's thesis, MIT, June 2005. [6] Anthony Barrett. Model compilation for realtime planning and diagnosis with feedback. In The Proceedings of the IJCAI , pp. 11951200, Edinburgh, Scotland, UK, July 30August 5, 2005. [7] Paul Elliott and Brian Williams. DNNFbased Belief State Estimation. In Proceedings of the AAAI , Boston, MA, USA, July 2006. 

