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

Eren Deniz; Emine Sezer

doi:10.35377/saucis...1853953

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.

Keywords

Ethical Statement

This study does not involve human participants or animals. The research was conducted using the VRX/Gazebo simulation environment and does not require ethics committee approval. It is declared that during the preparation process of this study, scientific and ethical principles were followed, and all the studies benefited from are stated in the bibliography.

References

C. Barrera, I. Padron, F. S. Luis, O. Llinas, and G. N. Marichal, “Trends and challenges in unmanned surface vehicles (USV): From survey to shipping,” TransNav Int. J. Mar. Navig. Saf. Sea Transp., vol. 15, no. 1, pp. 135–142, 2021, doi: 10.12716/1001.15.01.13. [Online]. Available: https://doi.org/10.12716/1001.15.01.13
M. Issa, A. Ilinca, H. Ibrahim, and P. Rizk, “Maritime autonomous surface ships: Problems and challenges facing the regulatory process,” Sustainability, vol. 14, no. 23, Art. no. 15630, 2022, doi: 10.3390/su142315630. [Online]. Available: https://doi.org/10.3390/su142315630
A. Stentz, “Optimal and efficient path planning for partially-known environments,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), 1994, pp. 3310–3317, doi: 10.1109/ROBOT.1994.351061. [Online]. Available: https://doi.org/10.1109/ROBOT.1994.351061
S. Koenig and M. Likhachev, “D* Lite,” in Proc. AAAI Conf. Artif. Intell., 2002, pp. 476–483. [Online]. Available: https://aaai.org/papers/00476-aaai02-072-d-lite/
L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom., vol. 12, no. 4, pp. 566–580, Aug. 1996, doi: 10.1109/70.508439. [Online]. Available: https://doi.org/10.1109/70.508439
S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robot. Res., vol. 30, no. 7, pp. 846–894, 2011, doi: 10.1177/0278364911406761. [Online]. Available: https://doi.org/10.1177/0278364911406761
O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” Int. J. Robot. Res., vol. 5, no. 1, pp. 90–98, 1986, doi: 10.1177/027836498600500106. [Online]. Available: https://doi.org/10.1177/027836498600500106
W. Yuan, Z. Liu, and Z. Zhang, “Model predictive control-based collision avoidance for autonomous surface vehicles in congested inland waters,” Math. Probl. Eng., vol. 2022, Art. no. 7584489, 2022, doi: 10.1155/2022/7584489. [Online]. Available: https://doi.org/10.1155/2022/7584489

