2021/10/17 by Shushman Choudhury, Kiril Solovey, Choudhury, Shushman +5
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Robotic Path Planning Algorithms #Robotics (cs.RO) #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2110.08802
openalex publication_date 2021/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We address the problem of routing a team of drones and trucks over\nlarge-scale urban road networks. To conserve their limited flight energy,\ndrones can use trucks as temporary modes of transit en route to their own\ndestinations. Such coordination can yield significant savings in total vehicle\ndistance traveled, i.e., truck travel distance and drone flight distance,\ncompared to operating drones and trucks independently. But it comes at the\npotentially prohibitive computational cost of deciding which trucks and drones\nshould coordinate and when and where it is most beneficial to do so. We tackle\nthis fundamental trade-off by decoupling our overall intractable problem into\ntractable sub-problems that we solve stage-wise. The first stage solves only\nfor trucks, by computing paths that make them more likely to be useful transit\noptions for drones. The second stage solves only for drones, by routing them\nover a composite of the road network and the transit network defined by truck\npaths from the first stage. We design a comprehensive algorithmic framework\nthat frames each stage as a multi-agent path-finding problem and implement two\ndistinct methods for solving them. We evaluate our approach on extensive\nsimulations with up to 100 agents on the real-world Manhattan road network\ncontaining nearly 4500 vertices and 10000 edges. Our framework saves on\nmore than 50 % of vehicle distance traveled compared to independently solving\nfor trucks and drones, and computes solutions for all settings within 5\nminutes on commodity hardware.\n