Chapter 18 – Symbolic Relaxation Systems

How a problem solver can converge on a consistent interpretation by letting local constraints repeatedly prune away impossible options, and how Allen-style temporal reasoning falls out of the same machinery. companion index

The big idea

Most of this book has been about deriving beliefs: a rule fires, a value is computed, a clause forces a literal. Chapter 18 looks at a different and very old AI technique that gets to a consistent answer by eliminating possibilities instead. The pattern is called relaxation (also constraint propagation or, for the discrete case, arc/path consistency), and the chapter’s vehicle for it is a small system named WALTZER.

The setup is simple to describe:

You have a set of cells (variables). Each cell starts out with a whole value-domain: the set of all values it could possibly take.
Cells are wired together by constraints. A constraint says which combinations of neighbouring cell values are allowed.
The engine repeatedly looks at each constraint and, for every cell it touches, throws away any value in that cell’s domain for which no consistent combination of neighbour values survives. Removing a value can shrink a neighbour’s domain, which can shrink its neighbours’ domains, and so on.

You iterate this pruning until nothing changes — a fixpoint. At that point every cell’s domain contains only values that are locally consistent with their neighbours. If some cell’s domain has shrunk to a single value, you have forced that value. If some cell’s domain has become empty, you have proved the whole problem has no consistent solution. The empty domain is the relaxation analogue of a contradiction in a TMS.

The chapter’s two big applications are:

Line-labelling / scene analysis (the historical “Waltz filtering” that gives WALTZER its name): label every line in a line drawing as convex, concave, or occluding, where each junction type permits only certain combinations of edge labels. Relaxation prunes impossible labellings until a coherent 3-D interpretation of the drawing remains (or it proves the drawing is an impossible figure).
Allen’s temporal interval algebra: reason about when events happen relative to one another (before, overlaps, during, meets, …) using exactly the same propagate-to-consistency loop, with a transitivity table as the constraint.

The deep lesson is continuity with the rest of the book. Relaxation is, at heart, the same local-propagation-to-fixpoint idea as Boolean Constraint Propagation in the LTMS (ch09) — and it has the same headline limitation. BCP is incomplete: it never invents a case split, so it can stall without deciding everything. Arc/path consistency is incomplete in exactly the same way: reaching a non-empty fixpoint does not prove a global solution exists. To go from “locally consistent” to “globally consistent” you must layer search (backtracking) on top, just as the LTRE layers dependency-directed search on top of BCP.

A note on this chapter and this repo. WALTZER — the symbolic constraint propagator over finite value-domains, plus the temporal/interval database — is not implemented in this package. Porting it is an explicit non-goal (see BRIEFING.md). So this page is conceptual. Where it helps it points at the closest available machinery (the LTMS/LTRE and its dependency-directed search, the explanation utilities), and all of the exercise analysis lives in ../exercises/ch18/.

Concepts, step by step

Cells with value-domains (not single values)

This is the one structural difference from the constraint language of chapter 15. There, a cell held at most one value and the job was to derive it. Here a cell holds a set of candidate values — its domain — and the job is to narrow it. A cell whose domain is:

the full set → completely undetermined,
a proper subset → partly constrained,
a singleton → forced to one value,
empty → no consistent value exists (local failure).

For line-labelling, a cell is a line in the drawing and its domain is the subset of {convex, concave, occluding-left, occluding-right} still possible. For the temporal database, a cell is an ordered pair of intervals and its domain is the subset of Allen’s 13 relations still possible between them.

Constraints as “allowed-combination” filters

A constraint links some cells and lists which joint value assignments are legal. The engine never enumerates the whole joint space; it works one cell at a time using a local test usually called support:

A value v in cell c is supported under a constraint if, for every other cell the constraint touches, there is at least one value still in that cell’s domain that, together with v, satisfies the constraint.

If a value loses all support, it is removed. That single rule, applied everywhere until quiescent, is arc consistency (for binary constraints) / generalized arc consistency (for n-ary ones). For Allen’s algebra the constraint between cells R(a,b) and R(b,c) is the transitivity (composition) table: given the relations still possible for a-b and b-c, the table says which relations are possible for a-c, and any relation outside that set is pruned from R(a,c)’s domain. Doing this for every triple to quiescence is path consistency.

The propagation loop (worklist relaxation)

The algorithm is a classic worklist:

put every constraint on the agenda
while the agenda is not empty:
    take a constraint
    for each cell it touches:
        remove unsupported values from that cell's domain
        if the domain became empty:  report "no interpretation" and stop
        if the domain changed:       re-enqueue every constraint touching that cell

Two things to notice:

It is monotone. Domains only ever shrink, never grow. That is what guarantees termination: there is a finite amount of stuff to remove. It is the same monotonicity that makes BCP terminate.
It is local. A change only wakes the constraints adjacent to the changed cell. This is precisely the agenda/queue discipline you have seen in the rule engines and in the LTMS’s clause queue.

