RJ-RRT: Improved RRT for Path Planning in Narrow Passages
Source abstract
Abstract
As a representative of sampling-based planning algorithms, rapidly exploring random tree (RRT), is extensively welcomed in solving robot path planning problems due to its wide application range and easy addition of nonholonomic constraints. However, it is still challenging for RRT to plan the path for configuration space with narrow passages. As a variant algorithm of RRT, rapid random discovery vine (RRV) gives a better solution, but when configuration space contains more obstacles instead of narrow passages, RRV performs slightly worse than RRT. In order to solve these problems, this paper re-examines the role of sampling points in RRT. Firstly, according to the state of the random tree expanding towards the current sampling point, a greedy sampling space reduction strategy is proposed, which decreases the redundant expansion of the random tree in space by dynamically changing the sampling space. Secondly, a new narrow passage judgment method is proposed according to the environment around of sampling point. After the narrow passage is identified, the narrow passage is explored by generating multiple subtrees inside the passage. The subtrees can be merged into the main tree that expands in a larger area by subsequent sampling. These improvements further enhance the value of sampling points. Compared with the existing RRT algorithms, the adaptability for different environments is improved, and the planning time and memory usage are saved.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Robotics and Sensor-Based Localization · Control and Dynamics of Mobile Robots
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Computer and Information Science, Southwest University, Chongqing 400715, China
Funding
Chongqing science and Technology Bureau
References (30)
Show source-provided references
1. A review of global path planning methods for occupancy grid maps regardless of obstacle density10.1007/s10846-016-0362-z ↗
2. Sampling-based path planning on configuration-space costmaps10.1109/TRO.2010.2049527 ↗
3. A formal basis for the heuristic determination of minimum cost paths10.1109/TSSC.1968.300136 ↗
4. A note on two problems in connexion with graphs10.1007/BF01386390 ↗
5. Hegedűs, T., Németh, B., and Gáspár, P. (2020). Design of a low-complexity graph-based motion-planning algorithm for autonomous vehicles. Appl. Sci., 10.10.3390/app10217716 ↗
6. Probabilistic roadmaps for path planning in high-dimensional configuration spaces10.1109/70.508439 ↗
7. LaValle, S.M. (2022, September 10). Rapidly-Exploring Random Trees: A New Tool for Path Planning. Available online: http://msl.cs.illinois.edu/~lavalle/papers/Lav98c.pdf.
8. LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press.10.1017/CBO9780511546877 ↗
9. Sampling-based robot motion planning: A review10.1109/ACCESS.2014.2302442 ↗
10. Hsu, D., Latombe, J.C., and Motwani, R. (1997, January 25). Path planning in expansive configuration spaces. Proceedings of the International Conference on Robotics and Automation, Albuquerque, NM, USA.
11. Hsu, D., Kavraki, L.E., Latombe, J.C., Motwani, R., and Sorkin, S. (1998). On finding narrow passages with probabilistic roadmap planners. Robotics: The algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics, CRC Press.
12. Wilmarth, S.A., Amato, N.M., and Stiller, P.F. (1999, January 10–15). MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space. Proceedings of the 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C), Detroit, MI, USA.
13. Boor, V., Overmars, M.H., and Van Der Stappen, A.F. (1999, January 10–15). The Gaussian sampling strategy for probabilistic roadmap planners. Proceedings of the 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C), Detroit, MI, USA.
14. Hsu, D., Jiang, T., Reif, J., and Sun, Z. (2003, January 14–19). The bridge test for sampling narrow passages with probabilistic roadmap planners. Proceedings of the 2003 IEEE international conference on robotics and automation (cat. no. 03CH37422), Taipei, Taiwan.
15. Aarno, D., Kragic, D., and Christensen, H.I. (May, January 26). Artificial potential biased probabilistic roadmap method. Proceedings of the IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004, New Orleans, LA, USA.10.1109/ROBOT.2004.1307192 ↗
16. Denny, J., and Amato, N.M. (2011, January 25–30). Toggle PRM: Simultaneous mapping of C-free and C-obstacle-a study in 2D. Proceedings of the 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, USA.10.1109/IROS.2011.6048865 ↗
17. 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.
18. Zhang, L., and Manocha, D. (2008, January 19–23). An efficient retraction-based RRT planner. Proceedings of the 2008 IEEE International Conference on Robotics and Automation, Pasadena, CA, USA.
19. Wu, Z., Meng, Z., Zhao, W., and Wu, Z. (2021). Fast-RRT: A RRT-Based Optimal Path Finding Method. Appl. Sci., 11.10.3390/app112411777 ↗
20. Strandberg, M. (May, January 26). Augmenting RRT-planners with local trees. Proceedings of the IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004, New Orleans, LA, USA.10.1109/ROBOT.2004.1308756 ↗
21. Wang, W., Li, Y., Xu, X., and Yang, S.X. (2010, January 3–7). An adaptive roadmap guided Multi-RRTs strategy for single query path planning. Proceedings of the 2010 IEEE International Conference on Robotics and Automation, Anchorage, AK, USA.
22. Lai, T., Ramos, F., and Francis, G. (2019, January 20–24). Balancing global exploration and local-connectivity exploitation with rapidly-exploring random disjointed-trees. Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada.10.1109/ICRA.2019.8793618 ↗
23. Shi, K., Denny, J., and Amato, N.M. (June, January 31). Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages. Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, China.10.1109/ICRA.2014.6907540 ↗
24. Liu, H., Xiao, F., and Wang, C. (2015, January 26–30). A predictive model for narrow passage path planner by using support vector machine in changing environments. Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.10.1109/ICRA.2015.7139609 ↗
25. Baldwin, I., and Newman, P. (2010, January 18–22). Non-parametric learning for natural plan generation. Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, Taipei, Taiwan.10.1109/IROS.2010.5651569 ↗
26. A learning-based multi-RRT approach for robot path planning in narrow passages10.1007/s10846-017-0641-3 ↗
27. Neural RRT*: Learning-based optimal path planning10.1109/TASE.2020.2976560 ↗
28. An adaptive rapidly-exploring random tree10.1109/JAS.2021.1004252 ↗
29. Kuffner, J.J., and LaValle, S.M. (2000, January 24–28). RRT-connect: An efficient approach to single-query path planning. Proceedings of the 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), San Francisco, CA, USA.
30. A fast procedure for computing the distance between complex objects in three-dimensional space10.1109/56.2083 ↗