Abstract
Path planning through a bidirectional fast extended random tree algorithm cannot converge quickly, which does not meet the requirements of mobile robot path planning. To address this problem, an improved, central circle sampling bidirectional RRT (CC-BRRT) algorithm is proposed in this paper. The algorithm searches for the next sampling point by a central circle sampling strategy to reduce the numbers of searching nodes, and reduces the randomness by a target biasing strategy to speed up the convergence of the algorithm. For the obtained path, a sextic spline interpolation method is used to generate a smooth and executable path. Finally, experiments on mobile robot path planning are conducted both in simple with fewer obstacles and complex with more obstacles scenarios. The results show that the proposed CC-BRRT algorithm is superior to several other algorithms, with substantially fewer nodes sampled and a good smoothness and feasibility of the planned path.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Xiang, J.L., Wang, H.D., Ou, Y.: Algorithm of local path planning for unmanned surface vehicles based on improved Bi-RRT. Ship Build. China 061(001), 157–166 (2020)
Zhang, W.B., Xiao, J.L.: Application of improved RRT in intelligent vehicle path planning under complicated environment. China J. Highway Transp. 34(03), 225–234 (2020)
Ammar, A., Bennaceur, H., Châari, I., Koubâa, A., Alajlan, M.: Relaxed Dijkstra and A* with linear complexity for robot path planning problems in large-scale grid environments. Soft. Comput. 20(10), 4149–4171 (2015). https://doi.org/10.1007/s00500-015-1750-1
Wang, D.J.: Indoor mobile-robot path planning based on an improved A* algorithm. J. Tsinghua Univ. Sci. Technol. 52(08), 1085–1089 (2012)
Liu, C.J., Han, J.Q., Kang, A.: Dynamic path planning based on an improved RRT algorithm for roboCup robot. Robot 39(01), 8–15 (2017). https://doi.org/10.13973/j.cnki.robot.2017.0008
Song, J.Z., Dai, B., Shan, E.: An improved RRT path planning algorithm. Acta Electron. Sin. 38(2A), 225–228 (2010)
Tan, J.H., Pan, B., et al.: Robot path planning based on improved RRT*FN algorithm. Control Dec. 36(08), 1834–1840 (2020)
Zou, Q.J., Liu, S.H., Hou, Y.P.: Rapidly-exploring random tree algorithm for path re-planning based on reinforcement learning under the peculiar environment. Control Theory Appl. 37(08), 1737–1748 (2020)
Urmson, C., Simmons, R.: Approaches for heuristically biasing RRT growth. In: Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003), vol. 2, pp. 1178–1183 (2003). https://doi.org/10.1109/IROS.2003.1248805
Kuffner, J.J., LaValle, S.M.: RRT-Connect: an efficient approach to single-query path planning. In: IEEE International Conference on Robotics and Automation, vol.2, pp. 995–1001(2000). https://doi.org/10.1109/ROBOT.2000.844730
Song, X.L., Zhou, N., Huang, Z.Y.: An improved RRT algorithm of local path planning for vehicle collision avoidance. J. Hunan Univ. Nat. Sci. 44(4), 30–37 (2017)
Karaman, S., Frazzoli, E.: Incremental sampling-based algorithms for optimal motion planning. In: Robotics: Science and Systems (2010). https://arxiv.org/abs/1005.0416
Gao, M., et al.: Online anomaly detection via incremental tensor decomposition. In: Ni, W., Wang, X., Song, W., Li, Y. (eds.) WISA 2019. LNCS, vol. 11817, pp. 3–14. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30952-7_1
Pareektty, N., James, F., Ravindran, B.: RRT-HX: RRT with heuristic extend operations for motion planning in robotic systems. In: ASME International Design Engineering Technical Conferences & Computers & Information in Engineering Conference (2016). https://doi.org/10.1115/DETC2016-60547
Liu, J.S., Ji, H.Y., Li, Y.: Robot path planning based on improved bat algorithm and cubic spline interpolation. Acta Automatica Sinica (2020).
Mashayekhi, R., Idris, M., Anisi, M., et al.: Informed RRT*-Connect: an asymptotically optimal single-query path planning method. IEEE Access 8, 19842–19852 (2020). https://doi.org/10.1109/ACCESS.2020.2969316
Li, X.W., Yu, H.S.: RRT robot path planning algorithm based on bidirectional growth improvement. Mod. Comput. 21(4), 28–31 (2019)
Acknowledgment
This work was supported by National Natural Science Foundation of China (62071356), and Program for Science & Technology Development of Henan Province (202102310198, 212102210412).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Li, W., Ren, M., Zhu, Y., Zhang, Y., Zhou, S., Zhou, Y. (2021). CC-BRRT: A Path Planning Algorithm Based on Central Circle Sampling Bidirectional RRT. In: Xing, C., Fu, X., Zhang, Y., Zhang, G., Borjigin, C. (eds) Web Information Systems and Applications. WISA 2021. Lecture Notes in Computer Science(), vol 12999. Springer, Cham. https://doi.org/10.1007/978-3-030-87571-8_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-87571-8_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-87570-1
Online ISBN: 978-3-030-87571-8
eBook Packages: Computer ScienceComputer Science (R0)
