From Heuristics to Learning: A Factorial Study of Coordination Complexity in Multi-Agent Task Allocation

Autonomous robot fleets are increasingly deployed in logistics, delivery, and service environments, where they must coordinate task allocation under deadlines, battery limitations, fluctuating demand, and incomplete information. Despite rapid progress in learning-based coordination for Multi-Robot Task Allocation (MRTA), choosing between heuristic and learning-based approaches remains difficult because existing studies typically evaluate policies under a single fixed operating condition. As a result, it remains unclear when the additional engineering complexity of learning is genuinely justified in practice. We address this gap through a factorial evaluation framework that decomposes MRTA coordination difficulty into four operational axes: temporal constraints, battery limitations, task load, and scale and fleet availability. To isolate the value of learning itself rather than architectural sophistication, we deliberately employ an independent Deep Q-Network (DQN) with parameter sharing as the learning-based policy, representing a simple instantiation of the Centralised Training Decentralised Execution (CTDE) paradigm. Across 36 configurations and 7,200 evaluation episodes, three findings emerge; first, decentralised greedy coordination recovers most of the benefit of global information when local observations are sufficiently informative; second, learning provides its clearest advantage in worst-case delivery latency under hard deadlines, constrained availability, and dense load; third, coordination difficulty arises primarily from interactions between constraints---deadline and battery limits combine non-additively under low availability to produce cascading failures invisible to single-axis analysis. We show that the benefit of learning-based coordination in MRTA is regime-dependent, emerging from these constraint interactions rather than from isolated factors.