courtesy of JPL Conflict-directed Diagnosis and Probabilistic Mode Estimation Brian C. Williams 16.412J/6.834J March 10 th , 2004 Brian C. Williams, copyright 2000 Outline ? Conflicts and Kernel Diagnoses ? Generating Kernels from Conflicts ? Finding Consistent Modes ? Estimating Likely Modes ? Conflict-directed A* 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 ? As more constraints are relaxed, candidates are more easily satisfied. ? Typically an exponential number of candidates. Diagnosis identifies All sets of consistent modes Adder(i): ? G(i): Out(i) = In1(i)+In2(i) ? U(i): ? Diagnosis D: Candidate consistent with model Phi and observables OBS. ? As more constraints are relaxed, candidates are more easily satisfied. ?Typically an exponential number of candidates. 3 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 Diagnosis = {A1=G, A2=U, M1=G, M2=U, M3=G} ? ? “Smallest” sets of modes that remove all symptoms 3 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ? Kernel Diagnosis = {A2=U, M2=U} Representing Diagnoses Compactly: Kernel Diagnoses Every candidate that is a subset of a kernel diagnosis is a diagnosis. Diagnosis by Divide and Conquer Given model Phi and observations OBS ? 1. Find all symptoms ? 2. Diagnose each symptom separately (each generates a conflict →candidates) ? 3. Merge diagnoses (set covering →kernel diagnoses) General Diagnostic Engine [de Kleer & Williams, 87] Or1 Or2 And1 A B C D E 1 1 1 1 F G X Y Z Symptom: F is observed 0, but should be 1 if O1, O2 and A1 are okay. Conflict: {A1=G, O1=G, O2=G} is inconsistent 0 1 1 1 →At least A1=U, O1=U, or O2=U Conflicts Explain How To Remove Symptoms 0 Or3 And3 Conflicts Explain How to Remove Symptoms M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z 10 Symptom: F is observed 10, but should be 12 if A1, M1 & M2 are okay. 6 6 12 M3 A2 Conflicts Explain How to Remove Symptoms M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z Symptom: F is observed 10, but should be 12 if A1, M1 & M2 are okay. Conflict: A1=G & M1=G & M2=G is inconsistent 10 12 6 6 M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z Symptom: F is observed 10, but should be 12 Conflict: A1=G & M1=G & M2=G is inconsistent A1=U or M1=U or M2=U removes conflict. 10 12 6 6 Conflicts Explain How to Remove Symptoms Find Another Symptom 3 2 3 M1 M3 A1 A2 A B C D E F G X Y Z 10 12 4 6 10 Symptom: G is observed 12, but should be 10 ... 3 2 3 M1 M3 A1 A2 A B C D E F G X Y Z 10 12 4 6 10 Symptom: G is observed 12, but should be 10 Conflict: A1=G & M2=G & M1=G & M3=G is inconsistent Conflict not just upstream from symptom … and its Conflict 3 2 3 M1 M3 A1 A2 A B C D E F G X Y Z 10 12 4 6 10 Symptom: G is observed 12, but should be 10 Conflict: A1=G & M2=G & M1=G & M3=G is inconsistent A1=U or A2=U or M1=U or M3=U removes conflict Conflict not just upstream from symptom … and its Conflict Recap: Conflicts M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z 10 Conflict ? A set of component modes M that are inconsistent with the model and observations. ? Every superset of a conflict is a conflict ? Only need conflicts that are minimal under subset ? Logically, not M is an implicate of model & Obs 6 6 12 M3 A2 ? ? 3 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ? Kernel Diagnosis = {A2=U & M2=U} Recap: Kernel Diagnoses Partial Diagnosis: A set of component modes M all of whose extensions are diagnoses. ? M removes all symptoms ? M entails Model & Obs (implicant) Kernel Diagnosis: A minimal partial diagnosis K ? M is a prime implicant of model & obs Outline ? Conflicts and Kernel Diagnoses ? Generating Kernels from Conflicts ? Finding Consistent Modes ? Estimating Likely Modes ? Conflict-directed A* Diagnoses Found by Mapping Conflicts to Kernels Conflict: A set of component modes M that are inconsistent with the model and observations. ? not M is an implicate of Model & Obs Kernel Diagnosis: A minimal set of component modes K that eliminate all symptoms. ?M is a prime implicant of Model & Obs Conflicts map to Kernels by minimal set covering M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z 10 6 6 12 M3 A2 ? ? 3 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ? Kernel Diagnoses = Generate Kernels From Conflicts A1=U or M1=U or M2=U removes conflict 1. A1=U or A2=U or M1=U or M3=U removes conflict 2 “Smallest” sets of modes that remove all conflicts {A1=G, M1=U, M2=U} conflict 1. {A1=U, A2=U, M1=U, M3=U} conflict 2 Kernel Diagnoses = {A1=U} “Smallest” sets of modes that remove all conflicts A1=U or M1=U or M2=U removes conflict 1. A1=U or A2=U or M1=U or M3=U removes conflict 2 Generate Kernels From Conflicts Kernel Diagnoses = {M1=U} {A1=U} “Smallest” sets of modes that remove all conflicts A1=U or M1=U or M2=U removes conflict 1. A1=U or A2=U or M1=U or M3=U removes conflict 2 Generate Kernels From Conflicts Kernel Diagnoses = {A2=U, M2=U} {M1=U} {A1=U} “Smallest” sets of modes that remove all conflicts A1=U or M1=U or M2=U removes conflict 1. A1=U or A2=U or M1=U or M3=U removes conflict 2 Generate Kernels From Conflicts Kernel Diagnoses = {M2=U, M3=U} {A2=U, M2=U} {M1=U} {A1=U} “Smallest” sets of modes that remove all conflicts A1=U or M1=U or M2=U removes conflict 1. A1=U or A2=U or M1=U or M3=U removes conflict 2 Generate Kernels From Conflicts Outline ? Conflicts and Kernel Diagnoses ? Generating Kernels from Conflicts ? Finding Consistent Modes ? Estimating Likely Modes ? Conflict-directed A* Diagnosis With Only the Unknown Inverter(i): ? G(i): Out(i) = not(In(i)) ? U(i): X Y AB C 0 000 Nominal and Unknown Modes ? Isolates surprises ? Doesn’t explain Diagnosis With Only the Known Inverter(i): ? G(i): Out(i) = not(In(i)) ? S1(i): Out(i) = 1 ? S0(i): Out(i) = 0 X Y AB C 0 000 Exhaustive Fault Modes ? No surprises ? Explains Solution: Diagnosis as Estimating Behavior Modes Inverter(i): ? G(i): Out(i) = not(In(i)) ? S1(i): Out(i) = 1 ? S0(i): Out(i) = 0 ? U(i): X Y AB C 0 000 Nominal, Fault and Unknown Modes ? Isolates surprises ?Explains Example Diagnoses X Y AB C 0 0 1 Diagnosis: [S1(A),G(B),U(C)] 00 Sherlock [de Kleer & Williams, 89] Example Diagnoses X Y AB C 0 0 1 Diagnosis: [S1(A),G(B),U(C)] Kernel Diagnosis: [U(C)] X Y AB C 0 0 ?? 00 00 Sherlock [de Kleer & Williams, 89] 1. Find Symptoms & Conflicts Conflict: not G(A), G(B) and G(C) X Y AB C 0 0 1 0 GG G 0 0 1 0 More Symptoms & Conflicts Not S1(A), G(B), and G(C) X Y AB C 0 0 1 0 S1 G G 0 0 1 0 not S0(B) and G(C) X Y AB C 0 0 0 S0 G 0 0 1 More Symptoms & Conflicts 0 not S1(C) X Y AB C 0 0 1 S1 0 0 More Symptoms & Conflicts All Conflicts ? < S1(C) > ? < S0(B), G(C) > ? < S1(A), G(B), G(C) > ? < G(A), G(B), G(C) > 2. Constituent Diagnoses from Conflicts ? < S1(C) > => G(C),S0(C) or U(C) ? < S0(B), G(C) > => G(B),S1(B),U(B),S1(C),S0(C) or U(C) ? < S1(A), G(B), G(C) > => G(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C) or U(C) ? < G(A), G(B), G(C) > => S1(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C) or U(C) 3. Generate Kernel Diagnoses ? [U(C)] ? [G(C),S0(C),U(C)] ? [G(B),S1(B),U(B),S1(C),S0(C),U(C)] ? [G(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [S1(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [U(C)] ? [S0(C)] ? [G(C),S0(C),U(C)] ? [G(B),S1(B),U(B),S1(C),S0(C),U(C)] ? [G(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [S1(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] 3. Generating Kernel Diagnoses ? [U(C)] ? [S0(C)] ? [U(B),G(C)] ? [G(C),S0(C),U(C)] ? [G(B),S1(B),U(B),S1(C),S0(C),U(C)] ? [G(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [S1(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] 3. Generating Kernel Diagnoses ? [U(C)] ? [S0(C)] ? [U(B),G(C)] ? [G(C),S0(C),U(C)] ? [G(B),S1(B),U(B),S1(C),S0(C),U(C)] ? [G(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [S1(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [S1(B),G(C)] 3. Generating Kernel Diagnoses ? [U(C)] ? [S0(C)] ? [U(B),G(C] ? [S1(B),G(C)] ? [U(A),G(B),G(C)] ? [G(C),S0(C),U(C)] ? [G(B),S1(B),U(B),S1(C),S0(C),U(C)] ? [G(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [S1(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] 3. Generating Kernel Diagnoses ? [U(C)] ? [S0(C)] ? [U(B),G(C] ? [S1(B),G(C)] ? [U(A),G(B),G(C)] ? [S0(A),G(B),G(C)] ? [G(C),S0(C),U(C)] ? [G(B),S1(B),U(B),S1(C),S0(C),U(C)] ? [G(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] ? [S1(A),S0(A),U(A),S1(B),S0(B),U(B),S1(C),S0(C),U(C)] 3. Generate Kernel Diagnoses Diagnoses: (42 of 64 candidates) Fully Explained Failures ? [G(A),G(B),S0(C)] ? [G(A),S1(B),S0(C)] ? [S0(A),G(B),G(C)] . . . Fault Isolated, But Unexplained ? [G(A),G(B),U(C)] ? [G(A),U(B),G(C)] ? [U(A),G(B),G(C)] Partial Explained ? [G(A),U(B),S0(C)] ? [U(A),S1(B),G(C)] ? [S0(A),U(B),G(C)] . . . X Y AB C 0 0 00 Outline ? Conflicts and Kernel Diagnoses ? Generating Kernels from Conflicts ? Finding Consistent Modes ? Estimating Likely Modes ? Conflict-directed A* Due to the unknown mode, there tends to be an exponential number of diagnoses. U Candidates with UNKNOWN failure modes Candidates with KNOWN failure modes Good Good G F1 Fn G U But these diagnoses represent a small fraction of the probability density space. Most of the density space may be represented by enumerating the few most likely diagnoses Candidate Initial (prior) Probabilities p(c) = p(m) m∈c ∏ ABC p(G) .99 .99 .99 p(S1) .008 .008 .001 p(S0) .001 .001 .008 p(U) .001 .001 .001 p([G(A),G(B),G(C)]) = .97 p([S1(A),G(B),G(C)]) = .008 p([S1(A),G(B),S0(C)]) = .00006 p([S1(A),S1(B),S0(C)]) = .0000005 Assume Failure Independence 0 0.2 0.4 0.6 0.8 1 1.2 OK S 0 ( A ) S 1 (B ) S 0 (C ) U (A ) U (B ) U( C ) S 1( A ), S 0 ( C ) X Y AB C 0 0 0 Posterior Probability, after Observation x = v P(x=v|c) estimated using Model: ? If previous obs, c and Phi entails x = v Then p(x = v | c) = 1 ? If previous obs, c and Phi entails x <> v Then p(x = v | c) = 0 ? If Phi consistent with all values for x Then p(x = v | c) is based on priors ? E.g., uniform prior = 1/m for m possible values of x p(c | x = v)= p(x = v | c)p(c) p(x = v) Bayes’ Rule Normalization Term Observe out = 1: ? C = [G(A),G(B),G(C)] ? P(C) = .97 ? P(out = 1 | C) = ? ? = 1 ? P(C | out = 0 ) = ? ? = .97/p(x=v) p(c | x = v)= p(x = v | c)p(c) p(x = v) X Y AB C 1 0 Observe out = 0: ? C = [G(A),G(B),G(C)] ? P(C) = .97 ? P(out = 0 | C) = ? ? = 0 ? P(C | out = 0 ) = ? ? = 0 x .97/p(x=v) = 0 p(c | x = v)= p(x = v | c)p(c) p(x = v) X Y AB C 0 0 X Y AB C 0 A B C p(S1) .008 .008 .001 p(S0) .001 .001 .008 p(U) .001 .001 .001 0 How do the single faults change? ? which are eliminated? ? which predict observations? ? Which are agnostic? Priors for Single Fault Diagnoses: 0 0.2 0.4 0.6 0.8 1 1.2 OK S 0 ( A ) S 1 (B ) S 0 (C ) U (A ) U (B ) U( C ) S 1( A ), S 0 ( C ) X Y AB C 0 0 0 0 0.1 0.2 0.3 0.4 0.5 OK S0 ( A ) S1 ( B ) S0 ( C ) U( A ) U( B ) U( C ) S1 (A ) S0 ( C) X Y AB C 0 0 0 0 Top 6 of 64 = 98.6% of P Summary: Candidate Probabilities p(c) = p(m) m∈c ∏ Assume Failure Independence P(x=v|c) estimated using Model: ? If previous obs, c and Phi entails x = v Then p(x = v | c) = 1 ? If previous obs, c and Phi entails x <> v Then p(x = v | c) = 0 ? If Phi consistent with all values for x Then p(x = v | c) is based on priors ? E.g., uniform prior = 1/m for m possible values of x p(c | x = v)= p(x = v | c)p(c) p(x = v) Bayes’ Rule Normalization Term Outline ? Conflicts and Kernel Diagnoses ? Generating Kernels from Conflicts ? Finding Consistent Modes ? Estimating Likely Modes ? Conflict-directed A* Due to the unknown mode, there tends to be an exponential number of diagnoses. U Candidates with UNKNOWN failure modes Candidates with KNOWN failure modes Good Good G F1 Fn G U But these diagnoses represent a small fraction of the probability density space. Most of the density space may be represented by enumerating the few most likely diagnoses When you have eliminated the impossible, whatever remains, however improbable, must be the truth. - Sherlock Holmes. The Sign of the Four. Exploring the Improbable Compare Most Likely Hypothesis to Observations Helium tank Fuel tankOxidizer tank Main Engines Flow 1 = zero Pressure 1 = nominal Pressure 2 = nominal Acceleration = zero It is most likely that all components are okay. Increasing Cost Feasible Infeasible A* Increasing Cost Feasible Infeasible Conflict-directed A* Increasing Cost Feasible Infeasible Conflict 1 Conflict-directed A* Increasing Cost Feasible Infeasible Conflict 1 Conflict-directed A* Increasing Cost Feasible Infeasible Conflict 3 Conflict 2 Conflict 1 Conflict-directed A* A2=U M1=U M3=UA1=U A1=U, A2=U, M1=U, M3=U A1=U M1=U M2=U A1=U M1=U M1=U ∧ A2=U M2=U ∧ M3=U Conflict-Directed A*: Generating The Best Kernel A1=U, M1=U , M2=U Conflicts ? Minimal set covering is an instance of breadth first search. ? To find the best kernel, expand tree in best first order. Insight: ? Kernels found by minimal set covering A1=U, A2=U, M1=U, M3=U A1=U M1=U M2=U M1=U Conflict-Directed A*: Generating The Best Kernel A1=U, M1=U , M2=U Conflicts ? Minimal set covering is an instance of breadth first search. ? To find the best kernel, expand tree in best first order. Insight: ? Kernels found by minimal set covering 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. Research in Model-based Diagnosis Methods exist for: ? Focusing on likely diagnoses ? Active probing ? Diagnosing dynamic systems and monitoring behavior ? Repairing and compensating for failures ? Diagnosing hybrid discrete/continuous systems ? Performing distributed diagnosis Brian C. Williams, copyright 2000 Appendix 1 Extracting Conflicts Through Unit Propagation r q p C 2 : ? p ∨ ? t true false true t false procedure propagate(C)// C is a clause if all literals in C are false except l, and l is unassigned then assign true to l and record C as a support for l and for each clause C’ mentioning “not l”, propagate(C’) end propagate C 1 : ?r ∨ q ∨ p Find Symptom Using Unit Propagation Find Symptom Using Unit Propagation ?(O1=G) ∨?(A=1) ∨ X=1 ?(A1=G) ∨?(X=1) ∨?(Y=1) ∨ F=1 ?(O2=G) ∨?(B=1) ∨ Y=1 ?(F=1) ∨?(F=0) O1=G B=1O2=G A=1 X=1 Y=1 A1=G F=1 F=1 Find Symptom Using Unit Propagation ?(O1=G) ∨?(A=1) ∨ X=1 ?(A1=G) ∨?(X=1) ∨?(Y=1) ∨ F=1 ?(O2=G) ∨?(B=1) ∨ Y=1 ?(F=1) ∨?(F=0) B=1 O1=G B=1 true O2=G A=1 A=1 true X=1 Y=1 A1=G F=1 F=1 F=1 true Find Symptom Using Unit Propagation ?(O1=G) ∨?(A=1) ∨ X=1 ?(A1=G) ∨?(X=1) ∨?(Y=1) ∨ F=1 ?(O2=G) ∨?(B=1) ∨ Y=1 ?(F=1) ∨?(F=0) O1=G B=1 O1=G true B=1 true O2=G O2=G true A=1 A=1 true X=1 Y=1 A1=G A1=G true F=1 F=1 F=1 true Find Symptom Using Unit Propagation ?(O1=G) ∨?(A=1) ∨ X=1 ?(A1=G) ∨?(X=1) ∨?(Y=1) ∨ F=1 ?(O2=G) ∨?(B=1) ∨ Y=1 ?(F=1) ∨?(F=0) O1=G B=1 O1=G true B=1 true O2=G O2=G true A=1 A=1 true X=1 true Y=1 true A1=G A1=G true F=1 F=1 F=1 true Find Symptom Using Unit Propagation ?(O1=G) ∨?(A=1) ∨ X=1 ?(A1=G) ∨?(X=1) ∨?(Y=1) ∨ F=1 ?(O2=G) ∨?(B=1) ∨ Y=1 ?(F=1) ∨?(F=0) O1=G B=1 O1=G true B=1 true O2=G O2=G true A=1 A=1 true X=1 true Y=1 true A1=G A1=G true F=1 true F=1 F=1 true procedure Conflict(C)// C is an inconsistent clause for each literal I in C union Support-Conflict(l, support(l) ) end Conflict procedure Support-Conflict(l,S) If unit-clause?(C) If mode-assignment?(literal (C)) Then { literal(C) } Else { } Else for each literal I1 in C, other than l Union Support-Conflict(l1, support(l1)) end Support-Conflict Extract Conflict by Tracing Support Candidate Test with Conflict Extraction procedure Test_Candidate(c,M,obs) 1. Assert candidate assignment c 2. Propagate obs through model M using unit propagation. 3. If inconsistent clause return Conflict(c) 4. Else search for satisfying solution using DPLL ? If inconsistent return c as a conflict. ?Else return “consistent” Brian C. Williams, copyright 2000 Appendix 2 Single-Fault Diagnosis using Conflicts Single Fault Diagnosis w Conflicts: Generate Candidates From Symptom Single_Fault_w_Conflicts(M, X, Obs) \\ Model M, Mode variables X, Observation Obs 1. Assume all components okay, All_Good = { x=G | x ∈ X} 2. Conflict ← Test_Candidate(All_Good, M, Obs) 3. If Conflict = “consistent” return All_Good 4. Generate single fault candidates Cands ← {{x=U}∪Z=G | x=G ∈ Conflict, Z=X-{x}} 5. Test_Candidates(Cands, M, Obs) Symptom: F is observed 0, but should be 1 Conflict: {O1=G, O3=G, A1=G, A2=G} is inconsistent Candidates: {O1=U, O3=U, A1=U, A2=G} Generate Candidates From Symptom Symptom 1 0 Or1 Or2 Or3 And1 And2 A B C D E F G X Y Z 1 1 1 1 0 0 1 1 0 Single Fault Diagnosis w Conflicts: Test Candidates Collecting Conflicts Single_Fault_Test_Candidates(C,M, Obs) \\ Candidates C, Model M, Observation Obs Solutions ← {}, Conflicts ← {} For each c in C If c is a superset of some conflict in Conflicts Then inconsistent candidate, ignore. Else Conflict = Test_Candidate(c, M, Obs) If Conflict = “consistent” Then add c to Solutions Else add Conflict to Conflicts return Solutions Test Candidates Collecting Conflicts Or1 1 1 1 1 0 Or2 Or3 And1 And2 A B C D E F G X Y Z 0 1 1 1 ? First candidate {O1=U, …} Candidates: {{O1=U…}, {O3=U…}, {A1=U…}, {A3=U…}} Solutions: {} 1 1 1 1 0 Or2 Or3 And1 And2 A B C D E F G X Y Z 0 1 ? First candidate {O1=U, …} ? Suspend O1’s constraints Test Candidates Collecting Conflicts Candidates: {{O1=U…}, {O3=U…}, {A1=U…}, {A3=U…}} Solutions: {} 1 1 1 1 0 Or2 Or3 And1 And2 A B C D E F G X Y Z 0 1 1 1 1 ? First candidate {O1=U, …} ? Suspend O1’s constraints ? Test consistency Test Candidates Collecting Conflicts Candidates: {{O1=U…}, {O3=U…}, {A1=U…}, {A3=U…}} Solutions: {} 1 1 1 1 0 Or2 Or3 And1 And2 A B C D E F G X Y Z 0 1 1 1 1 ? First candidate {O1=U, …} ? Suspend O1’s constraints ? Test consistency → Consistent: Add to solutions Test Candidates Collecting Conflicts Candidates: {{O3=U…}, {A1=U…}, {A3=U…}} Solutions: {{O1=U…}} 1 1 1 1 0 Or1 Or2 Or3 And2 A B C D E F G X Y Z 0 1 Test Candidates Collecting Conflicts ? Second candidate {O3=U, …} ? Suspend O3’s constraints ? Test consistency And1 Candidates: {{O3=U…}, {A1=U…}, {A2=U…}} Solutions: {{O1=U…}} 1 1 1 1 0 Or1 And1 And2 A B C D E F G X Y Z 0 1 1 1 Test Candidates Collecting Conflicts ? Second candidate {O3=U, …} ? Suspend O3’s constraints ? Test consistency→ Inconsistent 11 Testing Consistency ≠ Forward Prediction Candidates: {{O3=U…}, {A1=U…}, {A2=U…}} Solutions: {{O1=U…}} Or2 1 1 1 1 0 Or1 And1 And2 A B C D E F G X Y Z 0 1 1 1 Test Candidates Collecting Conflicts ? Second candidate {O3=U, …} ? Suspend O3’s constraints ?Test → Inconsistent 11 ? Extract Conflict: {O1=G, O2=G, A1=G} ? Use to prune candidates Candidates: {{O3=U…}, {A1=U…}, {A2=U…}} Solutions: {{O1=U…}} Conflicts: {{O1=G, O2=G, A1=G}} Or2 1 1 1 1 0 Or1 Or3 And1 And2 A B C D E F G X Y Z 0 1 1 1 Test Candidates Collecting Conflicts ? Third candidate {A1=U, …} ? Subsumed by conflict? → ? Suspend A1’s constraints ?Test → 1 1 Or2 Consistent Candidates: {{A1=U…}, {A2=U…}} Solutions: {{O1=U…}} Conflicts: {{O1=G, O2=G, A1=G}} No, since A1 = U, not A1=G 1 1 1 1 0 Or1 Or3 And1 And2 A B C D E F G X Y Z 0 1 Test Candidates Collecting Conflicts ? Fourth candidate {A2=U, …} ? Subsumed by conflict? → ? Eliminate candidate Or2 Consistent Candidates: {{A2=U…}} Solutions: {{O1=U…}, {A1=U…}} Conflicts: {{O1=G, O2=G, A1=G}} Yes, since O1=G,O2=G and A1=G 1 1 1 1 0 Or1 Or3 And1 And2 A B C D E F G X Y Z 0 1 Test Candidates Collecting Conflicts ? Return Solutions →O1 or A1 broken Or2 Candidates: {} Solutions: {{O1=U…}, {A1=U…} Conflicts: {{O1=G, O2=G, A1=G}} Single Fault Diagnoses = {A1=U, M1=U} Single Fault Diagnoses are the Intersection of All Conflicts A1=U or M1=U or M2=U removes conflict 1. A1=U or A2=U or M1=U or M3=U removes conflict 2 {A1=G, M1=U, M2=U} conflict 1. {A1=U, A2=U, M1=U, M3=U} conflict 2