1   Introduction

Inland waterways are the origin of civilization. Even in modern society, people still rely heavily on inland waterways for their livelihoods. Populations are often concentrated in inland river basins such as the Amazon, Nile, Yangtze, Pearl, Rhine, and Mississippi Rivers. At the end of 2020, the navigable mileage of China's inland waterways was 127 700 kilometers, ranking first in the world (Liu, 2021). In China, the main stream of the Yangtze River is more than 6 300 kilometers long, with a basin area of about 1.8 million square kilometers, accounting for roughly 18.8% of China's land area. The population of the Yangtze River basin is over 460 million, about 33% of China's population. The gross output of the Yangtze River basin makes up around 34% of national GDP (Ministry of Ecology and Environment of China, 2022). However, frequent inland flood disasters result in enormous economic losses, damage to cultural heritage, environmental impairment, and loss of life (Borowska-Stefańska et al., 2023). Between 2000 and 2019 there were 3 254 floods globally, affecting 1.65 billion people (Mizutori and Guha-Sapir, 2020). It is estimated that between 1870 and 2016, floods affected on average 0.03% of the European population per year, causing damage equivalent to 0.08%-0.09% of GDP (Paprotny et al., 2018). In comparison with developed countries, developing countries are more likely to suffer from human casualties and economic losses due to their weak economic base and imperfect flood prevention and control systems. The catastrophic floods in India in June 2013 led to more than 5 000 deaths (Hirabayashi et al., 2013). It is estimated that there are up to 20 000 deaths and over 25 million people displaced by floods worldwide each year (Kellens et al., 2013).

Floods accounted for 38.4% of global natural disasters in 2017 (Li et al., 2019). In responding to floods, it is important to both recover from the disaster and establish a local flood protection system (Borowska-Stefańska et al., 2023). As an important part of the local flood protection system, inland waterway rescues are necessary and urgently needed to minimize injuries, deaths, and property damage. Emergency rescue vessels (ERRVs) are an important component of national emergency and security systems. ERRVs provide medical after-care facilities and mechanical recovery devices for timely salvage and rescue. They are also equipped with engineering machinery for conducting disaster relief work such as piling, closuring breach, riprapping, and dredging. These vehicles are often large and heavy with abundant equipment and machines, and cannot sail through narrow inland waterways. Traditional scheduling programs that rely on expert knowledge and experience may not succeed in reaching rescue points within complex inland water areas. Path planning for ERRVs is necessary to avoid stranding in complex inland waterways leading to failure of rescue operations, and better ERRV path planning is critical to improve the efficiency of the rescue. Therefore, quick planning of an optimal route in complex and changing inland waterways is a key technical problem that needs to be solved urgently.

While path planning studies are popular, most of them are focused on overland vehicles. There are few studies for path planning of ERRVs, especially for inland rivers. In this paper, an improved artificial potential field (APF) algorithm is developed to optimize the paths of inland ERRVs with short response times and sailing distances. A smoothing strategy based on the improved repulsive potential field is also proposed to simulate the dynamics characteristic of inland ERRVs, including rapid speed and underdriven navigation. The Yangtze River basin was selected as the study area and eight tests were conducted based on its conditions to verify the proposed path planning model.

2   Literature review

Most current studies emphasize vessel scheduling for different rescue scenarios (Ma et al., 2023), while vessel-specific path planning has rarely been investigated (Xiong et al., 2020). Due to the intricate changes of inland flood disasters, a quick response under complex conditions is required. Fast and accurate path planning is key to increasing rescue efficiency of ERRVs and for human and property protection (Zhang et al., 2021). Path planning and decision making for inland ERRVs are inherently complex tasks, influenced by a multitude of factors such as waterline, wind speed, sail speed, and disaster losses. Hence, path planning for inland ERRVs is a typical non-deterministic polynomial (NP) hard problem (Pinedo, 2022). To solve such a problem, there are three types of algorithms: intelligent algorithms, sampling-based algorithms, and traditional algorithms (Table 1).

