A Robust Path Planning of Messenger UAV for Air-Ground Coordination Under Road Network Constraints

This paper addresses the path planning problem for unmanned aerial vehicle (UAV), where a UAV serves as a messenger to periodically traverse over road-constrained ground vehicles (GVs) to relay information. The GVs may not move on the road network with the velocities agreed with the UAV due to their movement uncertainties. The UAV path planning problem can be formulated as the Dynamic Dubins Traveling Salesman Problem with Uncertain Neighborhood (DDTSPUN). To address the uncertainty in GVs motion, we define robust neighborhoods and corridors and prove that the UAV visiting these areas can revisit GVs reliably, thus transforming DDTSPUN into a Revisit-time-constrained Dubins Traveling Salesman Problem with Neighborhood (RDTSPN). To address the RDTSPN, we propose an online heuristic path planning algorithm. This algorithm incorporates a gradient-based method for visiting robust neighborhoods and a sampling-based search strategy along robust corridors to obtain the Dubins paths of UAV that achieve the robust visit for each GV. Finally, computational experiments demonstrate its advantage over other benchmark algorithms in obtaining the shortest path satisfying UAV curvature constraints, and ensuring robust access to all GVs.