Ship Path Planning Based on Sparse A* Algorithm
Yongjian Zhai , Jianhui Cui , Fanbin Meng , Huawei Xie , Chunyan Hou , Bin Li
Journal of Marine Science and Application ›› : 1 -11.
Ship Path Planning Based on Sparse A* Algorithm
An improved version of the sparse A* algorithm is proposed to address the common issue of excessive expansion of nodes and failure to consider current ship status and parameters in traditional path planning algorithms. This algorithm considers factors such as initial position and orientation of the ship, safety range, and ship draft to determine the optimal obstacle-avoiding route from the current to the destination point for ship planning. A coordinate transformation algorithm is also applied to convert commonly used latitude and longitude coordinates of ship travel paths to easily utilized and analyzed Cartesian coordinates. The algorithm incorporates a hierarchical chart processing algorithm to handle multilayered chart data. Furthermore, the algorithm considers the impact of ship length on grid size and density when implementing chart gridification, adjusting the grid size and density accordingly based on ship length. Simulation results show that compared to traditional path planning algorithms, the sparse A* algorithm reduces the average number of path points by 25%, decreases the average maximum storage node number by 17%, and raises the average path turning angle by approximately 10°, effectively improving the safety of ship planning paths.
Sparse A* algorithm / Path planning / Rasterization / Coordinate transformation / Image preprocessing
| [1] |
Bi T, Ye P, Xu Y, Zhang F (2019) Route planning of unmanned aerial vehicle based on sparse A* algorithm. Proceedings of 2019 International Conference on Informatics, Control and Robotics (ICICR 2019), Shanghai, China, 31–37. DOI: https://doi.org/10.26914/c.cnkihy.2019.077835 |
| [2] |
|
| [3] |
|
| [4] |
|
| [5] |
|
| [6] |
|
| [7] |
|
| [8] |
|
| [9] |
Hu S, Wu M, Shi J (2023) Research on improved A* algorithm integrating vector cross-product and jump point search strategy. Mechanical Science and Technology for Aerospace Engineering: 1–10. DOI: https://doi.org/10.13433/j.cnki.1003-8728.20230017 |
| [10] |
|
| [11] |
|
| [12] |
|
| [13] |
|
| [14] |
|
| [15] |
|
| [16] |
|
| [17] |
|
| [18] |
DWA algorithm for mobile robot path planning. Computer Integrated Manufacturing Systems: 1–20. http://kns.cnki.net/kcms/detail/11.5946.TP.20221125.1957.004.html |
| [19] |
|
| [20] |
|
| [21] |
|
| [22] |
|
| [23] |
|
| [24] |
|
| [25] |
|
| [26] |
|
| [27] |
|
| [28] |
|
| [29] |
|
| [30] |
|
| [31] |
|
| [32] |
|
| [33] |
|
/
| 〈 |
|
〉 |