An Optimal Task Allocation Strategy for Heterogeneous Multi-Robot Systems

The goal of the deployment of multi-robot systems often consists of executing multiple tasks. Task allocation is a widely studied discipline that deals with strategies to assign tasks to robots. In this work, we propose an optimal task allocation algorithm which accounts for limited energy availability for the robots, task prioritization and robot specializations in executing different tasks. The tasks we consider are encoded as constraints in an energy minimization problem solved at each point in time by each robot. Moreover, the prioritization of the tasks is a result of the same optimization problem too, and it effectively determines the allocation of tasks to robots. Furthermore, the same formulation explicitly takes into account different suitabilities that different robots might have for different tasks, thus fully exploiting the advantages of the heterogeneity of the robotic swarm. The efficacy of the developed task allocation approach has been demonstrated both in simulation and on a team of real robots on the Robotarium (link to the video of the experiments:

Snapshot from the experiment performed on the Robotarium showing 10 differential drive robots asked to perform two tasks, environment surveillance and formation control. The robots are heterogeneous in their capabilities, with some being specialized to perform surveillance (circled in red), formation control (circled in green), and some equally capable of performing both tasks (circled in blue). The optimal control input drives the robots to the depicted configuration where the robots circled in red are close to the centroids of their Voronoi cells (depicted as gray squares), whereas the robots circled in green reached the locations corresponding to a circle formation and indicated by the red circles. The two robots circled in blue did not have bias in their specialization: as a consequence, one of them is assigned to the formation (the rightmost one) and the other one to surveillance.

: Gennaro Notomista, Siddharth Mayya, Seth Hutchinson, and Magnus Egerstedt, “An Optimal Task Allocation Strategy for Heterogeneous Multi-Robot Systems”, to appear in European Control Conference, Napoli, 2019 (
Task: RA2.A3 Composable Autonomy in Heterogeneous Groups
Points of Contact: Magnus Egerstedt (PI), Gennaro Notomista and Siddharth Mayya