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

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

URL: http://arxiv.org/abs/2110.08802v1
Date: Sun, 17 Oct 2021 12:00:30 GMT
Title: Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks
Authors: Shushman Choudhury and Kiril Solovey and Mykel Kochenderfer and Marco Pavone
Abstract summary: We address the problem of routing a team of drones and trucks over large-scale urban road networks. Drones can use trucks as temporary modes of transit en route to their own destinations. But it comes at the potentially prohibitive computational cost of deciding which trucks and drones should coordinate.
Score: 31.52357826598224
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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.

Related papers

Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks [10.18252143035175]
We introduce the multi-agent flying sidekick traveling salesman problem (MA-FSTSP) on road networks. We propose a mixed-integer linear programming model and an efficient three-phase algorithm for this NP-hard problem. Our approach scales to more than 300 customers within a 5-minute time limit, showcasing its potential for large-scale, real-world logistics applications.
arXiv Detail & Related papers (2024-08-20T20:44:18Z)
Decentralized traffic management of autonomous drones [0.3374875022248865]
We present a solution that enables self-organization of cooperating autonomous agents into an effective aerial coordination task. We show that our algorithm is safe, efficient, and scalable regarding the number of drones and their speed range. We experimentally demonstrate coordinated aerial traffic of 100 autonomous drones within a circular area with a radius of 125 meters.
arXiv Detail & Related papers (2023-12-18T13:52:52Z)
Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
arXiv Detail & Related papers (2023-10-26T15:42:29Z)
Drone navigation and license place detection for vehicle location in indoor spaces [55.66423065924684]
This work is aimed at creating a solution based on a nano-drone that navigates across rows of parked vehicles and detects their license plates. All computations are done in real-time on the drone, which just sends position and detected images that allow the creation of a 2D map.
arXiv Detail & Related papers (2023-07-19T17:46:55Z)
TransVisDrone: Spatio-Temporal Transformer for Vision-based Drone-to-Drone Detection in Aerial Videos [57.92385818430939]
Drone-to-drone detection using visual feed has crucial applications, such as detecting drone collisions, detecting drone attacks, or coordinating flight with other drones. Existing methods are computationally costly, follow non-end-to-end optimization, and have complex multi-stage pipelines, making them less suitable for real-time deployment on edge devices. We propose a simple yet effective framework, itTransVisDrone, that provides an end-to-end solution with higher computational efficiency.
arXiv Detail & Related papers (2022-10-16T03:05:13Z)
Deep Learning on Home Drone: Searching for the Optimal Architecture [54.535788447839884]
We suggest the first system that runs real-time semantic segmentation via deep learning on a weak micro-computer such as the Raspberry Pi Zero v2 attached to a toy-drone. In particular, since the Raspberry Pi weighs less than $16$ grams, and its size is half of a credit card, we could easily attach it to the common commercial DJI Tello toy-drone. The result is an autonomous drone that can detect and classify objects in real-time from a video stream of an on-board monocular RGB camera.
arXiv Detail & Related papers (2022-09-21T11:41:45Z)
Decentralized Vehicle Coordination: The Berkeley DeepDrive Drone Dataset [103.35624417260541]
Decentralized vehicle coordination is useful in understructured road environments. We collect the Berkeley DeepDrive Drone dataset to study implicit "social etiquette" observed by nearby drivers. The dataset is of primary interest for studying decentralized multiagent planning employed by human drivers and for computer vision in remote sensing settings.
arXiv Detail & Related papers (2022-09-19T05:06:57Z)
AutoDrone: Shortest Optimized Obstacle-Free Path Planning for Autonomous Drones [0.0]
We propose a method to find out an obstacle-free shortest path in the coordinate system guided by GPS. This can be especially beneficial in rescue operations and fast delivery or pick-up in an energy-efficient way.
arXiv Detail & Related papers (2021-10-30T07:52:57Z)
A metaheuristic for crew scheduling in a pickup-and-delivery problem with time windows [0.0]
A vehicle routing and crew scheduling problem (VRCSP) consists of simultaneously planning the routes of a fleet of vehicles and scheduling the crews. We present a VRCSP where pickup-and-delivery requests with time windows have to be fulfilled over a given planning horizon by using trucks and drivers. We find high-quality solutions on instances of 100 requests spread across 15 cities with a fleet of 12-32 trucks in less than an hour.
arXiv Detail & Related papers (2021-02-02T22:14:10Z)
The two-echelon routing problem with truck and drones [0.0]
We study novel variants of the well-known two-echelon vehicle routing problem in which a truck works on the first echelon to transport parcels and a fleet of drones to intermediate depots. The objective is to minimize the completion time instead of the transportation cost as in classical 2-echelon vehicle routing problems.
arXiv Detail & Related papers (2020-04-05T18:33:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.