Conflict-directed Diagnosis and Probabilistic mode estimation Brian c. williams 16412J/6.834J March 10th. 2004 courtesy of JPL Outline MERS CSAIL Conflicts and Kernel diagnoses Generating Kernels from Conflicts Finding Consistent Modes Estimating likely modes Conflict-directed a
courtesy of JPL Conflict-directed Diagnosis and Probabilistic Mode Estimation Brian C. Williams 16.412J/6.834J March 10th, 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( OrI G(0) 0 AndI Out(=In1( AND In2 U() ALL components have Or3 unknown Mode'U Whose assignment is Diagnosis=(Al=G, A2=UO1=G, 02=U, 03=G) never mentioned in C Obs Assignment to o Candidate C;: Assignment of modes to X Diagnosis D A candidate such that D, Obs A C(X, Y is satisfiable As more constraints are relaxed, candidates are more easily satisfied 2 Typically an exponential number of candidates Diagnosis identifies All sets of consistent modes Adder(i MI G() Al E10 out()=In1()+n2( U() 12 DiagnoSis =(Al=G, A2=U, MI=G, M2=U, M3=G) Diagnosis D: Candidate consistent with model phi and observables oBs As more constraints are relaxed. candidates are more easily satisfied e Typically an exponential number of candidates
Consistency-based Diagnosis And(i): G(i): Out(i) = In1(i) AND In2(i) U(i): Obs: Assignment to O Candidate Ci : Assignment of modes to X Diagnosis Di : A candidate such that Di ∧ 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}
Representing Diagnoses Compactly: Kernel Diagnoses F10 Al D G12 M3 Kernel Diagnosis=(A2=U, M2=U) Smallest sets of modes that remove all symptoms Every candidate that is a subset of a kernel diagnosis is a diagnosis Diagnosis by Divide and Conquer Given model phi and observations OBs a1. 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, 871
? ? “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]
Conflicts Explain How To Remove Symptoms Orl 1_AndA 0 Or2 D And3 EOr ymptom F is observed 0, but should be 1 if. 02 and Al are okay Conflict fAl=G, O1=G, 02=G) is inconsistent At least Al=0. 01=0. or 2=U Conflicts Explain How to Remove Symptoms 6 MI B F10 Al M2 D A2 M3 ptom F is observed 10, but should be 12 if Al, Mi m2 are okay
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 F 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 F10 Al M2 D ymptom F is observed 10, but should be 12 if Al, Ml m2 are okay. Conflict al=G M1=g M2=G is inconsistent Conflicts Explain How to Remove Symptoms B F10 Al M2 D ptom F is observed 10. but should be 12 Conflict al=G&Ml-g M2=G is inconsistent Al=U or Ml=U or M2=U removes conflict
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 F 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