Back to Backtracking: Controlling the ATMS

Johan de Kleer, Brian C. WilliamsAAAI 1986

Abstract

This seminal 1986 research introduces a hybrid reasoning strategy that merges the exhaustive, parallel power of Assumption-Based Truth Maintenance Systems (ATMS) with the focused, depth-first efficiency of Dependency-Directed Backtracking (DDB). The resulting "best of both worlds" solver avoids the unfocused overhead of ATMS while maintaining a global memory of contradictions to prevent redundant work.

The Conflict in Truth Maintenance

In the mid-1980s, AI researchers faced a dilemma in managing logical consistency within problem solvers. Two primary schools of thought existed:

  1. Conventional DDB (Dependency-Directed Backtracking): This approach focuses on finding one solution at a time via depth-first search. While focused, it is often redundant; it might rediscover the same contradiction in different branches of the search tree because it lacks a global "memory" of why certain combinations of choices failed.
  2. ATMS (Assumption-Based TMS): Introduced by Johan de Kleer, the ATMS was revolutionary because it explored all possible solutions simultaneously (effectively breadth-first). However, this "all-at-once" approach is often a hindrance. If a problem has millions of potential solutions but you only need one, the ATMS does a massive amount of unnecessary work. Furthermore, ATMS-based systems are notoriously difficult to debug because they don't have a single "current state" for a developer to inspect.

The authors tackle the challenge of creating a control strategy that is as focused as backtracking but as efficient and "knowledgeable" as an ATMS.

A Hybrid Control Strategy

The authors propose a hybrid algorithm called Assumption-based DDB. The key technical innovations include:

  • Control Disjunctions: The user defines sets of mutually exclusive choices (e.g., "Queen 1 must be in Column 1, 2, or 3"). The system maintains a "current environment" consisting of exactly one choice from each active disjunction.
  • The Hybrid Scheduler: The system uses DDB to provide a "coarse focus" (picking a specific path to explore), while the ATMS provides "fine-grained discrimination." The ATMS identifies the minimal set of assumptions (a nogood) that lead to a contradiction.
  • Hyperresolution Rules: The system uses a specific logical rule to infer new contradictions. If every possible choice in a disjunction leads to a known contradiction when combined with Assumption A, the system can immediately conclude that Assumption A itself is a "nogood" without ever having to explore its consequences further.
  • Justification-Based Consumers: Inferences (rules) are only executed if their antecedents are consistent with the current backtracking state, preventing the "shotgun" execution style of a pure ATMS.

Evaluation and Illustrative Examples

The paper evaluates the logic using classic combinatorial puzzles. The $n$-Queens Problem is specifically used to illustrate how DDB can avoid regions of the search space that a pure ATMS would waste time exploring.

The n-Queens problem used to illustrate search space pruning.

Additionally, abstract Lattice Search Examples visualize how the hybrid approach prunes the search tree. By recording global contradictions, the system can skip entire branches that share a common failure point.

Lattice search visualization showing how the hybrid approach identifies nogoods and focuses search.

Key Insights and Results

  • The Intersection Advantage: The core "aha moment" is that the hybrid approach only explores the intersection of the environments that ATMS and DDB would visit individually. It is mathematically guaranteed to perform at least as well as (and usually much better than) either method alone.
  • Global Contradiction Memory: Unlike standard backtracking, which might "forget" a conflict once it moves to a different branch, the ATMS backend records every "nogood" permanently. This ensures that the solver never makes the same mistake twice, regardless of where it is in the search tree.
  • Efficiency Gains: The authors demonstrate that the hybrid system significantly reduces the number of "consumers" (rules) executed and "contexts" (states) examined. The paper argues that the most accurate metric for solver performance is the number of rule invocations, which the hybrid approach minimizes more effectively than pure ATMS or pure DDB.

Limitations and Future Work

While the hybrid reduces rule executions, maintaining the ATMS "nogood" database and performing hyperresolution carries its own computational overhead. In very simple problems, this overhead might outweigh the savings. Furthermore, the initial version of the algorithm assumes that the sets of choices (disjunctions) are fixed at the start; handling dynamic choices that emerge during problem-solving is significantly more complex to implement.

Summary updated

BibTeX
@inproceedings{kleer1986back,
  author = {Johan de Kleer and Brian C. Williams},
  title = {{Back to Backtracking: Controlling the ATMS}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure