Reasoning about Connectivity Constraints

Bessiere, Christian; Hebrard, Emmanuel; Katsirelos, George; Walsh, Toby

Reasoning about Connectivity Constraints

Christian Bessière, Emmanuel Hebrard, George Katsirelos, Toby Walsh

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Computational Sustainability. Pages 2568-2573.

Abstract

Many problems in computational sustainability involve constraints on connectivity. When designing a new wildlife corridor, we need it to be geographically connected. When planning the harvest of a forest, we need new areas to harvest to be connected to areas that have already been harvested so we can access them easily. And when town planning, we need to connect new homes to the existing utility infrastructure. To reason about connectivity, we propose a new family of global connectivity constraints. We identify when these constraints can be propagated tractably, and give some efficient, typically linear time propagators for when this is the case. We report results on several benchmark problems which demonstrate the efficiency of our propagation algorithms and the promise offered by reasoning globally about connectivity.

Christian Bessiere, Emmanuel Hebrard, George Katsirelos, and Toby Walsh. 2015. Reasoning about Connectivity Constraints. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 2568–2573. https://ijcai.org/proceedings/2015/364

@inproceedings{ijcai2015p364,
  title     = {Reasoning about Connectivity Constraints},
  author    = {Bessiere, Christian and Hebrard, Emmanuel and Katsirelos, George and Walsh, Toby},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {2568--2573},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Computational Sustainability},
  url       = {https://ijcai.org/proceedings/2015/364},
}

TY  - CPAPER
TI  - Reasoning about Connectivity Constraints
AU  - Bessiere, Christian
AU  - Hebrard, Emmanuel
AU  - Katsirelos, George
AU  - Walsh, Toby
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 2568
EP  - 2573
UR  - https://ijcai.org/proceedings/2015/364
ER  -