Chapter 14 – Putting the ATMS to Work (diagnosis / GDE)

How the many-worlds reasoning of the ATMS becomes a working problem solver: blocks-world envisioning, focused control, and the model-based diagnosis style that underlies GDE. companion index

The big idea

Chapter 12 introduced the ATMS (assumption-based TMS): instead of holding one current set of beliefs the way a JTMS or LTMS does, the ATMS tracks every consistent combination of assumptions at once. Each derived fact (a node) carries a label — a small set of environments, where each environment is a minimal, consistent bundle of assumptions under which that fact holds. The ATMS keeps those labels sound, consistent, complete, and minimal, and remembers nogoods (assumption combinations known to be contradictory).

Chapter 14 is the “now do something with it” chapter. It takes that machinery and builds three things:

An ATMS-coupled rule engine (the book calls it ATRE), the assumption-based analogue of the LTRE from chapter 10. Rules fire on patterns and the ATMS does all the multi-context label bookkeeping underneath.
A focused / suggestions control architecture — a way to stop the ATMS from eagerly exploring all worlds when you only care about a few, by separating generating candidate inferences from deciding which to pursue.
Two flagship applications: a blocks-world planner/envisioner (plan-a forward, plan-e for the full envisionment) and the model-based diagnosis style that the General Diagnostic Engine (GDE) made famous.

The reason the ATMS is such a natural fit for diagnosis is the whole point of the chapter. Diagnosis asks “which components could be broken?”, and that is a question about many hypotheses at once. If you make each component’s “working correctly” status an assumption, then a discrepancy between predicted and observed behaviour is a contradiction, the ATMS records it as a nogood, and the nogood is a candidate diagnosis (a set of components that cannot all be healthy). The ATMS computes all minimal diagnoses in one sweep instead of re-running a solver once per hypothesis.

Scope note. This chapter’s systems (the ATMS itself, ATRE, the focused/suggestions controller, and the plan-a/plan-e blocks-world planners) are not implemented in this package — they are an explicit non-goal (see BRIEFING.md). So this page is conceptual, and the exercise solutions in ../exercises/ch14/ are analysis, design sketches, and complexity derivations rather than runnable code. The “Try it in this repo” section points you at the closest machinery we do ship (the LTMS/LTRE and dependency-directed search) so you can feel the same ideas at work.

Concepts, step by step

From one world to many: the ATMS contract, recapped

You only need a handful of definitions from chapter 12 to follow this chapter. They are worth restating because every algorithm below is phrased in terms of them:

An assumption is a primitive choice you are allowed to make and unmake (a component is working; a block sits on the table; a die shows a 4).
An environment is a set of assumptions. It is consistent if it is not a superset of any recorded nogood.
A node’s label is the set of environments under which the node is believed. “Minimal” means no environment in the label is a superset of another; “complete” means every consistent environment that derives the node is covered by some label entry.
A nogood is an environment that has been shown to be contradictory. Once recorded, every superset of it is dead too.

The slogan: a JTMS/LTMS answers “is this believed right now?”; the ATMS answers “in exactly which worlds is this believed?” — and answers it for all nodes simultaneously.

ATRE: rules over an ATMS

ATRE is to the ATMS what the LTRE is to the LTMS. The engine does universal instantiation (matching rule patterns against ground facts), and the ATMS does all the label maintenance. The interesting part is the trigger conditions, because in a many-worlds setting “when does a rule fire?” has more than one sensible answer:

:INTERN — fire once, on the interned pattern itself, independent of any environment. This is for installing structure that is true everywhere: constraints, consistency laws, the wiring of a device. An :INTERN rule does not re-fire per world, so it is cheap.
:IN — fire when the triggering datum is believed in the current focus environment. This is for work that only matters in the world you are actually looking at.

That distinction looks small but it is the hinge of several exercises. A pruning law (for example “a block cannot be on itself”) must be :INTERN: it has to run on the pattern so it can manufacture the nogood. If you wrote it as an :IN rule it would never fire, because the only environments where both of its antecedents are simultaneously believed are exactly the environments it would declare contradictory — and an inconsistent environment is never the focus. (That is Exercise 1.) Chapter 14 also proposes two further triggers as exercises: :EACH-IN (fire when each antecedent is believed individually, somewhere, not necessarily together) and :CONSISTENT-WITH (fire when the antecedents do not conflict with the focus). The first is a speculative, opportunistic trigger; the second is a generator that proposes a step whenever it is “not yet ruled out.” We unpack both in the exercises walk-through.

Why eager many-worlds reasoning needs control

The ATMS’s strength is also its danger. If you let an ATRE chase every rule in every environment, you materialize the entire space of consistent worlds. For a tightly constrained problem with a handful of answers (cryptarithmetic, say, or N-queens) that is enormously wasteful: you pay to maintain labels for vast numbers of environments that are ultimately inconsistent or irrelevant.

