Leader-Based Coalition Formation for Extremely Large Scale Collectives

Abstract

Robotic collectives deployed in challenging environments require efficient coordination algorithms. Coalition formation partitions robots into task-oriented teams enabling coordinated execution of complex multiple robot tasks. The coalition formation problem's computational complexity is often directly related to the collective's size and number of tasks. LeaderGRAPE-S, a hedonic game-based coalition formation algorithm was developed for extremely large scale heterogeneous robot collectives (i.e., 10000 robots) and a fixed number of tasks. These collectives' heterogeneity is restricted to a small number of robot types relative to the collective size. The developed algorithm extends a hedonic game-based coalition formation algorithm by integrating a leader-follower model to leverage the reduced heterogeneity and improve runtime efficiency. A centralized evaluation with simulated heterogeneous robot collectives of up to 10000 robots demonstrated that the LeaderGRAPE-S algorithm achieved a significant runtime reduction with a negligible increase in communication, while generating optimal solutions, making it the first algorithm to demonstrate hedonic game-based coalition formation for extremely large scale heterogeneous collectives.