Evolutionary Hyper-Transformation for Multi-AAV Path Planning to Visit Moving Targets
本文提出一种进化超变换框架，通过优化采样位置和航向，将多无人机访问移动目标的路径规划问题转化为非对称多旅行商问题，从而高效生成协调且时间最优的Dubins路径。
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.