Optimal UGV-UAV Cooperative Partitioning and Inspection of Shortest Paths

Researchers Ninh Nguyen and Srinivas Akella have published a paper at Robotics: Science and Systems (RSS) 2026 tackling the challenge of cooperative shortest path planning for unmanned ground vehicles (UGVs) assisted by unmanned aerial vehicles (UAVs) in environments with unknown road blockages. This problem generalizes the classic Canadian Traveller Problem (CTP), which assumes a single ground vehicle discovers road status only upon reaching a damaged point. The team first analyzed cases where start and goal are connected by k disjoint paths, proving the worst-case competitive ratio for a single UGV is 2k-1. With UAV assistance and assuming negligible initial transit and deadheading costs, the ratio improves to ρ = 2(v_G/(v_A+v_G))k - 1, where v_G and v_A are UGV and UAV speeds.

The researchers then developed an optimal path partitioning strategy for general graphs with non-negligible UAV costs, assigning prefix inspection to the UGV and suffix inspection to the UAV. They proved the optimality of this UAV inspection strategy on general graphs. In experiments on road networks from the world's 50 most populous cities with randomized blockages, the method reduced UGV travel times by up to 30%. This work has direct applications in autonomous logistics, disaster response, and military reconnaissance where mixed ground-air robot teams must navigate uncertain terrain efficiently.