Research Abstracts - 2007

The 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 hand-coded 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 system-level diagnostic rules are specified separately by engineers, who generate the specifications by reasoning manually about system-wide interactions.

This hand-coding of diagnostic rules is error prone in both steps: the specification of the system-wide interactions and the process of hard-coding the rules. The system-wide diagnosis rules are error-prone because they require having humans reason over a large set of system-wide interactions and manually inferring the system state from low-level sensory measurements. The hand-coding of the rules is also error-prone because the software produced is very specific to each system, and thus always new and untested.

Problem

A model-based 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.

Approach

We propose a technique for compiling the estimation problem into a smooth deterministic decomposable negation normal form (sd-DNNF) [4] to replace the potentially exponential OCSP solver with a new solver that is polynomial in the size of the sd-DNNF. An sd-DNNF 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 sd-DNNF 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 sd-DNNF estimation algorithms [6].

Innovation

We propose an optimal sd-DNNF 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 sd-DNNF can be used to create a polynomial-time 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 sd-DNNF, where the precomputation is included in the sd-DNNF, and the precomputation required is naturally decomposed. In a single pass of the sd-DNNF, we can compute the total preprocessing step. We can then run a modified OCSP algorithm on the remaining sd-DNNF and get the k-best belief states.

Results

Preliminary results in [7] suggest that given a natural sd-DNNF 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. 1324-1330, 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. Model-based Programming of Intelligent Embedded Systems and Robotic Space Explorers. In Proceedings of the IEEE , vol. 9, pp. 212-237, Jan 2003.

[4] Adnan Darwiche. Decomposable Negation Normal Form. J. ACM , 48(4):608-647, 2001.

[5] Oliver Martin. Accurate belief state update for probabilistic constraint automata. Master's thesis, MIT, June 2005.

[6] Anthony Barrett. Model compilation for real-time planning and diagnosis with feedback. In The Proceedings of the IJCAI , pp. 1195-1200, Edinburgh, Scotland, UK, July 30-August 5, 2005.

[7] Paul Elliott and Brian Williams. DNNF-based Belief State Estimation. In Proceedings of the AAAI , Boston, MA, USA, July 2006.