A. Vagale, R. Oucheikh, T. A. Johansen, and T. I. Fossen, “Path planning and collision avoidance for autonomous surface vehicles I: A review,” J. Mar. Sci. Technol., vol. 26, pp. 1292–1306, 2021, doi: 10.1007/s00773-020-00787-6. [Online]. Available: https://doi.org/10.1007/s00773-020-00787-6
B. Xing, M. Yu, Z. Liu, and B. Li, “A review of path planning for unmanned surface vehicles,” J. Mar. Sci. Eng., vol. 11, no. 8, Art. no. 1556, 2023, doi: 10.3390/jmse11081556. [Online]. Available: https://doi.org/10.3390/jmse11081556
L. Hu et al., “COLREGs-compliant path planning for autonomous surface vehicles: A multiobjective optimization approach,” IFAC-PapersOnLine, vol. 50, no. 1, pp. 13662–13667, 2017, doi: 10.1016/j.ifacol.2017.08.2525. [Online]. Available: https://doi.org/10.1016/j.ifacol.2017.08.2525
L. Hu, H. Hu, W. Naeem, and Z. Wang, “A review on COLREGs-compliant navigation of autonomous surface vehicles: From traditional to learning-based approaches,” J. Autom. Intell., vol. 1, no. 1, Art. no. 100003, 2022, doi: 10.1016/j.jai.2022.100003. [Online]. Available: https://doi.org/10.1016/j.jai.2022.100003
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol. 1, no. 1, pp. 269–271, 1959, doi: 10.1007/BF01386390. [Online]. Available: https://doi.org/10.1007/BF01386390
A. Candra, M. A. Budiman, and K. Hartanto, “Dijkstra’s and A-Star in finding the shortest path: A tutorial,” in Proc. 2020 Int. Conf. Data Sci., Artif. Intell., Bus. Anal. (DATABIA), 2020, pp. 28–32, doi: 10.1109/DATABIA50434.2020.9190342. [Online]. Available: https://doi.org/10.1109/DATABIA50434.2020.9190342
P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern., vol. SSC-4, no. 2, pp. 100–107, Jul. 1968, doi: 10.1109/TSSC.1968.300136. [Online]. Available: https://doi.org/10.1109/TSSC.1968.300136
A. Brodnik and M. Grgurovič, “Solving all-pairs shortest path by single-source computations: Theory and practice,” Discrete Appl. Math., vol. 231, pp. 119–130, 2017, doi: 10.1016/j.dam.2017.03.008. [Online]. Available: https://doi.org/10.1016/j.dam.2017.03.008
R. Raman, “Recent results on the single-source shortest paths problem,” ACM SIGACT News, vol. 28, no. 2, pp. 81–87, 1997, doi: 10.1145/261342.261352. [Online]. Available: https://doi.org/10.1145/261342.261352
R. Duan, J. Mao, X. Mao, X. Shu, and L. Yin, “Breaking the sorting barrier for directed single-source shortest paths,” in Proc. 57th Annu. ACM Symp. Theory Comput. (STOC), 2025, pp. 36–44, doi: 10.1145/3717823.3718179. [Online]. Available: https://doi.org/10.1145/3717823.3718179
B. Bingham et al., “Toward maritime robotic simulation in Gazebo,” in Proc. OCEANS 2019 MTS/IEEE Seattle, 2019, doi: 10.23919/OCEANS40490.2019.8962724. [Online]. Available: https://doi.org/10.23919/OCEANS40490.2019.8962724
N. Koenig and A. Howard, “Design and use paradigms for Gazebo, an open-source multi-robot simulator,” in Proc. 2004 IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS), vol. 3, 2004, pp. 2149–2154, doi: 10.1109/IROS.2004.1389727. [Online]. Available: https://doi.org/10.1109/IROS.2004.1389727
S. Macenski, T. Foote, B. Gerkey, C. Lalancette, and W. Woodall, “Robot Operating System 2: Design, architecture, and uses in the wild,” Sci. Robot., vol. 7, no. 66, 2022, doi: 10.1126/scirobotics.abm6074. [Online]. Available: https://doi.org/10.1126/scirobotics.abm6074
M. Chen, R. A. Chowdhury, V. Ramachandran, D. L. Roche, and L. Tong, “Priority queues and Dijkstra’s algorithm,” Dept. Comput. Sci., Univ. Texas at Austin, Austin, TX, USA, Tech. Rep. TR-07-54, 2007.
K. Subhashini, G. Rathiksha, B. Keerthana, and P. Amirthavarshini, “Autonomous navigation using Lidar sensor in ROS and GAZEBO,” in Proc. IEEE Int. Conf. Women Innov., Technol. Entrepreneurship (ICWITE), 2024, pp. 670–674, doi: 10.1109/ICWITE59797.2024.10502689. [Online]. Available: https://doi.org/10.1109/ICWITE59797.2024.10502689
A. Ravankar, A. A. Ravankar, Y. Kobayashi, Y. Hoshino, and C.-C. Peng, “Path smoothing techniques in robot navigation: State-of-the-art, current and future challenges,” Sensors, vol. 18, no. 9, Art. no. 3170, 2018, doi: 10.3390/s18093170. [Online]. Available: https://doi.org/10.3390/s18093170
S. P. Singh, T. Lazouski, and M. Ghaffari, “GPS-DRIFT: Marine surface robot localization using IMU-GPS fusion and invariant filtering,” 2025, arXiv:2507.02198. [Online]. Available: https://arxiv.org/abs/2507.02198
P. Jin, W. Li, Y. Yang, S. C. Shan, and Y. Zhang, “Construction of simulation system for USV motion control and design of multi-mode controllers based on VRX and Simulink,” Appl. Sci., vol. 15, no. 8, Art. no. 4213, 2025, doi: 10.3390/app15084213. [Online]. Available: https://doi.org/10.3390/app15084213
J. Pimentel, et al., “Design of an autonomous surface vehicle (ASV) for the 2022 Maritime RobotX Challenge,” Tumi Robotics, 2022. [Online]. Available: http://tumirobotics.com
N. Yuldashev, A. Dobrokvashina, and R. Lavrenov, “On sensor modeling in Gazebo simulator,” in Proc. Int. Conf. Artif. Life Robot. (ICAROB), 2024, doi: 10.5954/ICAROB.2024.OS10-6. [Online]. Available: https://doi.org/10.5954/ICAROB.2024.OS10-6
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA, USA: MIT Press, 2009.
M. Fourment and M. R. Gillings, “A comparison of common programming languages used in bioinformatics,” BMC Bioinformatics, vol. 9, Art. no. 82, 2008, doi: 10.1186/1471-2105-9-82. [Online]. Available: https://doi.org/10.1186/1471-2105-9-82
T. I. Fossen, Handbook of Marine Craft Hydrodynamics and Motion Control, 2nd ed. Hoboken, NJ, USA: Wiley, 2021, doi: 10.1002/9781119994138. [Online]. Available: https://doi.org/10.1002/9781119994138
M. Friedman, “The use of ranks to avoid the assumption of normality implicit in the analysis of variance,” J. Amer. Stat. Assoc., vol. 32, no. 200, pp. 675–701, 1937, doi: 10.1080/01621459.1937.10503522. [Online]. Available: https://doi.org/10.1080/01621459.1937.10503522
F. Wilcoxon, “Individual comparisons by ranking methods,” Biometrics Bull., vol. 1, no. 6, pp. 80–83, 1945, doi: 10.2307/3001968. [Online]. Available: https://doi.org/10.2307/3001968
S. Holm, “A simple sequentially rejective multiple test procedure,” Scand. J. Stat., vol. 6, no. 2, pp. 65–70, 1979.
M. G. Kendall and B. Babington Smith, “The problem of m rankings,” Ann. Math. Stat., vol. 10, no. 3, pp. 275–287, 1939, doi: 10.1214/aoms/1177732186. [Online]. Available: https://doi.org/10.1214/aoms/1177732186
N. Marini, L. Pampaloni, F. Di Martino, R. Verdecchia, and E. Vicario, “Green AI: Which programming language consumes the most?” 2025, arXiv:2501.14776, doi: 10.48550/arXiv.2501.14776. [Online]. Available: https://doi.org/10.48550/arXiv.2501.14776
R. Pereira et al., “Energy efficiency across programming languages: How do energy, time, and memory relate?” in Proc. 10th ACM SIGPLAN Int. Conf. Softw. Lang. Eng. (SLE), 2017, pp. 256–267, doi: 10.1145/3136014.3136031. [Online]. Available: https://doi.org/10.1145/3136014.3136031
S. B. Aruoba and J. Fernández-Villaverde, “A comparison of programming languages in macroeconomics,” J. Econ. Dyn. Control, vol. 58, pp. 265–273, 2015, doi: 10.1016/j.jedc.2015.05.009. [Online]. Available: https://doi.org/10.1016/j.jedc.2015.05.009
K. J. Kyriakopoulos and G. N. Saridis, “Minimum jerk path generation,” in Proc. IEEE Int. Conf. Robot. Autom., 1988, pp. 364–369, doi: 10.1109/ROBOT.1988.12075. [Online]. Available: https://doi.org/10.1109/ROBOT.1988.12075

