Journal Search Engine

ISSN : 1229-3431(Print)
ISSN : 2287-3341(Online)

Journal of the Korean Society of Marine Environment and Safety Vol.29 No.3 pp.281-287
DOI : https://doi.org/10.7837/kosomes.2023.29.3.281

Passage Planning in Coastal Waters for Maritime Autonomous Surface Ships using the D* Algorithm

Hyeong-Tak Lee^*†, Hey-Min Choi^**

^*Post Doctoral Scientist, Korea Ocean Satellite Center, Korea Institute of Ocean Science & Technology, Busan 49111, Korea
^**Researcher, Busan BigData Innovation Center, Busan Techno-Park, Busan 48059, Korea

^† Corresponding Author : htlee@kiost.ac.kr 051-664-3155

Received April 3, 2023 Review May 11, 2023 Accepted May 29, 2023

Abstract

Establishing a ship's passage plan is an essential step before it starts to sail. The research related to the automatic generation of ship passage plans is attracting attention because of the development of maritime autonomous surface ships. In coastal water navigation, the land, islands, and navigation rules need to be considered. From the path planning algorithm's perspective, a ship's passage planning is a global path-planning problem. Because conventional global path-planning methods such as Dijkstra and A* are time-consuming owing to the processes such as environmental modeling, it is difficult to modify a ship's passage plan during a voyage. Therefore, the D* algorithm was used to address these problems. The starting point was near Busan New Port, and the destination was Ulsan Port. The navigable area was designated based on a combination of the ship trajectory data and grid in the target area. The initial path plan generated using the D* algorithm was analyzed with 33 waypoints and a total distance of 113.946 km. The final path plan was simplified using the Douglas–Peucker algorithm. It was analyzed with a total distance of 110.156 km and 10 waypoints. This is approximately 3.05% less than the total distance of the initial passage plan of the ship. This study demonstrated the feasibility of automatically generating a path plan in coastal navigation for maritime autonomous surface ships using the D* algorithm. Using the shortest distance–based path planning algorithm, the ship's fuel consumption and sailing time can be minimized.

Key Words : D* Algorithm , Passage Planning , Coastal Waters , Ship Trajectory Data , Maritime Autonomous Surface Ships

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. Introduction

A navigation officer should establish a passage plan for a ship to its next destination before the ship starts to sail (Chen et al., 2020;Lee et al., 2022a). Passage planning is essential for a ship to complete its voyage safely. Recently, with the active development of maritime autonomous surface ships (MASSs), the research on automating the passage planning of ships as a core technology has received considerable attention (Liu et al., 2016). Therefore, this study intended to investigate the establishment of automatic passage plans for the coastal navigation of MASSs.

The passage planning for coastal navigation has significantly more aspects to consider than that for ocean navigation. For example, narrow channels, navigation rules, water depth, and various obstacles including islands need to be considered meticulously in conjunction with the distance, time, and fuel consumption (Lee et al., 2022a;Wee et al., 2000). Therefore, from the perspective of the path planning algorithm, the passage planning of a ship in coastal navigation is a global path-planning problem. Global path planning generates an optimal path from a given map or other information to reach the desired destination at the minimum cost while preventing collisions with fixed obstacles (Jung et al., 2010). The global path-planning algorithm used to generate the passage plan of a ship is the path search method. Furthermore, research has been conducted using methods such as Dijkstra (Silveira et al., 2019), A* (Sang et al., 2021), and genetic algorithms (Wang et al., 2020). Wang et al. (2019) generated a global optimal ship route using 3D Dijkstra's algorithm to reduce the fuel consumption. Xie et al. (2019) utilized a global multidirectional A* algorithm for the route planning of a ship operating within an offshore wind farm. Sang et al. (2021) generated globally optimal routes for unmanned surface vehicles by using an improved heuristic A* algorithm. Grifoll et al. (2022) utilized the A* algorithm to implement software for ship weather routing and optimized the ship route as a function of wave action. Lee et al. (2022a) generated the shortest-distance passage plan for ships using automatic identification system (AIS) data and utilized the Dijkstra, A*, and improved A* algorithms. In general, because global path planning is time-consuming owing to processes such as environmental modeling, it is difficult to modify the passage plan of a ship during a voyage when required. Therefore, this study used the D* algorithm. It addresses the limitations of these global path-planning algorithms.

