Efficient Mode Estimation through Knowledge CompilationP. Elliott, B. Williams & O. MartinThe 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 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. ApproachWe 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]. InnovationThe 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. ResultsA compiled and uncompiled estimation BestFirst 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 fourtytwo 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. 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] Michel Ingham. Timed Modelbased Programming: Executable Specifications for Robust MissionCritical Sequences. Ph.D. Thesis, Department of Aeronautics and Astronautics, MIT, 2003. 

