On Hierarchical Multi-UAV Dubins Traveling Salesman Problem Paths in a Complex Obstacle Environment
Jinyu Fu, Guanghui Sun, Jianxing Liu, Weiran Yao, Ligang Wu
Abstract
This article aims to solve a hierarchical multi-UAV Dubins traveling salesman problem (HMDTSP). Optimal hierarchical coverage and multi-UAV collaboration are achieved by the proposed approaches in a 3-D complex obstacle environment. A multi-UAV multilayer projection clustering (MMPC) algorithm is presented to reduce the cumulative distance from multilayer targets to corresponding cluster centers. A straight-line flight judgment (SFJ) was developed to reduce the calculation of obstacle avoidance. An improved adaptive window probabilistic roadmap (AWPRM) algorithm is addressed to plan obstacle-avoidance paths. The AWPRM improves the feasibility of finding the optimal sequence based on the proposed SFJ compared with a traditional probabilistic roadmap. To solve the solution to TSP with obstacles constraints, the proposed sequencing-bundling-bridging (SBB) framework combines the bundling ant colony system (BACS) and homotopic AWPRM. An obstacle-avoidance optimal curved path is constructed with a turning radius constraint based on the Dubins method and followed up by solving the TSP sequence. The results of simulation experiments indicated that the proposed strategies can provide a set of feasible solutions for HMDTSPs in a complex obstacle environment.