The study was conducted based on the experimental environment used in a previous study (Lee et al., 2022a). Accordingly, the target areas were near Busan New Port and Ulsan Port in the Republic of Korea. In addition, the trajectory data of the ship sailing through the target area were collected and used to generate a path plan. Because many of the vessel track data are records of the safe navigation of ships, these can be regarded as the results of a sufficient consideration of various obstacles including the water depth, land, and islands. Therefore, path planning in coastal navigation using ship trajectory data can reduce the uncertainty and increase the efficiency (Lee et al., 2022a;Silveira et al., 2019).

In this study, the navigable area was designated based on the results of combining the trajectory data and ship grid in the target area. Thereafter, based on information from electronic navigational charts (ENCs), the non-navigable areas such as restricted areas were designated by referring to the navigation rules. Subsequently, through density analysis, the grids with high vessel traffic were extracted, and the final navigable area was designated. Based on the derived navigable area, the path planning for MASSs was generated using the D* algorithm. Subsequently, the result of applying the D* algorithm was simplified by removing the unnecessary waypoints using the Douglas–Peucker algorithm (DPA). Finally, the passage plan of the ship and the results of this study were compared.

This paper proposes a path-planning algorithm based on the shortest distance that can minimize the fuel consumption and sailing time in coastal waters. Furthermore, unlike existing path planning studies, a ship's passage plan can be generated automatically using a data-driven approach. Because it refers to existing ship-voyage records, this study can help improve the navigation safety and efficiency of ships. Furthermore, it can serve as a basic study in the field of MASS path-planning.

2. Materials and Methods

The input data were set based on the geographic information of the target area and the trajectory data of the ships that navigated the target area. Thereafter, a grid map was constructed for the target area and combined with the ship trajectory data. Next, information from the ENC was input to designate the navigable area, and ship density analysis was performed to derive the route navigated by the ship. After designating the navigable area, the D* algorithm was applied. The results of the D* algorithm were supplemented with the DPA. A flowchart of the study is shown in Fig. 1.

2.1 Target Area and Ship Trajectory Data

The target area of this study comprised Busan New Port and Ulsan Port. These have the highest volumes of ship traffic in the Republic of Korea (Kweon et al., 2022;Lee et al., 2021a). The details of the target area are as follows: latitude 034.6 N–035.6 N and longitude 128.6 E–129.8 E around Busan New Port to Ulsan Port. The study aimed to generate a passage plan from Busan New Port to Ulsan Port. Therefore, the starting point of this study was Busan New Port, and the target point was Ulsan Port. To apply the D* algorithm, a grid map was constructed within the target area. The grid pixel size was set to 0.01 × 0.01°. An eight-way search was used as the algorithm-application principle (Lee et al., 2022a;Sun et al., 2021).

The ship trajectory data used in this study were collected using an AIS installed on a ship (Lee et al., 2021b;Lee et al., 2022a). The collection period was August 1–7, 2021, and cargo ships specified in the AIS information were targeted. A total of 691 cargo ships passed through the target area during this period. The number of AIS data points was 1,323,472. The ship trajectory data were preprocessed by removing erroneous or missing information. Moreover, the data involving a speed of at most three knots were deleted to exclude anchored and berthed ships. Table 1 summarizes the AIS data used in the study.

The geographic locations of the target area, grid map, and ship trajectory data are shown in Fig. 2. In addition, an overview of the eight-direction search is provided.

2.2 Navigable Area

