A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917923149316096 |
|---|---|
| author | Taguelmimt, Redha Aknine, Samir Boukredera, Djamila Changder, Narayan Sandholm, Tuomas |
| author_facet | Taguelmimt, Redha Aknine, Samir Boukredera, Djamila Changder, Narayan Sandholm, Tuomas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10226 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation Taguelmimt, Redha Aknine, Samir Boukredera, Djamila Changder, Narayan Sandholm, Tuomas Multiagent Systems Artificial Intelligence Computer Science and Game Theory 93A16, 68T01 I.2; F.2 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. |
| title | A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation |
| topic | Multiagent Systems Artificial Intelligence Computer Science and Game Theory 93A16, 68T01 I.2; F.2 |
| url | https://arxiv.org/abs/2502.10226 |