Geodesy

Robot

Algorithm

Engineering

Traverse

Materials science

Motion planning

Ant colony optimization algorithms

Layer (electronics)

Systems engineering

Probabilistic logic

Particle swarm optimization

Any-angle path planning

Computer science

Mathematical optimization

Path length

Computer network

Organic chemistry

Task (project management)

Mathematics

Geography

Path (computing)

Artificial intelligence

Hybrid algorithm (constraint satisfaction)

Composite material

Constraint satisfaction

Constraint logic programming

Chemistry

Programming language

Computers & Industrial Engineering

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.

ACO+PSO+A*: A bi-layer hybrid algorithm for multi-task path planning of an AUV