Starting from the initial state, Graphplan alternates proposition layers and action layers. An action enters when its preconditions appear without pairwise mutex; persistence actions carry unchanged propositions forward. The following proposition layer unions all effects. Mutex propagation records selected action and proposition pairs that cannot coexist.

Expansion continues until every goal appears at a proposition layer and no goal pair is mutex. That is necessary, not sufficient. The graph is a disjunctive compression of many forward states: individually reachable propositions can still lack a jointly consistent supporting assignment.

Backward search chooses an action supporting each goal at level k, rejecting action pairs marked mutex. The union of chosen preconditions becomes the goal set at k−1. Recursion succeeds on reaching the initial layer; otherwise it explores alternative supports. If no assignment works at the current depth, Graphplan expands another level.

The original algorithm memoises a failed subgoal set at its level. A later search containing that complete set fails immediately. Because layers can level off while search no-goods continue to change, Graphplan can prove absence of a finite plan in the classical setting when graph and memo conditions stabilise.

Kambhampati’s study does not replace the graph. It reinterprets extraction using constraint-satisfaction concepts, exposing what standard chronological backtracking and whole-set memoisation throw away. The transformation is analytical and operational: once failure has an explanation, the search can both learn and retreat more precisely.

Each proposition at each graph level is a DCSP variable. Its domain contains the actions at the previous action layer that support it. Top-level goals begin active. Assigning action a as the value of goal g activates every precondition of a as a variable at level k−1.

Action mutexes become constraints between value assignments. If actions a and b are mutex, then any propositions supported by them cannot simultaneously take those values. Proposition mutexes prohibit simultaneous activation: both variables cannot take non-null values in the same solution.

A DCSP can be compiled to an ordinary CSP by adding a null value ⊥ to every domain. Inactive means assigned ⊥; active means constrained not to ⊥. Activity implications become higher-arity constraints connecting a selected support to non-null predecessor variables. This allows standard CSP solvers but can create large extensional constraints.

The direct DCSP view mirrors Graphplan’s epoch-by-epoch backward search and avoids materialising every constraint. It also clarifies why generic CSP heuristics need not transfer unchanged. A present goal variable with a small domain may activate many difficult predecessors, while a larger domain may contain a support with easy preconditions.

The mapping separates graph-level pruning from search-level consistency. Planning-graph construction enforces partial directed one-consistency by admitting supported actions and partial directed two-consistency through mutex propagation. It does not establish full one- or two-consistency over actual values, much less higher-arity consistency.

Partial directed one-consistency excludes an action when its preconditions are absent or pairwise mutex. Yet the appearance of a proposition does not guarantee that any complete support assignment reaches it in conjunction with the rest of the goal set. A surviving value can still be impossible under other assignments.

Partial directed two-consistency marks proposition pairs mutex when all their supporting action pairs are mutex. This speaks about simultaneous activity: whether both can take some non-null value: not whether every particular value pair is feasible. Fine-grained action mutex constraints remain for extraction.

Higher-arity contradictions can evade all pairwise tests. Three goals may be pairwise supportable while no triple of actions is jointly consistent. Whole-goal memoisation then supplies failure-driven higher-order consistency, but only after search encounters the combination.

Deriving every value-level no-good during graph expansion could strengthen pruning dramatically and also explode storage. With l levels, m goals per level and d supporting actions per goal, Graphplan-style pairwise proposition mutexes scale roughly with l·m², whereas pairwise value no-goods can scale with l·[m(d+1)]².

The paper repeatedly treats learning as a utility problem. A fact may be logically derivable yet not worth storing or checking. Conservative graph mutexes and level-indexed memos keep management cost low; EBL seeks a better reuse-to-overhead ratio by making each learned set smaller and more relevant.

Suppose goals {P₁,P₂,P₃,P₄,P₅,P₆} fail because every support for P₄ conflicts with choices already made for P₁ and P₂. P₃, P₅ and P₆ are spectators. Whole-set memoisation records all six. It will prune only a future goal set containing all six, missing many contexts where {P₁,P₂,P₄} reappears.

Chronological backtracking likewise retreats first to P₃, the immediately preceding assignment, although changing P₃ cannot repair P₄. The search can revisit every value of irrelevant intervening goals before it changes P₂ or P₁. Learning and backtracking suffer from the same missing explanation.

Normal memos are nevertheless conservative and cheap. They contain only proposition variables from one planning-graph level, are stored separately by level and are checked only against same-level goal sets. They ignore value assignments, drastically limiting the no-good universe and lookup burden.

