1	Fundamentals of Model-Based Diagnosis Johan de Kleer James Kurien
2	Goals of this Talk Introduction to Model-Based Diagnosis as defined by the AI community Basic technical intuitions Basic definitions needed to read the literature Not a toolkit Help with the hard problems of Model-Based Diagnosis
3	Basic Underlying Assumptions
4	Some Model-Based DX Tasks
5
6	Rule-based Diagnostics Predefined set of possible faults Predefined set of possible symptoms Predefined relations among them Does not generalize Is not robust
7	Achievements of Model-Based DX
8
9	A Simple Expository Example
10
11
12
13
14
15
16
17
18	Diagnosis via Constraint Suspension For each component c: Remove constraints for component c Propagate constraints If inconsistency is removed, c is a diagnosis
19
20	Constraint Suspension
21
22	Constraint Suspension
23	Constraint Suspension Inefficient Scales poorly to multiple faults Informal
24	Formal Definition of System
25	Use of Abnormal Predicate
26	Syntax of Diagnoses
27	Definition of Diagnosis
28
29
30	Conflicts
31	A Minimal Conflict
32	From Conflicts to Diagnoses
33
34
35
36	Derivation of First Minimal Conflict
37	Derivation of Second Minimal Conflict
38
39	Conflict Directed Search Let M be the set of putative minimal diagnoses, initially containing only []. If no more conflicts, the M is the minimal diagnoses For every new conflict C For every diagnosis D in M If D identifies one component in C as faulted, do nothing. Else remove D from M and add to M all D’ which have some component of C faulted. Remove duplicates from M Go to 2.
40	Analytical Redundancy Relations
41	Same Diagnoses as Analytical Redundancy
42	Model-Based Diagnosis Computes at run-time Some recent MBD approaches compile Minimal conflicts and minimal diagnoses usually avoid exponential time and space. Every system can be different.
43	Probabilities Assuming components fail independently ( is faulted probability) prior probability of a diagnosis is: Bayes Rule:
44	Sequential Diagnosis Observation: Next observation: Observations are measurements
45	Evaluating
46	"p=0.01" p=0.01 m=16 Initially
47	"Minimal diagnoses:" Minimal diagnoses: [A1] [M1] [M2] P=0.323
48	"P([M1])=0.478" P([M1])=0.478 P([A1])=0.478 P([A2,M2])=0.0048
49	"p([A1])=0.942" p([A1])=0.942 p([A2,M2])=0.0095
50	Gathering Additional Evidence Assume: all measurements are of equal cost Optimal: Choose that measurement which, on average, yields lowest total diagnosis cost.
51	Myopic Strategies Optimal probing strategies are computationally unusable Myopic strategies are often close to optimal Use one-step lookahead, and use entropy of the diagnosis distribution. The entropy of a distribution S is:
52	Expected Entropy
53
54
55
56
57	Fault Modes
58	Modeling Continuous Quantities
59	Modeling a Xerographic Copier
60
61	Faster Algorithms Minimal conflicts Minimal diagnoses Myopic probing strategy
62	Compute Diagnoses First!
63	Intuitions Underlying Fast Algorithm Discover diagnoses with highest prior first Only draw inferences which apply to those diagnoses If conflict free, compute the posterior probability Continue until sure that the next diagnosis discovered will have posterior probability less than the ones obtained so far. Stop when we have the guaranteed n highest posterior probability diagnoses
64
65	Supervisory Control
66	Three New Ideas System evolution over time Reconfiguration Embedded system
67	Valve Driver Example
68	State Machine Models
69	Encoding Device Behavior
70	Encoding Device Behavior
71	Encoding Device Behavior
72	Encoding Device Behavior
73	Encoding Device Behavior
74	Trajectory Representation
75	Trajectory Representation
76	The Problem with Trajectories
77	Trajectory Representation
78	Generating Conflicts
79	Supervisory Control
80	Choosing Actions
81	Choosing Actions
82	Choosing Actions
83	Choosing Actions
84	Choosing Actions
85	Conflict-based Repair
86	Faults in Hybrid Systems: Motor Example
87
88	Particle Filtering for Hybrid Systems
89	Challenges for Model-Based DX Noise in observable quantities Metric rather than discrete time Autonomous transitions Continuous degradation Modeling of continuous systems (NFIS) Thick models Prognostics Learning
90	Challenges for Model-Based DX Noise in observable quantities Metric rather than discrete time Autonomous transitions Continuous degradation Modeling of continuous systems (NFIS) Thick models Prognostics Learning