麻省理工学院：自制决策制造原则：L15a_modelbased_diagnosis_up

10/03/03 copyright Brian Williams, 2003 1 Courtesy NASA/JPL-Caltech. http://www.jpl.nas.gov. Model-based Diagnosis Brian C. Williams 16.410-13 November 3 rd & 5 th 2003 Brian C. Williams, copyright 2000 10/03/03 copyright Brian Williams, 2003 2 Assignment ? Reading ? Model-based Diagnosis – Lecture notes ? Propositional Logic AIMA Chapter 6 ? Problem Set ? Model-based Diagnosis implementation ? Propositional Logic ? 16.413: Hello World implementation ? Due Monday, November 17 th 10/03/03 copyright Brian Williams, 2003 3 sense P(s) WORLD observations actions AGENT Diagnostic Agent: ? Monitors & Diagnoses ? Repairs & Avoids ? Probes and Tests Plant act Symptom-directed 10/03/03 copyright Brian Williams, 2003 4 Outline ? Model-based diagnosis ? Accounting for failures ? Explaining failures ? Handling unknown failures 10/03/03 copyright Brian Williams, 2003 5 Hidden Failures Require Reasoning from a Model: STS-93 Symptoms: ? Engine temp sensor high ? LOX level low ? GN&C detects low thrust ? H2 level possibly low Problem: Liquid hydrogen leak Effect: ? LH2 used to cool engine ? Engine runs hot ? Consumes more LOX Image taken from NASA’s web site: http://www.nasa.gov. 10/03/03 copyright Brian Williams, 2003 6 Model-based Diagnosis Given a system with symptomatic behavior and a model of the system, find diagnoses that account for symptoms. 12 Symptom6 6 O1 M2 M3 A1 A2 A B C D E F G X Y Z 3 2 2 3 3 10 12 M1 6 12 10/03/03 copyright Brian Williams, 2003 7 Model-based Diagnosis Given a system with symptomatic behavior and a model of the system, find diagnoses that account for symptoms. 12 Symptom6 6 M1 M2 M3 A1 A2 A B C D E F G X Y Z 3 2 2 3 3 10 12 6 12 10/03/03 copyright Brian Williams, 2003 8 Diagnosis as Hypothesis Testing 1. Generate candidates, given symptoms. 2. Test if candidates account for all symptoms. ? Set of diagnoses should be complete. ? Set of diagnoses should consider all available information. 10/03/03 copyright Brian Williams, 2003 9 Outline ? Model-based diagnosis ? Accounting for failures ? Explaining failures ? Handling unknown failures 10/03/03 copyright Brian Williams, 2003 10 How Should Diagnoses Account for Symptoms? Abductive Diagnosis: Given symptoms, find diagnoses that predict observations. 6 6 12 Symptom M1 M2 M3 A1 A2 A B C D E 3 2 2 3 3 F G X Y Z 10 12 Assume Exhaustive Fault Models: 10/03/03 copyright Brian Williams, 2003 11 How Should Diagnoses Account for Symptoms? Abductive Diagnosis: Given symptoms, find diagnoses that predict observations. 6 6 12 Symptom M1 M2 M3 A1 A2 A B C D E 3 2 2 3 3 F G X Y Z 10 12 Assume Exhaustive Fault Models: ? O1 Drops low bit on A A = 3 0011 A=2 0010 4 10 2 6 12 10/03/03 copyright Brian Williams, 2003 12 ? Model ? Structure ? Model of normal behavior for each component ? Model for every component failure mode ? Observations ? Inputs and Response 3 2 2 3 3 M1 M2 M3 A1 A2 A B C D E F G X Y Z Multiplier(i): ? G(i): Out(i) = In1(i)*In2(i) ? Stuck_in1(i): Out(i) = . . . 10 12 Abductive, Model-based Diagnosis 10/03/03 copyright Brian Williams, 2003 13 ? X mode variables, one for each component c ? D c modes of component c = domain of x c ? X ? Y model variables ? M(X, Y) model constraints ? O observable variables O ? Y ? Partitioned into Inputs I and Response R 3 2 2 3 3 M1 M2 M3 A1 A2 A B C D E F G X Y Z Multiplier(i): ? G(i): Out(i) = In1(i)*In2(i) ? Stuck_in1(i): Out(i) = . . . 10 12 Abductive, Model-based Diagnosis 10/03/03 copyright Brian Williams, 2003 14 ? In, Resp: Assignment to I and R, respectively ? Candidate C i : Assignment of modes to X ? Diagnosis D i : A candidate such that D i ? In ? C(X,Y) predicts (entails) Resp Diagnosis = {A1=G, A2=S, O1=G, M2=G, M3=G} M1 M2 M3 A1 A2 A B C D E F G X Y Z Multiplier(i): ? G(i): Out(i) = In1(i)*In2(i) ? Stuck_in1(i): Out(i) = . . . Abductive, Model-based Diagnosis 3 2 2 3 3 10 12 Candidate = {A1=G, A1=G, M1=G, A2=G, M3=G} 10/03/03 copyright Brian Williams, 2003 15 Abductive Diagnosis by Generate and Test Given: Correct and exhaustive fault models for each component. Generate: Consider each mode assignment as a candidate. Test: 1. Simulate candidate, given inputs. 2. Compare to observations ? Disagree: Discard ? Agree: Keep ? No prediction: Discard Problem: ? Fault models are often incomplete ? May incorrectly exonerate faulty components 10/03/03 copyright Brian Williams, 2003 16 Outline ? Model-based diagnosis ? Accounting for failures ? Explaining failures ? Handling unknown failures 10/03/03 copyright Brian Williams, 2003 17 ? Mars Observer ? Mars Climate Orbiter ? Mars Polar Lander ? Deep Space 2 Courtesy NASA/JPL-Caltech. http://www.jpl.nasa.gov. Issue: Failures are Often Novel 10/03/03 copyright Brian Williams, 2003 18 Helium tank Fuel tankOxidizer tank Main Engines Flow 1 = zero Pressure 1 = nominal Pressure 2 = nominal Acceleration = zero 10/03/03 copyright Brian Williams, 2003 19 How Should Diagnoses Account for Novel Symptoms? Consistency-based Diagnosis: Given symptoms, find diagnoses that are consistent with symptoms. Suspending Constraints: Make no presumptions about faulty component behavior. 1 1 1 Symptom Or1 Or2 Or3 And1 And2 A B C D E 1 1 1 1 0 F G X Y Z 0 1 10/03/03 copyright Brian Williams, 2003 20 Consistency-based Diagnosis: Given symptoms, find diagnoses that are consistent with symptoms. Suspending Constraints: Make no presumptions about faulty component behavior. 1 1 1 Symptom Or1 Or2 Or3 And1 And2 A B C D E 1 1 1 1 0 F G X Y Z 0 1 How Should Diagnoses Account for Novel Symptoms? 10/03/03 copyright Brian Williams, 2003 21 Consistency-based Diagnosis: Given symptoms, find diagnoses that are consistent with symptoms. Suspending Constraints: Make no presumptions about faulty component behavior. 1 1 Or1 Or2 Or3 And1 And2 A B C D E 1 1 1 1 0 F G X Y Z 0 1 How Should Diagnoses Account for Novel Symptoms? 10/03/03 copyright Brian Williams, 2003 22 Consistency-based Diagnosis And(i): ? G(i): Out(i) = In1(i) AND In2(i) ? U(i): ? Obs: Assignment to O ? Candidate C i : Assignment of modes to X ? Diagnosis D i : A candidate such that D i ? Obs ? C(X,Y) is satisfiable. 1 1 1 1 0 Or1 Or3 And1 A B C D E F G X Y Z 0 1 Diagnosis = {A1=G, A2=U O1=G, O2=U, O3=G} ALL components have “unknown Mode” U, Whose assignment is never mentioned in C 10/03/03 copyright Brian Williams, 2003 23 Testing Consistency
:Propositional Logic ?DPLL ? Unit propagation (incomplete) ?Finite Domain Constraints ? Backtrack w forward checking, … ? Waltz constraint propagation (incomplete) ? Algebraic Constraints ? Sussman/Steele Constraint Propagation: Propagate newly assigned values through equations mentioning variables. ? To propagate, use assigned values of constraint to deduce unknown value(s) of constraint. 10/03/03 copyright Brian Williams, 2003 24 X ?{1,0} X=1 ? X=0 ?X=1??X=0 Encoding Models In Propositional Logic ?(i=G) ??(In1(i)=1) ? Out(i)=1 ?(i=G) ??(In2(i)=1) ? Out(i)=1 ?(i=G) ??(In1(i)=0) ??(In2(i)=0) ? Out(i)=0 And(i): ? G(i): Out(i) = In1(i) AND In2(i) ? U(i): Or(i): ? G(i): Out(i) = In1(i) OR In2(i) ? U(i): ?(i=G) ??(In1(i)=0) ? Out(i)=0 ?(i=G) ??(In2(i)=0) ? Out(i)=0 ?(i=G) ??(In1(i)=1) ??(In2(i)=1) ? Out(i)=1 10/03/03 copyright Brian Williams, 2003 25 Summary: Model-based Diagnosis ? A failure is a discrepancy between the model and observations of an artifact. ? Diagnosis is symptom directed ? Symptoms identify conflicting components as initial candidates. ? Test novel failures by suspending constraints and testing consistency. ? Newly discovered conflicts further prune candidates.