IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality
Due to its asymptotic optimality, the Rapidly-exploring Random Tree star (RRT*) algorithm is widely used for robotic operations in complex environments. However, the RRT* algorithm suffers from poor path quality, slow convergence, and unstable generation of high-quality paths in the path planning pr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-09-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157824002350 |
| _version_ | 1827115079079821312 |
|---|---|
| author | Haidong Wang Huicheng Lai Haohao Du Guxue Gao |
| author_facet | Haidong Wang Huicheng Lai Haohao Du Guxue Gao |
| author_sort | Haidong Wang |
| collection | DOAJ |
| description | Due to its asymptotic optimality, the Rapidly-exploring Random Tree star (RRT*) algorithm is widely used for robotic operations in complex environments. However, the RRT* algorithm suffers from poor path quality, slow convergence, and unstable generation of high-quality paths in the path planning process. This paper proposes an Improved Bi-Tree Obstacle Edge Search Artificial Potential Field RRT* algorithm (IBPF-RRT*) to address these issues. First, based on the RRT* algorithm, this paper proposes a new obstacle edge search artificial potential field strategy (ESAPF), which speeds up the path search and improves the path quality simultaneously. Second, a bi-directional pruning strategy is designed to optimize the bi-directional search tree branch nodes and combine the bi-directional search strategy to reduce the number of iterations for convergence speed significantly. Third, a novel path optimization strategy is proposed, which enables high-quality paths to be generated stably by creating an entirely new node between two path nodes and then optimizing the paths using a pruning strategy based on triangular inequalities. Experimental results in three different scenarios show that the proposed IBPF-RRT* algorithm outperforms other methods in terms of optimal path quality, algorithm stability, and the number of iterations when compared to the RRT*, Q-RRT*, PQ-RRT*, F-RRT* and CCPF-RRT* algorithms, and proves the effectiveness of the proposed three strategies. |
| first_indexed | 2025-03-20T12:12:04Z |
| format | Article |
| id | doaj.art-6c2dbd9b98414ae39e38bdba6ddb51b8 |
| institution | Directory Open Access Journal |
| issn | 1319-1578 |
| language | English |
| last_indexed | 2025-03-20T12:12:04Z |
| publishDate | 2024-09-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj.art-6c2dbd9b98414ae39e38bdba6ddb51b82024-09-15T05:55:27ZengElsevierJournal of King Saud University: Computer and Information Sciences1319-15782024-09-01367102146IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path qualityHaidong Wang0Huicheng Lai1Haohao Du2Guxue Gao3School of The College of Computer Science and Technology, Xinjiang University, Urumqi 830017, China; The Key Laboratory of Signal Detection and Processing, Xinjiang Uygur Autonomous Region, Urumqi 830017, ChinaCorresponding author at: School of The College of Computer Science and Technology, Xinjiang University, Urumqi 830017, China.; School of The College of Computer Science and Technology, Xinjiang University, Urumqi 830017, China; The Key Laboratory of Signal Detection and Processing, Xinjiang Uygur Autonomous Region, Urumqi 830017, ChinaSchool of The College of Computer Science and Technology, Xinjiang University, Urumqi 830017, China; The Key Laboratory of Signal Detection and Processing, Xinjiang Uygur Autonomous Region, Urumqi 830017, ChinaSchool of The College of Computer Science and Technology, Xinjiang University, Urumqi 830017, China; The Key Laboratory of Signal Detection and Processing, Xinjiang Uygur Autonomous Region, Urumqi 830017, ChinaDue to its asymptotic optimality, the Rapidly-exploring Random Tree star (RRT*) algorithm is widely used for robotic operations in complex environments. However, the RRT* algorithm suffers from poor path quality, slow convergence, and unstable generation of high-quality paths in the path planning process. This paper proposes an Improved Bi-Tree Obstacle Edge Search Artificial Potential Field RRT* algorithm (IBPF-RRT*) to address these issues. First, based on the RRT* algorithm, this paper proposes a new obstacle edge search artificial potential field strategy (ESAPF), which speeds up the path search and improves the path quality simultaneously. Second, a bi-directional pruning strategy is designed to optimize the bi-directional search tree branch nodes and combine the bi-directional search strategy to reduce the number of iterations for convergence speed significantly. Third, a novel path optimization strategy is proposed, which enables high-quality paths to be generated stably by creating an entirely new node between two path nodes and then optimizing the paths using a pruning strategy based on triangular inequalities. Experimental results in three different scenarios show that the proposed IBPF-RRT* algorithm outperforms other methods in terms of optimal path quality, algorithm stability, and the number of iterations when compared to the RRT*, Q-RRT*, PQ-RRT*, F-RRT* and CCPF-RRT* algorithms, and proves the effectiveness of the proposed three strategies.http://www.sciencedirect.com/science/article/pii/S1319157824002350Rapidly-exploring Random Tree star (RRT*)Optimal path planningBarrier edge sampling |
| spellingShingle | Haidong Wang Huicheng Lai Haohao Du Guxue Gao IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality Journal of King Saud University: Computer and Information Sciences Rapidly-exploring Random Tree star (RRT*) Optimal path planning Barrier edge sampling |
| title | IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality |
| title_full | IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality |
| title_fullStr | IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality |
| title_full_unstemmed | IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality |
| title_short | IBPF-RRT*: An improved path planning algorithm with Ultra-low number of iterations and stabilized optimal path quality |
| title_sort | ibpf rrt an improved path planning algorithm with ultra low number of iterations and stabilized optimal path quality |
| topic | Rapidly-exploring Random Tree star (RRT*) Optimal path planning Barrier edge sampling |
| url | http://www.sciencedirect.com/science/article/pii/S1319157824002350 |
| work_keys_str_mv | AT haidongwang ibpfrrtanimprovedpathplanningalgorithmwithultralownumberofiterationsandstabilizedoptimalpathquality AT huichenglai ibpfrrtanimprovedpathplanningalgorithmwithultralownumberofiterationsandstabilizedoptimalpathquality AT haohaodu ibpfrrtanimprovedpathplanningalgorithmwithultralownumberofiterationsandstabilizedoptimalpathquality AT guxuegao ibpfrrtanimprovedpathplanningalgorithmwithultralownumberofiterationsandstabilizedoptimalpathquality |