AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Intelligent and Connected Vehicles Article
PDF (1.8 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research paper | Open Access

Global path planning of unmanned vehicle based on fusion of A* algorithm and Voronoi field

Jiansen Zhao, Xin Ma, Bing Yang( ), Yanjun Chen, Zhenzhen Zhou, Pangyi Xiao
Merchant Marine College, Shanghai Maritime University, Shanghai, China
Show Author Information

Abstract

Purpose

Since many global path planning algorithms cannot achieve the planned path with both safety and economy, this study aims to propose a path planning method for unmanned vehicles with a controllable distance from obstacles.

Design/methodology/approach

First, combining satellite image and the Voronoi field algorithm (VFA) generates rasterized environmental information and establishes navigation area boundary. Second, establishing a hazard function associated with navigation area boundary improves the evaluation function of the A* algorithm and uses the improved A* algorithm for global path planning. Finally, to reduce the number of redundant nodes in the planned path and smooth the path, node optimization and gradient descent method (GDM) are used. Then, a continuous smooth path that meets the actual navigation requirements of unmanned vehicle is obtained.

Findings

The simulation experiment proved that the proposed global path planning method can realize the control of the distance between the planned path and the obstacle by setting different navigation area boundaries. The node reduction rate is between 33.52% and 73.15%, and the smoothness meets the navigation requirements. This method is reasonable and effective in the global path planning process of unmanned vehicle and can provide reference to unmanned vehicles' autonomous obstacle avoidance decision-making.

Originality/value

This study establishes navigation area boundary for the environment based on the VFA and uses the improved A* algorithm to generate a navigation path that takes into account both safety and economy. This study also proposes a method to solve the redundancy of grid environment path nodes and large-angle steering and to smooth the path to improve the applicability of the proposed global path planning method. The proposed global path planning method solves the requirements of path safety and smoothness.

Keywords

Path planningGradient descent methodUnmanned vehicleImproved A* algorithmPath smoothing

References

 

Bibuli, M., Singh, Y., Sharma, S., Sutton, R., Hatton, D. and Khan, A. (2018), “A two layered optimal approach towards cooperative motion planning of unmanned surface vehicles in a constrained Maritime environment”, IFAC-Papers Online, Vol. 51 No. 29, pp. 378-383, doi: 10.1016/j.ifacol.2018.09.458.
Crossref Google Scholar
 

Candeloro, M., Lekkas, A.M. and Sørensen, A.J. (2017), “A Voronoi-diagram-based dynamic path-planning system for underactuated marine vessels”, Control Engineering Practice, Vol. 61, pp. 41-54., doi: 10.1016/j.conengprac.2017.01.007.
Crossref Google Scholar
 

Chen, Z., Zhang, Y., Zhang, Y., Nie, Y., Tang, J. and Zhu, S. (2019), “A hybrid path planning algorithm for unmanned surface vehicles in complex environment with dynamic obstacles”, IEEE Access, Vol. 7, pp. 126439-126449, doi: 10.1109/ACCESS.2019.2936689.
Crossref Google Scholar
 

Dolgov, D., Thrun, S., Montemerlo, M. and Diebel, J. (2008), “Practical search techniques in path planning for autonomous driving”, AAAI Work. – Tech. Rep., WS-08-10, pp. 32-37.
Google Scholar
 

Fedorenko, R. and Gurenko, B. (2016), “Local and global motion planning for unmanned surface vehicle”, MATEC Web of Conferences, Vol. 42, pp. 1-6, doi: 10.1051//matecconf/20164201005.
Crossref Google Scholar
 

Fu, M., Wang, S. and Wang, Y.H. (2019), “Multi-behavior fusion based potential field method for path planning of unmanned surface vessel”, China Ocean Engineering, Vol. 33 No. 5, pp. 583-592, doi: 10.1007/s13344-019-0056-y.
Crossref Google Scholar
 

Fujii, Y. and Tanaka, K. (1971), “Traffic capacity”, Journal of Navigation, Vol. 24 No. 4, pp. 543-552.
Crossref Google Scholar
 

Guo, H., Mao, Z., Ding, W. and Liu, P. (2019), “Optimal search path planning for unmanned surface vehicle based on an improved genetic algorithm”, Computers & Electrical Engineering, Vol. 79, doi: 10.1016/j.compeleceng.2019.106467.
Crossref Google Scholar
 

Junyi, L., Yanwei, H., Wenchao, H. and Shaobin, C. (2019), “Path planning for USV with FG-DA-RRT algorithm”, Proceedings – 2019 Chinese Automaton Congress CAC, pp. 3211-3215, doi: 10.1109/CAC48633.2019.8996955.
Crossref Google Scholar
 

Liu, Y. and Bucknall, R. (2018), “Efficient multi-task allocation and path planning for unmanned surface vehicle in support of ocean operations”, Neurocomputing, Vol. 275, pp. 1550-1566, doi: 10.1016/j.neucom.2017.09.088.
Crossref Google Scholar
 

Liu, Z., Zhang, Y., Yu, X. and Yuan, C. (2016), “Unmanned surface vehicles: an overview of developments and challenges”, Annual Reviews in Control, Vol. 41, pp. 71-93, doi: 10.1016/j.arcontrol.2016.04.018.
Crossref Google Scholar
 

Long, Y., Su, Y., Zhang, H. and Li, M. (2018), “Application of improved genetic algorithm to unmanned surface vehicle path planning”, Proceedings 2018 IEEE 7th Data Driven Control Learning System Conference DDCLS, pp. 209-212, 10.1109/DDCLS. 2018.8515966.
Crossref Google Scholar
 

Long, Y., Zuo, Z., Su, Y., Li, J. and Zhang, H. (2020), “An A*-based bacterial foraging optimisation algorithm for global path planning of unmanned surface vehicles”, Journal of Navigation, Vol. 73 No. 6, pp. 1247-1262, doi: 10.1017/S0373463320000247.
Crossref Google Scholar
 

Mousazadeh, H., Jafarbiglu, H., Abdolmaleki, H., Omrani, E., Monhaseri, F., Abdollahzadeh, M., Mohammadi-Aghdam, A., Kiapei, A., Salmani-Zakaria, Y. and Makhsoos, A. (2018), “Developing a navigation, guidance and obstacle avoidance algorithm for an unmanned surface vehicle (USV) by algorithms fusion”, Ocean Engineering, Vol. 159, pp. 56-65, doi: 10.1016/j.oceaneng.2018.04.018.
Crossref Google Scholar
 

Niu, H., Ji, Z., Savvaris, A. and Tsourdos, A. (2020), “Energy efficient path planning for unmanned surface vehicle in spatially-temporally variant environment”, Ocean Engineering, Vol. 196, doi: 10.1016/j.oceaneng.2019.106766.
Crossref Google Scholar
 

Niu, H., Lu, Y., Savvaris, A. and Tsourdos, A. (2016), “Efficient path planning algorithms for unmanned surface vehicle”, IFAC-PapersOnLine, Vol. 49 No. 23, pp. 121-126, doi: 10.1016/j.ifacol.2016.10.331.
Crossref Google Scholar
 

Özcan, M. and Yaman, U. (2019), “A continuous path planning approach on Voronoi diagrams for robotics and manufacturing applications”, Procedia Manufacturing, Vol. 38, pp. 1-8, doi: 10.1016/j.promfg.2020.01.001.
Crossref Google Scholar
 

Seda, M. and Pich, V. (2008), “Robot motion planning using generalised Voronoi diagrams”, Iscgav’08 Proceedings 8th Wseas International Conference Signal Processes Computational Geometry Artificial Vision, pp. 215-220,
Google Scholar
 

Singh, Y., Sharma, S., Sutton, R., Hatton, D. and Khan, A. (2018), “Feasibility study of a constrained Dijkstra approach for optimal path planning of an unmanned surface vehicle in a dynamic Maritime environment”, IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC), 117-122, 10.1109/ICARSC. 2018.8374170.
Crossref Google Scholar
 

Song, R., Liu, Y. and Bucknall, R. (2019), “Smoothed A* algorithm for practical unmanned surface vehicle path planning”, Applied Ocean Research, Vol. 83, pp. 9-20, doi: 10.1016/j.apor.2018.12.001.
Crossref Google Scholar
 
Wang, Q., Langerwisch, M. and Wagner, B. (2013), “Wide range global path planning for a large number of networked mobile robots based on generalized Voronoi diagrams”, PART 1. IFAC,
Crossref
 

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 – Proceedings of the 2nd International Conference on Transportation Information and Safety, pp. 2127-2136, 10.1061/9780784413036.285.
Crossref Google Scholar
 

Xia, G., Han, Z., Zhao, B., Liu, C. and Wang, X. (2019), “Global path planning for unmanned surface vehicle based on improved quantum ant colony algorithm”, Mathematical Problems in Engineering, Vol. 2019, doi: 10.1155/2019/2902170.
Crossref Google Scholar
 

Xiong, C., Chen, D., Lu, D., Zeng, Z. and Lian, L. (2019), “Path planning of multiple autonomous marine vehicles for adaptive sampling using Voronoi-based ant colony optimization”, Robotics and Autonomous Systems, Vol. 115, pp. 90-103, doi: 10.1016/j.robot.2019.02.002.
Crossref Google Scholar
 