Subset matching already makes a memo applicable when it is contained in the current goal set. But shrinking the learned set is what makes subset matching powerful. The experiments found that subset memoisation alone improved memo use without dramatic overall performance; EBL/DDB created the general no-goods that could be reused frequently.

Memo length becomes a measurable explanation-quality proxy. In Rocket-ext-a, average learned length fell from about 24 goals to 8.5 with EBL. A hidden eight-goal failure can be embedded in choose(24,8) larger contexts. Whole-set learning repeatedly rediscovers it under different irrelevant companions.

When the solver is about to assign condition c, its conflict set begins with {c}. If a candidate support action conflicts with an action already selected for c′, add c′. When all values of c fail, the accumulated set explains why c cannot be supported under the current partial assignment.

The explanation omits permanent domain facts and mutex relations because the planning graph already represents them. It retains the variable names whose current assignments participate. This compressed conflict set is sufficient for backjumping and for regressing failure to the preceding level.

If an epoch at level k−1 fails, its conflict set names predecessor goals. Those goals arose as preconditions of actions selected to support level-k goals. Regression maps each conflicting predecessor back to the higher-level goal whose chosen action activated it, forming a learned memo at level k.

Two regression heuristics control generality. One prefers a higher-level goal whose action contributed the failing precondition and is already in the current conflict. Another can choose a goal that supports deeper DDB. These choices affect efficiency, not soundness or completeness, because the regressed set still entails failure.

EBL is therefore not learning a domain rule in unrestricted language. It is projecting a proof of local extraction failure into Graphplan’s level-indexed proposition vocabulary. The learned object is small enough to match quickly and general enough to prune sibling and later epochs.

In the P₄ example, chronological search backtracks to P₃ because P₃ was assigned last. DDB examines {P₁,P₂,P₄} and returns to P₂, the most recent earlier member. Changing P₃ cannot make A₈ compatible with A₆ or A₉ compatible with A₅, so reconsidering it is provably wasted under the explanation.

At the jump target, the downstream conflict is merged into its own conflict set, with the target variable removed before propagation. If P₂ also exhausts its supports, the combined explanation travels farther back. This is conflict-directed backjumping generalised from static binary CSPs to variables activated dynamically across planning levels.

DDB does not leap to an arbitrary promising point. It follows logical dependency among current assignments. The most recent implicated variable preserves depth-first progress while ensuring the next changed choice can affect at least one clause of the failure explanation.

EBL and DDB are separable in principle. DDB can use an explanation once and discard it; EBL can store generalised memos but retreat chronologically. The experiments show both contribute, with DDB sometimes supplying much of the immediate saving and stored EBL gaining from reuse across branches and epochs.

Soundness is maintained because skipped assignments are outside the explanation: holding them fixed or changing them cannot rescue the known contradiction as long as responsible assignments remain. Completeness remains because the algorithm eventually explores alternatives of every implicated decision.

EBL memos are proposition sets, not complete value-level explanations. A memo M fails any current goal set G at the same level when M⊆G. Reducing M increases the number of supersets it can prune. It can also make subset tests cheaper, though more frequent matches and more generated memos affect total overhead.

Graphplan’s conservative representation controls three classic no-good problems. It learns comparatively few sets, keeps only goal variables from one level and queries only that level’s store. This structural indexing avoids scanning an unrestricted global database. Full EBL retains these advantages while improving memo content.

The empirical relationship is domain-sensitive. Rocket and logistics problems show large drops in average memo length and dramatic speedups. Blocks-world goals are more interdependent, so explanations remain close to the full set and gains are modest. A learning mechanism cannot generalise away genuinely coupled causes.

In Rocket-ext-b, the paper reports that an EBL memo is used to detect failure about 101 times on average, versus 3.2 for a normal memo. This statistic, failures found divided by memos generated, measures utility but can be inflated by longer searches; it should be interpreted beside runtime and backtracks.

DDB-only ablations remove memo checking while retaining intelligent retreat. On several problems, full EBL/DDB still substantially outperforms DDB alone, showing that generalised reuse is not merely overhead. Yet memo time can be a large fraction of runtime, so the balance can reverse on domains with little repetition.

Sticky values remember the last support action assigned to a proposition and try it first when that proposition is revisited. Standard Graphplan’s whole-set memo often prevents revisiting within similar contexts; more general EBL memos and DDB alter that pattern, leaving opportunities to reuse a previously successful value. Sticky values add roughly two- to four-fold improvements on some benchmarks.

“Folding” attempts to preserve value information in memos by recording sticky values associated with goals, seeking some precision without a full value-level no-good database. Its gains are mixed. The technique demonstrates a recurring tension: variable-only learning is broadly reusable, while value detail can guide reconstruction after backtracking.

