Dead-End Driven Learning

Daniel Frost, Rina DechterAAAI 1994

Introduction

Constraint Satisfaction Problems (CSPs), such as scheduling, map coloring, and circuit layout, are fundamental challenges in artificial intelligence. These problems are NP-hard, and standard search algorithms like backtracking often suffer from redundant exploration of the same "dead-ends"—combinations of variable assignments that cannot lead to a solution. While "learning" (recording these failures as new constraints or "nogoods") has been proposed to mitigate this, the computational overhead of managing these new constraints often outweighs the pruning benefits. This paper introduces jump-back learning, a method designed to find the optimal balance between pruning power and computational cost.

Methodology: The Jump-Back Approach

The core of the proposed method is built upon Conflict-Directed Backjumping (CBJ). Unlike standard backtracking, CBJ identifies the variable most likely responsible for a conflict and "jumps back" to it, bypassing irrelevant intermediate variables.

The authors evaluate several learning strategies:

  • Graph-based learning: Derived from the constraint graph structure.
  • Value-based learning: Prunes conflict sets by examining specific assigned values.
  • Deep learning: Identifies the minimal set of assignments causing a conflict (accurate but expensive).
  • Jump-back learning: This novel approach utilizes the "jump-back set" already calculated by the CBJ algorithm. Because the solver has already identified these variables to determine the jump-back destination, recording them as a new constraint is computationally "free."

These methods were tested alongside various variable ordering heuristics, including Dynamic Variable Ordering (DVO), which prioritizes the "most constrained" variables.

Experimental Setup

The study utilizes a four-parameter random CSP model defined by:

  • N: Number of variables.
  • K: Domain size.
  • T (Tightness): Fraction of disallowed value pairs.
  • C (Density): Number of constraints.

Experiments specifically targeted the "cross-over point," where problems have a 50% probability of being solvable. This region represents the empirical peak of problem difficulty, where the benefits of learning are most pronounced.

Key Results and Insights

The experiments demonstrate that jump-back learning consistently outperforms other learning variants in CPU time. As problem size ($N$) increases, the efficiency gains become substantial.

Performance comparison (Consistency Checks, Dead Ends, and CPU time) between search with and without learning as the number of variables (N) increases.

Scaling and Synergy

While Dynamic Variable Ordering (DVO) is powerful on its own, its synergy with jump-back learning becomes critical as problems scale beyond 100 variables. On problems with 200 variables, jump-back learning improved average CPU time by a factor of 7.8.

Tackling the "Hard" Instances

The most significant impact of learning is seen in the "tails" of the problem distribution—the exceptionally difficult instances. For the hardest 10% of problems, the speedup factor increased to 15. In one extreme case, a problem requiring 47 CPU hours without learning was solved in under one minute with jump-back learning enabled.

CPU time vs. number of constraints (C), illustrating how learning flattens the complexity peak at the phase transition.

Conclusion

Jump-back learning provides a "free lunch" by leveraging the internal state of the backjumping algorithm to prune the search space effectively. The research highlights that memory overhead is negligible compared to the massive time savings achieved, particularly on the most challenging problem instances. Future work may explore "bounded" learning to limit the size of recorded constraints and further optimize performance for varying domain sizes.

Summary updated

BibTeX
@inproceedings{frost1994dead,
  author = {Daniel Frost and Rina Dechter},
  title = {{Dead-End Driven Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure