GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi Diagram
The sampling-based RRT* algorithm has been extensively employed for path planning. The improved variant, F-RRT*, significantly reduces the initial cost by generating new nodes; however, it also leads to increased computational time and poses challenges in narrow passage environments. To address thes...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10982149/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850040621984645120 |
|---|---|
| author | Yitao Zhong Xiaojing Zhu Jianfang Huang Yaokun Ye Zhaoming Wang Yuhuai Wang |
| author_facet | Yitao Zhong Xiaojing Zhu Jianfang Huang Yaokun Ye Zhaoming Wang Yuhuai Wang |
| author_sort | Yitao Zhong |
| collection | DOAJ |
| description | The sampling-based RRT* algorithm has been extensively employed for path planning. The improved variant, F-RRT*, significantly reduces the initial cost by generating new nodes; however, it also leads to increased computational time and poses challenges in narrow passage environments. To address these issues, this paper proposes an improved F-RRT* algorithm based on the Generalized Voronoi Diagram (GVD), called GVDF-RRT*. First, a sparse sampling strategy based on GVD is proposed, which improves the sampling efficiency and reduces the initial sampling nodes and initial time by guiding the random tree to explore the space quickly through GVD nodes. At the same time, the success rate of planning in narrow passage environments is improved by equalizing the sampling probability of each channel in the map. Secondly, a node direct connection mechanism is established, which reduces the redundant computation and further reduces the initial time by hierarchical processing of creation nodes, while combined with the forward optimization mechanism to optimize the paths in iteration, effectively reducing the path cost. Finally, simulations in three test environments show that, compared to RRT*, Q-RRT*, and F-RRT*, the GVDF-RRT* algorithm reduces the initial number of sampled nodes by 47.42%-76.57%, the initial time by 37.07%-86.00%, and the initial path cost by 0.47%-0.91%, while significantly improving the success rate in narrow passage environments. This further demonstrates that the proposed GVDF-RRT* significantly outperforms the baseline method in terms of initial performance and adaptability to narrow passage environments. |
| format | Article |
| id | doaj-art-0cf8f843b2c64960901a32284e75a30b |
| institution | DOAJ |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-0cf8f843b2c64960901a32284e75a30b2025-08-20T02:56:02ZengIEEEIEEE Access2169-35362025-01-0113789687898110.1109/ACCESS.2025.356630610982149GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi DiagramYitao Zhong0https://orcid.org/0009-0000-2841-9434Xiaojing Zhu1https://orcid.org/0000-0002-7348-1082Jianfang Huang2https://orcid.org/0009-0004-5284-0682Yaokun Ye3https://orcid.org/0009-0006-8068-1433Zhaoming Wang4https://orcid.org/0009-0001-7289-1290Yuhuai Wang5https://orcid.org/0000-0002-6376-8231School of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou, Zhejiang, ChinaSchool of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou, Zhejiang, ChinaZhejiang Machinery Industry Federation, Hangzhou, Zhejiang, ChinaSinofork Equipment Company Ltd., Huzhou, Zhejiang, ChinaSinofork Equipment Company Ltd., Huzhou, Zhejiang, ChinaSchool of Engineering, Hangzhou Normal University, Hangzhou, Zhejiang, ChinaThe sampling-based RRT* algorithm has been extensively employed for path planning. The improved variant, F-RRT*, significantly reduces the initial cost by generating new nodes; however, it also leads to increased computational time and poses challenges in narrow passage environments. To address these issues, this paper proposes an improved F-RRT* algorithm based on the Generalized Voronoi Diagram (GVD), called GVDF-RRT*. First, a sparse sampling strategy based on GVD is proposed, which improves the sampling efficiency and reduces the initial sampling nodes and initial time by guiding the random tree to explore the space quickly through GVD nodes. At the same time, the success rate of planning in narrow passage environments is improved by equalizing the sampling probability of each channel in the map. Secondly, a node direct connection mechanism is established, which reduces the redundant computation and further reduces the initial time by hierarchical processing of creation nodes, while combined with the forward optimization mechanism to optimize the paths in iteration, effectively reducing the path cost. Finally, simulations in three test environments show that, compared to RRT*, Q-RRT*, and F-RRT*, the GVDF-RRT* algorithm reduces the initial number of sampled nodes by 47.42%-76.57%, the initial time by 37.07%-86.00%, and the initial path cost by 0.47%-0.91%, while significantly improving the success rate in narrow passage environments. This further demonstrates that the proposed GVDF-RRT* significantly outperforms the baseline method in terms of initial performance and adaptability to narrow passage environments.https://ieeexplore.ieee.org/document/10982149/F-RRT*generalized Voronoi diagramnarrow passage problempath planningrapidly-exploring random tree |
| spellingShingle | Yitao Zhong Xiaojing Zhu Jianfang Huang Yaokun Ye Zhaoming Wang Yuhuai Wang GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi Diagram IEEE Access F-RRT* generalized Voronoi diagram narrow passage problem path planning rapidly-exploring random tree |
| title | GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi Diagram |
| title_full | GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi Diagram |
| title_fullStr | GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi Diagram |
| title_full_unstemmed | GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi Diagram |
| title_short | GVDF-RRT*: An Improved F-RRT* Path Planning Algorithm Based on Generalized Voronoi Diagram |
| title_sort | gvdf rrt an improved f rrt path planning algorithm based on generalized voronoi diagram |
| topic | F-RRT* generalized Voronoi diagram narrow passage problem path planning rapidly-exploring random tree |
| url | https://ieeexplore.ieee.org/document/10982149/ |
| work_keys_str_mv | AT yitaozhong gvdfrrtanimprovedfrrtpathplanningalgorithmbasedongeneralizedvoronoidiagram AT xiaojingzhu gvdfrrtanimprovedfrrtpathplanningalgorithmbasedongeneralizedvoronoidiagram AT jianfanghuang gvdfrrtanimprovedfrrtpathplanningalgorithmbasedongeneralizedvoronoidiagram AT yaokunye gvdfrrtanimprovedfrrtpathplanningalgorithmbasedongeneralizedvoronoidiagram AT zhaomingwang gvdfrrtanimprovedfrrtpathplanningalgorithmbasedongeneralizedvoronoidiagram AT yuhuaiwang gvdfrrtanimprovedfrrtpathplanningalgorithmbasedongeneralizedvoronoidiagram |