Hostname: page-component-6dbcb7884d-g628x Total loading time: 0 Render date: 2025-02-14T08:28:30.292Z Has data issue: false hasContentIssue false
  • English
  • Français

Decentralized method for real-time optimal path planning of robot in dynamic environment

Published online by Cambridge University Press:  12 February 2025

Chen Zhang Open the ORCID record for Chen Zhang [Opens in a new window] ,
Lelai Zhou  and
Yibin Li
Chen Zhang
Affiliation:
The Center for Robotics, School of Control Science and Engineering, Shandong University, Jinan, Shandong, China The Ministry of Education Engineering Research Center of Intelligent Unmanned System, Jinan, Shandong, China
Lelai Zhou*
Affiliation:
The Center for Robotics, School of Control Science and Engineering, Shandong University, Jinan, Shandong, China The Ministry of Education Engineering Research Center of Intelligent Unmanned System, Jinan, Shandong, China
Yibin Li
Affiliation:
The Center for Robotics, School of Control Science and Engineering, Shandong University, Jinan, Shandong, China The Ministry of Education Engineering Research Center of Intelligent Unmanned System, Jinan, Shandong, China
*
Corresponding author: Lelai Zhou; Email: zhoulelai@sdu.edu.cn
Get access Rights & Permissions [Opens in a new window]

Abstract

Adaptation to the dynamic environment and variable task sequence is the critical ability for robot navigation and task execution. The Cyclic Networking Rapidly-exploring Random Tree (CNRRT) method is proposed to obtain the optimal path in real time and realize long-term path planning ability in a complex dynamic environment. The cyclic branch is introduced to the acyclic graph of Rapidly-exploring Random Tree (RRT) method, which forms a decentralized path network in the configuration space. An iterative searching strategy is built to search for the optimal path in the network. The branch prune, reconnection, and regrowth processes enable the decentralized network to efficiently respond to dynamic changes in the environment. The CNRRT can search for the real-time optimal path in the dynamic environment, dealing with the configuration and task changes robustly. Besides, the CNRRT is consistent for scenarios with long-term task sequence without significant performance fluctuation. Simulations and real-world comparative experiments verify the effectiveness of the proposed method.

Keywords

cyclic networking RRTreal-time path planningoptimization searchdynamic environment
Type
Research Article
Information
Robotica , First View , pp. 1 - 17
Copyright
© The Author(s), 2025. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Zhang, C., Li, Y. and Zhou, L., “Optimal path and timetable planning method for multi-robot optimal trajectory,” IEEE Robot. Autom. Lett. 7(3), 8130–8137 (2022).CrossRefGoogle Scholar
Zhang, C., Zhou, L. and Li, Y., “Pareto optimal reconfiguration planning and distributed parallel motion control of mobile modular robots,” IEEE Trans. Ind. Electron. 71(8), 9255–9264 (2024).CrossRefGoogle Scholar
Yoon, S. and Shim, D. H., “SLPA* shape-aware lifelong planning A* for differential wheeled vehicles,” IEEE Trans. Intell. Transp. 16(2), 730–740 (2015).CrossRefGoogle Scholar
Mishra, M., An, W., Sidoti, D., Han, X., Ayala, D. F. M., Hansen, J. A., Pattipati, K. R. and Kleinman, D. L., “Context-aware decision support for anti-submarine warfare mission planning within a dynamic environment,” IEEE Trans. Syst. Man Cybernet. Syst. 50(1), 318–335 (2020).CrossRefGoogle Scholar
Yang, Q., Liu, J. and Li, L., “Path Planning of UAVs Under Dynamic Environment Based on a Hierarchical Recursive Multiagent Genetic Algorithm,” In: IEEE Congress on Evolutionary Computation (CEC) (2020) pp. 1–8.Google Scholar
Roberge, V., Tarbouchi, M. and Labonte, G., “Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning,” IEEE Trans. Ind. Inform. 9(1), 132–141 (2013).CrossRefGoogle Scholar
Wang, N. and Xu, H., “Dynamics-constrained global-local hybrid path planning of an autonomous surface vehicle,” IEEE Trans. Veh. Technol. 69(7), 6928–6942 (2020).CrossRefGoogle Scholar
Hu, C., Zhao, L. and Qu, G., “Event-triggered model predictive adaptive dynamic programming for road intersection path planning of unmanned ground vehicle,” IEEE Trans. Veh. Technol. 70(11), 11228–11243 (2021).CrossRefGoogle Scholar
James Bruce, M. V.. “Real-Time Randomized Path Planning for Robot Navigation.” In: Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2383–2388 (2002).CrossRefGoogle Scholar
Otte, M. and Frazzoli, E., “RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning,” Int. J. Robot. Res. 35(7), 797–822 (2016).CrossRefGoogle Scholar
Yuan, C., Liu, G., Zhang, W. and Pan, X., “An efficient RRT cache method in dynamic environments for path planning,” Robot. Auton. Syst. 131, 103595 (2020).CrossRefGoogle Scholar
Naderi, K., Rajamäki, J. and Hämäläinen, P.. “RT-RRT*: A Real-Time Path Planning Algorithm Based On RRT* .” In: Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games, pp. 113–118 (2015).CrossRefGoogle Scholar
Pfotzer, L., Klemm, S., Roennau, A., Zöllner, J. M. and Dillmann, R., “Autonomous navigation for reconfigurable snake-like robots in challenging, unknown environments,” Robot. Auton. Syst. 89, 123–135 (2017).CrossRefGoogle Scholar
Qi, J., Yang, H. and Sun, H., “MOD-RRT*: A sampling-based algorithm for robot path planning in dynamic environment,” IEEE Trans. Ind. Electron. 68(8), 7244–7251 (2021).CrossRefGoogle Scholar
Chi, W. and Meng, M. Q.-H.. “Risk-RRT*: A Robot Motion Planning Algorithm for the Human Robot Coexisting Environment.” In: Proceedings of the 2017 18th International Conference on Advanced Robotics (ICAR), pp. 583–588 (2017).CrossRefGoogle Scholar
Katiyar, S. and Dutta, A., “Dynamic path planning over CG-Space of 10DOF Rover with static and randomly moving obstacles using RRT* rewiring,” Robotica 40(8), 2610–2629 (2022).CrossRefGoogle Scholar
Jaillet, L. and Simeon, T.. “A PRM-based Motion Planner for Dynamically Changing Environments.” In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sendai, Japan, 2 (2004) pp. 1606–1611.Google Scholar
Belghith, K., Kabanza, F. and Hartman, L., “Randomized path planning with preferences in highly complex dynamic environments,” Robotica 31(8), 1195–1208 (2013).CrossRefGoogle Scholar
Wang, J., Meng, M. Q. H. and Khatib, O., “EB-RRT: Optimal motion planning for mobile robots,” IEEE Trans. Autom. Sci. Eng. 17(4), 2063–2073 (2020).CrossRefGoogle Scholar
Du, Z., Li, D., Zheng, K. and Liu, S., “Speed profile optimisation for intelligent vehicles in dynamic traffic scenarios,” Int. J. Syst. Sci. 51(12), 2167–2180 (2020).CrossRefGoogle Scholar
Daniel, K., Nash, A. and Koenig, S., “Theta*: Any-angle path planning on grids,” J. Artif. Intell. Res. 39, 533–579 (2010).CrossRefGoogle Scholar
Karaman, S. and Frazzoli, E., “Sampling-based algorithms for optimal motion planning,” Int. J. Robot. Res. 30(7), 846–894 (2011).CrossRefGoogle Scholar