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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:

    Erscheinungsdatum :

    2021


    Anmerkungen:

    Accepted to Autonomous Agents and Multiagent Systems, 2022


    Medientyp :

    Preprint


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    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. | Europäisches Patentamt | 2021

    Freier Zugriff

    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. | Europäisches Patentamt | 2017

    Freier Zugriff

    Manifold braking for heavy "over the road" trucks

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