Extending Dynamic Backtracking to Solve Weighted Conditional CSPs

Robert T. Effinger, Brian Charles WilliamsAAAI 2006

Overview

This research introduces CondDB-B+B, an innovative algorithm designed to solve Weighted Conditional Constraint Satisfaction Problems (WCCSPs). By extending Dynamic Backtracking (DB) to handle both conditional variables and soft constraints, the algorithm significantly improves search efficiency in complex domains like product configuration and autonomous planning. The core innovation lies in treating suboptimality as a "conflict," allowing the solver to prune large, inefficient branches of the search space.

What Problem Does This Paper Address?

Classical Constraint Satisfaction Problems (CSPs) focus on finding assignments that meet all hard constraints. However, real-world applications often require more nuance:

  1. Conditional Variables: Some variables only exist based on previous choices. For instance, in a car configurator, selecting a "Luxury Package" might activate a "Sunroof" variable, whereas a "Standard Package" would not.
  2. Soft Constraints (Preferences): Choices often carry associated costs or weights. The goal is not just to find any valid solution, but the optimal one with the lowest total cost.
A hierarchical dependency graph illustrating conditional variables in a car configuration problem.

Combining these features into a Weighted Conditional CSP (WCCSP) is computationally intensive. Standard search algorithms frequently suffer from "thrashing"—repeatedly exploring failed or suboptimal sub-trees because they lack a mechanism to remember why a specific path was rejected.

The CondDB-B+B Algorithm

To address these challenges, the authors developed CondDB-B+B, which augments Dynamic Backtracking with four critical extensions:

  • Total Variable Ordering: The algorithm utilizes a dependency graph of activity constraints to ensure variables are instantiated in a logical, hierarchical order.
  • Modified Backjumping: When a conflict (dead-end) is reached, the solver analyzes the "nogood"—the specific set of assignments causing the failure—and jumps back to the source of the problem, skipping irrelevant intermediate steps.
  • Recursive Deactivation: If a value change deactivates a branch of variables, the algorithm recursively unassigns them and clears outdated conflict data to maintain a clean search state.
  • Branch-and-Bound with Suboptimal Nogoods: This is the algorithm's most significant advancement. When a partial solution's cost exceeds the current best solution (the incumbent), the algorithm treats this as a logical conflict. It generates a "minimal suboptimal nogood" to identify the expensive choices and uses backjumping to avoid any other solutions containing that same costly combination.

Experimental Evaluation

The authors evaluated CondDB-B+B using randomly generated WCCSP instances tuned to the "phase transition" region, where problems are most difficult to solve. They tested varying numbers of variables (up to 20) and different depths of nested activity constraints.

Key Results

The experiments demonstrated that CondDB-B+B offers a substantial performance advantage over the standard branch-and-bound approach (CondBT-B+B):

  • Search Efficiency: As shown in the performance data, CondDB-B+B explores significantly fewer nodes than the baseline. For problems with 20 variables, the gap in search effort is dramatic.
  • Scalability: The performance advantage widens as the complexity of the conditional dependencies (the "activity tree" depth) increases, proving the algorithm's robustness for complex hierarchies.
  • Heuristic Integration: Adding simple search heuristics (labeled "+h") further enhanced performance, indicating that CondDB-B+B serves as a strong foundation for even more advanced optimization strategies.
Comparison of search tree nodes explored by CondDB-B+B versus the baseline as the number of variables increases.

Conclusion and Future Directions

CondDB-B+B successfully bridges the gap between conditional logic and weighted optimization. By formalizing "excessive cost" as a conflict, it brings the pruning power of intelligent backtracking to optimization problems.

Future work may involve incorporating "local consistency" techniques to pre-filter impossible values or exploring memory-intensive A*-style searches to further accelerate the discovery of optimal solutions. Additionally, refining the lower bounds used in the branch-and-bound process could lead to even tighter pruning in deeply nested dependency structures.

Summary updated

BibTeX
@inproceedings{effinger2006extending,
  author = {Robert T. Effinger and Brian Charles Williams},
  title = {{Extending Dynamic Backtracking to Solve Weighted Conditional CSPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure