Identifying Conflicts in Overconstrained Temporal Problems
Abstract
We describe a strong connection between maximally satisfiable and minimally unsatisfiable subsets of constraint systems. Using this relationship, we develop a two-phase algorithm, employing powerful constraint satisfaction techniques, for the identification of conflicting sets of constraints in infeasible constraint systems. We apply this technique to overconstrained instances of the Disjunctive Temporal Problem (DTP), an expressive form of temporal constraint satisfaction problems. Using randomly-generated benchmarks, we provide experimental results that demonstrate how the algorithm scales with problem size and constraint density. 1
Cite
Text
Liffiton et al. "Identifying Conflicts in Overconstrained Temporal Problems." International Joint Conference on Artificial Intelligence, 2005.Markdown
[Liffiton et al. "Identifying Conflicts in Overconstrained Temporal Problems." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/liffiton2005ijcai-identifying/)BibTeX
@inproceedings{liffiton2005ijcai-identifying,
title = {{Identifying Conflicts in Overconstrained Temporal Problems}},
author = {Liffiton, Mark H. and Moffitt, Michael D. and Pollack, Martha E. and Sakallah, Karem A.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2005},
pages = {205-211},
url = {https://mlanthology.org/ijcai/2005/liffiton2005ijcai-identifying/}
}