AI Search · Exam notes
Diagnosis turns a wrong device output into sets of suspects: which components cannot all be OK? which suspect sets hit every conflict? which is minimal? One chain answers all: predict with everything OK, clash with the observation to get conflicts, keep the sets that touch each conflict, then apply Occam. The second half of this page revises every earlier topic in one table each.
| Term | Meaning |
|---|---|
| Component model | If OK, behavior is fixed: multiplier gives \(out = in1 \times in2\); adder gives \(out = in1 + in2\). Wires never fail, only components do. |
| Observation | Measured output, e.g. \(F1 = 10\). Prediction with all OK was 12: mismatch means something broke. |
| Conflict | A set of components that cannot ALL be OK: assuming each OK reproduces the mismatch. At least one member is faulty. |
| Diagnosis (hitting set) | A faulty set touching EVERY conflict. Miss one conflict and that conflict stays unexplained. |
| Minimal + Occam | Minimal: no subset still hits all conflicts. Occam's razor: simplest (smallest) explanation is best; ties need more measurements. |
3a. Device and observations (solve from this, then check the walkthrough)
A1 takes C1, C2 and outputs F1. A2 takes C3 (and a second feed) and outputs F2. All-OK prediction: \(F1 = F2 = 12\). Observed: \(F1 = 10\) (wrong), \(F2 = 12\) (right).
3b. Walkthrough: conflicts first, then candidates
Why this step
Tracker
3c. The three questions
Device and observations as above. Wires cannot fail.
3d. Answers first, then the working
Conflicts: {M1,M2,A1}, {A1,A2,M1,M3}. Minimal diagnoses: M1; A1; M2+M3; M2+A2. Occam: M1 or A1 (single faults first).
| Strategy | Path |
|---|---|
| Best | S,D,A,G |
| A* | S,F,A,G |
| B&B | S,F,E,C,G (shortest) |
Shortest = B&B. Heuristic inadmissible. Theory appendix (Search point 7): DFID needs new as well as closed; unknown heuristic with unit costs takes BFS, Dijkstra, B and B (general costs: Dijkstra, B and B only); wA* at large w is Best-First and not optimal, at w = 0 is Dijkstra and optimal.
| Paper | Refined / optimal | Cities / tour |
|---|---|---|
| 2024T1 FN | b1,c1,d1,d2 / e2,402 | 6 / A,C,B,E,D,F |
| 2024T2 FN | b1,c2,d1,b2 / d3,244 | 5 / A,C,B,D,E |
| 2024T3 AN | b1,c2,d1 / d1,162 | 5 / A,D,B,C,E |
| 2024T3 FN | b1,b2,c3 / d1,230 | 5 / A,C,E,B,D |
| 2025T2 FN | b1,c2,b2,c3 / d3,434 | 5 / A,B,D,E,C |
| Paper | Minimax / strategy / best / pruned / solved |
|---|---|
| 2024T2 | 56 / A,B + D,G,H / I,J / C,E,F,G,H,K / A,D,I,J |
| 2024T1 | - / A,C + D,F,G / D,E / C,F,G,I,J / A,D,E,H |
| 2024T3 FN | - / C,D,E,G,H + F,G,H / A,B / D,E,G,H unaffected / A,B,C,F |
| Eval assign FN | minimax 3 / cuts 0 alpha, 2 beta / pruned B,D |
| Eval assign AN | minimax 2 / cuts 2 alpha, 0 beta / pruned B,D |
| N-cutoff odd | N = 11 or 13 / Beta Cutoff |
| N-cutoff even | N = 2 or 4 / Alpha Cutoff |
| 2024T2 FN | S,C,A / 12,28,36 / 56 |
| 2024T1 FN | S,A,B / 22,32,24 / 38 |
| 2024T3 FN | S,C,B / 16,22,24 / 30 |
| 2024T3 AN | S,C,A / 16,22,24 / 32 |
Loop: expand S, walk the marked path, AND sums, OR mins, backpropagate, re-mark cheapest. Fourth question (some papers): all four heuristics above are admissible (every h at or below true cost); official keys seen elsewhere are admissible twice, inadmissible twice, never sometimes.
Conflict set: (F1-Car,104,107,109), (Luxury-Car,103,106,108), (Truck,101,102,105). Specificity (most tests): Truck (12 vs 9, 9). Recency (max timestamp): F1-Car (109 vs 108 vs 105).
Applicable: Unstack(D,A), Unstack(E,B), Pickup(C). Relevant: Stack(A,B), Stack(B,C). Mutex actions: (Unstack(D,A),Pickup(C)), (Unstack(D,A),Unstack(E,B)). Mutex props: (clear(A),holding(E)), (clear(A),clear(B)).
\(R_{AC}\): (1,2),(2,1),(2,4). \(R_{BA}\): (1,3),(2,2),(3,1). Arc consistent? No (C=3 dead). After enforcing: path consistent. Solution: 2,2,1.
Layer k cannot be the start (has mutexes). Applicable: Putdown(A), Stack(A,B), Unstack(A,B) (Unstack(B,C) dies on mutex pres). Mutex: all three queried pairs. Non-mutex props via Putdown(A)+nop-4. Theory keys: one ordering feasible iff P in pre(a) + del(b); both feasible with different outcomes iff P in add(a) + del(b); action mutex = all four at once; props mutex = every producer pair, non-mutex = one clean pair.
Evening: X=beach, Y=matrix, Z=saravanaBhavan (mall and pizzaHut fail likes-checks). Nice toy: X=D via rule 2. Leftmost goal, leftmost fact, backtrack on failure.
Solve each with a pen before opening the answer. Each drill is self contained.
Conflicts: {X,Y}, {Y,Z}. Q1: which singles are diagnoses? Q2: which minimal doubles? Q3: Occam pick?
Why this step
Tracker
Q1: Y only (sits in both; X misses the second, Z misses the first). Q2: X+Z (X covers the first, Z the second; pairs with Y are non-minimal). Q3: Y, the single fault.
Conflicts: {A,B}, {C,D}. Q1: any single diagnosis? Q2: list minimal diagnoses. Q3: Occam pick?
Why this step
Tracker
Q1: none (no component sits in both). Q2: four minimal doubles: A+C, A+D, B+C, B+D. Q3: four-way tie at size 2: Occam cannot choose; probe a component (e.g. test A) to split them.