GRAND: Guidance, Rebalancing, and Assignment for Networked Dispatch in Multi-Agent Path Finding
- 13 March 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 11 (5) , 5470-5477
Abstract
Large robot fleets are now common in warehouses and other logistics settings, where small control gains translate into large operational impacts. In this article, we address task scheduling for lifelong Multi-Agent Pickup-and-Delivery (MAPD) and propose a hybrid method that couples learning-based global guidance with lightweight optimization. A graph neural network policy trained via reinforcement learning outputs a desired distribution of free agents over an aggregated warehouse graph. This signal is converted into region-to-region rebalancing through a minimum-cost flow, and finalized by small, local assignment problems, preserving accuracy while keeping per-step latency within a 1 s compute budget. We call this approach GRAND: a hierarchical algorithm that relies on Guidance, Rebalancing, and Assignment to explicitly leverage the workspace Network structure and Dispatch agents to tasks. On congested warehouse benchmarks from the League of Robot Runners (LoRR) with up to 500 agents, our approach improves throughput by up to 10% over the 2024 winning scheduler while maintaining real-time execution. The results indicate that coupling graph-structured learned guidance with tractable solvers reduces congestion and yields a practical, scalable blueprint for high-throughput scheduling in large fleets.Keywords
All Related Versions
Funding Information
- MIT Amazon Science Hub
- MIT Schwarzman College of Computing
- Defense Advanced Research Projects Agency (D25AC00373)
This publication has 18 references indexed in Scilit:
- Online Multi-Agent Pickup and Delivery with Task Deadlines2024
- RTAW: An Attention Inspired Reinforcement Learning Method for Multi-Robot Task Allocation in Warehouse Environments2023
- Multiple Mobile Robot Task and Motion Planning: A SurveyACM Computing Surveys, 2023
- Multi-Goal Multi-Agent Pickup and Delivery2022
- Graph Neural Network Reinforcement Learning for Autonomous Mobility-on-Demand Systems2021
- Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and DeliveryIEEE Robotics and Automation Letters, 2021
- On-demand high-capacity ride-sharing via dynamic trip-vehicle assignmentProceedings of the National Academy of Sciences, 2017
- Minimum-cost flow algorithms: an experimental evaluationOptimization Methods and Software, 2014
- Guest Editorial: A Revolution in the Warehouse: A Retrospective on Kiva Systems and the Grand Challenges AheadIEEE Transactions on Automation Science and Engineering, 2012
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968