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

作     者：Wang, Yuyang Xin, Bin Ding, Yulong He, Bin Chen, Jie 

作者机构：Beijing Institute of Technology School of Automation Beijing100081 China Ministry of Education Frontiers Science Center for Intelligent Autonomous Systems Shanghai China National Key Lab of Autonomous Intelligent Unmanned Systems Beijing100081 China Tongji University Department of Control Science and Engineering Shanghai200092 China 

出 版 物：《IEEE Transactions on Vehicular Technology》 (IEEE Trans. Veh. Technol.)

年 卷 期：2024年第74卷第5期

页      面：7135-7151页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0837[工学-安全科学与工程] 0835[工学-软件工程] 0825[工学-航空宇航科学与技术] 0701[理学-数学] 0833[工学-城乡规划学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0823[工学-交通运输工程] 

基　　金：National Natural Science Foundation of China Shanghai Pilot Program for Basic Research 

主　　题：Traveling salesman problem 

摘      要：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. © 1967-2012 IEEE.