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.


    Access

    Download


    Export, share and cite



    Title :

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


    Contributors:

    Publication date :

    2021


    Remarks:

    Accepted to Autonomous Agents and Multiagent Systems, 2022


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




    Multi-Agent Coordinated Interception of Multiple Rogue Drones

    Valianti, Panayiota / Papaioannou, Savvas / Kolios, Panayiotis et al. | IEEE | 2020


    COORDINATED LABOR ACTIVITIES USING DRONES

    VALENTINO III HENRY / CORONEL JACK / RUTHERFORD MALCOLM et al. | European Patent Office | 2021

    Free access

    Multiple-Drones-Multiple-Trucks Routing Problem for Disruption Assessment

    Ermagun, Alireza / Tajik, Nazanin | Transportation Research Record | 2022


    Operating a plurality of drones and trucks in package delivery

    JAMJOOM HANI T / LUBENSKY DAVID M / MANWEILER JUSTIN G et al. | European Patent Office | 2017

    Free access

    Manifold braking for heavy "over the road" trucks

    Meyer, W.E. | Engineering Index Backfile | 1955