Spotlight Talk for 'Efficient Large-Scale Multi-Drone Delivery using Transit Networks'. The talk will appear at the IEEE International Conference on Robotics and Automation (ICRA) 2020 and is nominated for Best Paper in Multi-Robot Systems. Narrated by Shushman Choudhury.
Arxiv Link: https://arxiv.org/abs/1909.11840
We consider the problem of controlling a large fleet of drones to deliver packages simultaneously across broad urban areas. To conserve energy, drones hop between public transit vehicles (e.g., buses and trams). We design a comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery. We address the multifaceted complexity of the problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with a near-optimal polynomial-time task allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network while employing efficient bounded-suboptimal multi-agent pathfinding techniques tailored to our setting. Experiments demonstrate the efficiency of our approach on settings with up to 200 drones, 5000 packages, and transit networks with up to 8000 stops in San Francisco and Washington DC. Our results show that the framework computes solutions typically within a few seconds on commodity hardware, and that drones travel up to 360% of their flight range with public transit.