Graph Neural Network for Decentralized Multi-Robot Goal Assignment

The problem of assigning a set of spatial goals to a team of robots plays a crucial role in various multi-robot planning applications including, but not limited to exploration, search and rescue, or surveillance. The Linear Sum Assignment Problem (LSAP) is a common way of formulating and resolving this problem. This optimization problem aims at assigning the tasks to the robots minimizing the sum of costs while respecting a one-to-one matching constraint. However, communication restrictions in real-world scenarios pose significant challenges. Existing decentralized solutions often rely on numerous communication interactions to converge to a conflict-free and optimal solution or assume a prior conflict-free random assignment. In this paper, we propose a novel Decentralized Graph Neural Network approach for multi-robot Goal Assignment (DGNN-GA). We leverage a heterogeneous graph representation to model the inter-robot communication and the assignment relations between goals and robots. We compare in simulation its performance to other decentralized state-of-the-art approaches. Specifically, our method outperforms popular state-of-the art approaches in strictly restricted communication scenarios and does not rely on any initial conflict-free guess compared to two other algorithms. Finally, the DGNN-GA is also deployed and validated in real-world experiments.