ACO+PSO+A*: A bi-layer hybrid algorithm for multi-task path planning of an AUV. (January 2023)

• Record Type: Journal Article
• Authors: Sui, Fuli; Tang, Xiaoke; Dong, Zihao; Gan, Xingjia; Luo, Peng; Sun, Jing
• Is Part Of: Computers & industrial engineering. Volume 175(2023)
• Publication Date: 2023-01
• Subjects: Bi-lever optimization model -- Path planning -- Ant colony algorithm -- Particle swarm optimization algorithm -- A* algorithm -- Autonomous underwater vehicles; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108905
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: Autonomous underwater vehicle (AUV) plays a great role in the ocean engineering, and path planning is one of its key technologies. For such scenarios as oil spill detection, AUV should execute multiple tasks, which become more challenging due to the 3D ocean environment with obstacles. To solve the multi-task path planning problem of AUV, this paper first proposes a bi-level multi-objective path planning model aimed at minimizing the path length and dangerous distance. Then, a bi-layer hybrid algorithm is developed to solve the above model. In this algorithm, ant colony optimization algorithm (ACO) is adopted to generate a task sequence of the upper level model in the outer layer; particle swarm optimization algorithm (PSO) is employed to produce some waypoints between two adjacent tasks, and A* algorithm is used to generate a collision-free path of the lower level model based on waypoints in the inner layer. After that, the collision-free path in the inner layer is feedback to the ACO in the out layer to update its pheromone, and ACO yield a better task sequence in the next iteration, thus obtaining the shortest collision-free path traversing all tasks. Finally, PSO+A* and A* algorithms, together with the proposed bi-layer hybrid algorithm and some two-stage optimization algorithms are compared, respectively. Empirical results show that the proposed algorithm can produce an optimal collision-free path with shorter length and higher security. Highlights: A bi-level programming model of AUV multi-task path planning is constructed. A bi-layer hybrid algorithm is designed to solve the above model. The bi-layer algorithm can produce a path with shorter length and higher security. The bi-layer algorithm has higher competitiveness.