SCRAM: Scalable Collision-avoiding Role Assignment with Minimal-makespan for Formational Positioning

Abstract. Teams of mobile robots often need to divide up subtasks ef-ficiently. In spatial domains, a key criterion for doing so may depend on distances between robots and the subtasks ’ locations. This paper considers a specific such criterion, namely how to assign interchange-able robots to a set of target goal locations such that the makespan (time for all robots to reach their target locations) is minimized while also preventing collisions among robots. We present a scalable multia-gent dynamic role assignment system, used for formational positioning of mobile robots, known as SCRAM (Scalable Collision-avoiding Role Assignment with Minimal-makespan). SCRAM uses a graph theoretic approach to map robots to target goal locations such that our objectives for both minimizing the makespan and avoiding robot collisions are met. The system was originally designed to allow for decentralized coordina-tion among physically realistic simulated humanoid soccer playing robots in the partially observable, non-deterministic, noisy, dynamic, and lim-ited communication setting of the RoboCup 3D simulation league. In its current form, SCRAM generalizes well to many realistic and real-world multiagent systems, and scales to thousands of robots, as role assignment algorithms run in polynomial time.