Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space
Ship route planning is a crucial activity that must consider not only the safety of the ship but also the safe passage of nearby ships in the same space and time. This study aims to provide general route-planning guidance to shipping traffic by improving conventional sampling-based route-planning al...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-11-01
|
| Series: | Journal of Marine Science and Engineering |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2077-1312/10/12/1800 |
| _version_ | 1797456953420546048 |
|---|---|
| author | Da-un Jang Joo-sung Kim |
| author_facet | Da-un Jang Joo-sung Kim |
| author_sort | Da-un Jang |
| collection | DOAJ |
| description | Ship route planning is a crucial activity that must consider not only the safety of the ship but also the safe passage of nearby ships in the same space and time. This study aims to provide general route-planning guidance to shipping traffic by improving conventional sampling-based route-planning algorithms in accordance with the maritime environment from a ship operator’s perspective. The obstacle safety margin in a marine environment can be reflected in a binary image map space based on an electronic navigational chart. Consequently, an initial route was created using the probabilistic road map (PRM) algorithm in the configured map space to increase the speed of the conventional sampling-based route-planning algorithm. Based on the initial route created, a designated space—that is, a multi-elliptical area—was created to limit the route-search range. After searching the final route in the designated space based on the rapidly-exploring random tree (RRT*) algorithm, optimal route planning could be achieved by generating a collision-free space graph to remove unnecessary nodes from the searched final route. The simulation results showed that the route was shortened by approximately 33.7 km compared with the conventional RRT* algorithm, and the calculation time was shortened by approximately 2.5 times. |
| first_indexed | 2024-03-09T16:15:14Z |
| format | Article |
| id | doaj.art-cb518eb1529043ed804022a516662a68 |
| institution | Directory Open Access Journal |
| issn | 2077-1312 |
| language | English |
| last_indexed | 2024-03-09T16:15:14Z |
| publishDate | 2022-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Journal of Marine Science and Engineering |
| spelling | doaj.art-cb518eb1529043ed804022a516662a682023-11-24T15:54:33ZengMDPI AGJournal of Marine Science and Engineering2077-13122022-11-011012180010.3390/jmse10121800Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated SpaceDa-un Jang0Joo-sung Kim1Graduate School of Maritime Transportation System, Mokpo National Maritime University, Mokpo 58628, Republic of KoreaDivision of Navigation Science, Mokpo National Maritime University, Mokpo 58628, Republic of KoreaShip route planning is a crucial activity that must consider not only the safety of the ship but also the safe passage of nearby ships in the same space and time. This study aims to provide general route-planning guidance to shipping traffic by improving conventional sampling-based route-planning algorithms in accordance with the maritime environment from a ship operator’s perspective. The obstacle safety margin in a marine environment can be reflected in a binary image map space based on an electronic navigational chart. Consequently, an initial route was created using the probabilistic road map (PRM) algorithm in the configured map space to increase the speed of the conventional sampling-based route-planning algorithm. Based on the initial route created, a designated space—that is, a multi-elliptical area—was created to limit the route-search range. After searching the final route in the designated space based on the rapidly-exploring random tree (RRT*) algorithm, optimal route planning could be achieved by generating a collision-free space graph to remove unnecessary nodes from the searched final route. The simulation results showed that the route was shortened by approximately 33.7 km compared with the conventional RRT* algorithm, and the calculation time was shortened by approximately 2.5 times.https://www.mdpi.com/2077-1312/10/12/1800route planningsampling-based algorithmbinary imageprobabilistic roadmaprapidly-exploring random treemulti-ellipse space |
| spellingShingle | Da-un Jang Joo-sung Kim Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space Journal of Marine Science and Engineering route planning sampling-based algorithm binary image probabilistic roadmap rapidly-exploring random tree multi-ellipse space |
| title | Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space |
| title_full | Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space |
| title_fullStr | Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space |
| title_full_unstemmed | Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space |
| title_short | Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space |
| title_sort | development of ship route planning algorithm based on rapidly exploring random tree rrt using designated space |
| topic | route planning sampling-based algorithm binary image probabilistic roadmap rapidly-exploring random tree multi-ellipse space |
| url | https://www.mdpi.com/2077-1312/10/12/1800 |
| work_keys_str_mv | AT daunjang developmentofshiprouteplanningalgorithmbasedonrapidlyexploringrandomtreerrtusingdesignatedspace AT joosungkim developmentofshiprouteplanningalgorithmbasedonrapidlyexploringrandomtreerrtusingdesignatedspace |