Research map / Learning theory and algorithms / Combinatorial and search optimization
A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SALDAE, an anytime multiagent path-search algorithm over the coalition structure graph that uses split/merge bridging paths between best solutions, memory lists, and conflict resolution to solve coalition structure generation at scale.
Problem
Coalition structure generation (CSG): optimally partitioning agents into coalitions to maximize social welfare, which is intractable exactly for large numbers of agents and needs good anytime solutions under tight run times.
Approach
Treats CSG as multiagent path finding on the coalition structure graph: search agents expand nodes via splits/merges, and after each improvement they build bridging paths (SPLIT-THEN-MERGE, MERGE-THEN-SPLIT, APPROACH-THEN-SWAP) between the incumbent and new best solutions, with OPEN/RESERVE/SUBSTITUTE lists and conflict resolution across agents.
Key results
- On 2000 executions per distribution, SALDAE finds the optimal solution in an average of 65.86% of cases vs 17.36% for PICS and 6.48% for CSG-UCT.
- With the Exponential distribution, SALDAE produces up to 28% higher solution quality than CSG-UCT and up to 15% higher than PICS on small instances.
- On large-scale benchmarks SALDAE outperforms PICS on most tests, notably Gamma, Exponential, Normal, Disaster Response and Electric Vehicles Allocation distributions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SALDAE instead of PICS | CSG algorithms · nine distributions, including Uniform, Normal, Beta, Exponential, Gamma, Pascal, Zipf, and Cauchy | optimal-solution success rate | Helped |
| Use SALDAE instead of CSG-UCT | CSG algorithms · nine distributions, including Uniform, Normal, Beta, Exponential, Gamma, Pascal, Zipf, and Cauchy | optimal-solution success rate | Helped |
| Use SPLIT-THEN-MERGE rather than MERGE-THEN-SPLIT bridging paths (ablation) | SALDAE · Uniform, A-b Normal, A-b Uniform, Beta, Exponential, Gamma, and Zipf | optimal-solution success rate: 1580 (79%) vs 1402 (70.1%); 582 (29.1%) vs 503 (25.2%); 551 (27.5%) vs 532 (26.6%); 1485 (74.3%) vs 1392 (69.6%); 1826 ( | Helped |
| Use MERGE-THEN-SPLIT rather than SPLIT-THEN-MERGE bridging paths (ablation) | SALDAE · Normal and Cauchy | optimal-solution success rate: 531 (26.6%) vs 519 (26%); 1722 (86.1%) vs 1714 (85.7%) | Helped |
| Change the bridging strategy among SPLIT-THEN-MERGE, MERGE-THEN-SPLIT, and APPROACH-THEN-SWAP (ablation) | SALDAE · Gamma and Zipf | optimal-solution success rate: Gamma: 1628 (81.4%), 1623 (81.2%), 1673 (83.7%); Zipf: 1286 (64.3%), 1263 (63.2%), 1287 (64.4%) | Mixed |
Surprising findings
- A single-search-agent SALDAE variant still outperforms PICS (with 20 processes) and CSG-UCT in the appendix comparison.
- PICS performs on par with SALDAE on Beta and Uniform distributions in large-scale tests, and there is almost a tie on Pascal for under 100 agents.
Limitations
- No optimality guarantee for large-scale problems; anytime solutions only approximate the optimum.
- Bridging paths via APPROACH-THEN-SWAP can be long, and not all strategies are uniformly best; the best strategy varies by distribution.
- Hyperparameters (theta, omega, number of agents) were tuned on experiments, and goal nodes were not defined in the current version.
Experimental setup
Datasets: synthetic value distributions (Agent-based Uniform, Agent-based Normal, Beta, Exponential, Gamma, Normal, Uniform, Pasca Disaster Response distribution Electric Vehicles Allocation distribution
Benchmarks: nine value distributions for small-scale (4-20 agents) vs ODP-IP optimum large-scale gain rate on Disaster Response, Electric Vehicles Allocation and other distributions with hundreds to thousa
Metrics: solution quality success rate (optimal solutions found over 2000 executions) gain rate
Baselines: PICS CSG-UCT ODP-IP FACS C-Link
Builds on: Conflict-Based Search PICS CSG-UCT ODP-IP
Closest papers by meaning
- Coalition Formation for Task Allocation Using Multiple Distance Metrics (Student Abstract) (AAAI 2024 · similarity 0.85)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.85)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.85)
- Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.85)
- Learning Coalition Structures with Games (AAAI 2024 · similarity 0.84)
- Improved Anonymous Multi-Agent Path Finding Algorithm (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.