Zhang, W., Xu, Y. and Xie, J. (2019b), “Path planning of USV based on improved hybrid genetic algorithm”, European Navigation Conference ENC, doi: 10.1109/EURONAV.2019.8714160.
Crossref Google Scholar
 

Zhang, J., Zhang, F., Liu, Z. and Li, Y. (2019a), “Efficient path planning method of USV for intelligent target search”, Journal of Geovisualization and Spatial Analysis, Vol. 3 No. 2, pp. 1-9, doi: 10.1007/s41651-019-0035-0.
Crossref Google Scholar
 

Zhou, C., Gu, S., Wen, Y., Du, Z., Xiao, C., Huang, L. and Zhu, M. (2019), “Motion planning for an unmanned surface vehicle based on topological position maps”, Ocean Engineering, Vol. 198, doi: 10.1016/j.oceaneng.2019.106798.
Crossref Google Scholar
 

Zhou, C., Gu, S., Wen, Y., Du, Z., Xiao, C., Huang, L. and Zhu, M. (2020), “The review unmanned surface vehicle path planning: based on multi-modality constraint”, Ocean Engineering, Vol. 200, doi: 10.1016/j.oceaneng.2020.107043.
Crossref Google Scholar
Journal of Intelligent and Connected Vehicles
Volume 5 Issue 3,
October 2022
Pages 250-259
DOI: 10.1108/JICV-01-2022-0001
Cite this article:
Zhao J, Ma X, Yang B, et al. Global path planning of unmanned vehicle based on fusion of A* algorithm and Voronoi field. Journal of Intelligent and Connected Vehicles, 2022, 5(3): 250-259. https://doi.org/10.1108/JICV-01-2022-0001

637

Views

29

Downloads

8

Crossref

7

Scopus

Altmetrics
Received: 03 January 2022
Revised: 03 May 2022
Accepted: 24 June 2022
Published: 15 July 2022
© 2022 Jiansen Zhao, Xin Ma, Bing Yang, Yanjun Chen, Zhenzhen Zhou and Pangyi Xiao. Published in Journal of Intelligent and Connected Vehicles. Published by Emerald Publishing Limited.

This article is published under the Creative Commons Attribution (CC BY 4.0) licence. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this licence maybe seen at http://creativecommons.org/licences/by/4.0/legalcode
Return