Intelligent algorithm is a general term for bionic algorithms and machine learning algorithms. In recent years, intelligent algorithms have been widely used to improve the performance of computer-assisted decision-making processes. Most intelligent algorithms including genetic algorithms (GA) (Pehlivanoglu and Pehlivanoğlu, 2021), neural network algorithms (Sung et al., 2021), metaheuristic optimization algorithms (Khan et al., 2020), and deep reinforcement learning (DRL) algorithms (Lan et al., 2024) have been applied in path planning for different vehicles and vessels. For specific vessel path planning, the complexity of obstacle situations makes it difficult to adapt a single intelligent algorithm to simulate the environment. Therefore, hybrid algorithms are commonly used (Wang et al., 2021b). Li et al. (2021) proposed autonomous collision avoidance path planning by combining a DRL algorithm with an APF algorithm. Lyridis (2021) improved an ant colony optimizer (ACO) with Fuzzy Logic to address the multi-objective problem of unmanned surface vessel (USV) path planning and obstacle avoidance. However, after making such improvements, the intelligent algorithms took longer to solve path planning problems (Gan et al., 2022), which is not conducive to quick responses to dynamic and complex floor disaster relief works.

The rapidly random tree (RRT) algorithm is the most widely used sampling-based algorithm for path planning. It is able to quickly find a satisfactory path with simple obstacle modeling (Liao et al., 2021). However, under sampling-based algorithms, there are redundant points in planning paths (LaValle, 1998), leading to an unsmooth path. Therefore, many studies adopting sampling-based algorithms have focused on how to smooth the paths. Chi et al. (2022) utilized the generalized Voronoi diagram (GVD) feature matrix to fuse the nodes to plan a smooth path for mobile robots. After generating the path with the RRT algorithm, Cao et al. (2022) used the three-order B-spline curve to obtain a smooth path. Although there are plentiful similar studies, smoothing does not often work well for RRT algorithms, especially when the path is long (Yu et al., 2024; Ye et al., 2023; Tu et al., 2024). Additionally, sampling-based algorithms suffer from high randomness and are non-optimal (Cao et al., 2022).

An artificial potential field (APF) algorithm is often used in vessel path planning for simplicity and real-time performance (Gan et al., 2022). This elegant algorithm is widely used in unmanned aerial vehicles (Zhou and Kong, 2022), vessels (Lyu and Yin, 2019), and robots (RodríguezGuerra et al., 2023). Since the original APF algorithm is prone to fall into local minimum, numerous improvements have been made in recent studies (Ni et al., 2021; Liu et al., 2024a). Liu et al. (2024b) introduced dynamic perturbation to address the local minimum problem. The A* algorithm is also used to combine with the APF algorithm to enhance the global search capability (Sang et al., 2021; Rao et al., 2023). The paths generated by this integrated algorithm are smooth and generally no additional smoothing strategies are required.

To sum up, intelligent algorithms are inadequate for path planning of inland ERRVs, because flood disasters that occur in rivers often change rapidly. There might be limited time to learn the data and run the whole program of intelligent algorithms. Moreover, inland rivers are not straight lines, but have numerous obstacles under water. The complex environment of inland water areas makes it difficult to generate smooth paths by sampling-based algorithms. The planning of a suitable path for ERRVs within an acceptable time plays an important role in flood rescue projects (Ozkan et al., 2019). To fill this gap, it seems that the APF algorithm is the best option for path planning of ERRVs in complex inland waters. Therefore, this paper proposed an improved APF algorithm by avoiding local minimum problems and the proposed method was applied to solve path planning problems for inland ERRVs.

3   Methodology

3.1   Traditional APF

The artificial potential field (APF) is a virtual force method proposed by Khatib (1985). APF sets the gravitational field at the destination and the repulsive field at the obstacles. The algorithm ensures the objects approach the destination while avoiding obstacles. To solve path planning of inland ERRVs, the original position of the ERRV is expressed as X = (x, y). The position of the goal of the ERRV is represented as X_t = (x_t, y_t), and the position of the obstacle from the original position to the goal is represented as X_o = (x_o, y_o). The gravitational potential field function is defined as:

