Article

Agent interaction in distributed POMDPs and its implications on complexity

Authors:

Jiaying Shen,

Raphen Becker,

Victor LesserAuthors Info & Claims

AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems

Pages 529 - 536

https://doi.org/10.1145/1160633.1160730

Published: 08 May 2006 Publication History

Get Access

Abstract

The ability to coordinate effectively is critical for agents to accomplish their goals in a multi-agent system. A number of researchers have modeled the coordination problem for multi-agent systems using decision theory. The most general models have proven to be extremely complex to solve optimally (NEXP-complete). Some of the more restricted models have been much more tractable, though still difficult (NP-complete). What is missing is an understanding about why some models are much easier than others. This work fills this gap by providing a condition that distinguishes between problems in NP and those strictly harder than NP. This condition relates to the quantity of information each agent has about the others, and whether this information can be represented in a succinct way. We show that the class of problems that satisfy this condition is NP-complete. We illustrate this idea with two interaction protocols that satisfy the condition. For those problems that do not satisfy this condition we demonstrate how our theoretical results can be used to generate an NP approximation of the original problem.

References

[1]

R. Becker, V. Lesser, and S. Zilberstein. Analyzing myopic approaches for multi-agent communication. In Proceedings of the 2005 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pages 550--557, Compiegne, France, September 2005. IEEE Computer Society.

Digital Library

Google Scholar

[2]

R. Becker, S. Zilberstein, and V. Lesser. Decentralized Markov decision processes with structured transitions. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multi Agent Systems, volume 1, pages 302--309, New York City, New York, July 2004. ACM Press.

Digital Library

Google Scholar

[3]

R. Becker, S. Zilberstein, V. Lesser, and C. V. Goldman. Solving transition independent decentralized MDPs. Journal of Artificial Intelligence Research, 22:423--455, 2004.

Digital Library

Google Scholar

[4]

D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein. The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research, 27(4):819--840, November 2002.

Digital Library

Google Scholar

[5]

M. Ghavamzadeh and S. Mahadevan. Learning to communicate and act in cooperative multiagent systems using hierarchical reinforcement learning. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multi Agent Systems, pages 1114--1121, New York, July 2004. ACM Press.

Digital Library

Google Scholar

[6]

C. V. Goldman and S. Zilberstein. Optimizing information exchange in cooperative multi-agent systems. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multi Agent Systems, pages 137--144, Melbourne, Australia, July 2003. ACM Press.

Digital Library

Google Scholar

[7]

C. V. Goldman and S. Zilberstein. Decentralized control of cooperative systems: Categorization and complexity analysis. Journal of Artificial Intelligence Research, 22:143--174, 2004.

Crossref

Google Scholar

[8]

H. Li, E. H. Durfee, and K. G. Shin. Multiagent planning for agents with internal execution resource constraints. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multi Agent Systems, pages 560--567, New York, NY, USA, 2003. ACM Press.

Digital Library

Google Scholar

[9]

C. H. Papadimitriou and J. Tsitsiklis. On the complexity of designing distributed protocols. Information and Control, 53:211--218, 1982.

Crossref

Google Scholar

[10]

C. H. Papadimitriou and J. Tsitsiklis. Intractable problems in control theory. SIAM Journal on Control and Optimization, 24(4):639--654, 1986.

Digital Library

Google Scholar

[11]

L. Peshkin, K.-E. Kim, N. Meuleau, and L. P. Kaelbling. Learning to cooperate via policy search. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, pages 489--496, San Francisco, CA, 2000. Morgan Kaufmann.

Digital Library

Google Scholar

[12]

D. V. Pynadath and M. Tambe. The communicative multiagent team decision problem: Analyzing teamwork theories and models. Journal of Artificial Intelligence Research, 16:389--423, 2002.

Crossref

Google Scholar

[13]

J. Shen, V. Lesser, and N. Carver. Minimizing communication cost in a distributed Bayesian network using a decentralized MDP. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multi Agent Systems, pages 678--685, Melbourne, Australia, July 2003. ACM Press.

Digital Library

Google Scholar

[14]

P. Xuan and V. Lesser. Multi-agent policies: From centralized ones to decentralized ones. In Proceedings of the First International Joint Conference on Autonomous Agents and Multi Agent Systems, pages 1098--1105. ACM Press, 2002.

Digital Library

Google Scholar

Cited By

View all

Le Tian Jian Luo Zhili Huang (2013)Communication based on Interactive Dynamic Influence Diagrams in cooperative multi-agent systems2013 8th International Conference on Computer Science & Education10.1109/ICCSE.2013.6553883(56-61)Online publication date: Apr-2013
https://doi.org/10.1109/ICCSE.2013.6553883
Beynier ACharpillet FSzer DMouaddib A(2013)DEC‐MDP/POMDPMarkov Decision Processes in Artificial Intelligence10.1002/9781118557426.ch9(277-318)Online publication date: 7-Mar-2013
https://doi.org/10.1002/9781118557426.ch9
Witwicki SDurfee ESonenberg LStone PTumer KYolum P(2011)Towards a unifying characterization for quantifying weak coupling in dec-POMDPsThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/2030470.2030475(29-36)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.5555/2030470.2030475
Show More Cited By

Recommendations

The Landscape of Communication Complexity Classes

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$P and $${\mathsf{PSPACE}}$$PSPACE, short of proving lower bounds ...
Query Complexity in Errorless Hardness Amplification

An errorless circuit for a Boolean function is one that outputs the correct answer or "don't know" on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if f has no size s errorless circuit that ...
On the complexity of fixed parameter problems
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

The authors address the question of why some fixed-parameter problem families solvable in polynomial time seem to be harder than others with respect to fixed-parameter tractability: whether there is a constant alpha such that all problems in the family ...

Comments

Information & Contributors

Information

Published In

AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems

May 2006

1631 pages

ISBN:1595933034

DOI:10.1145/1160633

General Chairs:
Hideyuki Nakashima
Future University - Hakodate, Japan
,
Michael Wellman
University of Michigan
,
Program Chairs:
Gerhard Weiss
Technical University Munich, Germany
,
Peter Stone
The University of Texas at Austin

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

AAMAS06

Sponsor:

IFMAS
SIGAI
ATAL

AAMAS06: AAMAS '06 - 5th International Joint Conference on Autonomous Agents and Multi-agent Systems 2006

May 8 - 12, 2006

Japan, Hakodate

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
282
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Le Tian Jian Luo Zhili Huang (2013)Communication based on Interactive Dynamic Influence Diagrams in cooperative multi-agent systems2013 8th International Conference on Computer Science & Education10.1109/ICCSE.2013.6553883(56-61)Online publication date: Apr-2013
https://doi.org/10.1109/ICCSE.2013.6553883
Beynier ACharpillet FSzer DMouaddib A(2013)DEC‐MDP/POMDPMarkov Decision Processes in Artificial Intelligence10.1002/9781118557426.ch9(277-318)Online publication date: 7-Mar-2013
https://doi.org/10.1002/9781118557426.ch9
Witwicki SDurfee ESonenberg LStone PTumer KYolum P(2011)Towards a unifying characterization for quantifying weak coupling in dec-POMDPsThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 110.5555/2030470.2030475(29-36)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.5555/2030470.2030475
Tasaki MYabu YIwanari YYokoo MMarecki JVarakantham PTambe M(2010)Introducing communication in Dis-POMDPs with locality of interactionWeb Intelligence and Agent Systems10.5555/1839537.18395428:3(303-311)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.5555/1839537.1839542
Beynier AMouaddib A(2010)A Rich Communication Model in Opportunistic Decentralized Decision MakingProceedings of the 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 0210.1109/WI-IAT.2010.41(133-140)Online publication date: 31-Aug-2010
https://dl.acm.org/doi/10.1109/WI-IAT.2010.41
Rosenfeld AKraus SOrtiz C(2009)Measuring the expected gain of communicating constraint informationMultiagent and Grid Systems10.5555/1735317.17353225:4(427-449)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.5555/1735317.1735322
Iwanari YYabu YTasaki MYokoo M(2009)Network Distributed POMDP with CommunicationNew Frontiers in Artificial Intelligence10.1007/978-3-642-00609-8_4(26-38)Online publication date: 6-Apr-2009
https://dl.acm.org/doi/10.1007/978-3-642-00609-8_4
Gabel TRiedmiller M(2008)Reinforcement learning for DEC-MDPs with changing action sets and partially ordered dependenciesProceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 310.5555/1402821.1402865(1333-1336)Online publication date: 12-May-2008
https://dl.acm.org/doi/10.5555/1402821.1402865
Tasaki MYabu YIwanari YYokoo MTambe MMarecki JVarakantham P(2008)Introducing Communication in Dis-POMDPs with Locality of InteractionProceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Volume 0210.1109/WIIAT.2008.316(169-175)Online publication date: 9-Dec-2008
https://dl.acm.org/doi/10.1109/WIIAT.2008.316
Seuken SZilberstein S(2008)Formal models and algorithms for decentralized decision making under uncertaintyAutonomous Agents and Multi-Agent Systems10.1007/s10458-007-9026-517:2(190-250)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1007/s10458-007-9026-5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Recommendations

The Landscape of Communication Complexity Classes

Query Complexity in Errorless Hardness Amplification

On the complexity of fixed parameter problems

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations