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
Find Another Symptom B Al D A2 12 E M3 Symptom G is observed 12. but should be 10 and its Conflict Conflict not just upstream from symptom MI B F10 Al 12 M3 10 mptom G is observed 12. but should be 10 Conflict al=G M2=g& mi-g& m3=G is inconsistent
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
and its Conflict Conflict not just upstream from symptom B Al D A2 12 E M3 Symptom G is observed 12. but should be 10 Conflict al=G M2=g& ml-g& m3=G is inconsistent al=U or A2=U or Ml=U or M3=U removes conflict Recap: Conflicts 6 3 MI B F10 2 M2 A2G Conflict E M3 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
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
Recap: Kernel Diagnoses MI Kernel Diagnosis B A1E10 A2=U&M2=U} 」G12 M3 Partial Diagnosis: A set of component modes M all of whose extensions are diagnoses M removes all symptoms · Mentals model&Obs (implicant Kernel Diagnosis: A minimal partial diagnosis K M is a prime implicant of model obs Out line Conflicts and Kernel Diagnoses Generating Kernels from Conflicts Finding Consistent Modes Estimating Likely Modes Conflict-directed a
? 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 MI 于10 M2 EM3 M3 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 Generate ernels from Conflicts RAl=G, MI=U, M2=U) conflict 1 RAl=U, A2=U, Ml=U, M3=U) conflict 2 al=U or Ml=u or M2=U removes conflict 1 al=U or A2=U or Ml=U or M3=U removes conflict 2 Kernel Diagnoses "Smallest sets of modes that remove all conflicts
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
Generate Kernels from Conflicts Al U or Ml=U or M2=U removes conflict Al=Uor A2=U or Ml=U or M3=0 removes conflict 2 Kernel Diagnoses= Al=Ui Smallest sets of modes that remove all conflicts Generate ernels from Conflicts Al= u or m1∈UorM2=U removes conflict 1 Al=U or A2=U or Ml=U or M3=U removes conflict 2 Kernel Diagnoses- MI=U HAl=Uj " Smallest sets of modes that remove all conflicts
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