Optimal UGV-UAV Cooperative Partitioning and Inspection of Shortest Paths

• URL: http://arxiv.org/abs/2604.25284v1
• Date: Tue, 28 Apr 2026 06:47:22 GMT
• Title: Optimal UGV-UAV Cooperative Partitioning and Inspection of Shortest Paths
• Abstract summary: We study cooperative shortest path planning for an unmanned ground vehicle (UGV) assisted by an unmanned aerial vehicle (UAV) in environments with unknown road blockages.<n>We present an optimal path partitioning strategy that assigns path prefix inspection to the UGV and path suffix inspection to the UAV.<n>We show that the proposed method reduces UGV travel times by up to 30%.
• Score: 4.941630596191806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study cooperative shortest path planning for an unmanned ground vehicle (UGV) assisted by an unmanned aerial vehicle (UAV) in environments with unknown road blockages that are only discovered when a robot reaches the damaged point. This formulation generalizes the original Canadian Traveller Problem (CTP), which assumes a single ground vehicle and that the traversability status of all incident edges is revealed upon arrival at a vertex. We first analyze the case where the start and the goal are connected by $k$ disjoint paths, and prove that the worst-case competitive ratio $ρ$ for a single UGV is $2k-1$. With UAV assistance, and under the simplifying assumption of negligible initial transit and deadheading UAV costs, the ratio improves to $ρ= 2\frac{v_G}{v_A + v_G}k - 1$, where $v_G$ and $v_A$ denote the UGV and UAV speed, respectively. To address general graphs and non-negligible UAV initial transit and deadheading costs, we present an optimal path partitioning strategy that assigns path prefix inspection to the UGV and path suffix inspection to the UAV, and prove the optimality of the UAV inspection strategy on general graphs. We evaluate our algorithm by performing experiments on road networks from the world's 50 most populous cities, with randomized blockages, and show that the proposed method reduces UGV travel times by up to 30%.

Related papers

• Gaze-DETR: Top-Down Guidance Through Priority Maps for Infrared Weak-Small UAV Detection with DETR [60.12701295852494]
  We propose Gaze-DETR, a detector that learns an internal priority map before localization.<n> Priority head predicts a normalized priority map from image features,RPFM enhances high-priority responses, and PAQI converts high-priority locations into decoder anchor queries.<n>Results show that explicit spatial-priority learning provides pre-localization guidance complementary to bounding-box supervision.
  arXiv  Detail & Related papers  (2026-07-21T12:29:58Z)
• A Digital Twin Framework for Traffic-Aware UAV Pavement Monitoring without Lane Closure [0.0]
  This paper presents a Unity-based digital twin framework for traffic-aware UAV pavement monitoring without lane closure.<n>The proposed environment integrates procedurally generated road defects, dynamic vehicles and pedestrians, autonomous UAV navigation, and an embedded road-damage perception pipeline.<n>The digital twin was then used to evaluate three recovery strategies for occluded road segments: hover-and-recheck, micro-repositioning, and skip-and-revisit.
  arXiv  Detail & Related papers  (2026-06-17T20:30:52Z)
• Dynamic UGV-UAV Cooperative Path Planning in Uncertain Environments [4.941630596191806]
  We present strategies to optimize UGV-UAV cooperation for finding a safe path in an uncertain road network.<n>We explore the impact of using multiple UAVs on reducing the UGV's travel time, and evaluate the associated time.
  arXiv  Detail & Related papers  (2026-04-28T06:26:43Z)
• Energy-Aware Collaborative Exploration for a UAV-UGV Team [0.0]
  We present an energy-aware collaborative exploration framework for a UAV-UGV team operating in unknown environments.<n>We construct a sparsely coupled air-ground roadmap using a density-aware layered probabilistic roadmap.<n>We validate our method through simulation studies, benchmark comparisons, and real-world experiments.
  arXiv  Detail & Related papers  (2026-03-23T19:14:01Z)