In this study, the navigable area was defined as a designated grid on which the D* algorithm could be applied and a ship could navigate safely. The navigation area was determined using the following methods. The first method combined the ship trajectory data and a grid map to select the area containing the data. Next, the navigation rules were applied using the ENC information, and the grids in which ships could not navigate were excluded. Finally, through a density analysis of the ship trajectory data included in the grid map, the grid in which a small number of ships sailed was excluded from the navigable area.

First, the grid maps and ship trajectory data were combined, and the grids without data were removed. The remaining grid cells became areas where the ships could navigate. Thus, land, islands, as well as areas where ships do not typically navigate were removed. Furthermore, because the grid with ship trajectory data was a record of the safe navigation of the ship, the water depth could be regarded as having been considered. Therefore, a data-based approach is suitable for path planning for the coastal navigation of ships (Lee et al., 2022b).

Second, the ENC information such as the restricted area, traffic separation scheme (TSS), and vessel traffic service system (VTS) control area was referred to. Using this information, we removed the grids through which the ships should not navigate. The ENC is an international standard vector chart displayed on electronic charts and information systems (Lee and Suh, 2000). It is used by navigation officers to collect navigation information while establishing a ship passage plan. Therefore, using ENC, the information referred to by navigation officers can be reflected directly in the path-planning algorithm.

Finally, a density analysis was conducted to extract the grids with high vessel traffic and remove those with a small number of ships (Lee et al., 2022b). In this study, density was divided into 10 stages using the equal-interval method (Lee et al., 2022a). Furthermore, the study aimed to complete the final navigable area by removing the grid cells of the stage with the lowest density.

2.3 D* and Douglas-Peucker Algorithm

The D* algorithm, called dynamic A*, is a heuristic search algorithms that minimize the path cost from the start point to the target point (Jung et al., 2010;Stentz, 1997;Yu et al., 2022). Unlike the A* algorithm, which follows a path from the start to the target point, the D* algorithm searches backward from the target point. In path planning using the D* algorithm, the next node can be referred to through the backpointer of each grid cell, (see Fig. 3). That is, the backpointer indicates the node with the smallest path cost among nearby nodes.

The path cost h (X ) of the D* algorithm is the total path cost required to reach node X . Y is the node immediately before the node X . c (Y ,X ) is the proximity path cost. It indicates the path cost from the previous node Y to the node X . It is expressed by the following equations:

h (X) = h (Y) + c (Y, X)

(1)

c (Y, X) = A (Y, X) + I (X)

(2)

In Eq. (2), A(Y, Z) is the cost of moving to node X and Y , and I (X ) is a cost function considering adjacent obstacles as the characteristic cost of the node. When a new obstacle is identified, the characteristic cost near the new obstacle is modified based on the existing path-planning results. Thereafter, the path cost and backpointer of the surrounding nodes are modified accordingly. Therefore, when the path plan needs to be modified or when there are obstacles, the D* algorithms can transform conveniently in real time unlike the A* algorithms (which need to reconstruct a map based on new environmental information to identifies a new path).

The A* algorithm identifies a new route by reconstructing the environment to establish a passage plan. However, based on the global path planning performed earlier for a given environment, the D* algorithm performs local path planning only in the necessary area (Jung et al., 2010). Therefore, if a military-exercise area is present or an offshore wind farm is installed at sea, the D* algorithm is more advantageous than the conventional Dijkstra, A* algorithm in generating a ship's passage plan.

Path planning using the D* algorithm generates many waypoints, many of which are unnecessary (Lee et al., 2019;Lee et al., 2022a). Therefore, the unnecessary waypoints need to be removed through postprocessing that simplifies the results. In this study, the DPA was used to simplify the path (Douglas and Peucker, 1973). The DPA identifies a straight line connecting the start and target points from the initial result and the farthest waypoint from the straight line. If the distance is larger than a set threshold, the farthest point is maintained. This process is repeated for all the waypoints in the initial results. The waypoints smaller than the threshold are removed, and a simplified path is obtained. If an appropriate threshold value is not set and it increases, the optimal solution may be lost. Therefore, an appropriate value should be selected. In this study, this value was derived by inputting and comparing various threshold values.

