Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels

Abstract

The efficiency and stability of path planning algorithms are important factors in the autonomous navigation of Unmanned Surface Vehicles (USVs), particularly in maritime environments where obstacle avoidance, control smoothness, and computational workload must be considered together. Classical deterministic planners such as Dijkstra’s algorithm and A* are widely used for shortest-path planning, but their priority-queue-based structure is theoretically related to the sorting barrier in the Single-Source Shortest Path (SSSP) problem. This study provides an applied validation of the Bounded Multi-Source Shortest Path (BMSSP) approach, based on the sorting-barrier-breaking algorithm proposed by Duan et al., in a realistic VRX/Gazebo-based USV simulation environment. Dijkstra, A*, and BMSSP were evaluated across 120 simulation runs, including four goal locations, two obstacle-density levels, and five repetitions for each configuration. The results show that A* achieved the fastest initial planning time, with an average of 260.41 ms, while BMSSP achieved the lowest explored search space, with an average of 22,594.13 nodes. However, BMSSP also required higher dictionary accesses and bookkeeping/relaxation calls, resulting in a higher average planning time of 1,827.31 ms in the Python implementation. Statistical analysis showed significant differences in computational workload metrics, whereas total mission time, path length, and smoothness differences were not statistically significant. These findings indicate that BMSSP can provide practical search-space reduction in USV path planning, but its runtime performance depends strongly on implementation-level overhead.