The Viability of Domain Constrained Coalition Formation for Robotic Collectives
This work addresses a scalability problem for robotic collectives in applications like military and disaster response, but it is incremental as it surveys and evaluates existing methods rather than proposing a new solution.
The paper tackles the challenge of designing coalition formation algorithms for very large robotic collectives (e.g., 1000 robots) under domain constraints like distribution and minimal communication, finding that no existing algorithm is viable for certain collective compositions but suggesting potential paths forward based on simulations and a literature survey.
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.