MAGNET: A Multi-Agent Graph Neural Network for Efficient Bipartite Task Assignment

Assignment problems are prevalent in many autonomous agent contexts, where the learning task involves mapping elements from a domain set to a range set. While current state-of-the-art machine learning solutions employ graph neural networks (GNNs) on bipartite agent-task graphs, these approaches frequently fall short when addressing more complex constraints and objectives. To broaden the utility of GNNs for a wider variety of assignment problems, we introduce MAGNET-a novel Multi-Agent Graph Neural network designed for Efficient Task assignment. MAGNET is composed of three integral components that together deliver enhanced performance: (1) a pre-processor that expands the bipartite graph such that it is amenable to multi-task assignment, (2) an edge-centric GNN, enabled through a line graph transformation, which generates candidate assignments, and (3) a post-processor that filters these candidate assignments to ensure they meet the feasibility criteria. Recognizing that the line graph transformation can affect execution time, we enhance MAGNET's efficiency by incorporating an inferencetime pruning strategy. This strategy leverages both GNN scoring and sparsification techniques to streamline the assignment process. Experimental evaluations demonstrate that MAGNET delivers substantial performance improvements over previous GNN-based and heuristic methods, and notably reduces execution time by several orders of magnitude compared to state-of-the-art commercial solvers.