With the rapid development of technologies such as big data, AI technology, and intelligent communication, intelligent ships have become a global research focus. The China Classification Society’s “Intelligent Ship Code” released in 2024 subdivides ship intelligent functions into eight areas: intelligent navigation, intelligent hull, intelligent engine room, intelligent energy efficiency management, intelligent cargo management, intelligent integrated platform, remote control ships, and autonomous operation ships. Among these, intelligent navigation, as one of the core key technologies, primarily relies on advanced perception systems to obtain maritime environment information. It uses backend decision-making systems to plan based on chart information, mastering all environmental information, which belongs to offline planning. In contrast, the environmental information for local planning comes from real-time collection by perception systems, constructing local map information, determining the current real-time position and the real-time positions of detected obstacles, and performing real-time planning and obstacle avoidance, which belongs to online planning. This article primarily discusses ship online motion planning methods.
The basic types of motion planning are divided into path planning and trajectory optimization. Path planning involves planning the shortest path from the ship’s current starting point to the target point that safely avoids all obstacles, often by introducing various objective functions to constrain the path’s shortness and economy. Trajectory optimization further incorporates the time dimension, detailing the planning of the ship’s speed changes and acceleration curves, i.e., applying kinematic and dynamic constraints to achieve controllable ship speed, smooth tracks, and dynamic rationality.
Online Path Planning
Path planning can be divided into two major categories: offline path planning and online path planning. The information obtained by online path planning from perception systems can be divided into two types: one is long-term stored information describing the distribution of static obstacles in the environment; the other is short-term information reflecting dynamic obstacles and undetected obstacles in the environment. Depending on the nature of the acquired information, online path planning can be categorized into online static path planning and online dynamic path planning.
1. Online Static Path Planning
Online static path planning methods aim to achieve static obstacle avoidance and path minimization, and are widely used in robotics and vehicle autonomous driving. Currently, the main static path planning methods roughly include: Artificial Potential Field method, Vector Field Histogram method, Fuzzy Logic method, Intelligent Optimization Algorithms, etc.
The Artificial Potential Field (APF) method, from an intuitive perspective, treats obstacles as “hills” with high potential energy, while the target position is treated as a “depression” with low potential energy. In this potential field, the controlled object starts near the “hills” and moves along the force lines of the potential field by avoiding these high-potential energy areas, eventually reaching the low-potential energy area, i.e., the target location. Typically, the controlled object moves in the negative direction of the potential energy gradient, i.e., the gradient descent method, and the path taken is the shortest path. Therefore, APF can achieve both real-time obstacle avoidance and distance-optimal paths under the constraints of the potential field, with low algorithm computational complexity and fast response speed.
However, due to the unique virtual force mechanism of APF, its application in actual ship navigation needs to overcome issues such as goal unreachability and collisions. Scholars worldwide have proposed improved methods based on APF to address these problems, mainly in two directions: one is improving the potential field function based on the traditional APF, adding various factors or optimizing parameters within the potential field function to tackle goal unreachability and local minimum problems; the other is combining other planning algorithms or introducing optimization algorithms to enhance path planning performance, adapting to complex environments and dynamically changing scenarios.
The Vector Field Histogram (VFH) method can overcome local minima problems and oscillation issues in gaps while maintaining the low complexity of APF. The basic principle of VFH is to create a grid map of the ship’s surrounding environment in real-time, then calculate the motion cost in each direction for the ship. If there are more obstacles in a certain direction, the corresponding cost becomes greater. Based on this, costs for different directions are plotted in a histogram, while a balancing function is used to weigh and calculate the target direction and forward cost, ultimately deriving the optimal motion planning scheme.
VFH is applied in the field of unmanned surface vehicles due to its high efficiency, real-time performance, and good robustness. However, this method lacks consideration for obstacle velocity attributes and ship dynamic characteristics. In response, researchers have improved VFH. Loe combined VFH with the A* algorithm to achieve local collision avoidance and path planning in complex environments; Babinec processed the motion space by grid division into binary information units, calculated the confidence of these units, and extracted the vector values and angle information of obstacle grids, enabling obstacle avoidance path planning in complex environments.
Fuzzy logic essentially uses the basic ideas and methods of fuzzy mathematics to control the object. Fuzzy logic simulates the driver’s handling method, fuzzifying information before segmentation, and making decisions based on experience with the segmented information. Fuzzy logic is characterized by high speed and good real-time performance, but it suffers from poor fault tolerance in U-shaped obstacle environments and symmetric obstacle environments, difficulties in high-precision solutions, and lock-in problems. To address the issues with fuzzy logic, researchers combine the optimization and search capabilities of intelligent algorithms with the imprecise reasoning ability of fuzzy logic to solve path planning problems in unknown waters.
Intelligent optimization algorithms are a class of algorithms inspired by natural laws and biological behaviors. These algorithms are characterized by simplicity, strong applicability, and strong multi-objective optimization capabilities, often used to solve engineering optimization problems in fields such as electronics, robotics, and automation. For online motion planning problems, traditional intelligent algorithms mainly include: Genetic Algorithm (GA), Simulated Annealing (SA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO), etc. With in-depth research on intelligent algorithms, various emerging intelligent algorithms such as Imperialist Competitive Algorithm, Bacterial Foraging Optimization Algorithm, and Cuckoo Search Algorithm have been proposed and applied in the field of ship motion planning.
When handling ship path planning tasks, intelligent optimization algorithms follow a similar process: first transforming the path planning problem into an optimization problem, then using heuristic signals provided by evaluation functions, such as shortest path, minimum energy consumption, smooth trajectory, etc., and gradually guiding the population towards the optimal solution through group collaboration in an iterative process. The main difference between various intelligent algorithms lies in the method of population update. For example, GA uses operations like selection, crossover, and mutation to evolve the population, while PSO relies on particle position and velocity information for updates. These different update mechanisms result in algorithms exhibiting different characteristics in terms of convergence speed and population diversity.
2. Online Dynamic Path Planning
Online dynamic path planning is a behavioral planning based on real-time sensor perception information. It has high requirements for perception sensitivity, communication fluency, and decision-making real-time performance. Dynamic path planning is mostly used for dynamic collision avoidance and encountering vessel collision avoidance, etc. Its main planning methods include: Dynamic Window Approach, Velocity Obstacle method, Neural Network method, Reinforcement Learning method, etc.
The Dynamic Window Approach (DWA) is a behavioral planning method proposed by Dieter Fox et al. It reacts to external information based on the ship’s onboard sensors and performs real-time dynamic planning. The basic principle of this method is: discretizing the ship’s current velocity space in terms of angular velocity and linear velocity, combining different linear and angular velocities into multiple sample points, analyzing the possible navigation paths for each sample point, performing collision detection on each estimated path, eliminating infeasible paths, and evaluating feasible paths using evaluation functions such as distance to target and distance to obstacles, with the optimal solution as the planning goal. Because DWA has advantages like high real-time performance and the ability to introduce dynamic constraints, its application in dynamic collision avoidance and path planning in complex waters is relatively widespread.
However, the traditional DWA still uses constant weight parameters under different obstacle distributions, leading to problems such as inability to bypass obstacles and difficulty passing through narrow channels. Researchers have improved this by dynamically adjusting DWA’s own weight parameters using a fuzzy logic controller, effectively solving dynamic and static obstacle avoidance problems; by integrating DWA with D*, treating dynamic obstacles as entities that can move within grid cells of the map, using DWA to predict the potential motion trajectories of grid cells, assessing collision risk, and virtualizing the problem of active ship obstacle avoidance as a physical obstacle avoidance problem.
The Velocity Obstacle (VO) method was proposed by Fiorini et al. as a method for avoiding collisions with dynamic obstacles. Its basic principle is to represent the ship and dynamic targets with minimum bounding circles, constructing a collision cone area, i.e., the velocity obstacle area, based on the positions, dimensions, and velocities of the ship and dynamic targets. It determines whether the ship needs collision avoidance and local motion planning based on whether the ship’s velocity relative to the dynamic obstacle falls within the velocity obstacle area. Depending on the velocity change characteristics of obstacles, VO is typically divided into three types: Linear Velocity Obstacle, Nonlinear Velocity Obstacle, and Probabilistic Velocity Obstacle. VO has advantages such as fast computation, good real-time performance, and strong adaptability, and is widely used in high-speed boat collision avoidance, UAV swarms, and other fields. The main limitation of this method is that the selected motion velocities outside the velocity obstacle area can vary significantly, causing discontinuities in the ship’s motion state.
The application of neural networks and reinforcement learning in ship path planning has been a research hotspot in recent years. In path planning, neural networks optimize path selection by defining reward and cost functions. Rewards are typically associated with reaching the target position and avoiding obstacles, while the cost function is related to path length or arrival time. The focus of reinforcement learning is to take actions by interacting with the environment with the goal of maximizing cumulative reward. The application of reinforcement learning in path planning is mainly divided into optimal value reinforcement learning and policy gradient reinforcement learning. For example, to address the dynamic obstacle avoidance problem, researchers proposed a collision avoidance path planning algorithm based on DQN. They improved the original DQN algorithm’s reward return function based on the International Regulations for Preventing Collisions at Sea (COLREGs), and then set up simulation experiments for three ship encounter situations: head-on, crossing, and overtaking. The results proved that this method can effectively perform dynamic collision avoidance according to the rules and reach the target position. By improving the DDPG algorithm through focused learning in failure regions and classifying the experience pool, and then setting up ship head-on and overtaking simulation experiments in narrow waters, the improved DDPG algorithm demonstrated better learning speed and effectiveness. Compared with the original DDPG algorithm, the improved algorithm’s collision avoidance path has a smaller average distance deviation from the real path, better feasibility in real water environments, and meets the requirements of general ship collision avoidance planning situations.
Online Trajectory Optimization
Path planning outputs a geometric path composed of multiple connected line segments, represented as an ordered set of points in the data structure. Trajectory optimization, however, involves time parameterization, where each trajectory point contains specific time information. The main task of trajectory optimization is to optimize based on the path planning, smoothing the discrete points from the path planning using specific methods to obtain a smooth curve that conforms to the ship’s dynamic characteristics, facilitating the actual ship’s tracking control. Currently, the main methods for trajectory optimization include: methods based on dynamic discrete search, methods based on mathematical optimization, methods based on bio-inspired techniques, and hybrid methods.
Dynamic discrete trajectory optimization methods advance the low-dimensional projection space of discrete search-based path planning to a higher dimension, thereby achieving high-quality trajectory optimization that searches for motion trajectories containing richer motion information in the higher-dimensional space, improving the method’s feasibility. Typical algorithms based on this method include the Hybrid A* algorithm and the Kinodynamic RRT* algorithm. Building on the A* algorithm, Hybrid A* incorporates ship kinematics, uses basic trajectory combinations to simulate the grid map of ship motion and connect discrete grid maps, and then follows the search strategy of the A* algorithm to search the map to obtain the optimal trajectory. The Kinodynamic RRT* algorithm, when finding the nearest node on the RRT tree, considers not only positional proximity but also dynamic constraints to optimize the trajectory. These methods all use discrete methods to search for ship trajectories, cannot fully utilize the ship’s maneuvering capabilities, and their trajectory optimization has certain limitations. Furthermore, the optimized trajectory is generated based on map resolution; when the resolution increases and the motion model precision improves, it will increase the computational pressure of trajectory search.
Mathematical optimization-based trajectory optimization methods do not discretize the state space or use search methods. Instead, they mathematically model the optimization problem, using an objective function to represent the shortest trajectory or smooth trajectory, and the ship’s three-degree-of-freedom motion model, speed, acceleration, etc., as constraint functions, thereby solving for the optimal trajectory that meets the objective function and constraints. Solving optimal control problems using mathematical optimization can be divided into three categories of methods: indirect methods, direct methods, and dynamic programming. Indirect methods use variational principles to determine the first-order necessary conditions for the optimal control problem, transforming the problem into a boundary value problem, and finally solving a set of differential equations that satisfy specific boundary and internal conditions to obtain the optimal solution. Unlike indirect methods, direct methods do not solve differential equations. Instead, they discretize the state variables and control variables in the optimal control problem, transforming the original continuous problem into a discrete nonlinear optimization problem. Then, numerical methods such as direct shooting, direct multiple shooting, or direct collocation can be used to solve for the optimal value. Dynamic programming decomposes complex optimal control problems into a series of simple sub-problems, and then obtains the global optimal solution through local solutions of the sub-problems. However, as the state space increases, the computational time complexity of dynamic programming grows exponentially. Therefore, researchers have developed approximate dynamic programming methods that use approximation techniques to solve large-scale complex system problems.
Bio-inspired techniques utilize ideas obtained from observing nature’s responses and behaviors to different things to solve complex problems, which are considered to have uncertain and imprecise characteristics, obtaining robust solutions at minimal cost. Common methods used for ship trajectory optimization and obstacle avoidance include: Artificial Neural Networks (ANN), Artificial Bee Colony (ABC) algorithm, and Fish School Search (FSS), etc. ANN processes information by simulating the processing methods of neurons and can be used to predict and generate smooth ship navigation trajectories while considering obstacles and dynamic environment constraints. FSS finds the optimal solution by simulating the foraging, predator avoidance, and group cooperative behaviors of fish schools. In ship trajectory optimization problems, FSS can effectively handle complex constraints and dynamic environments. ABC finds efficient trajectory solutions by simulating the dance and information exchange behaviors of bees, while avoiding obstacles and the influence of the dynamic environment.
Ship trajectory optimization is a complex problem with multi-modal constraints. Using a single optimization method alone is difficult to meet the requirements of multiple objectives. Integrating multiple optimization methods can combine the advantages of each method, achieve balanced optimization of multiple objectives, and improve the robustness of trajectory optimization to adapt to complex maritime environments. To address the situation where there are few non-dominated solutions for multi-objective optimization problems, incorporating operations such as crossover and mutation from genetic algorithms into the ant colony algorithm can effectively expand the optimization solutions for ship multi-objective weather routing. Dynamic programming can handle decision-making problems with multiple stages, while heuristic algorithms have fast solving speeds. Combining the two can quickly find feasible optimized trajectories in complex environments.
Prospects
With the development of artificial intelligence technology and computer technology, technological products such as autonomous vehicles and autonomous robots have been successively implemented, while the field of autonomous ship navigation still awaits research. This article summarizes the development trends of ship online motion planning algorithms in recent years from the aspects of path planning and trajectory optimization. Based on the current research status of such methods, the following prospects are proposed:
1. Hybrid Planning
Currently, research on offline planning methods is relatively mature, capable of generating predetermined paths based on global map information and avoiding static obstacles such as islands and static buoys. However, the actual ship navigation environment changes in real-time, and applying offline planning cannot meet the needs of dynamic obstacle avoidance. Online planning is based on online perception information and can perform tasks with high real-time requirements. However, using online planning as a separate system cannot consider the global information of ship navigation, easily leading to problems such as local minima and ships entering dead zones. Therefore, hybrid planning combining offline and online planning is an ideal solution, where offline planning incorporates some obstacle avoidance rules from online planning, and online planning uses offline information as constraints.
2. Hierarchical Planning
In actual ship navigation, using a single method alone often cannot provide a feasible planning solution. A feasible approach is to adopt a hierarchical planning strategy for specific navigation scenarios, i.e., front-end path search and back-end trajectory optimization. The front-end search must ensure the real-time and rapid generation of an efficient and safe optimal path, while the back-end optimization, based on the ship’s dynamic characteristics and sea area conditions, applies various constraints and objectives, considers the time dimension, and uses numerical optimization and other methods to finally generate a feasible ship motion trajectory.
3. Integration with Tracking Control Methods
Common ship planning methods involve planning and optimizing a feasible navigation path at the front end, and then the underlying controller performs tracking control according to the planned path. The real-time performance of these methods largely depends on the speed of the front-end planning, and the actual tracking effect of the underlying controller restricts the real-time planning of the ship to a certain extent. Applying tracking control methods to the path planning problem, so that tracking control signals are output simultaneously while planning the path, would greatly improve planning real-time performance. Therefore, the integration of planning methods and tracking control methods will be one of the future research directions.
4. Multi-Algorithm Fusion
Ship online motion planning is a complex problem. Using a single algorithm alone is difficult to solve the problem and does not conform to practical applications. Multi-algorithm fusion can integrate the advantages of various algorithms, enhance system robustness, improve algorithm generalization ability, and adapt to various complex scenarios in ship navigation. Therefore, how to efficiently fuse algorithms and improve the comprehensive performance of the fused algorithms to achieve optimal motion planning is a future research direction for ship motion planning.
Author: Chen Weibang Li Shijie Liu Jialun Yang Fan