Support, exclusion, and explanation

Because each removal is caused by a specific constraint plus specific neighbour states, you can record that cause as the value’s support — and once you record support, you can explain an exclusion by walking the support graph backward. This is the very same well-founded-support idea the whole book is built on, now applied to “why was this value eliminated?” rather than “why is this proposition believed?” (Exercise 1 is exactly this: an explain-exclusion walk with a depth bound to keep long propagation chains readable.)

That parallel is so close that exercise 2 proposes literally bolting a JTMS underneath WALTZER: represent each cell = value possibility as a node, and have each pruning install a justification whose antecedents are the neighbour cell-value nodes responsible. Then belief revision — re-instating a value when the reason for excluding it goes away — comes for free from the TMS, and you get a detailed trace of the propagation as a bonus.

Allen’s interval algebra in one paragraph

For temporal reasoning the “values” are James Allen’s 13 basic relations between two intervals: before/after, meets/met-by, overlaps/ overlapped-by, starts/started-by, during/contains, finishes/ finished-by, and equals. They are jointly exhaustive and pairwise disjoint: any two definite intervals stand in exactly one of them. A cell’s domain is a set of these relations (a disjunction of possibilities, e.g. “a is before or meets b”). Asserting knowledge narrows a cell toward a singleton; the transitivity table propagates those narrowings around the network; an empty domain means the asserted constraints are temporally inconsistent. As with line drawings, path consistency here is incomplete — it can miss some global inconsistencies — so it is a strong filter, not a decision procedure.

Why incompleteness matters (the recurring theme)

Arc/path consistency removes everything that can be removed by local reasoning, but global consistency can require reasoning about several cells at once. A network can be arc-consistent yet have no solution (or be path-consistent yet have no globally consistent labelling). So a pure relaxer might reach a tidy non-empty fixpoint and still be wrong about “a solution exists.” The standard fix is to interleave relaxation with backtracking search: pick a cell, commit to one of its remaining values, re-propagate, and on an empty domain undo and try the next value. That is the same architecture as BCP + dependency-directed search in the LTRE — relaxation is the cheap deterministic core; search supplies the case splits relaxation refuses to make.

The examples, explained

The chapter’s worked material clusters around two demonstrations, each chosen to expose a different facet of the propagate-to-fixpoint idea.

The line drawing (Waltz filtering). A picture of, say, a stacked pair of blocks is turned into a network: each line is a cell whose domain is the set of possible physical labels, and each junction (an L, Y, T, or arrow) imposes a constraint listing the only edge-label combinations that junction type can physically produce. Relaxation from the picture’s boundary inward prunes label combinations that no junction permits until each line has a consistent interpretation. The point of the example is that a huge combinatorial labelling space collapses very fast under purely local pruning — most impossible interpretations die without any global search at all. It is the canonical success story for relaxation.
The impossible figure. Hand the same labeller a drawing that cannot correspond to any real 3-D object (a Penrose-style trident or triangle). What should happen is that propagation drives some line’s domain empty — “no interpretation,” the relaxation form of a contradiction. What can actually happen with a pure arc-consistency relaxer is subtler and is the heart of exercise 4: because arc consistency is incomplete, the relaxer may instead settle at a non-empty but globally inconsistent fixpoint and so fail to prove the figure impossible without an added search step. The example is there to make the incompleteness limitation concrete and visceral.
The temporal database. A sequence of interval assertions (e.g. “meeting A is before lunch,” “lunch overlaps the afternoon session”) is fed in, and the transitivity closure infers the relations the user did not state and surfaces any contradiction. This shows the same relaxation engine doing something that looks completely unlike line drawings, which is exactly the chapter’s argument: relaxation is a general substrate, and Allen’s algebra is just one instantiation of “cells with set-valued domains plus a composition constraint.”

The throughline across all three: the engine is identical; only the cells, the domains, and the constraint table change. Swap in junction tables and you get a scene analyzer; swap in Allen’s composition table and you get a temporal reasoner; swap in RCC-8’s table (exercise 8) and you get a qualitative spatial reasoner.

Exercises walk-through

Full paraphrased statements and original analysis (analysis-only — this chapter’s system is not implemented, so there is no solutions.py) are in ../exercises/ch18/README.md. Highlights:

Exercise 1 (★★) — `explain-exclusion`

Record, on each value-elimination, the constraint and the neighbour cell-states that triggered it — its support — then walk that support graph backward from a given exclusion, emitting one step per constraint firing, stopping at a depth bound (or at user premises). The depth bound is the practical ingredient: propagation chains can be long, and an unbounded “why?” is unreadable. This is the relaxation reflection of chapter 7’s explanation walk and of the repo’s own explain.py.