Dynamic variable ordering selects the next active goal using live domain information, often preferring fewest remaining supports. Forward checking removes support values from unassigned goals when they conflict with a selected action. Emptying a domain gives early failure and an explanation containing the assignments responsible for each removal.

On plain Graphplan, DVO and forward checking reduce backtracks but are not competitive with EBL/DDB. Added on top of EBL/DDB, they provide additional backtrack reductions and occasional two- to four-fold time gains, yet several CPU times worsen because filtering and ordering cost more than the avoided search.

The DCSP interpretation explains why generic minimum-domain ordering can mislead. Difficulty lies not only in assigning present variables but in which predecessor variables a value activates. A two-value goal can create enormous subproblems, while a five-value goal may contain a persistence action with trivial support.

A randomised Graphplan shuffles goal or action choices, stops after a backtrack limit and restarts. It may solve instances that systematic extraction cannot reach within a day. But failure within a cap no longer proves that the current graph depth is barren; it reports only censored search.

One might expect luck to replace learning. The paper argues the opposite: accurate conflict sets keep a short run from spending its hundred backtracks revisiting the same dependency. Stored memos also transfer information across restarts, so diversification retains accumulated structural failure.

On Att-log-a with five restarts, fifty backtracks and a twenty-level limit, EBL/DDB solves 99 per cent of trials with average fourteen-step, eighty-two-action plans. Normal Graphplan solves two per cent, averaging nineteen steps and 103 actions. Increasing normal Graphplan’s limits raises solvability but also runtime and plan length.

The reported random experiments use one hundred trials for most configurations and report solvability, average plan length and runtime. These quantities are conditional in different ways: averages over successful runs should not obscure failures, and longer level limits can make discovery easier while yielding more suboptimal plans.

EBL/DDB thus improves both efficiency and use of bounded incompleteness. Under identical caps, it achieves more solutions and better plans. The result does not mean every learned randomised search is complete; completeness returns only when limits expand so all relevant depths and assignments are eventually explored.

The implementation ran in Franz Allegro Common Lisp 5 on a 500 MHz Pentium III under Linux, and the main tables report CPU minutes and backtracks over logistics, rocket, blocks-world, grid and mystery-style instances. Those conditions matter. Absolute timings are historical machine measurements; the durable evidence is the controlled comparison between configurations in the same implementation.

Full EBL/DDB reaches improvements of up to roughly three orders of magnitude on some extended rocket and logistics problems. The mechanism is visible in the supporting statistics: learned memos become much shorter than full goal sets, are matched repeatedly, and direct the search past assignments absent from the conflict. The result is not merely a constant-factor implementation trick.

Blocks-world supplies the limiting case. Its subgoals interact densely, so the responsible conflict can be nearly as large as the complete goal set. Learning cannot manufacture independence that the domain lacks. Ordinary memoisation already captures much of the true coupling, leaving smaller differences between baseline and explanatory search.

Ablations are essential. DDB without stored memo checking sometimes provides large immediate savings, but full EBL/DDB wins substantially on several tasks because the generalised failures recur. Conversely, dynamic ordering and forward checking can reduce backtracks while taking more CPU time. Their extra scans and conflict bookkeeping have to be paid on every node.

Censored cells must be read carefully. A timeout establishes that one configuration exceeded the stated bound; it does not reveal its eventual runtime. Speedup claims against such cells are lower bounds only when the faster run completed under the same task and measurement rules. Randomised tables add sampling variation and condition plan averages on solved trials.

Solvable fork. Two action pairs are mutex, but cross-pair supports remain compatible. A valid assignment is shown and there is no failure memo. This guards against treating any mutex edge as global impossibility.

Irrelevant middle goal. P₄’s first value conflicts with P₂’s only support and its second conflicts with P₁’s. P₃ participates in neither rejection. The learned memo is {P₁,P₂,P₄}; under forward order DDB jumps from P₄ to P₂ and skips P₃.

Three-way contradiction. X must equal Y, Y must equal Z and X must differ from Z. Every pair of goals has a compatible assignment, while the triple has none. The smallest memo therefore contains all three goals, demonstrating a conflict invisible to proposition-level pairwise consistency.

The “rotate” control changes assignment order without changing constraints. The logical memo stays fixed, while the DDB target changes with recency. This distinguishes declarative learning: what combination is impossible: from procedural control: which implicated choice should be reconsidered next.

