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 is 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 Constriant Satisfaction Problem (OCSP) based techniques are transparent but frequently inefficient, as solving OCSPs is computationally expensive.

Approach

We propose a technique for reducing solving OCSPs over a subset of the variables into an A* search problem that supports pruning over the same subset. 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].

Innovation

The POCSP solver generates candidates over the projected variables and must then check that they are consistent with the theory and observations. This check is only necessary as there exists a number of internal or dependent variables that are neither known nor are they being estimated. They only contribute to a diagnosis in so far as they help determine what is consistent. Performing this consistency check would not be necessary if the theory did not contain these variables. Moreover, reorganizing the theory so it is framed as observations imply estimates, one can quickly look up all partial diagnoses in the theory. One can then generate all candidates based on the partial diagnoses and know that they are both consistent with the internal variables and the observations.

Results

A compiled and uncompiled estimation Best-First Trajectory Enumeration (BFTE) estimation algorithm were written in C++. The following experimental data was computed on a Mars Entry, Decent, and Landing (EDL) model [4] that is roughly the sisze of a spacecraft subsystem. The model has fourty-two variables, of which ten are internal and ten are estimated. The average domain size was 4.4 values per variable. The results were gathered on a 1.7GHz Intel Pentium M computer with 512MB of RAM.

Each estimation algorithm is given k initial estimates and computes the k most likely next estimates, simulating average case performance. The space requirements reflect the maximum heap space required. The time required is the average number of milliseconds elapsed for one full estimation cycle. The figures show that the compiled algorithm requires as little as one fourth the memory and runs about twice as fast.

References:

[1] Johan de Kleer and Brian C. Williams. Diagnosis with Behavioral Modes. In 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] Michel Ingham. Timed Model-based Programming: Executable Specifications for Robust Mission-Critical Sequences. Ph.D. Thesis, Department of Aeronautics and Astronautics, MIT, 2003.