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

Redha Taguelmimt (Univ Lyon, UCBL, CNRS, INSA Lyon, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205), Samir Aknine (Univ Lyon, UCBL, CNRS, INSA Lyon, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205), Djamila Boukredera (Faculty of Exact Sciences, Laboratory of Applied Mathematics, University of Bejaia), Narayan Changder (TCG Centres for Research and Education in Science and Technology), Tuomas Sandholm (Carnegie Mellon University, Strategic Machine, Inc., Strategy Robot, Inc., & Optimized Markets, Inc.)

Abstract

Coalition structure generation (CSG) is a critical problem in multiagent systems, involving the optimal partitioning of agents into disjoint coalitions to maximize social welfare. This paper introduces SALDAE, a novel multiagent path finding algorithm for CSG on a coalition structure graph. SALDAE employs various heuristics and strategies for efficient search, making it an anytime algorithm suitable for handling large-scale problems.