where λ is gravitational parameter, and R the distances between the original position of the ERRV and the goal, which can be defined as:

The goal position exerts a gravitational force on the ERRV. The magnitude is the negative gradient of the gravitational potential field function, such that:

The repulsive potential field function is defined as:

where U_r is the repulsive force field generated by the obstacle on the ERRV, μ the repulsive force parameter, and α_o the radius of influence of the obstacle. When the ERRV was out of the radius (α_o), the obstacle had no repulsive influence on the ERRV. r is the distances between the current state of the vessel and the obstacle, which can be defined as:

The obstacle exerts a repulsive force on the ERRV as:

The combined force on the ERRV is:

where i is the number of obstacles and F_rⁱ the repulsive force of the i^th obstacle on the ERRV.

The traditional APF method benefits from concise modeling, high efficiency, and rapid speed of convergence, which can satisfy the local dynamic obstacle avoidance of the ERRV. Nevertheless, the traditional APF method has planning failures in some cases. For example, when the distance between the goal and the obstacle is close, the gravitational force tends to reduce and the repulsive force increases. The path planning could fail as the combined forces of the ERRV are directed away from the goal (see Figure 1). If the combined force on the ERRV is 0 or if the gravitational and repulsive forces are co-linear (see Figure 2), the vessel will appear to stall or wander in a localized area. Thus, it falls into a local minimum.

Figure  1  Failure case of APF method (unable to reach the goal)

Download: Full-Size Img

Figure  2  Failure case of APF method (stuck in a local minimum)

Download: Full-Size Img

3.2   Improved APF for inland river ERRVs

Compared to the navigable environment at sea, inland waterways are narrow and shallow (Bolbot et al., 2020). Flood disasters occurring in inland water areas often create an even more complex and dangerous environment, such as converging waters, curved waters, and vortexes. (Roeleven et al., 1995). The poor natural conditions of inland waters make the passage of ERRVs difficult. To address the path planning failures of traditional APF algorithms, a series of improvements can be made, including repulsive potential field correcting, virtual obstacles setting, and path smoothing.

3.2.1   Repulsive potential field correcting

A correction of a repulsive potential field function is amended as U_rg, expressed as Equation 8. A parameter β included in the corrected repulsive potential field aims to fix the direction of the combined force biased towards the destination. The value of β is between 0 and 1.

After the improvement of the APF algorithm, additional force directed at the goal is applied. The distance R between the original position of the ERRV and its goal position is taken as the influence factor. The negative gradient of the repulsive potential field function on the ERRV is expressed as:

From Equations 11 and 13, only when the value of β is between 0 and 1, as the value of R decreases, the force F_rg2 pointing toward the goal becomes lager and the force F_rg1 back away from the obstacle becomes small. In this case, the direction of the combined force on the ERRV is constantly corrected toward the goal, and thus it will continually move to the goal. The distinct angle θ of bias toward the goal being marked in Figure 3. The value of angle θ is expressed as Equation 14. The corrected repulsive field decreases due to proximity to the goal, which visually explains the role of F_rg2 (as shown in Figure 4).

Figure  3  Force diagram after modification of the repulsive force

Download: Full-Size Img

Figure  4  Example of repulsive potential field correcting

Download: Full-Size Img

3.2.2   Virtual obstacles setting