First fix the classical planning semantics: grounded actions, no uncertainty, alternating proposition and action layers, persistence actions, and the same definitions of inconsistent effects, interference, competing needs and inconsistent support. A change in preprocessing or grounding can alter the graph before EBL is ever invoked.

Index every memo by proposition level. Test a memo by subset containment against the active goal set at that level. For explanatory search, record a goal-variable conflict set, accumulate the prior assignments responsible for eliminating each candidate support, and regress predecessor failure through the actions that activated it. Static domain absence and static mutex facts are reasons for rejection, not higher-level decisions to blame.

Compare at least four configurations: chronological whole-set memoisation, DDB without persistent memo checking, full EBL/DDB, and EBL/DDB plus the candidate enhancement. Keep value order, graph construction and stopping rules fixed within an ablation. Report wall or CPU time, backtracks, memos generated, failures detected by memos and average memo length.

For restart studies, publish seeds, number of trials, backtrack and depth caps, solved fraction, and whether learned memos persist across restarts. Report plan length and action count conditional on success, explicitly naming the denominator. A configuration that solves two trials is not directly comparable on mean plan quality with one solving ninety-nine.

Modern hardware will not reproduce 2000-era minutes, and a modern language can move the overhead boundary. The stronger target is qualitative and relational: small recurrent explanations should raise memo reuse; DDB should skip irrelevant goals; extra propagation should reduce nodes but help elapsed time only when its marginal saving exceeds its cost.

Review one: formal and causal integrity. Every operational claim was traced to the dynamic-CSP mapping or to the primary search procedure. The review separated proposition mutex from value-level action mutex, whole-set memoisation from explanation-based learning, and a learned no-good from the jump decision it informs. The laboratory was checked against exhaustive assignment and subset enumeration, so a displayed solution, memo or jump can be independently falsified.

The main formal danger was calling the returned set “minimum” when the paper’s procedural conflict analysis establishes a relevant no-good but need not solve a globally minimum-cardinality explanation problem. The companion therefore calls the laboratory output subset-minimal and explicitly marks it as an oracle abstraction. It does not attribute exhaustive subset search to the original planner.

Review two: historical and empirical fidelity. Dates, venue, pagination, machine, implementation language, reported magnitudes and named enhancements were checked against the 34-page JAIR paper. Numerical examples are labelled as reported observations, not fresh measurements. Timeouts and randomised success rates retain their denominators and do not become invented exact speedups.

The principal evidential danger was allowing a dramatic “up to 1,000×” result to stand for all domains. The review retained the blocks-world counter-pattern, distinguished backtrack reductions from CPU improvements, and described memo reuse as a mechanism indicator rather than proof by itself. No later Graphplan, SAT-planning or CSP result is silently credited to the 2000 article.

Blum and Furst’s Graphplan supplied a compact reachability structure and backwards extraction with memoised goal-set failures. Kambhampati shows that extraction is naturally a dynamic CSP: decisions do not merely narrow existing domains; they activate new variables in predecessor layers. This makes classical CSP advances available, but only after their assumptions are translated carefully.

The companion’s central contribution is epistemic as much as algorithmic. A failure record can name the whole situation in which failure was observed, or it can name the decisions that caused it. Only the second kind explains what must change. That distinction unifies smaller memos and non-chronological retreat.

Later planning systems increasingly encode search into SAT, use learned clauses, exploit heuristic estimates or organise hierarchical and temporal constraints. The representations differ, but the recurring question is recognisable: how much of a failed branch can be generalised, and how cheaply can that information redirect future search?

Canon 0087 moves into HTN temporal planning and asks how non-temporal heuristics can guide search in a richer temporal formalism. The transition is instructive. Here the challenge is learning from constraint failure inside a planning graph; next it is importing useful guidance across a representational mismatch.

This three-part progression: record, explain, intervene: is broader than Graphplan. A record can prevent exact repetition. An explanation travels across irrelevant context. An intervention turns the explanation into control. The quality of the system depends not on maximal detail, but on an abstraction precise enough to be sound and small enough to recur.

The dynamic-CSP view prevents a common simplification. Planning is not just static assignment with another vocabulary. Choosing an action changes which predecessor propositions require support. Search therefore manages an evolving boundary of obligation, and a useful explanation must cross that boundary by regression.

The experiments also discipline enthusiasm for stronger inference. Every additional consistency check competes with the search it hopes to remove. The right question is never merely whether a technique prunes. It is whether the distribution of future conflicts lets the technique recover its own cost.

Kambhampati’s lasting lesson is thus methodological: inspect the anatomy of failure, preserve the smallest defensible cause, and let the cause: not the accident of traversal order: decide where computation should resume.