Evolutionary Hyper-Transformation for Multi-AAV Path Planning to Visit Moving Targets

This article addresses a novel path planning problem for multiple fixed-wing autonomous aerial vehicles (AAVs) to visit a set of moving targets, originating from AAV cooperative missions such as emergency communication and target surveillance. This problem can be formulated as a multiple Dubins traveling salesman problem with moving targets (mDTSPMT). The key challenge lies in the strong cross-level coupling between target assignment, encounter sequences, and motion-constrained paths for multiple AAVs in the presence of moving targets. To solve mDTSPMT efficiently, we develop an efficient transformation method by sampling the access location and heading of each AAV to visit moving targets, constructing the mDTSPMT roadmap, and transferring it into an asymmetric multiple traveling salesman problem (AMTSP). This transformation allows the use of mature AMTSP solvers while preserving the essential motion and timing constraints of the original problem. However, the performance of the transformation method heavily depends on the quality of the samples. To improve the quality of samples, a hyper-transformation (HT) framework is proposed, which adaptively optimizes AAV sampling, guiding the search toward more promising configurations and enhancing both the solution quality and computational efficiency of the transformation method. Experiments with extensive instances show that the proposed method outperforms four competitive algorithms in generating coordinated and time-efficient Dubins paths for multiple AAVs encountering multiple targets.