Large obstacles or U-shaped obstacles may cause local minimum issues, as the combined force could become 0 before reaching the goal. Virtual obstacles are set to address this flaw. The specific flow of the improved algorithm is shown in Figure 5. When the combined force of the ERRV is 0 in path planning, it is determined whether the goal is reached. If not, it is concluded that it is in a local minimum and the virtual obstacle will be set. The virtual obstacle is a solid circle with radius ρ and center's coordinates (x + m, y + n), denoted as O_v(x + m, y + n, ρ). Coordinates (x, y) is the coordinate of the local minimum point in this path planning. Virtual obstacles at (x, y) will fail to resolve the co-linear situation. Therefore, the virtual obstacle is set near the local minimum point by randomized correction parameters m and n. The vessel will not be stuck in this local minimum further, as shown in Figure 6(b). With this virtual obstacle in place, the path is re-planned and the combined force detection mentioned above is repeated. If a local minimum issue occurs again, new virtual obstacles will be set until the goal is reached.

Figure  5  Flowchart of path planning for the introduction of virtual obstacles

Download: Full-Size Img

Figure  6  Example of trajectories with and without virtual obstacles

Download: Full-Size Img

3.2.3   Path smoothing

Considering the complex inland water environment and traveling characteristics of ERRVs (i. e., a certain turning radius, heavy weight, and high inertia), a smooth path is desired in the planning. Previous path smoothing strategies frequently used cubic spline (Li et al., 2021); however, cubic spline fails to guarantee the smoothness of the entire curve, and additional nodes to avoid local smoothness would significantly reduce the efficiency (Silverman, 1985). A smoothing strategy for ERRVs is thus developed by amending the repulsive potential field function to make the transit smoother. On the basis of Equation 8, the repulsive potential field function is modified as:

n: correction factor for the distance between the ERRV and the obstacle, n > 1.

The repulsive force in the direction of the line joining the ERRV and the obstacle in the range r ≤ α₀/n + 1 is as follows:

The repulsive effect of the goal on the ERRV (F_rs2) is not taken into account. The magnitude of the repulsive force varies more smoothly with the improvement. n determines how the repulsive forces vary smoothly with r. The repulsive force on the ERRV is similar to the original with smaller n, and change more smoothly with larger n (as shown in Figure 7).

Figure  7  Comparison of repulsive force magnitude

Download: Full-Size Img

With parameters other than n determined, the repulsive force on ERRV is compared as the distance r from the obstacle varies. Traditional. The AFP algorithm has excessive repulsion variation near obstacles, as shown in Figure 7. In large maps, even a tiny increase in α0 could result in significant improvements. This leads to inevitable sharp corners in the path (Figure 8(a)). With the improved APF algorithm, the trajectory obtained is smooth without sharp corners, as shown in Figure 8b. The exact value of n is related to numerous factors, such as the map size, the complexity of the map, etc. It is recommended to refer to Equation 16 for the approximate value of n:

Figure  8  Example of trajectories by initial and smoothing strategy

Download: Full-Size Img

The improved APF algorithm is given in Algorithm 1.

4   Case study

The inland river ERRV in Anhui Province was chosen as a case study to verify the proposed path planning method. The case study ERRV belongs to modernized multifunctional vessels, as shown in Figure 9. The vessel was equipped with plenty of engineering machines, including a crane with a capacity of 120 tons, a packing machine, and trebuchet to support flood rescue works. The ERRV thus has large loads that make it difficult to sail in the complex inland waterways. Considering the urgency of flood rescue efforts, a rapid response speed is required and a smooth path for the ERRV. Therefore, planning algorithms are needed to consider the typical characteristics of the ERRV (see Table 2).

Figure  9  An inland river ERRV

Download: Full-Size Img

Anhui, a key province in the lower reaches of the Yangtze River, collaborates with Shanghai, Suzhou, and Zhe-jiang to create a world-class port cluster in the Yangtze River Delta. In 2023, the mileage of high-grade waterways in Anhui Province with four or more levels exceeded 2 360 kilometers, ranking third in China (Fan and Xu, 2023). With such long and complex waterways, Anhui often suffers from flood disasters. The path planning of the ERRV is important to secure life and property safety in Anhui. In the current study, two Yangtze River areas in Anhui Province were selected as experimental scenarios for the case study, using MATLAB R2022b on a personal computer with 11th Gen Intel^® Core^TM i7 and 16 GB RAM.

