Hostname: page-component-6bf8c574d5-8gtf8 Total loading time: 0 Render date: 2025-02-16T23:43:19.387Z Has data issue: false hasContentIssue false
  • English
  • Français

Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles

Published online by Cambridge University Press:  24 January 2019

Hanlin Niu ,
Al Savvaris ,
Antonios Tsourdos  and
Ze Ji
Hanlin Niu*
Affiliation:
(School of Aerospace, Transport and Manufacturing, Cranfield University, Cranfield, Bedford, MK43 0AL, UK) (School of Engineering, Cardiff University, Cardiff, CF24 3AA, UK)
Al Savvaris
Affiliation:
(School of Aerospace, Transport and Manufacturing, Cranfield University, Cranfield, Bedford, MK43 0AL, UK)
Antonios Tsourdos
Affiliation:
(School of Aerospace, Transport and Manufacturing, Cranfield University, Cranfield, Bedford, MK43 0AL, UK)
Ze Ji
Affiliation:
(School of Engineering, Cardiff University, Cardiff, CF24 3AA, UK)
*
(E-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, a novel Voronoi-Visibility (VV) path planning algorithm, which integrates the merits of a Voronoi diagram and a Visibility graph, is proposed for solving the Unmanned Surface Vehicle (USV) path planning problem. The VM (Voronoi shortest path refined by Minimising the number of waypoints) algorithm was applied for performance comparison. The VV and VM algorithms were compared in ten Singapore Strait missions and five Croatian missions. To test the computational time, a high-resolution, large spatial dataset was used. It was demonstrated that the proposed algorithm not only improved the quality of the Voronoi shortest path but also maintained the computational efficiency of the Voronoi diagram in dealing with different geographical scenarios, while also keeping the USV at a configurable clearance distance c from coastlines. Quantitative results were generated by comparing the Voronoi, VM and VV algorithms in 2,000 randomly generated missions using the Singapore dataset.

Keywords

Unmanned Surface VehiclePath PlanningVoronoi DiagramVisibility Graph
Type
Research Article
Information
The Journal of Navigation , Volume 72 , Issue 4 , July 2019 , pp. 850 - 874
Copyright
Copyright © The Royal Institute of Navigation 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Bhattacharya, P. and Gavrilova, M. (2008). Roadmap-based path planning-Using the Voronoi diagram for a clearance-based shortest path. IEEE Robotics & Automation Magazine, 15(2), 58–66.10.1109/MRA.2008.921540Google Scholar
Buniyamin, N., Wan Ngah, W., Sariff, N. and Mohamad, Z. (2011). A simple local path planning algorithm for autonomous mobile robots. International Journal of Systems Applications, 5(2), 151–159.Google Scholar
Campbell, S., Naeem, W. and Irwin, G. W. (2012). A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance manoeuvres. Annual Reviews in Control, 36(2), 267–283.10.1016/j.arcontrol.2012.09.008Google Scholar
Candeloro, M., Lekkas, A. and Sørensen, A. (2017). A Voronoi-diagram-based dynamic path-planning system for underactuated marine vessels. Control Engineering Practice, 61, 41–54.10.1016/j.conengprac.2017.01.007Google Scholar
Carpin, S. and Pillonetto, G. (2005). Motion planning using adaptive random walks. IEEE Transactions on Robotics, 21(1), 129–136.10.1109/TRO.2004.833790Google Scholar
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematic, 1(1), 269–271.10.1007/BF01386390Google Scholar
Ghosh, S. K. and Mount, D. M. (1991). An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing, 20(5), 888–910.10.1137/0220055Google Scholar
Hsu, D., Latombe, J. and Motwani, R. (1997). Path planning in expansive configuration spaces. Robotics and Automation, 3, 2719–2726.10.1109/ROBOT.1997.619371Google Scholar
Ibarra-Zannatha, J., Sossa-Azuela, J. and Gonzalez-Hernandez, H. (1994). A new roadmap approach to automatic path planning for mobile robot navigation. Systems, Man, and Cybernetics, 3, 2803–2808.10.1109/ICSMC.1994.400298Google Scholar
Iswanto, I., Wahyunggoro, O. and Cahyadi, A. (2016). Quadrotor Path Planning Based On Modified Fuzzy Cell Decomposition Algorithm. TELKOMNIKA (Telecommunication Computing Electronics and Control), 14(2), 655–664.10.12928/telkomnika.v14i2.2989Google Scholar
Kaluder, H., Brezak, M. and Petrović, I. (2011). A visibility graph based method for path planning in dynamic environments.MIPRO, 2011, Proceedings of the 34th International Convention, 717–721. IEEE.Google Scholar
Kim, J., Pearce, R. A. and Amato, N. M. (2003). Extracting optimal paths from roadmaps for motion planning. Robotics and Automation, 2003. Proceedings. ICRA'03. IEEE International Conference, 2424–2429, IEEE.Google Scholar
Kuffner, J. and Latombe, J. (2000). Interactive manipulation planning for animated characters. In Computer Graphics and Applications, 2000. Proceedings. The Eighth Pacific Conference, 417–418. IEEE.10.1109/PCCGA.2000.883973Google Scholar
Lazarowska, A. (2015). Ship's trajectory planning for collision avoidance at sea based on ant colony optimisation. The Journal of Navigation, 68(2), 291–307.10.1017/S0373463314000708Google Scholar
Loe, G. (2008). Collision avoidance for Unmanned Surface. Master thesis, Norwegian University of Science and Technology (NTNU).Google Scholar
Lu, Q., Xu, Y., Chen, Y., Huang, R. and Chen, L. (2016). Enhancing state space search for planning by Monte-Carlo random walk exploration. International Conference on Intelligent Data Engineering and Automated Learning, 37–45. Springer, Cham.Google Scholar
Masehian, E. and Amin Naseri, M. R. (2004). A voronoi diagram visibility graph potential field compound algorithm for robot path planning. Journal of Field Robotics, 21(6), 275–300.Google Scholar
Moon, C. and Chung, W. (2015). Kinodynamic planner dual-tree RRT (DT-RRT) for two-wheeled mobile robots using the rapidly exploring random tree. IEEE Transactions on industrial electronics, 62(2), 1080–1090.10.1109/TIE.2014.2345351Google Scholar
Niu, H., Lu, Y., Savvaris, A. and Tsourdos, A. (2016a). Efficient path following algorithm for Unmanned Surface Vehicle. Shanghai, OCEANS 2016, IEEE.10.1109/OCEANSAP.2016.7485430Google Scholar
Niu, H., Lu, Y., Savvaris, A. and Tsourdos, A. (2016b). Efficient path planning algorithms for Unmanned Surface Vehicle. IFAC-PapersOnLine, 49(23), 121–126.10.1016/j.ifacol.2016.10.331Google Scholar
Phanthong, T., Maki, T., Ura, T., Sakamaki, T. and Aiyarak, P. (2014). Application of A* algorithm for real-time path re-planning of an unmanned surface vehicle avoiding underwater obstacle. Journal of Marine Science and Application, 13(1), 105–116.10.1007/s11804-014-1224-3Google Scholar
Polvara, R. Sharma, S., Wan, J., Manning, A. and Sutton, R. (2018). Obstacle avoidance approaches for autonomous navigation of Unmanned Surface Vehicles. The Journal of Navigation, 71(1), 241–256.10.1017/S0373463317000753Google Scholar
Rezaee, H. and Abdollahi, F. (2014). A decentralized cooperative control scheme with obstacle avoidance for a team of mobile robots. IEEE Transactions on Industrial Electronics, 61(1), 347–354.10.1109/TIE.2013.2245612Google Scholar
Savvaris, A., Niu, H., Oh, H. and Tsourdos, A. (2014). Development of collision avoidance algorithms for the C-Enduro USV. IFAC Proceedings Volumes, 47(3), 12174–12181.10.3182/20140824-6-ZA-1003.02362Google Scholar
Szlapczynski, R. (2015). Evolutionary planning of safe ship tracks in restricted visibility. The Journal of Navigation, 68(1), 39–51.10.1017/S0373463314000587Google Scholar
Tam, C., Bucknall, R. and Greig, A. (2009). Review of collision avoidance and path planning methods for ships in close range encounters. The Journal of Navigation, 62(3), 455–476.10.1017/S0373463308005134Google Scholar
Wein, R., Van den Berg, J. P. and Halperin, D. (2007). The visibility–Voronoi complex and its applications. Computational Geometry, 36(1), 66–87.10.1016/j.comgeo.2005.11.007Google Scholar
Wu, B., Wen, Y., Huang, Y. and Zhu, M. (2013). Research of Unmanned Surface Vessel (USV) Path-Planning Algorithm Based on ArcGIS. ICTIS 2013: Improving Multimodal Transportation Systems-Information, Safety, and Integration, 2125–2134.Google Scholar
Yuan, F., Liang, J. H., Fu, Y. W., Xu, H. C. and Ma, K. (2015). A hybrid sampling strategy with optimized probabilistic roadmap method. Fuzzy Systems and Knowledge Discovery (FSKD), 2015 12th International Conference, 2298–2302.10.1109/FSKD.2015.7382311Google Scholar
Zimmermann, M. and König, C. (2016). Integration of a visibility graph based path planning method in the ACT/FHS rotorcraft. CEAS Aeronautical Journal, 7(3), 391–403.10.1007/s13272-016-0197-0Google Scholar