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 critical factors in the autonomous navigation of Unmanned Surface Vehicles (USVs), particularly in dynamic maritime environments where energy conservation and control smoothness are paramount. While Dijkstra's algorithm and A* (A-Star) have long served as standard solutions for the Single-Source Shortest Path (SSSP) problem, their performance is theoretically constrained by the sorting barrier, imposing a time complexity of $O(m + n \log n)$. This study empirically evaluates a novel deterministic algorithm that theoretically breaks this barrier by utilizing a pivot-based recursive partitioning technique to achieve $O(m \log^{\frac{2}{3}} n)$ complexity. This algorithm, referred to as the Bounded Multi-Source Shortest Path (BMSSP) algorithm, was benchmarked against classical Dijkstra and A* using a high-fidelity VRX/Gazebo simulation environment that accounts for hydrodynamic drag and water currents. The results from 30 repeated trials demonstrate that while A* remains the fastest in terms of CPU time (322 ms), the BMSSP algorithm achieves superior algorithmic efficiency by expanding 29% fewer nodes without using heuristics. Furthermore, the BMSSP algorithm generated the smoothest trajectories with the lowest total angular deviation (664.08°), offering a significant advantage in navigation stability over A* (679.34°) and Dijkstra (664.82°). These findings suggest that breaking the sorting barrier translates into practical benefits for marine robotics, providing a robust alternative for energy-efficient and stable autonomous navigation.