An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path Planning
In order to solve the problems of long path planning time and large number of redundant points in the rapidly-exploring random trees algorithm, this paper proposed an improved algorithm based on the parent point priority determination strategy and the real-time optimization strategy to optimize the...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/21/20/6907 |
| _version_ | 1797513147883454464 |
|---|---|
| author | Lijing Tian Zhizhuo Zhang Change Zheng Ye Tian Yuchen Zhao Zhongyu Wang Yihan Qin |
| author_facet | Lijing Tian Zhizhuo Zhang Change Zheng Ye Tian Yuchen Zhao Zhongyu Wang Yihan Qin |
| author_sort | Lijing Tian |
| collection | DOAJ |
| description | In order to solve the problems of long path planning time and large number of redundant points in the rapidly-exploring random trees algorithm, this paper proposed an improved algorithm based on the parent point priority determination strategy and the real-time optimization strategy to optimize the rapidly-exploring random trees algorithm. First, in order to shorten the path-planning time, the parent point is determined before generating a new point, which eliminates the complicated process of traversing the random tree to search the parent point when generating a new point. Second, a real-time optimization strategy is combined, whose core idea is to compare the distance of a new point, its parent point, and two ancestor points to the target point when a new point is generated, choosing the new point that is helpful for the growth of the random tree to reduce the number of redundant points. Simulation results of 3-dimensional path planning showed that the success rate of the proposed algorithm, which combines the strategy of parent point priority determination and the strategy of real-time optimization, was close to 100%. Compared with the rapidly-exploring random trees algorithm, the number of points was reduced by more than 93.25%, the path planning time was reduced by more than 91.49%, and the path length was reduced by more than 7.88%. The IRB1410 manipulator was used to build a test platform in a laboratory environment. The path obtained by the proposed algorithm enables the manipulator to safely avoid obstacles to reach the target point. The conclusion can be made that the proposed strategy has a better performance on optimizing the success rate, the number of points, the planning time, and the path length. |
| first_indexed | 2024-03-10T06:12:34Z |
| format | Article |
| id | doaj.art-9d0934098ebc4a3ca68d487ea17a4509 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T06:12:34Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-9d0934098ebc4a3ca68d487ea17a45092023-11-22T19:59:22ZengMDPI AGSensors1424-82202021-10-012120690710.3390/s21206907An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path PlanningLijing Tian0Zhizhuo Zhang1Change Zheng2Ye Tian3Yuchen Zhao4Zhongyu Wang5Yihan Qin6School of Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Technology, Beijing Forestry University, Beijing 100083, ChinaIn order to solve the problems of long path planning time and large number of redundant points in the rapidly-exploring random trees algorithm, this paper proposed an improved algorithm based on the parent point priority determination strategy and the real-time optimization strategy to optimize the rapidly-exploring random trees algorithm. First, in order to shorten the path-planning time, the parent point is determined before generating a new point, which eliminates the complicated process of traversing the random tree to search the parent point when generating a new point. Second, a real-time optimization strategy is combined, whose core idea is to compare the distance of a new point, its parent point, and two ancestor points to the target point when a new point is generated, choosing the new point that is helpful for the growth of the random tree to reduce the number of redundant points. Simulation results of 3-dimensional path planning showed that the success rate of the proposed algorithm, which combines the strategy of parent point priority determination and the strategy of real-time optimization, was close to 100%. Compared with the rapidly-exploring random trees algorithm, the number of points was reduced by more than 93.25%, the path planning time was reduced by more than 91.49%, and the path length was reduced by more than 7.88%. The IRB1410 manipulator was used to build a test platform in a laboratory environment. The path obtained by the proposed algorithm enables the manipulator to safely avoid obstacles to reach the target point. The conclusion can be made that the proposed strategy has a better performance on optimizing the success rate, the number of points, the planning time, and the path length.https://www.mdpi.com/1424-8220/21/20/6907rapidly-exploring random treesmanipulatorpriority determinationreal-time optimizationpath planning |
| spellingShingle | Lijing Tian Zhizhuo Zhang Change Zheng Ye Tian Yuchen Zhao Zhongyu Wang Yihan Qin An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path Planning Sensors rapidly-exploring random trees manipulator priority determination real-time optimization path planning |
| title | An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path Planning |
| title_full | An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path Planning |
| title_fullStr | An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path Planning |
| title_full_unstemmed | An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path Planning |
| title_short | An Improved Rapidly-Exploring Random Trees Algorithm Combining Parent Point Priority Determination Strategy and Real-Time Optimization Strategy for Path Planning |
| title_sort | improved rapidly exploring random trees algorithm combining parent point priority determination strategy and real time optimization strategy for path planning |
| topic | rapidly-exploring random trees manipulator priority determination real-time optimization path planning |
| url | https://www.mdpi.com/1424-8220/21/20/6907 |
| work_keys_str_mv | AT lijingtian animprovedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT zhizhuozhang animprovedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT changezheng animprovedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT yetian animprovedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT yuchenzhao animprovedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT zhongyuwang animprovedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT yihanqin animprovedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT lijingtian improvedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT zhizhuozhang improvedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT changezheng improvedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT yetian improvedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT yuchenzhao improvedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT zhongyuwang improvedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning AT yihanqin improvedrapidlyexploringrandomtreesalgorithmcombiningparentpointprioritydeterminationstrategyandrealtimeoptimizationstrategyforpathplanning |