# Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks

arXiv: https://arxiv.org/abs/2110.08802 · HTML: https://mlsanity.com/paper/2110.08802/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 17 Oct 2021.

## Builds on (most cited first, 10 of 10)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Efficient Large-Scale Multi-Drone Delivery Using Transit Networks](https://mlsanity.com/paper/1909.11840/) (2019)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds](https://mlsanity.com/paper/2104.08759/) (2021)
- [Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance](https://mlsanity.com/paper/2105.10993/) (2021)
- [A Decomposition Algorithm to Solve the Multi-Hop Peer-to-Peer Ride-Matching Problem](https://mlsanity.com/paper/1704.06838/) (2017)
- [Dynamic Real-time Multimodal Routing with Hierarchical Hybrid Planning](https://mlsanity.com/paper/1902.01560/) (2019)
- [Multi-Agent Path Finding with Capacity Constraints](https://mlsanity.com/paper/1907.12648/) (2019)
- [Risk Sensitive Rendezvous Algorithm for Heterogeneous Agents in Urban Environments](https://mlsanity.com/paper/2002.05749/) (2020)

## Built on by (most cited first, 6 of 6)

- [Multi Agent Path Finding using Evolutionary Game Theory](https://mlsanity.com/paper/2212.02010/) (2022)
- [MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem](https://mlsanity.com/paper/2404.19518/) (2024)
- [QD-MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi-Agent Path Finding Algorithms in Diverse Maps](https://mlsanity.com/paper/2409.06888/) (2024)
- [Hybrid Quantum-Classical Multi-Agent Pathfinding](https://mlsanity.com/paper/2501.14568/) (2025)
- [An Efficient Approach to the Online Multi-Agent Path Finding Problem by Using Sustainable Information](https://mlsanity.com/paper/2301.04446/) (2023)
- [Dynamic UGV-UAV Cooperative Path Planning in Uncertain Environments](https://mlsanity.com/paper/2604.25267/) (2026)

## Abstract (arXiv)

We address the problem of routing a team of drones and trucks over large-scale urban road networks. To conserve their limited flight energy, drones can use trucks as temporary modes of transit en route to their own destinations. Such coordination can yield significant savings in total vehicle distance traveled, i.e., truck travel distance and drone flight distance, compared to operating drones and trucks independently. But it comes at the potentially prohibitive computational cost of deciding which trucks and drones should coordinate and when and where it is most beneficial to do so. We tackle this fundamental trade-off by decoupling our overall intractable problem into tractable sub-problems that we solve stage-wise. The first stage solves only for trucks, by computing paths that make them more likely to be useful transit options for drones. The second stage solves only for drones, by routing them over a composite of the road network and the transit network defined by truck paths from the first stage. We design a comprehensive algorithmic framework that frames each stage as a multi-agent path-finding problem and implement two distinct methods for solving them. We evaluate our approach on extensive simulations with up to 100 agents on the real-world Manhattan road network containing nearly 4500 vertices and 10000 edges. Our framework saves on more than 50% of vehicle distance traveled compared to independently solving for trucks and drones, and computes solutions for all settings within 5 minutes on commodity hardware.