Coupled Task Assignment for Hierarchical Multi-Agent Systems: A Nested Hungarian Approach

This work formulates a novel variant of the classical linear task assignment problem, which we refer to as the coupled linear task assignment problem. This formulation models the task assignment process involving two-echelon agents and tasks, aiming to optimally assign tasks to agents within the same echelon to maximize global utility while satisfying the coupling constraints imposed by the hierarchical structure. After discussing the problem’s inherent properties that prevent the use of standard relaxation techniques, we propose a variant of the Hungarian algorithm, the nested Hungarian algorithm, that solves the problem exactly in polynomial time. We demonstrate the superior performance of the proposed algorithm by benchmarking it against seven open-source and commercial MILP solvers. Finally, we apply our proposed approach to a fictitious disaster response scenario motivated by the January 2025 Southern California wildfires in the Greater Los Angeles area.