Fast-RRT: A RRT-Based Optimal Path Finding Method
Source abstract
Abstract
As a sampling-based pathfinding algorithm, Rapidly Exploring Random Trees (RRT) has been widely used in motion planning problems due to the ability to find a feasible path quickly. However, the RRT algorithm still has several shortcomings, such as the large variance in the search time, poor performance in narrow channel scenarios, and being far from the optimal path. In this paper, we propose a new RRT-based path find algorithm, Fast-RRT, to find a near-optimal path quickly. The Fast-RRT algorithm consists of two modules, including Improved RRT and Fast-Optimal. The former is aims to quickly and stably find an initial path, and the latter is to merge multiple initial paths to obtain a near-optimal path. Compared with the RRT algorithm, Fast-RRT shows the following improvements: (1) A Fast-Sampling strategy that only samples in the unreached space of the random tree was introduced to improve the search speed and algorithm stability; (2) A Random Steering strategy expansion strategy was proposed to solve the problem of poor performance in narrow channel scenarios; (3) By fusion and adjustment of paths, a near-optimal path can be faster found by Fast-RRT, 20 times faster than the RRT* algorithm. Owing to these merits, our proposed Fast-RRT outperforms RRT and RRT* in both speed and stability during experiments.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Robotics and Sensor-Based Localization · Fluid Dynamics Simulations and Interactions
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Aeronautic Science and Engineering, Beihang University, Beijing 100191, China
Funding
National Natural Science Foundation of China
References (26)
Show source-provided references
1. A note on two problems in connexion with graphs10.1007/BF01386390 ↗
2. A formal basis for the heuristic determination of minimum cost paths10.1109/TSSC.1968.300136 ↗
3. Online graph pruning for pathfinding on grid maps10.1609/aaai.v25i1.7994 ↗
4. Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-d complex environments10.1109/LRA.2017.2663526 ↗
5. Practical search techniques in path planning for autonomous driving
6. Probabilistic roadmaps for path planning in high-dimensional configuration spaces10.1109/70.508439 ↗
7. Lavalle, S.M. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning, Computer Science Department, Iowa State University. Technical Report.
8. Lee, J., Kwon, O.S., Zhang, L., and Yoon, S.E. (2012, January 14–18). SR-RRT: Selective retraction-based RRT planner. Proceedings of the 2012 IEEE International Conference on Robotics and Automation, Saint Paul, MN, USA.
9. Research on Intelligent Vehicle Path Planning Based on Rapidly-Exploring Random Tree
10. Sampling-based algorithms for optimal motion planning10.1177/0278364911406761 ↗
11. RRT*-SMART: A rapid convergence implementation of RRT10.5772/56718 ↗
12. Neural RRT*: Learning-based optimal path planning10.1109/TASE.2020.2976560 ↗
13. RRT-connect: An efficient approach to single-query path planning
14. Finding a high-quality initial solution for the RRTs algorithms in 2D environments10.1017/S0263574719000195 ↗
15. Gammell, J.D., Srinivasa, S.S., and Barfoot, T.D. (2015, January 26–30). Batch informed trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs. Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.10.1109/ICRA.2015.7139620 ↗
16. Potential functions based sampling heuristic for optimal path planning10.1007/s10514-015-9518-0 ↗
17. Brunner, M., Brüggemann, B., and Schulz, D. (2013, January 6–10). Hierarchical rough terrain motion planning using an optimal sampling-based method. Proceedings of the 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, Germany.10.1109/ICRA.2013.6631372 ↗
18. A learning-based multi-RRT approach for robot path planning in narrow passages10.1007/s10846-017-0641-3 ↗
19. Gammell, J.D., Srinivasa, S.S., and Barfoot, T.D. (June, January 31). Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, Hong Kong, China.10.1109/IROS.2014.6942976 ↗
20. Hybrid rrt: A semi-dual-tree rrt-based motion planner10.1109/ACCESS.2020.2968471 ↗
21. Wang, J., Li, X., and Meng, M.Q.H. (2016, January 3–7). An improved rrt algorithm incorporating obstacle boundary information. Proceedings of the 2016 IEEE International Conference on Robotics and Biomimetics (ROBIO), Qingdao, China.10.1109/ROBIO.2016.7866392 ↗
22. Yershova, A., Jaillet, L., Siméon, T., and LaValle, S.M. (2005, January 18–22). Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain. Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain.
23. Islam, F., Nasir, J., Malik, U., Ayaz, Y., and Hasan, O. (2012, January 5–8). Rrt∗-smart: Rapid convergence implementation of rrt∗ towards optimal solution. Proceedings of the 2012 IEEE International Conference on Mechatronics and Automation, Chengdu, China.
24. RL-RRT: Kinodynamic motion planning via learning reachability estimators from RL policies10.1109/LRA.2019.2931199 ↗
25. Teaching robot navigation behaviors to optimal RRT planners10.1007/s12369-017-0448-1 ↗
26. Incremental sampling-based algorithms for optimal motion planning