Exercise 2 (★★) — put a JTMS under WALTZER

(a) conventions. Each cell = value possibility becomes a JTMS node; a pruning installs a justification whose antecedents are the neighbour cell-value nodes responsible. “v is still possible for cell c” is then just the node for “v excluded from c” being OUT. Belief revision (re-instating values when the cause of exclusion disappears) falls out of the JTMS automatically.
(b) efficiency. With k cells and domain size d there are up to k·d nodes; each binary constraint can in the worst case justify excluding each of one cell’s d values from each of the other’s d values, i.e. O(d²) justifications per edge, so O(E·d²) overall for E edges. That quadratic blow-up in domain size is the price of a full trace, and is why production relaxation systems trace selectively rather than recording every elimination.

Exercise 3 (★/★★) — saving, diffing, and breadth-first search

(a) save/restore snapshots each cell’s current value-domain under a name and reinstalls it later.
(b) diff compares two snapshots cell-by-cell and reports which cells’ domains differ and how (values gained/lost), machine-readably.
(c) breadth-first search-network swaps the depth-first completion search for a queue of partial networks, expanding the shallowest first. BFS finds the shallowest solution and dodges deep dead-ends but holds many partial states in memory; DFS is memory-light but can chase long dead branches. The right choice depends on solution depth versus branching: BFS for shallow-and-wide, DFS for deep-and-narrow.

Exercise 4 (★★) — an impossible figure

What you expect/want: propagation drives a domain empty and the system reports “no interpretation.” What you actually get from a pure arc-consistency relaxer: possibly a non-empty but globally inconsistent fixpoint, because arc consistency (like BCP) is incomplete and cannot always prove impossibility without an added search/backtracking step. The exercise is the chapter’s incompleteness lesson in miniature.

Exercises 5, 6 — robustness and temporal rule triggering

(5, ★) robust temporal interface. The naive interval/t-assert interface is fragile: no endpoint validation (start after end), silent acceptance of duplicate/contradictory relations, no inconsistency check on assert. The robust rewrite validates inputs, normalizes relations to a canonical form, and runs the transitivity closure on assert so contradictions surface immediately.
(6, ★★★) temporally-triggered rules. Index pattern-triggered rules by the temporal relation they wait on; when the transitivity closure newly establishes a relation between two intervals, wake the rules whose patterns match. This is the temporal analogue of the pattern-directed rule engines of chapters 4–5, with the interval network playing the role of the fact database.

Exercise 7 (★★) — merging Allen relations into `within`

Collapse starts/finishes/during into a single within. (a) The transitivity table shrinks (fewer rows/columns; merged, coarser entries — a composition that used to pin one of the three now yields within). (b) Reasoning gets weaker: you can no longer tell “shares an endpoint” from “strictly inside,” so some inferences Allen’s full algebra supports are lost. A precision-for-compactness trade.

Exercises 8, 9 — research-scale extensions

(8, ★★★) RCC-8 spatial reasoning. Implement Randell & Cohn’s qualitative spatial relations on WALTZER. RCC-8 is the topological analogue of Allen’s algebra: eight jointly-exhaustive, pairwise-disjoint relations between regions — DC (disconnected), EC (externally connected), PO (partial overlap), EQ (equal), TPP/NTPP (tangential / non-tangential proper part) and their converses TPPi/NTPPi. The build mirrors the Allen code exactly: each ordered region pair is a cell whose domain is the still-possible subset of the eight; RCC-8’s published 8×8 composition table is the constraint; propagate to path consistency. Asserting narrows a cell to a singleton; propagation reaches a consistent fixpoint or empties a domain. And — same caveat — path consistency is incomplete for RCC-8 in general, so global consistency may still need backtracking.
(9, ★★★★) reference intervals at scale. Naive Allen reasoning is O(n²) storage and O(n³) to maintain the path-consistency closure — hopeless for very large n. The standard fix is an Allen–Kautz reference hierarchy: cluster intervals under a smaller set of reference intervals, store precise relations only within a cluster and between reference intervals across clusters, and derive cross-cluster relations on demand by composing local→reference→reference→local. With m clusters of size ≈ n/m, intra-cluster storage is O(n²/m) and the reference layer O(m²), minimized near m ≈ n^{2/3} for roughly O(n^{4/3}) storage and sub-cubic reasoning — at the cost of coarser (possibly disjunctive) cross-hierarchy answers. A genuinely open-ended (★★★★) design with no single optimal answer.

