Transition Constraints: A Study on the Computational Complexity of Qualitative Change

Westphal, Matthias; Hué, Julien; Wölfl, Stefan; Nebel, Bernhard

Transition Constraints: A Study on the Computational Complexity of Qualitative Change

Matthias Westphal, Julien Hué, Stefan Wölfl, Bernhard Nebel

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 1169-1174.

Abstract

Many formalisms discussed in the literature on qualitative spatial reasoning are designed for expressing static spatial constraints only. However, dynamic situations arise in virtually all applications of these formalisms, which makes it necessary to study variants and extensions involving change. This paper presents a study on the computational complexity of qualitative change. More precisely, we discuss the reasoning task of finding a solution to a temporal sequence of static reasoning problems where this sequence is subject to additional transition constraints. Our focus is primarily on smoothness and continuity constraints: we show how such transitions can be defined as relations and expressed within qualitative constraint formalisms. Our results demonstrate that for point-based constraint formalisms the interesting fragments become NP-complete in the presence of continuity constraints, even if the satisfiability problem of its static descriptions is tractable.

Matthias Westphal, Julien Hué, Stefan Wölfl, and Bernhard Nebel. 2013. Transition Constraints: A Study on the Computational Complexity of Qualitative Change. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 1169–1174. https://ijcai.org/proceedings/2013/176

@inproceedings{ijcai2013p176,
  title     = {Transition Constraints: A Study on the Computational Complexity of Qualitative Change},
  author    = {Westphal, Matthias and Hué, Julien and Wölfl, Stefan and Nebel, Bernhard},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {1169--1174},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/176},
}

TY  - CPAPER
TI  - Transition Constraints: A Study on the Computational Complexity of Qualitative Change
AU  - Westphal, Matthias
AU  - Hué, Julien
AU  - Wölfl, Stefan
AU  - Nebel, Bernhard
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 1169
EP  - 1174
UR  - https://ijcai.org/proceedings/2013/176
ER  -