The land cover data used in the case study was obtained from the open database GlobeLand30 (National Geomatics Center of China, 2024) and was converted to binary data on the river channel (see Figure 10). As ERRV is used as an emergency rescue, a service range of 10 to 15 km is appropriate based on an arrival time of 45 minutes. Two typical areas were selected, represented as Area 1 and Area 2. Area 1 was a 20 km square area (center coordinates 118°20′21.008″E, 31°28′13.473″N) and Area 2 was a 15 km square area (center coordinates 117°27′52.233″E, 30°43′23.276″N). Both areas were pre-treated with 2 000 units of length and width. Eight tests were carried out in two areas and the start and target coordinates are shown in Table 3. Traditional APF algorithm and RRT algorithm were included in tests as a comparison. In addition, the basic parameters set for algorithms are shown in Table 4.

Figure  10  GIS data in the case

Download: Full-Size Img

5   Results

The results of eight path planning tests are illustrated in Figure 11, where black lines represent paths planned by the improved APF algorithm, pink lines represent trajectories planned by the traditional APF algorithm, and blue lines represent paths estimated by the RRT algorithm. Since the RRT algorithm is not successfully planned the tree-like paths, paths planned by RRT algorithm are not shown in Figure 11(f) and Figure 11(g). The results indicate that the improved APF algorithm used in the case study achieved the desired trajectories. The improved APF algorithm achieved all planned paths to the goal successfully in eight tests, while the traditional APF algorithm achieved twice and the RRT algorithm achieved six tests. The traditional APF algorithm was trapped at the edge of huge obstacles for tests 1, 4, 5 and 7. The improved APF algorithm enhanced the obstacle's reach (as shown in Figure 8), which attenuated the influence of the obstacle edges and prevented the ERRVs from being only locally optimal at the obstacle edges. For tests 3 and 8, the traditional algorithm was stuck in the U-shaped obstacle region and could not proceed further. Virtual obstacles were set up and used to escape from the U-shaped region in the improved algorithm.

Figure  11  Planning path for tests

Download: Full-Size Img

A comparison of the planned paths of tests 2 and 6 were shown in Figures 12 and 13 by calculating the curvatures of the entire paths. All algorithms were successful in providing the planned paths for test 2. Significantly, all APF algorithms planned smoother paths than RRTs, as shown in Figure 12(a), 13(a), and 13(b), which is consistent with Gu et al. (2023). Furthermore, a comparison of the two planned paths in tests 6 indicated that the paths estimated by the improved APF algorithm had the smallest curvature float range. The trajectory estimated by the traditional APF were affected by the irregular edges of the obstacles, which moved around the obstacles, as shown in Figure 12(b). The improved APF algorithm suggested an optimized path to elude obstacles, resulting in smoother path. In test 6, the curvature of the initial APF trajectory was even above 1, while the curvature of the improved APF trajectory was always fluctuating around 0, as shown in Figures 13(c)-13(d).

Figure  12  Localized enlarged view

Download: Full-Size Img

Figure  13  Curvature comparison

Download: Full-Size Img

The response time and number of iterations for both algorithms are described in Table 5. The results demonstrated that all APF algorithms performed more efficiently than the RRT algorithm significantly, which is consistent with Li et al. (2021). In test 2, the trajectory estimated by the improved APF algorithm was solved with 1 245 iterations, which was less than the traditional APF algorithm. This indicated that the relatively smoother path was solved by the improved algorithm in fewer steps. The response times of both APF algorithms were relatively close, but the time used by the improved APF algorithm (i. e., 8.38 s) was shorter than the traditional algorithm (i. e., 8.56 s). With the existing inland waterway GIS information, the improved APF algorithm responds quickly and successfully gives applicable paths for ERRVs.

6   Discussion