Chapter 14’s answer is the focused / suggestions architecture. Two ideas:

Suggestions separate proposing an inference from performing it. A rule, instead of immediately asserting its conclusion in all worlds, emits a suggestion: a triple (rule, bindings, environment) saying “this inference is available, and here is the world it applies to.” Suggestions go on a queue.
Focus picks what to do next. A controller maintains a current focus environment (plus a frontier of alternatives) and orders the pending suggestions by a control policy — best-first, depth-first, breadth-first. Only the chosen suggestion is executed; the ATMS then propagates labels and drops any suggestion whose environment has become a nogood.

The payoff is that you get the ATMS’s bookkeeping benefits — shared subexpressions across worlds, automatic nogood pruning, instant “is this still possible?” checks — without paying to expand worlds you do not care about. The loop is: pop the best suggestion consistent with the focus → execute it (assert nodes and justifications under its environment) → update the focus → repeat. This kernel is what Exercises 12–14 build the reusable solver around.

Blocks world: planning and envisioning

The chapter’s running planning domain is blocks world, encoded with STRIPS operators (preconditions + add-list + delete-list). Two solvers:

plan-a is a forward planner: from the initial state, apply applicable operators until the goal is reached. Each operator choice is an assumption, so a plan is an environment, and conflicting operator choices become nogoods that the ATMS uses to prune.
plan-e computes an envisionment: the complete graph of all reachable states and the transitions between them. This is where the ATMS earns its keep — the envisionment naturally lives across many worlds, and the ATMS shares the structure that different states have in common.

Two recurring blocks-world facts to keep in mind, because the exercises lean on them:

The number of distinct legal states for N labeled blocks on a table is the “sets of sequences” count A000262: 1, 3, 13, 73, 501, … — so three blocks give 13 states. (Derivation and recurrence are in Exercise 2.)
The blocks-world consistency laws (no block on itself; no two-block cycle) are pruning constraints, not generators. They never create states; they only kill impossible ones — and with the standard clear/on operator preconditions they turn out to be redundant, because the impossible configurations were already unreachable (Exercise 1).

Model-based diagnosis and GDE (why the ATMS shines here)

The diagnosis flavour the chapter points toward is model-based diagnosis, the idea behind de Kleer & Williams’ GDE (General Diagnostic Engine). The recipe:

Model the device structurally. Each component (a multiplier, an adder, a wire) has a behaviour rule that holds when the component is working. Make “component C is OK” an assumption.
Predict. Run the rules forward from the observed inputs. Predicted values carry labels: each predicted value is believed in the environment of the OK-assumptions that produced it.
Compare with observation. When a predicted value conflicts with a measured value, you have a contradiction. The set of OK-assumptions that jointly produced the conflicting prediction is a conflict — the ATMS records it as a nogood. A conflict says “these components cannot all be healthy.”
Diagnose. A diagnosis is a set of components whose failure explains every conflict — formally, a minimal hitting set of the conflicts. Because the ATMS has already computed all the minimal conflicts as nogoods, you read the candidate diagnoses straight off them, including multiple-fault diagnoses, in one pass.
Choose the next measurement. GDE’s other half is using the labels to pick the most informative next probe (the one whose outcome best discriminates among the surviving diagnoses) — an entropy/information-gain calculation over the environments. The chapter treats this as the natural extension once the conflict-recognition machinery is in place.

The deep reason this is elegant: in a single-context system you would re-run the solver once per fault hypothesis. With the ATMS, prediction across all OK-assumption combinations happens simultaneously, and conflicts fall out as nogoods for free. The envisionment-style label sharing pays for itself precisely because diagnosis genuinely needs all the worlds, not one.

The examples, explained

The chapter’s worked examples each isolate one of the moving parts above.

A blocks-world plan with plan-a. Stacking a small tower shows the forward loop: applicable operators are the choices, each choice is an assumption, the resulting state’s literals get labels, and an impossible combination (trying to move a block that is not clear) shows up as a nogood that prunes that branch. The lesson is that a plan is just an environment and plan failure is just a contradiction.
A three-block envisionment with plan-e. Running the full envisionment yields the 13 states and the transitions between them. The example demonstrates two things at once: that the ATMS shares the substructure common to many states (so you are not recomputing clear/on facts independently per world), and that the consistency laws prune the geometrically impossible configurations. It is the concrete payoff of “reason in many worlds at once.”
:INTERN vs :IN triggers side by side. The examples contrast a structural law installed once with :INTERN against work that should only happen in the focus with :IN. This is the example that makes Exercise 1 obvious: a contradiction-posting law has to be :INTERN, because the world where its antecedents co-occur is exactly the world it forbids.
Focused control on a constrained search. Pointing the suggestions architecture at a CSP-flavoured problem shows the controller committing to a focus, extending it one consistent suggestion at a time, and backjumping when a nogood fires — the difference between “explore one promising world deeply” and “expand all worlds.” This is the example the cryptarithmetic exercises (14a/14b) build on to compare many-worlds against focused search.
A diagnosis sketch. A small device with a couple of components and a measured discrepancy shows the conflict → nogood → candidate-diagnosis pipeline: the OK-assumptions behind a wrong prediction become a nogood, and the minimal hitting set over the nogoods gives the suspect components. This is the GDE idea in miniature.

