Development of Ship Route-Planning Algorithm Based on Rapidly-Exploring Random Tree (RRT*) Using Designated Space

Abstract

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.

Keywords

• route planning
• sampling-based algorithm
• binary image
• probabilistic roadmap
• rapidly-exploring random tree
• multi-ellipse space