Identifying Conflicts in Overconstrained Temporal Problems
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 205-210.
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.
@inproceedings{ijcai2005p153,
title = {Identifying Conflicts in Overconstrained Temporal Problems},
author = {Liffiton, Mark H. and Moffitt, Michael D. and Pollack, Martha E. and Sakallah, Karem A.},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {205--210},
year = {2005},
url = {https://ijcai.org/proceedings/2005/153},
}
TY - CPAPER TI - Identifying Conflicts in Overconstrained Temporal Problems AU - Liffiton, Mark H. AU - Moffitt, Michael D. AU - Pollack, Martha E. AU - Sakallah, Karem A. T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 205 EP - 210 UR - https://ijcai.org/proceedings/2005/153 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
