Extending Dynamic Backtracking to Solve Weighted Conditional CSPs
Abstract
Many planning and design problems can be characterized as optimal search over a constrained network of conditional choices with preferences. To draw upon the advanced methods of constraint satisfaction to solve these types of problems, many dynamic and flexible CSP variants have been proposed. One such variant is the Weighted Conditional CSP (WCCSP). So far, however, little work has been done to extend the full suite of CSP search algorithms to solve these CSP variants. In this paper, we extend Dynamic Backtracking and similar backjumpingbased CSP search algorithms to solve WCCSPs by utilizing activity constraints and soft constraints in order to quickly prune infeasible and suboptimal regions of the search space. We provide experimental results on randomly generated WCCSP instances to prove these claims.
Cite
Text
Effinger and Williams. "Extending Dynamic Backtracking to Solve Weighted Conditional CSPs." AAAI Conference on Artificial Intelligence, 2006.Markdown
[Effinger and Williams. "Extending Dynamic Backtracking to Solve Weighted Conditional CSPs." AAAI Conference on Artificial Intelligence, 2006.](https://mlanthology.org/aaai/2006/effinger2006aaai-extending/)BibTeX
@inproceedings{effinger2006aaai-extending,
title = {{Extending Dynamic Backtracking to Solve Weighted Conditional CSPs}},
author = {Effinger, Robert T. and Williams, Brian Charles},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2006},
pages = {28-35},
url = {https://mlanthology.org/aaai/2006/effinger2006aaai-extending/}
}