3. Results

3.1 Designation of the Navigable Area

Before applying the D* algorithm to MASS passage planning, the navigable area was designated. The grid map was combined with the AIS data, and the grid pixels without AIS data were deleted. In this process, the areas that were typically not navigated by ships (including land, islands, and obstacles) were removed. Thereafter, it was applied to the navigable area by referring to ENC information such as the restricted area, TSS, and VTS control areas. The areas within the restricted area and Busan Port VTS control area were excluded from the navigable area. The experiment was performed by considering the VTS control area as an obstacle to the experimental environment. In addition, for the TSS near Busan New Port, the grid pixels of the port arrival direction were deleted from the navigable area.

Finally, the density was analyzed using the equal-interval method. The number of ship-trajectory data points included in a grid cell ranged from 1 to 1159. The color of each stage and number of ship-trajectory data points were analyzed, as shown in Table 2. As a result of the division of the density analysis into 10 stages, the grid corresponding to the 0 stage with the lowest density was excluded from the navigable area.

The final designated navigable area after completing the density analysis is shown in Fig. 4. As illustrated in the figure, we aimed to generate path planning for coastal navigation by MASSs using a grid map corresponding to a designated navigable area.

3.2 Application of the D* Algorithm

In this study, the D* algorithm was applied based on the navigable area to generate a passage plan for MASSs. The results of applying the D* algorithms from the pilot disembarkation location of Busan New Port (the starting point) to the pilot station of the target point (Ulsan Port) are shown in Fig. 5. By applying the D* algorithm, the distance was determined to be 113.946 km, and the number of waypoints was 33. The results derived using the Dijkstra, A*, and improved A* algorithms by Lee et al. (2022a) were 112.173, 112.172, and 109.888 km, respectively. Although the results of using the D* algorithm increased the distance compared with the Dijkstra, A*, and improved A* algorithms, these three algorithms have the disadvantage of obtaining results that are significantly close to the VTS control or restricted areas.

As shown in Fig. 5, the result of the initial path plan generated using the D* algorithm is complex with many unnecessary waypoints. Therefore, the initial result was simplified using the DPA, and the unnecessary waypoints were deleted.

3.3 Final Passage Plan

To generate the final passage plan for coastal water navigation for MASSs, the DPA was applied to the initial results. The simplification of the path plan depends on the DPA threshold. In this study, threshold values from 0.1 to 0.17 were input in units of 0.01, and the results were compared. Subsequently, by inputting an appropriate threshold value, a final path plan was generated.

The results obtained when each threshold value was entered were as follows: When a threshold of 0.1–0.13 was entered, there were 11 waypoints, and the total distance was 110.594 km. For a threshold of 0.14–0.16, 10 waypoints were analyzed, and the total distance was 110.156 km. When a threshold of 0.17 was entered, it was outside the navigable area. Therefore, the appropriate threshold for generating the final path plan was 0.14–0.16. The results are summarized in Table 3.

The final path plan was visualized using the passage plan for the ship, as shown in Fig. 6. The passage plan used for the ship has six waypoints and a distance of 113.626 km. This was considered to account for the ship traffic congestion near Busan Port and the voyage time according to the estimated time of arrival at the destination. The final path plan in this study showed a tendency similar to the passage plan of a ship. However, there still were many unnecessary waypoints. Nonetheless, the total distance was reduced by approximately 3.05%.

4. Discussion

This paper proposes a methodology for automatic passage planning in coastal water navigation for MASSs using the D* algorithm. This is significant because the D* algorithm was used. It is a more advanced algorithm than Dijkstra’s algorithm and A* (a conventional global path planning algorithm used in previous studies (Lee et al., 2022a)). This algorithm is the shortest path-planning algorithm and can automatically generate a path plan that minimizes the fuel consumption and sailing time of the ship. In addition, by designating a navigable area, obstacles such as the water depth and islands are considered automatically. Furthermore, the navigation safety and efficiency can be improved by generating a path plan targeting the area where the ship has mainly navigated.

