A varied-width path planning method for multiple AUV formation

Multiple autonomous underwater vehicle (AUV) systems are widely used for various ocean missions. With the continuous improvement of formation control capabilities, path planning performance has gradually become an essential factor limiting the efficiency of AUV formations. To ensure the optimality of formation trajectories under different circumstances, this paper proposes a varied-width A* (VWA*) algorithm for global path planning of multiple AUV formations. Different from the conventional methods that consider formation control and global path planning separately or focus on solving fixed-formation path planning problems, VWA* searches for optimal navigation schemes composed of collision-free paths and formation control scenarios. In the presented strategy, an additional dimension related to formation structure is added to the state space, and the state space is constructed according to the environment and the predefined available formations. Then, with a multi-objective function applied to guide the searching process, VWA* searches in the state space in a manner similar to conventional A*. Moreover, a path generation method based on VWA* is proposed to plan paths for each AUV in the formation. In numerical simulations, the path quality of VWA* is validated in comparison with the optimal global fixed-width path. The performance of varied-formation AUV formation trajectories is compared with fixed-formation trajectories guided by state-of-the-art path planning algorithms. The results demonstrate that VWA* can effectively ensure the optimality of the navigation schemes, and the varied-formation path planning outperforms various fixed-formation path planning techniques. Finally, a test is conducted to verify the feasibility of the proposed methods further.