Dynamic UGV-UAV Cooperative Path Planning in Uncertain Environments
Ninh Nguyen, Srinivas Akella
AI summary
Problem
UGVs navigating disaster zones face severe delays from unknown impassable road edges. This paper addresses how to optimally coordinate UAV inspections with UGV routing to dynamically avoid obstacles and minimize travel time.
Approach
The authors develop multiple UGV-UAV coordination strategies, including a novel bidirectional search algorithm, where UAVs prioritize and inspect critical road edges to enable real-time UGV rerouting.
Key results
- Bidirectional strategy achieves the best overall performance
- Multiple UAVs further reduce UGV travel time
- Increased computation time scales with UAV count
- Benchmarked across 100 diverse urban road networks
Why it matters
Provides a practical, scalable framework for first responders and logistics teams navigating damaged infrastructure during emergencies.
Abstract
This paper addresses the Dynamic UGV-UAV Cooperative Path Planning (DUCPP) problem involving one unmanned ground vehicle (UGV) assisted by one or more unmanned aerial vehicles (UAVs) operating on an uncertain road network with potentially impassable edges. DUCPP is particularly relevant for scenarios such as disaster response, emergency supply transport, and rescue operations, where a UGV must reach a specified destination in the presence of partially unknown road conditions. To enable the UGV to travel safely and efficiently to its destination, the UAV(s) dynamically inspect edges in the environment to identify and prune damaged or impassable edges from consideration. We present multiple strategies, including a bidirectional approach, to optimize UGV-UAV cooperation for finding a safe path in an uncertain road network. Furthermore, we explore the impact of using multiple UAVs on reducing the UGV’s travel time, and evaluate the associated computation time. The pro- posed strategies are implemented and evaluated on 100 urban road networks. The results demonstrate that the bidirectional strategy achieves the best performance in most instances, and using multiple UAVs further reduces UGV travel time at the expense of increased computation time. This paper presents a robust framework for DUCPP to achieve efficient UGV-UAV cooperation for path planning and inspection, offering practical solutions for navigation in challenging and uncertain conditions.