Path planning for unmanned naval surface vehicles
Abstract
There nowadays is a myriad of approaches to real-time avoidance of fixed obstacles for unmanned surface vehicles (USVs) and, to a lesser extent, also the task of avoiding moving obstacles such as boats, ships, swimmers, and other USVs, but both topics still present challenges. This paper offers novel approaches to both of these problems. It uses a combination of a global path planner, which finds a path from a start point to a goal point that avoids fixed obstacles (given that their locations are known in advance), and a local path planner, which can circumnavigate a moving obstacle (as well as any previously unknown fixed obstacles). The global planner is novel in that it employs a combination of three path planners, one known in the literature as Grassfire, one that is a new modification of Grassfire, and one that is a new, and arguably more intuitive, version of the well-known Probabilistic Roadmap. The local planner is novel in that it employs a higher-level decision logic based on its observations regarding the direction of movement of the obstacle relative to the USVs global path. This logic enables the USV to determine the best strategy for avoiding the obstacle by systematically routing the vehicle behind the obstacle rather than running parallel to it until the opportunity to pass appears. Simulations are provided that validate these claims. For comparison with other systems, the simulations include an implementation of the well-known D* algorithm, and the discussion covers additional dynamic path planning systems, which, like D*, do not necessarily route the vehicle behind the moving obstacle.
References
1. Dorst L, Trovato K. Optimal path planning by cost wave propagation in metric configuration space. In: Mobile Robots III. vol. 1007. International Society for Optics and Photonics; 1989. pp. 186–197.
2. Kavraki LE, Kolountzakis MN, Latombe JC. Analysis of probabilistic roadmaps for path planning. IEEE Transactions on Robotics and Automation. 1998; 14(1): 166–171.
3. Dijkstra EW. A note on two problems in connexion with graphs. Numerische Mathematik. 1959; 1(1): pp. 269–271.
4. Stentz A. Optimal and efficient path planning for unknown and dynamic environments. International Journal of Robotics and Automation. 1993; 10: 89–100.
5. Philippsen R, Siegwart R. An interpolated dynamic navigation function. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA); Barcelona, Spain; 18–22 April 2005. pp. 3782–3789. doi: 10.3929/ethz-a-010080385
6. U.S. Department of Homeland Security. United States Coast Guard, Navigation Rules, International—Inland, COMDTINST M16672.2D. Available online: https://www.navcen.uscg.gov/sites/default/files/pdf/navRules/navrules.pdf (accessed on 2 January 2025).
7. Benjamin MR. Autonomous COLREGS Modes and Velocity Functions, Massachusetts Institute of Technology. In: Computer Science and Artificial Intelligence Laboratory Technical Report. Massachusetts Institute of Technology; 2017.
8. MOOS-IvP. Available online: www.moos-ivp.org (accessed on 2 January 2025).
9. Bentley JL. Multidimensional binary search trees used for associative searching. Communications of the ACM. 1975; 18(9): 509–517.
10. Chowdhury MI, Schwartz DG. Recursion-based probabilistic roadmap for robot path planning. In: Proceedings of the 54th International Symposium on Robotics, ISR Europe 2022; Munich, Germany; 20–21 June 2022. pp. 1–7.
11. Chowdhury MI, Schwartz DG. USV obstacle avoidance using a novel local path planner and novel global path planner With r-PRM. In Proceedins of the 54th International Symposium on Robotics, ISR Europe 2022; Munich, Germany; June 20–21 2022. pp. 1–8.
12. Chowdhury MI. Path Planning Algorithms for Autonomous Vehicles [PhD thesis]. Florida State University; 2022.
13. Nilsson NJ. Principles of Artificial Intelligence. Morgan Kaufmann; 1980.
14. LaValle SM. Rapidly-exploring random trees: A new tool for path planning. The annual research report. 1998.
15. Latombe J. Robot Motion Planning. Kluwer Academic Publishers; 1991.
16. Kavraki LE, Svestka P, Latombe JC, Overmars MH. Probabilistic roadmaps for path planning in high dimensional configuration spaces. IEEE Transactions on Robotics and Automation. 1996; 12(4): 566–580.
17. Amato NM, Bayazit OB, Dale LK, et al. OBPRM: An obstacle-based PRM for 3D workspaces. In: Proceedings of the 3rd Workshop on the Algorithmic Foundations of Robotics (WAFR); Houston Texas USA; 1 August 1998. pp.155–168.
18. Flemming S, la Andrews C-H, Morten B. Configuration space and visibility graph generation from geometric workspaces for USVs. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference; Portland, Oregon; 8–11 August 2011.
19. Hsu D, Kindel R, Latombe J-C, Rock S. Randomized kinodynamic motion planning with moving obstacles. The International Journal of Robotics Research. 2002; 21(3): 233–255.
20. Yan F, Liu Y-S, Xiao J-Z. Path planning in complex 3D environments using a probabilistic roadmap method. International Journal of Automation and Computing. 2013; 10(6): 525–533.
21. Geraerts R. Planning short paths with clearance using explicit corridors. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA); Anchorage, Alaska, USA; 3–7 May 2010. pp. 1997–2004.
22. Khatib O. Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research. 1986; 5(1): 90-98.
23. Connolly CI, Burns JB, Weiss R. Path planning using Laplace’s equation. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA); Cincinnati, Ohio, USA; May 1990. pp. 2102–2106.
24. Rimon E, Koditschek DE. Exact robot navigation using artificial potential functions. IEEE Transactions on Robotics and Automation. 1992; 8(5): 501–518, .
25. Barraquand J, Latombe JC. Robot motion planning: A distributed representation approach. The International Journal of Robotics Research. 1991; 10(6): 628–649.
26. Yershova A, Jaillet L, Siméon T, LaValle SM. Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA); Barcelona, Spain; 18–22 April 2005; pp. 3856–3861.
27. Karaman S, Frazzoli E. Optimal kinodynamic motion planning using incremental sampling-based methods. In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC); Atlanta, GA, USA; 15–17 December 2010. pp. 7681–7687.
28. Erinc G, Carpin S. A genetic algorithm for nonholonomic motion planning. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA); Roma, Italy; April 2007. pp. 1843–1849.
29. Shamos MI, Hoey D. Closest-point problems. In: Proceedings of the 16th Annual Symposium on Foundations of Computer Science; Berkeley, California, USA; 13–15 October 1975. pp. 151–162.
30. Luchnikov VA, Medvedev NN, Oger L, Troadec JP. Voronoi-Delaunay analysis of voids in systems of nonspherical particles. Physical Review E. 1999; 59(6): 7205–7212.
31. Roos T, Noltemeier H. Dynamic Voronoi diagrams in motion planning. In: Workshop on Computational Geometry. Springer; 1991. pp. 227–236.
32. Liu L, Zhang S. Voronoi diagram and GIS-based 3D path planning. In: Proceedings of the 17th International Conference on Geoinformatics; Fairfax, VA, USA; 12–14 August 2009. pp. 1–5.
33. Dalpe AJ, Thein MW. Obstacle avoidance strategies for autonomous surface vehicles. In: Proceedings of the OCEANS 2017-Anchorage; Anchorage, Alaska; 18–21 September 2017. pp. 1–8.
34. Dalpe AJ, Cook AE, Thein MW, Renken M. A multi-layered approach to autonomous surface vehicle map-based autonomy. In: Proceedings of the OCEANS 2018 MTS/IEEE Charleston; Charleston, South Carolina; 22–25 October 2018. pp. 1–8.
35. Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics. 1968; 4(2): 100–107.
36. Chowdhury MI, Schwartz DG. The PRM-A* path planning algorithm for UUVs: An application to Navy mission planning. In: Proceedings of the Global Oceans 2020: Singapore/US Gulf Coast; Biloxi MS USA; 5–30 October 2020. pp.1–9.
37. Chowdhury MI, Schwartz DG. UUV on-board path replanning using PRM-A*. In: Proceedings of the Global Oceans 2020: Singapore/US Gulf Coast; 2020; Biloxi MS USA; 5–30 October 2020. pp. 1–8.
38. Krogh B. A generalized potential field approach to obstacle avoidance control. In: Proceedings of the SME Conference on Robotics Research: The Next Five Years and Beyond; Bethlehem, PA, USA; 14–16 August 1984. pp. 11–22.
39. Xue Y, Clelland D, Lee BS, Han D. Automatic simulation of ship navigation. Ocean Engineering. 2011; 38(17–18); pp. 2290-2305.
40. Song R, Liu Y, Bucknall R. A multi-layered fast marching method for unmanned surface vehicle path planning in a time-variant maritime environment. Ocean Engineering. 2017; 129: 301–317.
41. Borenstein J, Koren Y. Real-time obstacle avoidance for fast mobile robots. IEEE Transactions on Systems, Man, and Cybernetics. 1989; 19(5): 1179–1187.
42. Koren Y, Borenstein J. Potential field methods and their inherent limitations for mobile robot navigation. In: Proceedings of the IEEE Conference on Robotics and Automation (ICRA); Sacramento, California; 7-12 April 1991. pp. 1398–1404.
43. Cai X, Li Y, Wu T. Dynamic path planning of mobile robots in uncertain environments based on PSO and receding horizon optimization. Bulletin of Science and Technology. 2008; 24(2): 260–265.
44. Lin X, Fu Y. Research of USV obstacle avoidance strategy based on dynamic window. In: Proceedings of the IEEE International Conference on Mechatronics and Automation (ICMA); Takamatsu, Japan; 6–9 August 2017. pp. 1410–1415.
45. Nasrollahy AZ, Javadi HH. Using particle swarm optimization for robot path planning in dynamic environments with moving obstacles and target. In: Proceedings of the third UKSim European Symposium on Computer Modeling and Simulation; Athens, Greece; 25–27 November 2009. pp.60–65.
46. Yang SX, Meng M. Neural network approaches to dynamic collision-free trajectory generation. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 2001; 31(3): 302–318.
47. Carelli R, Freire EO. Corridor navigation and wall-following stable control for sonar-based mobile robots. Robotics and Autonomous Systems. 2003; 45(3–4): 235–247.
48. Chen L. UUV path planning algorithm based on virtual obstacle. In: Proceedings of the IEEE International Conference on Mechatronics and Automation; Tianjin, China; 3–6 August 2014. pp. 1722–1727.
49. Chiang H-T, Malone N, Lesser K, et al. Path-guided artificial potential fields with stochastic reachable sets for motion planning in highly dynamic environments. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA); Seattle, WA USA; 26–30 May 2015. pp. 2347–2354.
50. Ueno K, Kinoshita T, Kobayashi K, Watanabe K. Development of a robust path-planning algorithm using virtual obstacles for an autonomous mobile robot. Journal of Robotics and Mechatronics. 2015; 27(3): 286–292.
51. Miotto P, Wilde J, Menozzi A. UUV on-board path planning in a dynamic environment for the Manta test vehicle. In: Proceedings of the OCEANS; San Diego, CA, USA; 22–26 September 2003. pp. 2454–2461.
52. Simic M. From recursion to iterative functions. Available online: https://www.baeldung.com/cs/convert-recursion-to-iteration (accessed on 2 January 2025).
Copyright (c) 2025 Author(s)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Submit a Paper