Details

Primary Language

English

Subjects

Spatial Data and Computing Applications

Journal Section

Research Article

Authors

Eren Deniz ^*
0009-0009-4191-0338
Türkiye

Emine Sezer
0000-0003-4776-6436
Türkiye

Publication Date

September 30, 2026

Submission Date

January 1, 2026

Acceptance Date

June 1, 2026

Published in Issue

Year 2026 Volume: 9 Number: 4

DOI

https://doi.org/10.35377/saucis...1853953

IZ

https://izlik.org/JA95BU27TY

Cite

RIS / Bibtex

APA

Deniz, E., & Sezer, E. (2026). Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels. Sakarya University Journal of Computer and Information Sciences, 9(4), 1080-1091. https://doi.org/10.35377/saucis...1853953

AMA

1.Deniz E, Sezer E. Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels. SAUCIS. 2026;9(4):1080-1091. doi:10.35377/saucis.1853953

Chicago

Deniz, Eren, and Emine Sezer. 2026. “Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels”. Sakarya University Journal of Computer and Information Sciences 9 (4): 1080-91. https://doi.org/10.35377/saucis. 1853953.

EndNote

Deniz E, Sezer E (September 1, 2026) Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels. Sakarya University Journal of Computer and Information Sciences 9 4 1080–1091.

IEEE

[1]E. Deniz and E. Sezer, “Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels”, SAUCIS, vol. 9, no. 4, pp. 1080–1091, Sept. 2026, doi: 10.35377/saucis...1853953.

ISNAD

Deniz, Eren - Sezer, Emine. “Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels”. Sakarya University Journal of Computer and Information Sciences 9/4 (September 1, 2026): 1080-1091. https://doi.org/10.35377/saucis. 1853953.

JAMA

1.Deniz E, Sezer E. Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels. SAUCIS. 2026;9:1080–1091.

MLA

Deniz, Eren, and Emine Sezer. “Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels”. Sakarya University Journal of Computer and Information Sciences, vol. 9, no. 4, Sept. 2026, pp. 1080-91, doi:10.35377/saucis. 1853953.

Vancouver

1.Eren Deniz, Emine Sezer. Breaking the Sorting Barrier in Practice: A Comparative Analysis of Deterministic Path Planning for Autonomous Surface Vessels. SAUCIS. 2026 Sep. 1;9(4):1080-91. doi:10.35377/saucis. 1853953