Efficient Sampling-based for Mobile Robot Path Planning in a Dynamic Environment Based on the Rapidly-exploring Random Tree and a Rule-template Sets

Document Type : Special Issue for INCITEST 2022 Indonesia


Electrical Engineering Department, Universitas Komputer Indonesia, Jl. Dipatiukur 102-116, Bandung 40132, Indonesia


This study presents an efficient path planning method for mobile robots in a dynamic environment. The method is based on the rapidly-exploring random tree (RRT) algorithm. The two primary processes in mobile robot path planning in a dynamic environment are initial path planning and path re-planning. In order to generate a feasible initial path with fast convergence speed, we used a hybridization of rapidly-exploring random tree star and ant colony systems (RRT-ACS). When an obstacle obstructs the initial path, the path re-planner must be executed. In addition to the RRT-ACS algorithm, we proposed using a rule-template set based on the mobile robot in dynamic environment scenes during the path re-planner process. This novel algorithm is called RRT-ACS with Rule-Template Sets (RRT-ACS+RT). We conducted many benchmark simulations to validate the proposed method in a real dynamic environment. The performance of the proposed method is compared to the state-of-the-art path planning algorithms: RRT*FND and MOD-RRT*. Numerous experimental results demonstrate that the proposed method outperforms other comparison algorithms. The results show that the proposed method is suitable for the use on robots that need to navigate in a dynamic environment, such as self-driving cars.