Ex	Topic	Core result
1 (★★)	`explain-exclusion`	Record support per elimination; walk it backward with a depth bound.
2 (★★)	JTMS under WALTZER	Cell=value nodes + justified prunings give free belief revision; cost `O(E·d²)` justifications.
3 (★/★★)	save / diff / BFS	Snapshot domains; diff cell-by-cell; BFS = shallow-wide, DFS = deep-narrow.
4 (★★)	impossible figure	Should empty a domain; a pure arc-consistency relaxer may stall (incompleteness).
5 (★)	robust temporal API	Validate endpoints, normalize relations, close transitivity on assert.
6 (★★★)	temporal rule triggers	Index rules by awaited relation; wake on newly-closed relations.
7 (★★)	merge to `within`	Smaller table, coarser compositions; precision lost for compactness.
8 (★★★)	RCC-8 in WALTZER	Same engine, spatial composition table; path consistency still incomplete.
9 (★★★★)	reference intervals	Two-level hierarchy → ~`O(n^{4/3})` storage, sub-cubic reasoning, coarser cross answers.

Try it in this repo

WALTZER, the line-labeller, and the temporal/interval database are not in this package, so there is nothing to run for relaxation directly. The closest runnable machinery is the LTMS/LTRE, which shares the two ideas this chapter turns on — propagate-to-fixpoint and search layered on an incomplete local propagator — and the explanation utilities, which are the runnable analogue of exercise 1’s explain-exclusion.

. .venv/bin/activate

# Local propagation to a fixpoint (BCP) is the engine analogue of relaxation:
python examples/belief_revision_ltre.py    # assert/retract; watch consequences propagate

# Search layered on top of the incomplete local propagator (the ch18 "add
# backtracking to relaxation" architecture, here over clauses instead of cells):
python examples/coloring_dds.py            # dependency-directed search, learning nogoods
python exercises/ch10/solutions.py         # N-queens via DD-search

Why these stand in for relaxation:

BCP ≈ arc consistency. The LTMS’s Boolean Constraint Propagation in src/ltms/core.py (with the watched-literal scheme in src/ltms/watched.py) is exactly a propagate-to-quiescence loop over a clause network, and it is incomplete in the same way arc/path consistency is — it never case-splits on its own. That is the precise structural parallel to WALTZER’s relaxation core.
DD-search ≈ “relaxation + backtracking.” Exercise 3c and 4 both end with “you need to add search on top of the local propagator.” The repo already does that: src/ltms/dds.py commits to choices, re-propagates, and on a contradiction records a nogood identifying the responsible assumptions so the same dead branch is never re-explored — the clause-network twin of “commit a cell to a value, re-propagate, and on an empty domain undo.”
explain ≈ explain-exclusion. src/ltms/explain.py walks each forced literal’s well-founded support back to enabled assumptions and prints a numbered proof (explain_node, why_node). That is exactly the backward support walk exercise 1 asks for, applied to “why is this believed?” rather than “why was this value excluded?”.

A minimal taste of the local-propagation-then-explain idea in Python:

from ltms.ltre import LTRE
from ltms.explain import explain_node, why_node

e = LTRE()
# ... assert clauses (the analogue of WALTZER constraints) and premises ...
# BCP propagates to a fixpoint automatically; then ask "why?":
node = e.referent(("some", "forced", "fact")).tms_node
for line in explain_node(e.ltms, node):
    print(line)        # numbered proof back to the premises -- the explain-exclusion shape

For the actual chapter-18 analysis (the explanation walk, the JTMS-under-WALTZER design and its cost, the impossible-figure incompleteness argument, the temporal and RCC-8 work, and the reference-hierarchy design), read ../exercises/ch18/README.md — it is conceptual by design, with no solutions.py.

Takeaways

Relaxation = local pruning to a fixpoint. Cells hold value-domains; constraints remove unsupported values; removals cascade until nothing changes. Monotone (domains only shrink) ⇒ it terminates; local (only adjacent constraints re-fire) ⇒ it is efficient.
An empty domain is a contradiction. A singleton domain is a forced value; an empty one means no consistent solution — the relaxation analogue of a TMS contradiction.
It is the same idea as BCP, with the same limitation. Arc/path consistency, like Boolean Constraint Propagation, is incomplete: a non-empty fixpoint does not prove a global solution exists. You must layer backtracking search on top to be complete — precisely the LTRE’s BCP-plus-DD-search architecture.
One engine, many domains. Plug in junction tables → line-labelling / scene analysis; Allen’s composition table → temporal reasoning; RCC-8’s table → qualitative spatial reasoning. The relaxation loop never changes.
Support makes it explainable and revisable. Record why each value was pruned and you can explain exclusions (exercise 1) and even run the whole thing on a JTMS for automatic belief revision (exercise 2) — the same separate-belief-from-its-justification thread that runs through the entire book.
Scaling temporal reasoning is a real research problem. All-pairs Allen reasoning is O(n²)/O(n³); reference-interval hierarchies trade exactness for roughly O(n^{4/3}) storage and sub-cubic reasoning (exercise 9).

Back to the companion index · previous: Chapter 17 — A Tiny Diagnosis Engine · this is the final chapter of the book.