In particular, the final path plan in this study had more waypoints than the initial ship plan. However, the total distances were similar. This implies that from the perspective of the ship operator, the methodology of this study is highly effective for MASSs. The study provides as a basic approach for path planning in the coastal navigation of MASSs.

However, this study has several limitations. Because the trajectory data of all the ships were reflected without the target ship, accurate water depth information or the grid cell size according to the size of the target ship could not be applied. Because the DPA (a post-processing method) was used, it was difficult to fully automate the algorithm. In addition, although the navigation rules were not violated compared with the actual passage plan, practical results for navigation officers should be derived.

To supplement and advance the results of this study, future studies would consider the following: If a large amount of data is collected over a long period and a research is conducted by classifying the ship type, results similar to the initial passage plan established by navigation officers can be generated automatically. Therefore, future research should propose a method for automatically generating passage plans for each ship type by designating the target ships. In addition, we intend to study a method for generating a passage plan after extracting the main traffic routes of ships in South Korea’s coastal waters. Furthermore, using the most advanced global path-planning algorithm, our future work would select the optimal algorithm by comparing it with previous research results. The future research plans include the development of an automatic generation algorithm for passage plans that ship operators can utilize.

5. Conclusion

In this study, a path plan for coastal-water navigation for MASSs was generated using the D* algorithm based on ship trajectory data. The target areas were the coastal waters of Busan New Port and Ulsan Port in South Korea. A grid map with ship trajectory data was designated as a navigable area using ENC information and density analysis results. Subsequently, the initial path plan was generated using the D* algorithm, and the final path plan was derived using the DPA.

A comparison with the initial passage plan of the ship revealed that the number of waypoints obtained was larger by four. However, the total distance decreased by approximately 3.05%. Therefore, this study could automatically generate a path plan that minimized the fuel consumption and sailing time of the ship. Furthermore, it obtained results that could increase the safety and efficiency of navigation by targeting the area where the ship mainly navigated.

Acknowledgments

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean Government (Ministry of Science and ICT) (No. 2022R1C1C2010897).

Figure

Fig. 1.

Flowchart of study.

Fig. 2.

Experimental environment, including ship trajectory-data plot; search principle diagram.

Fig. 3.

Example of path planning using D* algorithm.

Fig. 4.

Designation of the navigable area using ENC information and density analysis.

Fig. 5.

Application of D* Algorithm for generating passage plan.

Fig. 6.

Final passage plan and the actual ship’s passage plan.

Table

Table 1.

Overview of AIS data used in this study

Table 2.

Color of the stages of density analysis

Table 3.

Number of waypoints and total distance according to the threshold of the Douglas–Peucker algorithm

Reference

