Introduction
Multi-agent systems often require two fundamental coordination tasks: Coalition Structure Generation (CSG), which involves partitioning agents into disjoint teams, and Assignment, which matches these teams to specific tasks to maximize overall utility. Traditionally, these problems were solved sequentially. However, the Simultaneous Coalition Structure Generation and Assignment (SCSGA) problem recognizes that the optimal grouping of agents is intrinsically linked to the tasks they perform.
SCSGA is NP-complete, and its search space grows exponentially with the number of agents and tasks. Previous state-of-the-art methods, such as the optimal branch-and-bound algorithm MP, struggle to scale beyond 30 agents. This paper introduces a suite of "anytime" algorithms designed to find near-optimal solutions for large-scale problems involving up to 1,000 agents.
Proposed Anytime Algorithms
The authors propose several algorithms that leverage permutations of agents to navigate the search space efficiently. These "anytime" methods provide a valid solution immediately and refine it as more computation time is allocated.
- Permutative Greedy (GA): Assigns agents sequentially based on their marginal contribution in a specific order.
- Random-Restart Hill Climb (RHC): Iteratively improves an initial assignment by moving agents between tasks to find local optima.
- Hybrid (RHY): Combines the Greedy start followed by Hill Climbing refinement.
- Permutative Monte Carlo Tree Search (RMCTS): Employs tree search and random rollouts to explore promising assignment paths.
- Simulated Annealing (SA): A metaheuristic that allows for temporary decreases in solution quality to escape local optima.
The Scalability Wall
A key contribution of this work is identifying the performance limitations of existing optimal solvers. While branch-and-bound methods like MP are effective for very small agent sets, their performance degrades rapidly as the problem size increases.
As shown in Figure 2, the proposed heuristics (RHC, RHY) maintain solution quality close to the optimum even as the number of agents grows, whereas MP's performance drops significantly once the search space becomes too large for its preprocessing requirements.
Large-Scale Performance and Efficiency
In scenarios with 1,000 agents and 50 tasks—a search space of approximately $50^{1000}$—the proposed algorithms demonstrate remarkable efficiency. The RHC and RHY methods consistently find solutions within 99.5% of the expected optimal value in just a few seconds.
Figure 3 illustrates the anytime nature of these algorithms. Most methods converge to a high-quality solution very quickly. While greedy-based methods (RHY, RHC) excel in uniform and normal distributions, Simulated Annealing (SA) proves more robust in "sparse" distributions where high-value coalitions are rare and harder to find.
Conclusion and Future Work
This research demonstrates that simple, myopic heuristics like Hill Climbing and Greedy search can outperform complex optimal solvers in large-scale multi-agent coordination. By transforming the partitioning problem into a permutative search, the authors achieve near-optimal results for problems previously considered intractable.
Future work includes exploring machine learning techniques to predict high-value coalitions and developing k-opt algorithms for further local search refinement. The authors also highlight the need for standardized, real-world SCSGA datasets to further validate these approaches in industrial settings.
Summary updated