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.
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
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
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
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
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
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
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
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
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
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
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
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
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 2015IEEE International conference on robotics and biomimetics (ROBIO), (2015) 1670-1677. https://doi.org/10.1109/robio.2015.7419012
Gammell, J. D., Barfoot, T. D., and Srinivasa, S. S. “Informed asymptotically optimal anytime search.” inInternational Journal of Robotics Research, (2017) 1-27. https://doi.org/10.1177/0278364919890396
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
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
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
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
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
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
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
Adiyatov, O., and Varol, H. A. “A novel RRT*-based algorithm for motion planning in Dynamic environments.” In 2017IEEE International Conference on Mechatronics and Automation (ICMA), (2017) 1416-1421. https://doi.org/10.1109/icma.2017.8016024
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
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
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
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
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
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
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
Pohan, M. A. R., & Utama, J. (2023). Efficient Sampling-based for Mobile Robot Path Planning in a Dynamic Environment Based on the Rapidly-exploring Random Tree and a Rule-template Sets. International Journal of Engineering, 36(4), 797-806. doi: 10.5829/ije.2023.36.04a.16
MLA
M. A. R. Pohan; J. Utama. "Efficient Sampling-based for Mobile Robot Path Planning in a Dynamic Environment Based on the Rapidly-exploring Random Tree and a Rule-template Sets". International Journal of Engineering, 36, 4, 2023, 797-806. doi: 10.5829/ije.2023.36.04a.16
HARVARD
Pohan, M. A. R., Utama, J. (2023). 'Efficient Sampling-based for Mobile Robot Path Planning in a Dynamic Environment Based on the Rapidly-exploring Random Tree and a Rule-template Sets', International Journal of Engineering, 36(4), pp. 797-806. doi: 10.5829/ije.2023.36.04a.16
VANCOUVER
Pohan, M. A. R., Utama, J. Efficient Sampling-based for Mobile Robot Path Planning in a Dynamic Environment Based on the Rapidly-exploring Random Tree and a Rule-template Sets. International Journal of Engineering, 2023; 36(4): 797-806. doi: 10.5829/ije.2023.36.04a.16