Heuristic Fast-Marching Tree for Ship Path Planning

To address the issues of high global path planning costs and low algorithmic efficiency for intelligent ships in complex marine environments, we propose a Heuristic Fast Marching Tree algorithm (HFMT*). This algorithm incorporates a heuristic function during the global path search process. The heuristic function uses the Euclidean distance from the current node to the target node to guide the growth direction of the search tree. This approach reduces redundant computations and excessive invalid iterations in the FMT* algorithm during the path search process. Additionally, “lazy” collision detection is performed during the search, enhancing planning efficiency while ensuring path safety. Finally, simulation experiments were conducted in two environments with different levels of complexity using PyCharm. The HFMT* algorithm was compared with the FMT* and Probabilistic Roadmap(PRM) algorithm. The simulation results indicate that the HFMT* algorithm significantly improves search efficiency and reduces path costs. The simulation experiments demonstrate that the proposed HFMT* algorithm overcomes the redundancy issues in path planning present in the FMT* and PRM algorithms, reduces the number of iterations, lowers path costs, and enhances the efficiency of path planning for intelligent ships.