Precedence-constrained path planning of messenger UAV for air-ground coordination  

作　　者：Yulong DING Bin XIN Jie CHEN 

机构地区：[1]School of Automation, Beijing Institute of Technology, Beijing 700087, China [2]Key Laboratory of Intelligent Control and Decision of Complex Systems, Beijing Institute of Technology, Beijing 100081, China [3]Beijing Advanced Innovation Center for Intelligent Robots and Systems, Beijing Institute of Technology, Beijing 100081, China

出　　处：《Control Theory and Technology》2019年第1期13-23,共11页控制理论与技术（英文版）

基　　金：National Outstanding Youth Talents Support Program (No. 61822304);in part by the National Natural Science Foundation of China (No. 61673058);in part by NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization (No. U1609214);in part by the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (No. 61621063);in part by the Projects of Major International (Regional) Joint Research Program NSFC (No. 61 720106011);in part by International Graduate Exchange Program of Beijing Institute of Technology.

摘　　要：This paper addresses an unmanned aerial vehicle (UAV) path planning problem for a team of cooperating heterogeneous vehicles composed of one UAV and multiple unmanned ground vehicles (UGVs). The UGVs are used as mobile actuators and scattered in a large area. To achieve multi-UGV communication and collaboration, the UAV serves as a messenger to fly over all task points to collect the task information and then flies all UGVs to transmit the information about tasks and UGVs. The path planning of messenger UAV is formulated as a precedence-constrained dynamic Dubins traveling salesman problem with neighborhood (PDDTSPN). The goal of this problem is to find the shortest route enabling the UAV to fly over all task points and deliver information to all requested UGVs. When solving this path planning problem, a decoupling strategy is proposed to sequentially and rapidly determine the access sequence in which the UAV visits task points and UGVs as well as the access location of UAV in the com mu nication n eighborhood of each task point and each UGV. The effectiveness of the proposed approach is corroborated through computational experiments on randomly generated instances. The computational results on both small and large in stances dem on strate that the proposed approach can generate high-quality solutions in a reasonable time as compared with two other heuristic algorithms.

关 键 词：Air-ground COORDINATION curvature-constrained path planningz precedence constraints Dubins TRAVELING SALESMAN problem 

分 类 号：TP[自动化与计算机技术]