Main Subjects

  1. Ganeshmurthy, M. S., and Suresh, G. R. “Path planning algorithm for autonomous mobile robot in dynamic environment.” In 2015 3rd International Conference on Signal Processing, Communication and Networking (ICSCN), (2015), 1-6. https://doi.org/10.1109/icscn.2015.7219901
  2. Ab Wahab, M. N., Lee, C. M., Akbar, M. F., and Hassan, F. H. “Path planning for mobile robot navigation in unknown indoor environments using hybrid PSOFS algorithm.” IEEE Access, Vol. 8, (2020), 161805-161815. https://doi.org/10.1109/access.2020.3021605
  3. Nascimento, L. B., Morais, D. S., Barrios-Aranibar, D., Santos, V. G., Pereira, D. S., Alsina, P. J., and Medeiros, A. A. “A Multi-Robot Path Planning Approach Based on Probabilistic Foam.” In 2019 Latin American Robotics Symposium (LARS), 2019 Brazilian Symposium on Robotics (SBR) and 2019 Workshop on Robotics in Education (WRE), (2019), 329-334. https://doi.org/10.1109/lars-sbr-wre48964.2019.00064
  4. Aria, M. “Optimal Path Planning using Informed Probabilistic Road Map Algorithm.” Journal of Engineering Research-ASSEEE Special Issue, (2021), 1-15. https://doi.org/10.36909/jer.asseee.16105
  5. Teshnizi, M. M., Kosari, A., Goliaei, S., and Shakhesi, S. “Centralized Path Planning for Multi-aircraft in the Presence of Static and Moving Obstacles.” International Journal of Engineering, Transactions B: Applications, Vol. 33, No. 5, (2020) 923-933. https://doi.org/10.5829/ije.2020.33.05b.25
  6. Connell, D., and Manh La, H. “Extended rapidly exploring random tree–based dynamic path planning and replanning for mobile robots.” International Journal of Advanced Robotic Systems, Vol. 15, No. 3 (2018), 1729881418773874. https://doi.org/10.1177/1729881418773874
  7. Zhang, H., Wang, Y., Zheng, J., and Yu, J. “Path planning of industrial robot based on improved RRT algorithm in complex environments.” IEEE Access, Vol. 6, (2018) 53296-53306. https://doi.org/10.1109/access.2018.2871222
  8. Li, X., Jiang, H., Shi, W., Chen, S., and Wang, Y. “Path planning of multipoint region attraction RRT* algorithm in complex environment.” In 2019 Chinese Control Conference (CCC), (2019) 4409-4414. https://doi.org/10.23919/chicc.2019.8865834
  9. Taheri, E. “Any-time randomized kinodynamic path planning algorithm in dynamic environments with application to quadrotor.” International Journal of Engineering, Transactions A: Basics, Vol. 34, No. 10, (2021) 2360-2370. https://doi.org/10.5829/ije.2021.34.10a.17
  10. Wang, J., Li, X., and Meng, M. Q. H. “An improved rrt algorithm incorporating obstacle boundary information.” In 2016 IEEE International Conference on Robotics and Biomimetics (ROBIO), (2016) 625-630. https://doi.org/10.1109/robio.2016.7866392
  11. Zhang, Y., Wang, R., Song, C., and Xu, J. “An Improved Dynamic Step Size RRT Algorithm in Complex Environments” In 2021 33rd Chinese Control and Decision Conference (CCDC), (2021) 3835-3840. https://doi.org/10.1109/ccdc52312.2021.9602069
  12. Solovey, K., Janson, L., Schmerling, E., Frazzoli, E., and Pavone, M. “Revisiting the asymptotic optimality of RRT.” In 2020 IEEE International Conference on Robotics and Automation (ICRA), (2020) 2189-2195. https://doi.org/10.1109/icra40945.2020.9196553
  13. Klemm, S., Oberländer, J., Hermann, A., Roennau, A., Schamm, T., Zollner, J. M., and Dillmann, R. “RRT-connect: Faster, asymptotically optimal motion planning.” In 2015 IEEE International conference on robotics and biomimetics (ROBIO), (2015) 1670-1677. https://doi.org/10.1109/robio.2015.7419012
  14. Gammell, J. D., Barfoot, T. D., and Srinivasa, S. S. “Informed asymptotically optimal anytime search.” in International Journal of Robotics Research, (2017) 1-27. https://doi.org/10.1177/0278364919890396
  15. Mashayekhi, R., Idris, M. Y. I., Anisi, M. H., Ahmedy, I., and Ali, I. “Informed RRT*-connect: An asymptotically optimal single-query path planning method.” IEEE Access, Vol. 8, (2020) 19842-19852. https://doi.org/10.1109/access.2020.2969316
  16. Pohan, M. A. R., Trilaksono, B. R., Santosa, S. P., and Rohman, A. S. “Path Planning Algorithm Using the Hybridization of the Rapidly-Exploring Random Tree and Ant Colony Systems.” IEEE Access, Vol. 9, (2021) 153599-153615. https://doi.org/10.1109/access.2021.3127635
  17. Connell, D., and La, H. M. “Dynamic path planning and replanning for mobile robots using RRT.” In 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), (2017) 1429-1434. https://doi.org/10.1109/smc.2017.8122814
  18. Yaghmaee, F., and Koohi, H. “Dynamic obstacle avoidance by distributed algorithm based on reinforcement learning.” International Journal of Engineering, Transactions B: Applications, Vol. 28, No. 2, (2015) 198-204. https://doi.org/10.5829/idosi.ije.2015.28.02b.05
  19. Kala, R., Shukla, A., and Tiwari, R. “Robot path planning using dynamic programming with accelerating nodes.” Paladyn, Vol. 3, 1, (2012) 23-34. https://doi.org/10.2478/s13230-012-0013-4
  20. Meng, L., Qing, S., and Jun, Z. Q. “UAV path re-planning based on improved bidirectional RRT algorithm in dynamic environment.” In 2017 3rd International Conference on Control, Automation and Robotics (ICCAR), (2017) 658-661. https://doi.org/10.1109/iccar.2017.7942779
  21. Chen, Y., and Wang, L. “Adaptively Dynamic RRT*-Connect: Path Planning for UAVs Against Dynamic Obstacles.” In 2022 7th International Conference on Automation, Control and Robotics Engineering (CACRE), (2022) 1-7. https://doi.org/10.1109/cacre54574.2022.9834188
  22. Adiyatov, O., and Varol, H. A. “A novel RRT*-based algorithm for motion planning in Dynamic environments.” In 2017 IEEE International Conference on Mechatronics and Automation (ICMA), (2017) 1416-1421. https://doi.org/10.1109/icma.2017.8016024
  23. Qi, J., Yang, H., and Sun, H. “MOD-RRT*: A sampling-based algorithm for robot path planning in dynamic environment.” IEEE Transactions on Industrial Electronics, Vol. 68, No. 8, (2020) 7244-7251. https://doi.org/10.1109/tie.2020.2998740
  24. Wei, K., Chu, Y., and Gan, H. “An improved Rapidly-exploring Random Tree Approach for Robotic Dynamic Path Planning.” In 2021 11th International Conference on Intelligent Control and Information Processing (ICICIP), (2021) 181-187. https://doi.org/10.1109/icicip53388.2021.9642182
  25. Meng, C., and Dai, H. “An Obstacle Avoidance Method Based on Advanced Rapidly-exploring Random Tree for Autonomous Navigation.” In 2021 IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), (2021) 1118-1125. IEEE. https://doi.org/10.1109/ispa-bdcloud-socialcom-sustaincom52081.2021.00154
  26. Ma, L., Xue, J., Kawabata, K., Zhu, J., Ma, C., and Zheng, N. “Efficient sampling-based motion planning for on-road autonomous driving.” IEEE Transactions on Intelligent Transportation Systems, Vol. 16, No. 4, (2015) 1961-1976. https://doi.org/10.1109/tits.2015.2389215
  27. Jin, Q., Tang, C., and Cai, W. “Research on Dynamic Path Planning Based on the Fusion Algorithm of Improved Ant Colony Optimization and Rolling Window Method.” IEEE Access, Vol. 10, (2021) 28322-28332. https://doi.org/10.1109/access.2021.3064831
  28. Wei, K., and Ren, B. “A method on dynamic path planning for robotic manipulator autonomous obstacle avoidance based on an improved RRT algorithm.” Sensors, Vol. 18, No. 2 (2018), 571. https://doi.org/10.3390/s18020571
  29. Wang J., Meng M. Q. -H., and Khatib, O. "EB-RRT: Optimal Motion Planning for Mobile Robots," in IEEE Transactions on Automation Science and Engineering, Vol. 17, No. 4 (2020), 2063-2073, https://doi.org/10.1109/TASE.2020.2987397