Exercises walk-through

The full set of solutions (all 16, with the multi-part items 5–9 and 14 broken out) is in ../exercises/ch14/README.md. They are analysis only — no solutions.py, because the ATMS/ATRE/focused-control machinery is outside this package’s scope. Highlights:

Ex. 1 — dropping the antisymmetry/irreflexivity laws. These are pruning axioms, not generators. With the standard clear/on operator preconditions the impossible states (a block on itself, a two-block cycle) are already unreachable, so removing the laws adds no new states — the three-block count stays 13. And if such a law were written :IN instead of :INTERN it would never fire, because its antecedents are only simultaneously believed in an environment that is itself a nogood. This is the textbook reason pruning laws are :INTERN.
Ex. 2 — counting states and transitions. The number of N-block states is A000262 (1, 3, 13, 73, 501, …), with the closed/recurrence form a(N) = (2N−1)·a(N−1) − (N−1)(N−2)·a(N−2). Transitions are counted per state as (ordered pairs of clear tops, for stack-on-stack moves) + (non-singleton clear tops, for moves to the table), summed over all states.
Ex. 3 — an ATMS explore-network browser. Port the graph walker to the ATMS by adding a visibility filter parametrized by (env, mode): :IMPLIED-BY shows only what is believed in env (a “why do I believe this here” view); :CONSISTENT shows everything still compatible with env (a “what is not yet ruled out” view). The two modes are the believed-view and the possibility-view of the same graph.
Ex. 4 — efficient :IN rules via remove-node. Implement an :IN trigger as a one-shot monitor node justified by the trigger datum; after it fires, call remove-node to delete the monitor and patch dependent labels. Without remove-node every transient monitor would live forever and drag down all future label propagation; with it the cost is paid once and reclaimed.
Exs. 5–6 — generalizing the domain. Ex. 5 replaces clear/on with set-valued straddles/straddlers (a block can rest on several supports and bear several blocks), which forces operators to have state-dependent add/delete lists — the recurring “partially specified effects” theme. Ex. 6 makes clear a default assumption: bookkeeping gets simpler (you stop asserting/retracting clear by hand) but belief revision gets harder (clear is now non-monotonic and must be defeated when something lands on the block). Both push complexity out of the operator code and into the TMS — which is exactly the trade ATMS defaults are meant to make.
Ex. 7 — the casino robot (odds via envisioning). Model the shaken dice as a disjunction over face assumptions (face1 ∈ {1..6}, face2 ∈ {1..6}) with mutual-exclusion nogoods. The ATMS envisions all 36 combinations, and the label of Score(n) is exactly the set of (f1,f2) environments that sum to n. So P(Score(n)) = |label(Score(n))| / 36 — the envisionment is the sample space, and label cardinality is the favourable-outcome count. A lovely illustration of reading probability straight off ATMS labels.
Exs. 8 — colour and the spreading paint. A plain paint(B,c) is an easy STRIPS operator, but spreading paint (recolour everything transitively on B) cannot be plain STRIPS: the add-list depends on the current tower shape, so it is a universally quantified / conditional effect — the classic motivation for ADL-style conditional effects and the “effect generators” of Ex. 8d.
Ex. 9 — :EACH-IN and :CONSISTENT-WITH. :EACH-IN does not need an ATMS (any TMS can tell you each datum is believed somewhere), and it is useful but speculative — good for opportunistic suggestion generation, risky for sound deduction (the premises might be individually believable yet mutually inconsistent). :CONSISTENT-WITH does need an ATMS (it asks whether the triggers could hold together, a multi-environment question), and it is the ideal generator trigger for focused search — propose a step whenever it is not yet ruled out.
Exs. 10–13 — bigger builds. Backward-chaining (goal-regression) planning on the plan-a template (Ex. 10); reimplementing a planning technique on ATRE as the world model, getting state-sharing and nogood-pruning for free (Ex. 11); the general focused/suggestions solver kernel (Ex. 12); and a natural-deduction propositional prover on top of it, where discharged assumptions map cleanly onto ATMS assumptions and KM* supplies the focus heuristic (Ex. 13). All are given as designs.
Ex. 14 — cryptarithmetic, many-worlds vs focused (the headline comparison). For a tightly constrained CSP with few solutions, the focused (DFS + consistency-driven) strategy is expected to win decisively: it commits to one partial assignment, extends it with :CONSISTENT-WITH, and backjumps on nogoods, instead of materializing the combinatorial space of worlds the many-worlds ATMS would label. Among triggers, :INTERN beats :IN for installing the uniform column-sum constraints (one structural install vs per-environment re-firing). The generalization is the chapter’s real takeaway: focused search wins on highly constrained problems with few answers and deep dependency chains (most CSPs, configuration, planning); many-worlds wins when you genuinely need many answers or a comparison across all contexts — diagnosis/GDE multiple-fault reasoning and qualitative envisioning — where the shared-label structure pays for itself.
Exs. 15–16 — research-flavoured. A scalable-multiprocessor ATMS (graph partitioning for few processors, bitvector environment operations for many; speedup bounded by the justification DAG’s critical path and the partition cut), and the “inside-out” idea of recasting ATMS concepts (assumptions → design decisions, nogoods → incompatibility records, label propagation → impact/reuse analysis) as a distributed dependency service for teams of human designers.