The test results demonstrated that the traditional APF algorithm tended to be inadequate for path planning of the ERRV in a complex inland water environment, which was consistent with previous studies (Gan et al., 2022; Jadhav et al., 2023). There are many narrow channels in inland rivers that lead to failure of path planning, as shown in tests 4 and 7. When large obstacles and barriers appear, there is likely to be poor performance of the traditional APF algorithm (e.g., tests 1, 3, and 8). The improved APF algorithm was shown to achieve better performance than the traditional algorithm for the destination approach of the ERRV

Besides destination approach, the improved APF algorithm was shown to be more efficient than the traditional APF algorithm in path planning of the ERRV. In the past, intelligent algorithms such as A* and RRT were often applied to avoid obstacles in planning appropriate path of different vehicles (Sang et al., 2021). The application of intelligent algorithms improves the overall search capability of the APF algorithm in a limited way but sacrifices the efficiency. In this study the proposed algorithm, based on the underlying layer of the algorithm, preserved the efficiency with fewer iterations and less response time (referred to Table 5).

To accommodate the dynamics of ERRVs, smooth paths are necessary. Instead of taking an additional curve fitting as most strategies do (Liu et al., 2024a), this study varies the gradient of the repulsive potential field to achieve a natural smooth path. In fact, additional fitting is necessary in the calculation process of some mainstream algorithms (e. g., RRT), because the generated paths are extremely convoluted. The proposed approach adds no extra computation, which increases algorithmic efficiency. The improved APF algorithm gave planning paths in only eight seconds when dealing with extreme maps with 4 000 000 units, which was only 0.05 time that of the RRT algorithm in some scenarios. It was shown that the improved APF algorithm was capable of planning paths to nearly ten different targets every minute in a real rescue application.

The proposed path planning algorithm could be applied beyond ERRVs. The traditional APF algorithm is sensitive to the parameters, such as the gravitational parameter, the repulsive force parameter, and the radius of influence of the obstacle (Gu et al., 2023). The parameter variations induce changes to the properties of the algorithm (e.g., an increase in the radius of influence of obstacles leads to a path away from the obstacles). The improved APF algorithm retains the original parameters. Therefore, it is necessary to debug the parameters in advance in different application scenarios, which could improve the applicability and feasibility of the proposed method. For example, a more flexible path is possible for vessels with excellent mobility with small n.

7   Conclusion

In light of the growing occurrence of extreme weather events, inland water areas are suffering from frequent flood disasters. The ERRV is one of the most important approaches in ensuring life and property security. However, a complex inland river environment enhances the difficulty of ERRV path planning. This study thus proposes an improved APF algorithm to increase decision-making efficiency for path planning of ERRVs. A case study was conducted with an ERRV serving the water areas in the Yangtze River.

By conducting eight tests in two water areas in the Yangtze River, the improved algorithm was shown to be appropriate for inland river ERRV path planning. The results indicated that 1) the trajectories estimated by the improved APF algorithm successfully achieved the rescue goals in all tests, 2) the improved APF algorithm has high efficiency with fewer iterations and less response time, and 3) it achieved excellent smoothness.

Although this research obtained interesting results for path planning of ERRVs, several limitations still exist. Only eight tests were carried out based on a simulation that had some discrepancy from the real situation. In future studies, an analysis of the proposed algorithm in largescale scenarios would be valuable to increase the scalability to larger or more complex environments. It was assumed that the wave and the wind parameter were constant, which might be inappropriate to accurately reflect the dynamic conditions that ERRVs typically face. Thus, it is suggested that future studies conducting field experiments and realworld trials, especially in flooding disaster conditions, are necessary to capture the full complexity and unpredictability of real-world environments. In order to improve the robustness of the proposed algorithm, it is also expected to consider variable environmental factors such as fluctuating wind and wave conditions based on further real-world experiments. It is also suggested to compare the ERRV's paths planned by the proposed algorithm and the practical paths in realistic flooding disasters. Due to the parameter sensitivity of the proposed algorithm, a detailed parameter tuning strategy is recommended in future studies. It is recommended to further optimize the path planning algorithm in order to make it more compatible with the navigation of ERRVs in harsh environments.