Chen, P. , Y. Huang, E. Papadimitriou, J. Mou, and P. van Gelder (2020), Global path planning for autonomous ship: A hybrid approach of Fast Marching Square and velocity obstacles methods. Ocean Engineering, Vol. 214, 107793.
Douglas, D. H. and T. K. Peucker (1973), Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica, Vol. 10, No. 2, pp. 112–122.
Grifoll, M. , C. Borén, and M. Castells-Sanabra (2022), A comprehensive ship weather routing system using CMEMS products and A* algorithm. Ocean Engineering, Vol. 255, 111427.
Jung, Y. H. , H. W. Park, S. J. Lee, and M. C. Won (2010), Development of a navigation control algorithm for mobile robots using D* search and fuzzy algorithm. Transactions of the Korean Society of Mechanical Engineers A, Vol. 34, No. 8, pp. 971–980. (in Korean)
Kweon, S. J. , S. W. Hwang, S. Lee, and M. J. Jo (2022), Demurrage pattern analysis using logical analysis of data: A case study of the Ulsan Port Authority. Expert Systems with Applications, Vol. 206, 117745.
Lee, H. T. , H. M. Choi, J. S. Lee, H. Yang, and I. S. Cho (2022a), Generation of ship’s passage plan using data-driven shortest path algorithms. IEEE Access, Vol. 10, pp. 126217–126231.
Lee, H. T. , J. S. Lee, H. Yang, and I. S. Cho (2021a), An AIS data-driven approach to analyze the pattern of ship trajectories in ports using the DBSCAN algorithm. Applied Sciences, Vol. 11, No. 2, 799.
Lee, H. T. , H. Yang, and I. S. Cho (2021b), Data-driven analysis for safe ship operation in ports using quantile regression based on generalized additive models and deep neural network. Sensors, Vol. 21, No. 24, 8254.
Lee, H. Y. and S. H. Suh (2000), An implementation of an ENC representation system which meets S-52 presentation specification and S-57 transfer standards. The Journal of the Korea Institute of Maritime Information & Communication Sciences, Vol. 4, No. 2, pp. 469–478. (in Korean)
Lee, J. S. , H. T. Lee, and I. S. Cho (2022b), Maritime traffic route detection framework based on statistical density analysis from AIS data using a clustering algorithm. IEEE Access, Vol. 10, 23355–23366.
Lee, W. , W. Yoo, G. H. Choi, S. H. Ham, and T. W. Kim (2019), Determination of optimal ship route in coastal sea considering sea state and under keel clearance. Journal of the Society of Naval Architects of Korea, Vol. 56, No. 6, pp. 480 –487. (in Korean)
Liu, Z. , Y. Zhang, X. Yu, and C. Yuan (2016), Unmanned surface vehicles: An overview of developments and challenges. Annual Reviews in Control, Vol. 41, pp. 71–93.
Sang, H. , Y. You, X. Sun, Y. Zhou, and F. Liu (2021), The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations. Ocean Engineering, Vol. 223, 108709.
Silveira, P. , A. P. Teixeira, and C. Guedes-Soares (2019), AIS based shipping routes using the Dijkstra algorithm. TransNav: International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 13, No. 3, pp. 565–571.
Stentz, A. (1997), Optimal and efficient path planning for partially known environments. In: Herbert, M. H., Thorpe, C., and Stentz, A. (eds.), Intelligent Unmanned Ground Vehicles, New York: Springer, pp. 203–220.
Sun, Y. , M. Fang, and Y. Su (2021), AGV path planning based on improved Dijkstra algorithm. Journal of Physics: Conference Series, Vol. 1746, No. 1, 012052.
Wang, H. , W. Mao, and L. Eriksson (2019), A Three- Dimensional Dijkstra's algorithm for multi-objective ship voyage optimization. Ocean Engineering, Vol. 186, 106131.
Wang, L. , Z. Zhang, Q. Zhu, and S. Ma (2020), Ship route planning based on double-cycling genetic algorithm considering ship maneuverability constraint. IEEE Access, Vol. 8, pp. 190746–190759.
Wee, S. M. , S. H. Kim, and I. D. Chang (2000), On the Implementation of Route Planning Algorithms on the Electronic Chart system. Journal of Korea Institute of Navigation, Vol. 24, No. 3, pp. 167–176. (in Korean)
Yu, J. , M. Yang, Z. Zhao, X. Wang, Y. Bai, J. Wu, and J. Xu (2022), Path planning of unmanned surface vessel in an unknown environment based on improved D* Lite algorithm. Ocean Engineering, Vol. 266, 112873.
Xie, L. , S. Xue, J. Zhang, M. Zhang, W. Tian, and S. Haugen (2019), A path planning approach based on multidirection A* algorithm for ships navigating within wind farm waters. Ocean Engineering, Vol. 184, pp. 311–322.