More Web Proxy on the site http://driver.im/

research-article

The Performance Impact of Combining Agent Factorization with Different Learning Algorithms for Multiagent Coordination

Authors:

Andreas Kallinteris,

Stavros Orfanoudakis,

Georgios ChalkiadakisAuthors Info & Claims

SETN '22: Proceedings of the 12th Hellenic Conference on Artificial Intelligence

Article No.: 32, Pages 1 - 10

https://doi.org/10.1145/3549737.3549773

Published: 09 September 2022 Publication History

Abstract

Factorizing a multiagent system refers to partitioning the state-action space to individual agents and defining the interactions between those agents. This so-called agent factorization is of much importance in real-world industrial settings, and is a process that can have significant performance implications. In this work, we explore if the performance impact of agent factorization is different when using different learning algorithms in multiagent coordination settings. We evaluated six different agent factorization instances—or agent definitions—in the warehouse traffic management domain, comparing the performance of (mainly) two learning algorithms suitable for learning coordinated multiagent policies: the Evolutionary Strategies (ES), and a genetic algorithm (CCEA) previously used in this setting. Our results demonstrate that different learning algorithms are affected in different ways by alternative agent definitions. Given this, we can deduce that many important multiagent coordination problems can potentially be solved by an appropriate agent factorization in conjunction with an appropriate choice of a learning algorithm. Moreover, our work shows that ES is an effective learning algorithm for the warehouse traffic management domain; while, interestingly, celebrated policy gradient methods do not fare well in this complex real-world problem setting.

References

[1]

