A Divide-and-Conquer Approach for Solving Interval Algebra Networks

Li, Jason Jingshi; Huang, Jinbo; Renz, Jochen

A Divide-and-Conquer Approach for Solving Interval Algebra Networks

Jason Jingshi Li, Jinbo Huang, Jochen Renz

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 572-576.

Abstract

Deciding consistency of constraint networks is a fundamental problem in qualitative spatial and temporal reasoning. In this paper we introduce a divide-and-conquer method that recursively partitions a given problem into smaller sub-problems in deciding consistency. We identify a key theoretical property of a qualitative calculus that ensures the soundness and completeness of this method, and show that it is satisfied by the Interval Algebra (IA) and the Point Algebra (PA). We develop a new encoding scheme for IA networks based on a combination of our divide-and-conquer method with an existing encoding of IA networks into SAT. We empirically show that our new encoding scheme scales to much larger problems and exhibits a consistent and significant improvement in efficiency over state-of-the-art solvers on the most difficult instances.Jason Jingshi Li, Jinbo Huang, Jochen Renz

Jason Jingshi Li, Jinbo Huang, and Jochen Renz. 2009. A Divide-and-Conquer Approach for Solving Interval Algebra Networks. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09. IJCAI, 572–576. https://ijcai.org/proceedings/2009/101

@inproceedings{ijcai2009p101,
  title     = {A Divide-and-Conquer Approach for Solving Interval Algebra Networks},
  author    = {Li, Jason Jingshi and Huang, Jinbo and Renz, Jochen},
  booktitle = {Proceedings of the Twenty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-09}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Hiroaki Kitano},
  pages     = {572--576},
  year      = {2009},
  url       = {https://ijcai.org/proceedings/2009/101},
}

TY  - CPAPER
TI  - A Divide-and-Conquer Approach for Solving Interval Algebra Networks
AU  - Li, Jason Jingshi
AU  - Huang, Jinbo
AU  - Renz, Jochen
T2  - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2009
SP  - 572
EP  - 576
UR  - https://ijcai.org/proceedings/2009/101
ER  -