# The Viability of Domain Constrained Coalition Formation for Robotic Collectives

arXiv: https://arxiv.org/abs/2306.05590 · HTML: https://mlsanity.com/paper/2306.05590/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 87 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 5 of 5)

- [An Anytime Algorithm for Optimal Coalition Structure Generation](https://mlsanity.com/paper/1401.3466/) (2014)
- [A Coalition Formation Algorithm for Multi-Robot Task Allocation in Large-Scale Natural Disasters](https://mlsanity.com/paper/1704.05905/) (2017)
- [Anonymous Hedonic Game for Task Allocation in a Large-Scale Multiple Agent System](https://mlsanity.com/paper/1711.06871/) (2017)
- [Multi-Robot Task Allocation -- Complexity and Approximation](https://mlsanity.com/paper/2103.12370/) (2021)
- [Ergodic Specifications for Flexible Swarm Control: From User Commands to Persistent Adaptation](https://mlsanity.com/paper/2006.06081/) (2020)

## Built on by (most cited first, 1 of 1)

- [GRAPE-S: Near Real-Time Coalition Formation for Multiple Service Collectives](https://mlsanity.com/paper/2310.12480/) (2023)

## Abstract (arXiv)

Applications, such as military and disaster response, can benefit from robotic collectives' ability to perform multiple cooperative tasks (e.g., surveillance, damage assessments) efficiently across a large spatial area. Coalition formation algorithms can potentially facilitate collective robots' assignment to appropriate task teams; however, most coalition formation algorithms were designed for smaller multiple robot systems (i.e., 2-50 robots). Collectives' scale and domain-relevant constraints (i.e., distribution, near real-time, minimal communication) make coalition formation more challenging. This manuscript identifies the challenges inherent to designing coalition formation algorithms for very large collectives (e.g., 1000 robots). A survey of multiple robot coalition formation algorithms finds that most are unable to transfer directly to collectives, due to the identified system differences; however, auctions and hedonic games may be the most transferable. A simulation-based evaluation of three auction and hedonic game algorithms, applied to homogeneous and heterogeneous collectives, demonstrates that there are collective compositions for which no existing algorithm is viable; however, the experimental results and literature survey suggest paths forward.