A Multi-Agent Graph Neural Network for Efficient Task Assignments

Assignment problems are prevalent in a multitude of autonomous agent and artificial intelligence (AI) 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 inference-time 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.

May 21, 2025 2:30 PM