Online Path Planning of Messenger UAV in Air–Ground Coordination Over Urban Areas

Fast-moving unmanned aerial vehicle (UAV), serving as a messenger to visit ground vehicles (GVs) for information relays, can be applied to complex tasks in urban environments, such as air-ground cooperative urban rescue and UAV-assisted data collection. Existing work ensures that the UAV visits all GVs by assuming that it knows the motion parameters of GVs (e.g., velocities or paths) at any given time. However, in practice, GVs may not move with anticipated velocities due to motion uncertainties. This UAV path planning problem can be formulated as a Dynamic Dubins Traveling Salesman Problem with Uncertain Neighborhoods (DDTSPUN). The problem involves variables with complex interdependencies (e.g., the visiting sequence of the UAV to GVs and the access location of the UAV to GVs) and requires solving a sequence of uncertain encounter problems. To address the uncertainty in GV motion, we define robust neighborhoods and corridors and prove that the UAV can revisit GVs reliably by visiting these areas. By flying the UAV through robust areas, the DDTSPUN can be transformed into a deterministic optimization problem, namely Revisit-time-constrained Dubins Traveling Salesman Problem with Neighborhood (RDTSPN), which provides a simplified model and compresses the solution space. To address the RDTSPN, we propose an online heuristic path planning algorithm. It incorporates a gradient-based method for visiting robust neighborhoods and a sampling-based search strategy along robust corridors to obtain the Dubins paths of the UAV that achieve robust visit for each GV. Finally, the computational experiments, including representative instances, random instances with different scales, and an instance generated using real-world data, demonstrate its advantages over other state-of-the-art algorithms in obtaining the shortest path that satisfies UAV curvature constraints while ensuring robust access to all GVs.