How can I quickly find optimal agent coalitions in large-scale systems?
A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation
February 17, 2025
https://arxiv.org/pdf/2502.10226This paper introduces SALDAE, a new algorithm for optimizing team formation in multi-agent systems. It aims to find the best way to divide agents into groups (coalitions) to maximize their overall effectiveness. SALDAE frames this as a search problem on a graph of possible team configurations, using multiple search "agents" that explore the graph concurrently, drawing inspiration from Multi-Agent Path Finding (MAPF). It improves search efficiency by creating "bridging paths" between known good solutions and managing conflicts between search agents.
Key points for LLM-based multi-agent systems:
- Scalability: SALDAE handles large numbers of agents, relevant for complex web apps with many LLMs.
- Anytime solutions: Useful when quick decisions are needed, even if not perfectly optimal.
- Graph-based search: Can be adapted to represent different LLM interaction structures and dependencies.
- Multi-agent search: Potentially adaptable for distributed LLM computations.
- Bridging paths & conflict resolution: Offers techniques for optimizing the combined output of multiple LLMs.