A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation

2025-02-14 · Redha Taguelmimt, Samir Aknine, Djamila Boukredera, Narayan Changder, Tuomas Sandholm

Coalition structure generation (CSG), i.e. the problem of optimally partitioning a set of agents into coalitions to maximize social welfare, is a fundamental computational problem in multiagent systems. This problem is important for many applications where small run times are necessary, including transportation and disaster response. In this paper, we develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures. Our algorithm utilizes a variety of heuristics and strategies to perform the search and guide it. It is an anytime algorithm that can handle large problems with hundreds and thousands of agents. We show empirically on nine standard value distributions, including disaster response and electric vehicle allocation benchmarks, that our algorithm enables a rapid finding of high-quality solutions and compares favorably with other state-of-the-art methods.

📄 PDF Abstract BibTeX arXiv:2502.10226

Code (0)

등록된 구현이 없습니다.

Tasks

Disaster Response

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Multiagent Soft Q-Learning

2018-04-25 · Ermo Wei, Drew Wicke, David Freelan, Sean Luke

Policy gradient methods are often applied to reinforcement learning in continuous multiagent games. These methods perform local search in the joint-action space, and as we show, they are susceptable to a game-theoretic p…

Policy Gradient Methods Q-Learning reinforcement-learning Reinforcement Learning+1

Solving Multiagent Path Finding on Highly Centralized Networks

2024-12-12 · Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos 외

The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without …

Scaling Up Multiagent Reinforcement Learning for Robotic Systems: Learn an Adaptive Sparse Communication Graph

2020-03-02 · Chuangchuang Sun, Macheng Shen, Jonathan P. How

The complexity of multiagent reinforcement learning (MARL) in multiagent systems increases exponentially with respect to the agent number. This scalability issue prevents MARL from being applied in large-scale multiagent…

Reinforcement Learning Reinforcement Learning (RL)

Multi Agent Path Finding using Evolutionary Game Theory

2022-12-05 · Sheryl Paul, Jyotirmoy V. Deshmukh

In this paper, we consider the problem of path finding for a set of homogeneous and autonomous agents navigating a previously unknown stochastic environment. In our problem setting, each agent attempts to maximize a give…

Multi-Agent Path Finding

From Few to More: Large-scale Dynamic Multiagent Curriculum Learning

2019-09-06 · Weixun Wang, Tianpei Yang, Yong liu, Jianye Hao 외

A lot of efforts have been devoted to investigating how agents can learn effectively and achieve coordination in multiagent systems. However, it is still challenging in large-scale multiagent settings due to the complex …

Deep Reinforcement Learning Reinforcement Learning