Adrian Agogino and Kagan Tumer. 2004. Efficient Evaluation Functions for Multi-rover Systems. In Genetic and Evolutionary Computation – GECCO 2004, Kalyanmoy Deb (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1–11.

[2]

Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle. 2018. A Large-Scale Experimental Evaluation of High-Performing Multi- and Many-Objective Evolutionary Algorithms. Evolutionary Computation 26, 4 (12 2018), 621–656.

[3]

Eric Budish. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy 119 (2011), 1061 – 1103.

[4]

Thomas Bäck and Hans-Paul Schwefel. 1993. An Overview of Evolutionary Algorithms for Parameter Optimization. Evolutionary Computation 1, 1 (03 1993), 1–23.

[5]

Fang-Yu Chen, Hongwei Wang, Yong Xie, and Chao Qi. 2016. An ACO-based online routing method for multiple order pickers with congestion consideration in warehouse. Journal of Intelligent Manufacturing 27 (2016), 389–408.

Digital Library

[6]

Jen Jen Chung, Damjan Miklic, Lorenzo Sabattini, Kagan Tumer, and Roland Siegwart. 2020. The impact of agent definitions and interactions on multiagent learning for coordination in traffic management domains. Autonomous Agents and Multi-Agent Systems 34 (2020).

[7]

Jen Jen Chung, Carrie Rebhuhn, Connor Yates, Geoffrey A. Hollinger, and Kagan Tumer. 2019. A multiagent framework for learning dynamic traffic management strategies. Autonomous Robots 43(2019).

[8]

Valerio Digani, M. A. Hsieh, Lorenzo Sabattini, and Cristian Secchi. 2019. Coordination of multiple AGVs: a quadratic optimization method. Autonomous Robots 43(2019), 539–555.

Digital Library

[9]

D. V. Dyke. 1994. Chapter 4 : Applications of Distributed Artificial Intelligence in Industry. In Foundations of Distributed Artificial Intelligence. Industrial Technology Institute, Ann Arbor, Michigan, USA.

[10]

Supriyo Ghosh, Sean Laguna, Shiau Hong Lim, L. Wynter, and Hasan A. Poonawala. 2020. A Deep Ensemble Multi-Agent Reinforcement Learning Approach for Air Traffic Control. ArXiv abs/2004.01387(2020).

[11]

Mustafa H. Hassan, Mohammed A. Jubair, Salama A. Mostafa, Hazalila Kamaludin, Aida Mustapha, Mohd F. M. Fudzee, and Hairulnizam Mahdin. 2020. A general framework of genetic multi-agent routing protocol for improving the performance of MANET environment. IAES International Journal of Artificial Intelligence 9 (2020), 310–316.

[12]

John H. Holland. 1975. Adaptation in natural and artificial systems. In An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, Cambridge, MA, USA, 89–120.

[13]

Sašo Karakatič and Vili Podgorelec. 2015. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing 27 (2015), 519–532.

Digital Library

[14]

Erich Kutschinski, Thomas Uthmann, and Daniel Polani. 2003. Learning competitive pricing strategies by multi-agent reinforcement learning. Journal of Economic Dynamics and Control 27, 11 (2003), 2207–2218. Computing in economics and finance.

[15]

Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, P. Abbeel, and Igor Mordatch. 2017. Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. In NIPS 2017. NIPS, Berkeley, England.

[16]

Ioannis Mallidis, Rommert Dekker, and Dimitrios Vlachos. 2012. The impact of greening on supply chain design and cost: a case for a developing region. Journal of Transport Geography 22 (2012), 118–128.

[17]

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. 2015. Human-level control through deep reinforcement learning. Nature 518, 7540 (Feb. 2015), 529–533.

[18]

Sugumar. Murugesan, Zhanhong. Jiang, Michael. James. Risbeck, Jaume. Amores, Chenlu. Zhang, Vish. Ramamurti, Kirk. H. Drees, and Young. M. Lee. 2020. Less is More: Simplified State-Action Space for Deep Reinforcement Learning Based HVAC Control. In Proceedings of the 1st International Workshop on Reinforcement Learning for Energy Management in Buildings & Cities(Virtual Event, Japan). ACM, New York, NY, USA, 20–23.

[19]

Joel Myerson and Leonard Green. 1995. Discounting of Delayed Rewards: Models of Individual Choice. Journal of the experimental analysis of behavior 64 (12 1995), 263–76.

[20]

Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. 2020. Comparative Evaluation of Multi-Agent Deep Reinforcement Learning Algorithms. CoRR abs/2006.07869(2020).

[21]

Mitchell A. Potter and Kenneth A. De Jong. 1994. A cooperative coevolutionary approach to function optimization. In Parallel Problem Solving from Nature — PPSN III, Yuval Davidor, Hans-Paul Schwefel, and Reinhard Männer (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 249–257.

[22]

Mingyao Qi, Xiaowen Li, Xuejun Yan, and Canrong Zhang. 2018. On the evaluation of AGVS-based warehouse operation performance. Simulation Modelling Practice and Theory 87 (2018), 379–394.

[23]

Sarvapali Ramchurn, Perukrishnen Vytelingum, A. Rogers, and N. Jennings. 2012. Putting the ’smarts’ into the smart grid: a grand challenge for artificial intelligence. Commun. ACM 55(2012), 86–97.

Digital Library

[24]

Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. 2017. Evolution Strategies as a Scalable Alternative to Reinforcement Learning. ArXiv abs/1703.03864(2017).

[25]

Raffaello Wurman, Peter R.and D’Andreaand Mick Mountz. 2008. Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses. AI Magazine 29, 1 (Mar. 2008), 9.

[26]

Dayong Ye, Minjie Zhang, and Yun Yang. 2015. A Multi-Agent Framework for Packet Routing in Wireless Sensor Networks. Sensors (Basel, Switzerland) 15 (2015), 10026 – 10047.

Cited By

Cook JTumer KLi XHandl J(2024)Learning Aligned Local Evaluations For Better Credit Assignment In Cooperative CoevolutionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654157(286-294)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654157
Kallinteris AOrfanoudakis SChalkiadakis G(2024)A comprehensive analysis of agent factorization and learning algorithms in multiagent systemsAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09662-938:2Online publication date: 26-Jun-2024
https://doi.org/10.1007/s10458-024-09662-9
Cook JTumer KScheiner TSilva SPaquete L(2023)Leveraging Fitness Critics To Learn Robust TeamworkProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590497(429-437)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590497

Index Terms

The Performance Impact of Combining Agent Factorization with Different Learning Algorithms for Multiagent Coordination
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Cooperation and coordination
      2. Multi-agent systems
    2. Planning and scheduling
      1. Multi-agent planning
      2. Planning for deterministic actions
  2. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Genetic algorithms
      2. Neural networks

Recommendations

A comprehensive analysis of agent factorization and learning algorithms in multiagent systems
Abstract
In multiagent systems, agent factorization denotes the process of segmenting the state-action space of the environment into distinct components, each corresponding to an individual agent, and subsequently determining the interactions among these ...
Multiagent Reinforcement Social Learning toward Coordination in Cooperative Multiagent Systems

Most previous works on coordination in cooperative multiagent systems study the problem of how two (or more) players can coordinate on Pareto-optimal Nash equilibrium(s) through fixed and repeated interactions in the context of cooperative games. ...
The Impact of Agent Definitions and Interactions on Multiagent Learning for Coordination
AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

The state-action space of an individual agent in a multiagent team fundamentally dictates how the individual interacts with the rest of the team. Thus, how an agent is defined in the context of its domain has a significant effect on team performance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SETN '22: Proceedings of the 12th Hellenic Conference on Artificial Intelligence

September 2022

450 pages

ISBN:9781450395977

DOI:10.1145/3549737

Copyright © 2022 ACM.

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: 09 September 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SETN 2022

SETN 2022: 12th Hellenic Conference on Artificial Intelligence

September 7 - 9, 2022

Corfu, Greece

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
62
Total Downloads

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

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cook JTumer KLi XHandl J(2024)Learning Aligned Local Evaluations For Better Credit Assignment In Cooperative CoevolutionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654157(286-294)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654157
Kallinteris AOrfanoudakis SChalkiadakis G(2024)A comprehensive analysis of agent factorization and learning algorithms in multiagent systemsAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09662-938:2Online publication date: 26-Jun-2024
https://doi.org/10.1007/s10458-024-09662-9
Cook JTumer KScheiner TSilva SPaquete L(2023)Leveraging Fitness Critics To Learn Robust TeamworkProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590497(429-437)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590497

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.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents