Randomized coordination search for scalable multiagent planning

N. Kemal Ure; Jonathan P. How; John Vian

Randomized coordination search for scalable multiagent planning

N. Kemal Ure, Jonathan P. How, John Vian

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

Multiagent Markov Decision Processes (MMDP5) are difficult problems to solve due to the exponential increase in the size of the planning space in the number of agents. One of the most successful approaches for solving MMDPs utilizes coordination graphs (CG5), which encode the decouplings between the agents to reduce the dimension of the value function, which in turn reduces the computational complexity. However, it is typically assumed that the structure of the CG is available a priori, which is a limiting assumption for many practical scenarios. This work presents a randomized planning scheme based on the Bayesian optimization algorithm to probabilistically search over the space of CGs to discover CG structures that yield high return policies. The results demonstrate that the proposed method is superior in terms of convergence speed and accumulated reward.

Original language	English
Title of host publication	AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems
Editors	Rafael H. Bordini, Pinar Yolum, Edith Elkind, Gerhard Weiss
Publisher	International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages	1793-1794
Number of pages	2
ISBN (Electronic)	9781450337717
Publication status	Published - 2015
Externally published	Yes
Event	14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015 - Istanbul, Turkey Duration: 4 May 2015 → 8 May 2015

Publication series

Name	Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume	3
ISSN (Print)	1548-8403
ISSN (Electronic)	1558-2914

Conference

Conference	14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
Country/Territory	Turkey
City	Istanbul
Period	4/05/15 → 8/05/15

Bibliographical note

Publisher Copyright:
Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

Keywords

Multi agent systems
Planning under uncertainty

Cite this

Ure, N. K., How, J. P., & Vian, J. (2015). Randomized coordination search for scalable multiagent planning. In R. H. Bordini, P. Yolum, E. Elkind, & G. Weiss (Eds.), AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (pp. 1793-1794). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 3). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Ure, N. Kemal ; How, Jonathan P. ; Vian, John. / Randomized coordination search for scalable multiagent planning. AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. editor / Rafael H. Bordini ; Pinar Yolum ; Edith Elkind ; Gerhard Weiss. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2015. pp. 1793-1794 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

@inproceedings{35e1de84ae7341669a588cf6d55f3c7b,

title = "Randomized coordination search for scalable multiagent planning",

abstract = "Multiagent Markov Decision Processes (MMDP5) are difficult problems to solve due to the exponential increase in the size of the planning space in the number of agents. One of the most successful approaches for solving MMDPs utilizes coordination graphs (CG5), which encode the decouplings between the agents to reduce the dimension of the value function, which in turn reduces the computational complexity. However, it is typically assumed that the structure of the CG is available a priori, which is a limiting assumption for many practical scenarios. This work presents a randomized planning scheme based on the Bayesian optimization algorithm to probabilistically search over the space of CGs to discover CG structures that yield high return policies. The results demonstrate that the proposed method is superior in terms of convergence speed and accumulated reward.",

keywords = "Multi agent systems, Planning under uncertainty",

author = "Ure, {N. Kemal} and How, {Jonathan P.} and John Vian",

note = "Publisher Copyright: Copyright {\textcopyright} 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.; 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015 ; Conference date: 04-05-2015 Through 08-05-2015",

year = "2015",

language = "English",

series = "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS",

publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

pages = "1793--1794",

editor = "Bordini, {Rafael H.} and Pinar Yolum and Edith Elkind and Gerhard Weiss",

booktitle = "AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems",

}

Ure, NK, How, JP & Vian, J 2015, Randomized coordination search for scalable multiagent planning. in RH Bordini, P Yolum, E Elkind & G Weiss (eds), AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, vol. 3, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 1793-1794, 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, 4/05/15.

Randomized coordination search for scalable multiagent planning. / Ure, N. Kemal; How, Jonathan P.; Vian, John.
AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. ed. / Rafael H. Bordini; Pinar Yolum; Edith Elkind; Gerhard Weiss. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2015. p. 1793-1794 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 3).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Randomized coordination search for scalable multiagent planning

AU - Ure, N. Kemal

AU - How, Jonathan P.

AU - Vian, John

PY - 2015

Y1 - 2015

N2 - Multiagent Markov Decision Processes (MMDP5) are difficult problems to solve due to the exponential increase in the size of the planning space in the number of agents. One of the most successful approaches for solving MMDPs utilizes coordination graphs (CG5), which encode the decouplings between the agents to reduce the dimension of the value function, which in turn reduces the computational complexity. However, it is typically assumed that the structure of the CG is available a priori, which is a limiting assumption for many practical scenarios. This work presents a randomized planning scheme based on the Bayesian optimization algorithm to probabilistically search over the space of CGs to discover CG structures that yield high return policies. The results demonstrate that the proposed method is superior in terms of convergence speed and accumulated reward.

AB - Multiagent Markov Decision Processes (MMDP5) are difficult problems to solve due to the exponential increase in the size of the planning space in the number of agents. One of the most successful approaches for solving MMDPs utilizes coordination graphs (CG5), which encode the decouplings between the agents to reduce the dimension of the value function, which in turn reduces the computational complexity. However, it is typically assumed that the structure of the CG is available a priori, which is a limiting assumption for many practical scenarios. This work presents a randomized planning scheme based on the Bayesian optimization algorithm to probabilistically search over the space of CGs to discover CG structures that yield high return policies. The results demonstrate that the proposed method is superior in terms of convergence speed and accumulated reward.

KW - Multi agent systems

KW - Planning under uncertainty

UR - http://www.scopus.com/inward/record.url?scp=84944705492&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84944705492

T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

SP - 1793

EP - 1794

BT - AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems

A2 - Bordini, Rafael H.

A2 - Yolum, Pinar

A2 - Elkind, Edith

A2 - Weiss, Gerhard

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

T2 - 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015

Y2 - 4 May 2015 through 8 May 2015

ER -

Ure NK, How JP, Vian J. Randomized coordination search for scalable multiagent planning. In Bordini RH, Yolum P, Elkind E, Weiss G, editors, AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2015. p. 1793-1794. (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

Randomized coordination search for scalable multiagent planning

Abstract

Publication series

Conference

Bibliographical note

Keywords

Other files and links

Fingerprint

Cite this