• Joint UAV-UGV Positioning and Trajectory Planning via Meta A3C for Reliable Emergency Communications [5.254446611211724]
  Joint deployment of unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs) has been shown to be an effective method to establish communications in areas affected by disasters.<n>This paper proposes a joint UAV-UGV-based positioning and trajectory planning framework for UAVs and UGVs deployment that guarantees optimal for ground users.
  arXiv  Detail & Related papers  (2025-12-20T08:53:15Z)
• Deep UAV Path Planning with Assured Connectivity in Dense Urban Setting [2.4156037371075088]
  This paper proposes a framework for UAV path planning with assured connectivity (DUPAC) During UAV flight, DUPAC determines the best route from a defined source to the destination in terms of distance and signal quality. The results confirm that DUPAC achieves an autonomous UAV flight path similar to base method with only 2% increment while maintaining an average 9% better connection quality throughout the flight.
  arXiv  Detail & Related papers  (2024-06-21T15:10:25Z)
• Ant Colony Optimization for Cooperative Inspection Path Planning Using Multiple Unmanned Aerial Vehicles [0.9208007322096533]
  This paper presents a new swarm intelligence-based approach to deal with the cooperative path planning problem of unmanned aerial vehicles (UAVs) The approach uses a 3D model of the structure to generate viewpoints for the UAVs. Experiments with 3D models of real structures have been conducted to evaluate the performance of the proposed approach.
  arXiv  Detail & Related papers  (2024-02-13T06:20:37Z)
• Evidential Detection and Tracking Collaboration: New Problem, Benchmark and Algorithm for Robust Anti-UAV System [56.51247807483176]
  Unmanned Aerial Vehicles (UAVs) have been widely used in many areas, including transportation, surveillance, and military. Previous works have simplified such an anti-UAV task as a tracking problem, where prior information of UAVs is always provided. In this paper, we first formulate a new and practical anti-UAV problem featuring the UAVs perception in complex scenes without prior UAVs information.
  arXiv  Detail & Related papers  (2023-06-27T19:30:23Z)
• Integrated Sensing, Computation, and Communication for UAV-assisted Federated Edge Learning [52.7230652428711]
  Federated edge learning (FEEL) enables privacy-preserving model training through periodic communication between edge devices and the server. Unmanned Aerial Vehicle (UAV)mounted edge devices are particularly advantageous for FEEL due to their flexibility and mobility in efficient data collection.
  arXiv  Detail & Related papers  (2023-06-05T16:01:33Z)
• A Multi-UAV System for Exploration and Target Finding in Cluttered and GPS-Denied Environments [68.31522961125589]
  We propose a framework for a team of UAVs to cooperatively explore and find a target in complex GPS-denied environments with obstacles. The team of UAVs autonomously navigates, explores, detects, and finds the target in a cluttered environment with a known map. Results indicate that the proposed multi-UAV system has improvements in terms of time-cost, the proportion of search area surveyed, as well as successful rates for search and rescue missions.
  arXiv  Detail & Related papers  (2021-07-19T12:54:04Z)
• Efficient UAV Trajectory-Planning using Economic Reinforcement Learning [65.91405908268662]
  We introduce REPlanner, a novel reinforcement learning algorithm inspired by economic transactions to distribute tasks between UAVs. We formulate the path planning problem as a multi-agent economic game, where agents can cooperate and compete for resources. As the system computes task distributions via UAV cooperation, it is highly resilient to any change in the swarm size.
  arXiv  Detail & Related papers  (2021-03-03T20:54:19Z)
• Anti-UAV: A Large Multi-Modal Benchmark for UAV Tracking [59.06167734555191]
  Unmanned Aerial Vehicle (UAV) offers lots of applications in both commerce and recreation. We consider the task of tracking UAVs, providing rich information such as location and trajectory. We propose a dataset, Anti-UAV, with more than 300 video pairs containing over 580k manually annotated bounding boxes.
  arXiv  Detail & Related papers  (2021-01-21T07:00:15Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.