1. Introduction
1.1. Background
Maritime transportation plays an extremely important role in global trade. According to statistics from the international maritime organisation, nearly 80% of global trade comes from the sea (Xu et al., Reference Xu, Ma, Qin and Hu2025). To enhance the efficiency and safety of navigation routes, reasonable path planning plays a significant role in navigation. However, path planning in complex marine environments faces multi-dimensional challenges: the dynamic meteorological and hydrological conditions (such as the wind fields, ocean currents, water depth) and the demand for energy efficiency optimisation under the carbon reduction targets of the international maritime organisation and the limitation of other rules. Therefore, it is meaningful to conduct research on path planning based on a multi-factor and multi-scale A* algorithm for improving the shipping economy and safety.
1.2. Research status
In the current research, many scholars have put forward many excellent ideas for path planning. Du et al. (Reference Du, Liu, Jiang, Cai and He2025) introduced an A* algorithm for dynamically adjusting the path based on traffic conditions. An improved A* algorithm considering multiple factors was designed for transportation vehicles, which divided the patterns into best time, minimum risk and based on task (Niu et al., Reference Niu, Wang, Liu and Yue2025). In the field of ship route planning, Lyu and Yin (Reference Lyu and Yin2019) presented a real-time and deterministic path planning method for autonomous ships which is fast, effective and deterministic. A dynamic weight algorithm was introduced to evaluate the generation value of neighbouring nodes and, finally, the connection forms the path (Zhang et al., Reference Zhang, Cai, Li, Li, Peng and Wang2025). A new type of obstacle avoidance algorithm has been designed (Zhu et al., Reference Zhu, Kong, Wen, Gu, Xue and Huang2025) and Allus and Unel (Reference Allus and Unel2025) introduced an optimised A* algorithm, which enhances the sequence continuity of the target node’s movement and reduces distance-related energy consumption. A graphic segmentation path algorithm that comprehensively considers obstacle density and AIS data was proposed (Yang et al., Reference Yang, Zou, Wu and Chen2025). Also in the field of unmanned underwater vehicles, many scholars have also proposed path planning schemes that can be used for reference and learning in ship path planning. Sun et al. (Reference Sun, Zhang, Li and Zhu2022) presented an optimised D* algorithm which considers the obstacle avoidance and ocean current environment. Meng et al. (Reference Meng, Pu, Yu, Gong and Chu2025) proposed a scheme for dynamically adjusting the path based on the surrounding environmental factors and energy-saving effects, where the planning of merged search tasks was based on a multi-level structure (Wang et al., Reference Wang, Liu, Geng and Zhang2024). Programming has been based on A* and APF mixed with dynamic constraints (Zhang et al., Reference Zhang, Wang and Wu2023). Planning has been based on a multi-strategy artificial bee colony algorithm and combined with angle constraints (Xu et al., Reference Xu, Han, Yin, Yan, Yu and Ma2024).
Recent studies have attempted to integrate the advantages of multiple algorithms. Liao Gongming et al. (Reference Gongming, Hongxiang, Delong and Xiao2025) combined the improved A* with the speed obstacle method (VO) to achieve dynamic and static hybrid collision avoidance, but failed to solve the problem of multi-scale environmental adaptability. Song et al. (Reference Song, Guo and Sui2024) designed a collision risk function to improve the multi-scale A* algorithm, comprehensively considering the movement cost and collision risk to plan the global optimal obstacle avoidance path; however, there is still room for improvement in the ability to avoid dynamic obstacles in changing environments. Some of the algorithms proposed in the research have improved the original ones, but they are applicable to specific regions. Yang et al., (Reference Yang, Zou, Wu and Chen2025) proposed that historical navigation data could be used as a reference factor for path planning, but the design algorithm was targeted to waters with traffic separation schemes. The algorithm designed by Gan et al. (Reference Gan, Zheng, Song, Cui, Shu and Yang2025) takes into account the freeboard height of the vessel and the environmental water depth, and is applicable to vessels navigating inland rivers. Langxiong et al. (Reference Langxiong, Li, Yan, Song, Xiao and Shu2025) has conducted research on the navigation of intelligent ships in narrow waterways. Xu et al. (Reference Xu, Ma, Qin and Hu2025) designed the strategies for coastal navigation of ships. The algorithm designed by Liu et al. (Reference Liu, Zhang, He, Lai and Chu2024) performs raster segmentation on the path, considers its respective factors and then connects them to form a path. Compared with multi-scale algorithms, the algorithm still has a greater computational burden due to considering too many nodes.
The current research primarily focuses on three categories of methods: (1) traditional search algorithms (e.g. A* and its improved variants) achieve static path planning by optimising heuristic functions, but they suffer from inefficiencies in node expansion and excessive path turns (Li et al., Reference Li, Hang, Zhang, Huang and Li2023); (2) bio-inspired algorithms (e.g. ant colony and particle swarm optimisation) can handle dynamic obstacles but are prone to local optima and high computational costs (Zhou et al., Reference Zhou, Yu, Liu, Lu and Zeng2025); (3) deep reinforcement learning methods (e.g. improved DQN) perform well in dynamic environments, but rely heavily on extensive training data and lack interpretability (Wei et al., Reference Wei, Sheng, Xianku and Tongbo2025).
Existing studies exhibit three key limitations. (1) Single-scale search deficiencies: traditional A* algorithms consume excessive time (approximately 96% spent on redundant node expansion) in 200 × 200 grid maps (Li et al., Reference Li, Hang, Zhang, Huang and Li2023), while macro-level path planning lacks refined modelling of local hazardous areas (e.g. vortices and no-sail zones). (2) Insufficient consideration of coupled navigational factors: most algorithms address only obstacle avoidance in ship motion control but neglect critical constraints during navigation. (3) Weak compatibility with regulations: many algorithms fail to incorporate maritime standards such as the four-quadrant ship domain model resulting in paths that do not meet practical manoeuvring requirements (Zhou et al., Reference Zhou, Yu, Liu, Lu and Zeng2025).
1.3. Innovation and contribution
Aimed at the above problems, this study presents a ship path planning algorithm which is based on a multi-scale A* algorithm and takes multiple factors into consideration. A cost function integrating navigational constraints (e.g. environmental factors, regulatory clauses and historical data) and facilitating factors is proposed, where predefined weight coefficients determine the contribution of each factor to the path. This enables optimised path planning under specialised restrictive conditions, such as dynamic positioning systems.
The structure of this paper is organised as follows. Section 2 provides an introduction to the multi-scale A* algorithm. Section 3 presents a multi-factor integrated multi-scale A* algorithm for ship path planning. Section 4 includes experimental simulations and analysis. Section 5 provides the conclusions.
2. Multi-scale A* algorithm
2.1. Traditional A* algorithm
The traditional A* algorithm is a heuristic search method widely used in path planning. This algorithm identifies optimal paths by evaluating the comprehensive cost of each node, with its core principle lying in balancing the relationship between actual movement cost and estimated remaining cost. In practical applications, the algorithm maintains two critical sets: an open set for storing nodes to be evaluated and a closed set for recording processed nodes.
During the path search process, the algorithm selects the node with the minimum comprehensive cost from the open set for expansion. For each expanded node, the algorithm calculates both the movement cost and heuristic estimate for all its neighbouring nodes, as shown by
$$f(n) = g(n) + h(n)$$
The movement cost g(n) represents the actual path length from the start node to the current node, while the heuristic estimate h(n) predicts the remaining path length to the goal. This dual evaluation mechanism enables the A* algorithm to efficiently narrow the search space and rapidly converge to the optimal solution.
While the traditional A* algorithm is simple and efficient, it still faces challenges with high computational complexity when dealing with large-scale environments. This limitation becomes particularly pronounced in applications such as ship path planning, where complex environmental factors must be considered. These shortcomings have motivated researchers to develop various enhanced algorithms, among which the multi-scale A* algorithm stands out as an effective solution to such problems.
2.2. Improved multi-scale A* algorithm
The multi-scale A* algorithm represents an enhanced approach derived from the traditional A* search method, incorporating an adaptive grid resolution mechanism to accommodate varying regional planning requirements. The core principle of this algorithm lies in its hierarchical resolution strategy: employing fine-grained grids in obstacle-dense areas (e.g. coastal waters and berthing zones) to ensure path accuracy, while using coarse-grained grids in open waters to enhance search efficiency (Xu et al., Reference Xu, Xianku and Hugan2023). This multi-resolution characteristic makes it particularly suitable for ship path planning applications, effectively balancing the trade-off between computational complexity and path quality.
The algorithm employs a quad-tree structure to recursively partition the maritime space, with the division depth dynamically adjusted based on regional complexity. As illustrated in Figure 1, each parent node can generate up to four child nodes, and the partitioning process continues until either the node becomes obstacle-free or reaches the predefined maximum depth (Song et al., Reference Song, Guo and Sui2024). Compared with conventional uniform grid methods, this approach significantly reduces redundant nodes and enhances search efficiency.
Schematic diagram of finite-depth quad-tree structure.
The multi-scale algorithm achieves significant improvements in planning speed through rational partitioning of nautical charts. By performing path searches on the generated grid map according to Equation (1), it effectively addresses the high computational complexity inherent in large-scale environments, thereby enhancing the algorithm’s practical applicability.
3. Improved multi-factor algorithm
Traditional A* algorithms rely solely on path length as the primary cost metric, which fails to account for the complex navigational constraints in real-world ship operations. To address this limitation, this section proposes an enhanced A* algorithm that integrates multiple environmental factors. The core innovation lies in extending the conventional cost function by incorporating weighted navigational influences, thereby constructing a comprehensive cost evaluation function that better aligns with practical maritime requirements.
The improved cost function can be expressed as
$$f\left( n \right) = \alpha * g\left( n \right) + \beta * h\left( n \right) + \sum {{w_i}} * {c_i}(n)$$
The meanings and functions of each factor in the formula are as follows.
-
1. Basic path factor
(3)
$$\alpha * g\left( n \right) + \beta * h\left( n \right)$$
retains the path length evaluation of the traditional A* algorithm, where
α, history estimation of cost weight;
β, heuristic estimation of cost weight.
Adjusting the rate of α/β can control the balance of searching speed and the result superiority or inferiority.
-
2. Conditional factor
(4)
$$\sum {{w_i}} * {c_i}(n)$$
${w_i}$
, estimation of cost function, input by the human.Evaluates the compliance of rules, environmental safety, airworthiness, etc. around the node.
3.1. Regulatory and institutional cost function
There are lots of laws and regulations in navigation. This section takes the traffic separate schemes as an example.
Traffic separation schemes are designed to enhance navigational safety in areas with high vessel concentration and restricted manoeuvrability due to limited sea room, navigational hazards, shallow waters or adverse weather conditions, with the primary objective of reducing maritime accidents. The specific purposes include: (1) segregating opposing traffic flows to minimise head-on encounter situations; and (2) reducing collision risks between crossing vessels and those following established traffic lanes.
A vessel using a traffic separation scheme shall follow the COLREGs, as follows:
-
1. proceed in the appropriate traffic lane in the general direction of traffic flow for that lane;
-
2. so far as practicable, keep clear of a traffic separation line or separation zone;
-
3. normally join or leave a traffic lane at the termination of the lane, but when joining or leaving from either side, do so at as small an angle to the general direction of traffic flow as practicable.
As shown in Figure 2, the nautical chart displays the waters near Chengshan cape, where the pink striped area on the right indicates the traffic separation scheme zone. Navigating vessels should adhere to the general direction of traffic flow by using the lane on the starboard side of their forward movement, while maintaining a safe distance from both the coastal traffic zone and the central separation line.
Chengshan cape and its surrounding areas.
The cost function is designed as
$$t(n) = {\tau _1} * {D_s}(n) + {\tau _2} * {D_c}(n)$$
${\tau _1} * {d_s}(n)$
, distance from the central separation zone and its weighting factor;
${\tau _2} * {d_c}(n)$
, distance from the coastal traffic zone and its weighting factor.
Adjusting the rate of
${\tau _1}/{\tau _2}$
can control the balance of the distance with central separation zone and coastal traffic zone.
3.2. Navigation environment cost function
The maritime navigation environment involves multiple constraining factors, with water depth serving as a representative example for analysis in this section.
Water depth constitutes a critical safety factor in ship route planning, directly affecting vessel draft, squat and navigational risks. The water depth cost function quantifies the depth suitability at current node n to prevent vessel entry into shallow waters or grounding hazard zones. To calculate the cost based on the relationship between the current water depth and the safe water depth of the vessel, we provide the detailed design methodology for this function:
$$d(n) = \lambda *\left(1 - {{{D_{depth}}(n)} \over {{D_{safe}}}}\right)$$
$d\left( n \right)$
, water depth estimate function;
${D_{depth}}\left( n \right)$
, current node water depth;
${D_{safe}}$
, threshold of safe water depth for ships;
$\lambda $
, water depth weighting factor.
Moreover, the water depth cost function should be further optimised by incorporating additional factors.
-
1. Seabed composition (mud, rock, sand) differentially impacts grounding risk:
-
• soft substrates (mud, clay), permit smaller threshold;
-
• hard substrates (rock, coral), require larger threshold.
-
-
2. Tidal and dynamic depth compensation:
for long-duration planning (e.g. spanning tidal cycles), tidal corrections must be applied to adjust charted depths,
(7)
$${D_{new}}(n) = {D_{_{depth}}}(n) + \rm{Tide(t)}$$
${D_{new}}\left( n \right)$
, water depth (corrected by tide);
${\mathop{\rm Tide}\nolimits} (t)$
, current tide height.
3.3. Historical data cost function
The historical data cost function quantitatively analyses past navigation experiences to provide data-driven support for route optimisation. By processing historical voyage tracks, it identifies optimal routes under similar seasonal, loading and navigational conditions. These selected routes are then integrated to generate standardised templates. The cost function calculates the Euclidean distance from the current node centre to the template route, expressed as
$$h(n) = \mu * H(n)$$
$H(n)$
, the straight-line distance from the node centre to the template line.
4. Simulation and analysis
4.1. Nautical chart environment
To validate the effectiveness of the improved A* algorithm in ship path planning, we conducted simulation experiments in the Dalian inner harbour waters from the Yalu River Estuary to Fuzhou Bay (as shown in Figure 3). The test area, bounded by longitude 121°36′15″E to 121°43′03″E and latitude 38°54′43″N to 38°58′25″N, was selected for path planning simulation.
Dalian port.
4.2. Route simulation
The maritime chart data were processed using MATLAB to extract critical navigation information. Through a multi-scale algorithm, we performed binarisation and rasterisation of the nautical charts, ultimately generating the simulation-ready map model as illustrated in Figure 4.
Multi-scale rasterised map.
The experimental area highlighted in Figure 3 encompasses typical navigation channels, shallow waters and obstacle distributions, providing a comprehensive testbed for evaluating algorithm adaptability in complex environments. The comparative analysis employs weighted optimisation with course alteration points and shallow-water zone ratio each weighted at 0.3 and path length at 0.4.
We conducted comparative analyses of three distinct path planning strategies.
The simulation results generated on the nautical chart area represented by the red rectangle in Figure 3, are shown on the enlargement in Figure 5.
Route simulation result.
As shown in the figure, the red circle represents the starting point of the path, the blue one is the target point, the black solid line is the traditional A* algorithm path, the green dotted dash line is the path dominated by water depth, and the dark yellow dotted line is the path that comprehensively weighs the factors of water depth and distance.
The combined result is calculated as follows:
$$f(n) = 0.3 * T(n) + 0.3 * S(n) + 0.4 * R(n)$$
$T(n)$
, number of turning points;
$S(n)$
, thousandth proportion of shallow water areas;
$R(n)$
, length of the route.
The performance metrics of the three path planning strategies are compared quantitatively in Table 1.
Comparation of performance
The simulation results demonstrate that while the conventional A* algorithm generates the shortest path, it traverses hazardous areas with minimum depths of only 4.6 m. Conversely, the deep-water route guarantees a water depth of more than 10 m throughout, but results in substantially longer routes with poor economic efficiency. In comparison, the improved A* algorithm achieves an optimal balance between these factors – producing shorter routes that simultaneously avoid extremely shallow waters (minimum depth 8.6 m), increasing the proportion of deep-water segments, and significantly enhancing both navigational safety and economic performance.
5. Conclusion
Ship path planning in complex marine environments needs to consider navigation efficiency, safety, dynamic adaptability and the requirements of navigation practice. Aiming at the problems existing in the global path planning of the existing multi-scale A* algorithms, such as single consideration factors, insufficient obstacle avoidance ability, low path smoothness and difficulty in adapting to the actual navigation environment, this paper proposes an improved A* algorithm that integrates multi-factor heuristic functions and multi-scale rasterisation strategies.
First, based on the electronic chart data, the canny edge detection algorithm is adopted to extract the obstacle contours and, combined with the adaptive threshold binarisation method, a high-precision obstacle map is generated. Based on this, a multi-scale rasterisation strategy is adopted to divide the environment into a coarse-scale (global planning layer) and a fine-scale (local obstacle avoidance area), to improve the adaptability of the algorithm in different scenarios. A coarse-scale grid is used to quickly generate global routes, while a fine-scale grid considers fine obstacle avoidance when the distance to obstacles is relatively close.
Second, during the path search process, a multi-factor heuristic function should be incorporated to comprehensively consider various elements including obstacle density, water depth, wind/wave/current effects, waterway regulations and vessel dynamic constraints. This approach adjusts search weighting to enable the algorithm to generate optimal paths in both open waters and narrow channels. Meanwhile, a curve smoothing algorithm is applied to optimise the initial path, reducing unnecessary waypoints to enhance navigation comfort and fuel efficiency.
Finally, to validate the algorithm’s effectiveness, the Dalian inner harbour waters were selected as the test environment for comparative analysis among three methods: the conventional A* algorithm, multi-scale A* algorithm and our improved approach. The experimental results demonstrate the following.
-
1. Path length optimisation: the path generated by the improved algorithm is a shorter navigation path.
-
2. Reduced turning points: after path smoothing processing, the number of turning points decreases.
-
3. Enhanced obstacle avoidance capability: in environments with dense obstacles, it can still maintain a safe distance and avoid the risk of collision.
Future research will focus on three key dimensions: (1) developing deep reinforcement learning-based dynamic weight adaptation mechanisms to enhance the algorithm’s responsiveness to emergent environmental changes; (2) establishing a multi-vessel collaborative path planning framework to resolve traffic conflicts in congested waterways; and (3) integrating digital twin technology to enable closed-loop validation from path planning to navigation control. These extended investigations will significantly advance intelligent navigation technologies, providing more reliable technical support for autonomous ship operations.
Acknowledgements
This work is partially supported by the National Key R&D Program of China (Grant No. 2022YFB4301402), National Science Foundation of China (Grant Nos. 51679024, 52571396), Dalian Innovation Team Support Plan in the Key Research Field (Grant No. 2020RT08), Fundamental Research Funds for the Central Universities (Grant No. 3132021139), Dalian Maritime University University-level Team ‘Open Ranking’ Project (No. 3132023502).
