Distributed Decoupling of Multiagent Simple Temporal Problems

Mogali, Jayanth Krishna; Smith, Stephen F.; Rubinstein, Zachary B.

Distributed Decoupling of Multiagent Simple Temporal Problems

Jayanth Krishna Mogali, Stephen F. Smith, Zachary B. Rubinstein

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 408-414.

Abstract

We propose a new distributed algorithm for decoupling the Multiagent Simple Temporal Network (MaSTN) problem. The agents cooperatively decouple the MaSTN while simultaneously optimizing a sum of concave objectives local to each agent. Several schedule flexibility measures are applicable in this framework. We pose the MaSTN decoupling problem as a distributed convex optimization problem subject to constraints having a block angular structure; we adapt existing variants of Alternating Direction Method of Multiplier (ADMM) type methods to perform decoupling optimally. The resulting algorithm is an iterative procedure that is guaranteed to converge. Communication only takes place between agents with temporal inter-dependences and the information exchanged between them is carried out in a privacy preserving manner. We present experimental results for the proposed method on problems of varying sizes, and demonstrate its effectiveness in terms of solving quality and computational cost.

Jayanth Krishna Mogali, Stephen F. Smith, and Zachary B. Rubinstein. 2016. Distributed Decoupling of Multiagent Simple Temporal Problems. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 408–414. https://ijcai.org/proceedings/2016/65

@inproceedings{ijcai2016p65,
  title     = {Distributed Decoupling of Multiagent Simple Temporal Problems},
  author    = {Mogali, Jayanth Krishna and Smith, Stephen F. and Rubinstein, Zachary B.},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {408--414},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/65},
}

TY  - CPAPER
TI  - Distributed Decoupling of Multiagent Simple Temporal Problems
AU  - Mogali, Jayanth Krishna
AU  - Smith, Stephen F.
AU  - Rubinstein, Zachary B.
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 408
EP  - 414
UR  - https://ijcai.org/proceedings/2016/65
ER  -