Try it in this repo

This chapter’s systems are not implemented here, so there is nothing in the package to run for the blocks-world planner, ATRE, or the focused controller. The honest answer is that Chapter 14 is conceptual in this repo, and the analysis lives in ../exercises/ch14/README.md.

What you can do is exercise the same ideas with the machinery we do ship — the single-context LTMS/LTRE and our dependency-directed search. These are not the ATMS, but they let you watch the underlying mechanisms (assumptions, contradictions, nogood-learning, conflict-driven pruning) in action.

. .venv/bin/activate

# Diagnosis in miniature: a lamp is off; rule out "no power"; conclude "bulb dead".
# This is the conflict-narrows-the-hypotheses idea, in a single-context LTMS.
python examples/run_kb.py examples/kb/diagnosis.kb

# Nogood-learning search: the focused/DFS idea of Ex. 14, in our DD-search.
python examples/coloring_dds.py                 # map colouring via dependency-directed search
python exercises/ch10/solutions.py              # includes N-queens counts via dd_search

The diagnosis .kb is the closest thing in the repo to the GDE story (examples/kb/diagnosis.kb):

lamp off -> bulb dead | no power
lamp off
~ no power
expect bulb dead true

Asserting lamp off introduces the disjunction of faults; ruling out no power leaves the single remaining cause — the one-context shadow of “conflicts narrow the candidate diagnoses.” The genuinely multi-fault, all-at-once version is exactly what the ATMS adds, and that is the part this package does not implement.

For the focused vs many-worlds contrast of Exercise 14, our dependency-directed search (src/ltms/dds.py) is the focused/DFS half done for real: it commits to one choice per choice set, runs rules, and on a contradiction learns a nogood via assumptions_of_clause so the dead combination is never re-explored. Reading it alongside Exercise 14’s analysis is the best way to feel why focused search beats materializing all worlds on a tightly constrained CSP. A minimal taste:

from ltms.ltre import LTRE
from ltms.dds import dd_search

e = LTRE()
# ... assert constraints as clauses ...
solutions = dd_search(e, choice_sets, extract=lambda eng: ...)

If you want the actual ATMS, it sits one layer beyond this repo’s deliberate scope; STUDY-NOTES.md §9 sketches where it would attach (via the CLTMS’s tms_env, reading ATMS-style environment labels off prime implicates).

Takeaways

The ATMS turns “which hypotheses hold?” into a single computation. Labels carry the worlds; nogoods carry the impossibilities; both are maintained incrementally for all nodes at once.
ATRE is the LTRE in many worlds. Its trigger conditions matter: :INTERN installs structure once (and is the only correct trigger for pruning/consistency laws), :IN does focus-local work, and the proposed :EACH-IN / :CONSISTENT-WITH triggers trade soundness for opportunism and generation.
Unrestrained many-worlds reasoning is expensive; the focused/suggestions architecture is the cure. Separate generating candidate inferences from choosing which to pursue, keep a current focus, and let nogoods prune.
Diagnosis is the killer app. Make “component OK” an assumption, predict across all OK-combinations at once, read conflicts off the nogoods, and take minimal hitting sets for the candidate (including multiple-fault) diagnoses — the GDE idea.
Choose the strategy to fit the problem. Focused search for tightly constrained problems with few answers (cryptarithmetic, configuration, planning); many-worlds when you truly need all contexts (multiple-fault diagnosis, envisioning).
In this repo it is conceptual. The runnable shadows are the LTMS/LTRE and dependency-directed search; the analysis is in ../exercises/ch14/.

Back to the companion index · previous: Chapter 13 — CLTMS · related: Chapter 12 — ATMS.