In this paper, an improved genetic algorithm (GA) is proposed for the global three-dimensional (3D) path planning of an under-actuated autonomous underwater vehicle (AUV) with a static environment and obstacles. The kinematics of under-actuated AUV is studied, and various constraints that the planned path needs to satisfy are analyzed. The shortest path (straight lines that connect the waypoints) that satisfies the constraints 3D space is obtained by hierarchical path planning. Finally, the Dubins method is used to optimize the 3D path to get the final flyable path.
For an AUV, finding a 3D optimal path in a complex environment is essential to improve the AUV's persistence and autonomy. Path planning can be divided into offline path planning and online path planning according to the way information is acquired. Online path planning, also called local motion planning, is to obtain environmental information in real time through sensors in unknown or partially unknown sea areas to avoid obstacles and return to the predetermined route. Offline path planning, also called global path planning, is to plan a collision-free path between the starting point and the target point according to certain criteria when the environmental information is known. In this paper, the global path planning is studied which is generally suitable for path planning of large-scale voyages and usually including includes two parts: path search and path optimization. Firstly, a path search algorithm is used to search a series of points in a given order, called the waypoints, according to certain optimization principles. And the path is defined as a set of waypoints to be connected by the successive straight lines. Then the curve is used to optimize the existing path to generate a flyable path.
The path search process is actually an optimal control problem under multiple constraints, usually with the shortest path, the shortest time, or the least energy consumption as the optimization goal, while satisfying the minimum safety distance, kinematic constraints, and seaworthiness.
Commonly used global path search algorithms include A* algorithm, APF algorithm (artificial potential field algorithm), GA, and PSO algorithm (particle swarm optimization). The A* algorithm is a heuristic graph search method, but it has (Ferguson and Stentz, 2006) the problem of computationally expensive to employ in high-dimensional problems. The APF algorithm has the advantage of being inexpensive, however, it has the drawback of producing locally optimal solutions. It was noted (Zeng, Liana and Sammut, 2015) GA and the PSO algorithm are two well-known forms of evolutionary algorithms that are generally recognized to be effective optimization techniques for solving path planning problems. PSO is a stochastic evolutionary algorithm, and there are no conventional evolutionary operators such as crossover and mutation. Alberto, Andrea and Reiner (2004) discovered that the genetic algorithm (GA), a population of possible paths is maintained and the paths are iteratively transformed by genetic operators such as crossover and mutation. The dimension has much less effect on performance than other approaches. However, the drawback of GA is that convergence to the optimal solution is not guaranteed in finite time, one may end up with a suboptimal solution.
