Distributed Decoupling of Multiagent Simple Temporal Problems

July 2016

Distributed Decoupling of Multiagent Simple Temporal Problems

Authors:

J. K. Mogali, S. F. Smith, and Z. B. Rubinstein

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 dependencies 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.
@conference{Mogali-2016-120465,
author = {J. K. Mogali And S. F. Smith And Z. B. Rubinstein},
title = {Distributed Decoupling of Multiagent Simple Temporal Problems},
booktitle = {Proceedings of 25th International Joint Conference on Artificial Intelligence (IJCAI '16)},
year = {2016},
month = {July},
pages = {408 - 415},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.