Path Planning in Multiple-AUV Systems for Difficult Target Traveling Missions: A Hybrid Metaheuristic Approach

Multiple autonomous underwater vehicles (AUVs) are popular for challenging submarine missions. In this article, we focus on the multi-AUV path planning for a common class of missions that need to traverse lots of mission targets in large and complex environments. Given that AUVs are often launched from a movable surface vehicle, e.g., a ship, a multi-AUV target traveling problem is formulated with a requirement of surface point location. Thereafter, a hybrid metaheuristic approach is developed by sequentially performing a cube-based environment modeling, cost map building, voyage planning, and detailed trajectory planning. Specifically, the shortest path faster algorithm (SPFA) is adopted to build a cost map among targets and candidate surface points, and the A* search is utilized for trajectory planning. The optimality of both SPFA and A* can indeed be guaranteed. Thus, voyage planning becomes critical and an algorithm namely DE-C-ACO is proposed by combining the ant colony optimization (ACO) and the differential evolution (DE) with a cluster-based adjustment strategy, i.e., DE-C. DE-C and ACO evolve in parallel for surface point location and voyage generation, respectively. Experiments based on realistic bathymetries are conducted and the results validate the effectiveness and efficiency of the proposed DE-C-ACO.