Enhanced RRT* with APF and Halton Sequence for Robot Path Planning
DOI:
https://doi.org/10.18196/jrc.v6i2.24921Keywords:
Path Planning, Rapid-Exploring Random Tree, Artificial Potential Fields, Halton Sequence, Free Cartesian Space (FCS)Abstract
This paper presents a new path planning method (APF-IRRT*-HS), which relies on the optimization process of the conventional RRT* algorithm and combined with the APF method where the sampling process of the RRT* algorithm is improved using the Halton sequence, which is known to be deterministic and repeatable and provides more efficient coverage than other low discrepancy sequences with the modified goal-based method which provides a probabilistic approach to decide whether to sample from a point directly at the target or to choose a random point from the Halton sequence based on the current distance. We implemented the proposed method in two cases of mass point and two-link robots. The proposed method compares path length with the conventional RRT* algorithm and APF-RRT*, as well as time efficiency and number of iterations. The technique proves effective in various dynamic environments. Specifically, the APF-IRRT*-HS algorithm achieved an improvement of approximately 21.88% and 7.5% in path length, 79.75% and 49.2% in computation time, and 57.39% and 40% in the number of iterations compared with the RRT* and RRT*-APF algorithms, respectively. We can use this method in everyday applications such as robotic arms, drones, self-driving cars, etc. More advanced methods, such as multi-link robots and real-time constraints, can be used in the future.
References
D. K. Muhsen, A. T. Sadiq, and F. A. Raheem, "A Systematic Review of Rapidly Exploring Random Tree RRT Algorithm for Single and Multiple Robots," Cybernetics and Information Technologies, vol 24, no. 1, 2024.
A. A. Kareem, B. K. Oleiwi, and M. J. Mohamed, "Planning the Optimal 3D Quadcopter Trajectory Using a Delivery System-Based Hybrid Algorithm," International Journal of Intelligent Engineering and Systems, vol. 16, no. 2, pp. 427–439, 2023.
F. N. Irzoqe, F. A. Raheem, and A. R. Nasser, "Path Planning Improvement Using a Modified Q-learning Algorithm Based on Artificial Potential Field," International Journal of Intelligent Engineering and Systems, vol. 17, no. 4, 2024.
Z. A. Ahmed and S. M. Raafat, "Enhanced Global Path Planning Efficiency by Bidirectional A*, Gradient Descent, and Orientation Interpolation Algorithms," International Journal of Intelligent Engineering and Systems, vol. 16, no. 5, 2023, doi: 10.22266/ijies2023.1031.39.
R. Kamil, M. Mohamed, and B. Oleiwi, "Path Planning of Mobile Robot Using Improved Artificial Bee Colony Algorithm," Engineering and Technology Journal, vol. 38, no. 9, pp. 1384–1395, Sep. 2020, doi: 10.30684/etj.v38i9a.1100.
A. A. Kareem, B. K. Oleiwi, and M. J. Mohamed, "Unmanned aerial vehicle path planning in a 3D environment using a hybrid algorithm," Journal of Field Robotics, vol. 13, no. 2, pp. 905-915, 2024
X. Zhou, J. Yan, M. Yan, K. Mao, R. Yang, and W. Liu, "Path Planning of Rail-Mounted Logistics Robots Based on the Improved Dijkstra Algorithm," Appl. Sci., vol. 13, p. 9955, 2023.
F. A. Raheem, A. T. Sadiq, and N. A. F. Abbas, "Ant colony algorithm improvement for robot arm path planning optimization based on D* strategy," Int. J. Mech. Mechatron. Eng., vol. 21, pp. 96–111, 2021.
F. A. Raheem and M. Abdulkareem, "Development of A* Algorithm for Robot Path Planning Based on Modified Probabilistic Roadmap and Artificial Potential Field," Journal of Engineering Science and Technology, vol. 15, pp. 3034–3054, 2020.
B. Li and B. Chen, "An adaptive rapidly- exploring random tree," IEEE/CAA Journal of Automatica Sinica, vol. 9, no. 2, pp. 283–294, 2021.
F. Raheem and M. Abdulakareem, "Development of Path Planning Algorithm Using Probabilistic Roadmap Based on Ant Colony Optimization," Engineering and Technology Journal, vol. 38, no. 3A, pp. 343–351, Mar. 2020, doi: 10.30684/etj.v38i3a.389.
S. Rahman, S. Akter, and S. Yoon, "A Deep Q-Learning Based UAV Detouring Algorithm in a Constrained Wireless Sensor Network Environment," Electronics, vol. 14, no. 1, 2025, doi: 10.3390 electronics14010001.
O. Syzonov, S. Tomasiello, and N. Capuano, “New Insights into Fuzzy Genetic Algorithms for Optimization Problems,” Algorithms, vol. 17, p. 549, 2024, doi: 10.3390/a17120549.
J. A. P. Ferreira and M. S. A. Teixeira, "Robust Linear Control for Autonomous Systems in Uncertain Environments," IEEE Transactions on Automatic Control, vol. 68, no. 10, pp. 5635-5647, 2023, doi: 10.1109/TAC.2023.3156754.
Y. Zhang and X. Liu, "Energy-Efficient Path Planning for UAVs Using Optimal Control," Journal of Field Robotics, vol. 41, no. 3, pp. 345-358, 2024, doi: 10.1002/rob.22317.
D. K. Muhsen, A. T. Sadiq, and F. A. Raheem, "Memorized Rapidly Exploring Random Tree Optimization (MRRTO): An Enhanced Algorithm for Robot Path Planning," Cybernetics and Information Technologies, vol. 24, no 1, pp. 190-204, 2024.
K. Ran, Y. Wang, C. Fang, Q. Chai, X. Dong, and G. Liu, “Improved RRT* Path-Planning Algorithm Based on the Clothoid Curve for a Mobile Robot Under Kinematic Constraints,” Sensors, vol. 24, p. 7812, 2024, doi: 10.3390/s24237812.
S. Davarzani and M. T. Ejaz, “A 2D path-planning performance comparison of RRT and RRT* for unmanned ground vehicles,” IAES International Journal of Robotics and Automation (IJRA), vol. 13, no. 1, pp. 105-112, 2024.
D. Wu, L. Wei, G. Wang, L. Tian, and G. Dai, "APF-IRRT*: An improved informed rapidly-exploring random trees-star algorithm by introducing artificial potential field method for mobile robot path planning," Appl. Sci., vol. 12, no. 21, p. 10905, Oct. 2022.
W. Burzynski, and W. Stecz, "Trajectory planning with multiplatform spacetime RRT*," Appl. Intell., vol. 54, 9524–9541, 2024.
Y. Li, "Comparative Analysis of Hybrid A* and RRT* Algorithms an Transactions on Computer Science and Intelligent Systems Research," IEEE Access, vol. 8, pp. 18658–18668.
J. Liang, W. Luo, and Y. Qin, "Path Planning of Multi-Axis Robotic Arm Based on Improved RRT∗," CMC, vol. 81, no. 1, 2024, doi: 10.32604/cmc.2024.055883.
R. Mashayekhi, M. Y. I. Idris, M. H. Anisi, I. Ahmedy, and I. Ali, "Informed RRT*-Connect: An Asymptotically Optimal Single-Query Path Planning Method," IEEE Access, vol. 8, 2020.
L. Keyu, L. Yonggen, and Z. Yanchi, "Dynamic obstacle avoidance path planning of UAV Based on improved APF," Proceedings of the 2020 5th International Conference on Communication, Image and Signal Processing (CCISP), pp. 159–163, 2020.
Q. Diao, J. Zhang, M. Liu, and J. Yang, "A Disaster Relief UAV Path Planning Based on APF-IRRT* Fusion Algorithm," Drones, vol. 7, no. 5, p. 323, May 2023.
J. Gao, X. Zheng, P. Liu, P. Yang, J. Yu, and Y. Dai, "APF-IBRRT*: A Global Path Planning Algorithm for Obstacle Avoidance Robots With Improved Iterative Search Efficiency," in IEEE Access, vol. 12, pp. 124740-124750, 2024, doi: 10.1109/ACCESS.2024.3451616.
X. Jin, Z. Yan, H. Yang, Q. Wang, and G. Yin, "A Goal-Biased RRT Path Planning Approach for Autonomous Ground Vehicle," Proceedings of the 2020 4th CAA International Conference on Vehicular Control and Intelligence (CVCI), pp. 743–746, 2020.
E. I. Atanassov, “On the discrepancy of the Halton sequences,” Math. Balkanica (NS), vol. 18, no. 1-2, pp. 15-32, 2004.
Y. Zhao, K. Liu, G. Lu, Y. Hu, and S. Yuan, “Path Planning of UAV Delivery Based on Improved APF-RRT* Algorithm,” J. Phys. Conf. Ser., vol. 1624, no. 4, p. 042004, 2020.
S. Huang, "Path planning based on mixed algorithm of RRT and artificial poten- tial field method," in 2021 4th International Conference on Intelligent Robotics and Control Engineering (IRCE), pp. 149–155, 2021.
L. Wang, X. Yang, Z. L. Chen, and B. R. Wang, "Application of the improved rapidly exploring random tree algorithm to an insect-like mobile robot in a narrow environment," Biomimetics, vol. 8, no. 4, 2023.
F. N. Irzoqe, F. A. Raheem, and A. R. Nasser, "A New Approach for Path Planning Algorithm Utilizing Modified Deep Q-Network Combined with Artificial Potential Field," International Journal of Intelligent Engineering and Systems, vol. 17, no. 6, 2024.
D. K. Muhsen, A. T. Sadiq, and F. A. Raheem, "Improved rapidly exploring random tree using salp swarm algorithm," Journal of Intelligent Systems, vol. 33, p. 20230219, 2024.
X. Zhong, Z. Wei, and T. Chen, "Motion Planning and Pose Control for Flexible Spacecraft Using Enhanced LQR-RRT*," in IEEE Transactions on Aerospace and Electronic Systems, vol. 59, no. 6, pp. 8743-8751, Dec. 2023, doi: 10.1109/TAES.2023.3309612.
W. Wu, "Research Process of Path Planning based on RRT Algorithm and Its Improvements," Transactions on Computer Science and Intelligent Systems Research, vol. 5, 2024
X. Li, G. Li, and Z. Bian, “Research on autonomous vehicle path planning algorithm based on improved RRT* algorithm and artificial potential field method,” Sensors, vol. 24, p. 3899, 2024.
X. Jiang, Z. Wang, and C. Dong, "A Path Planning Algorithm Based on Improved RRT Sampling Region," Computers, Materials ,and Continua CMC, vol. 80, no. 3, 2024, doi: 10.32604/cmc.2024.054640.
Q. Li, J. Wang, H. Li, B. Wang, and C. Feng, “Fast-RRT*: an improved motion planner for mobile robot in two-dimensional space,” IEEJ Trans Electr Electron Eng, vol. 17, pp. 200–208, 2022.
L. Li, W. Wu, Z. Li, and F. Wang, "Collision Avoidance Method for Unmanned Ships by Using a Modified APF Algorithm," Research Square, 2024.
M. M. Badr and F. A. Raheem, "Development of Modified path planning algorithm using artificial potential field (APF) based on PSO for factors optimization," American Scientific Research Journal for Engineering, Technology, and Sciences, vol. 37, no. 1, 2017.
J. Gao, X. Xu, Q. Pu, P. B. Petrovic, A. Rodi'c, and Z. Wang, “A Hybrid Path Planning Method Based on Improved A* and CSA-APF Algorithms,” IEEE Access, vol. 12, pp. 39139–39151, 2024.
F. A. Raheem and M. M. Badr, "Smoothed artificial potential field (apf) via points path planning algorithm based on pso," AL-yarmouk Journall, vol. 11, no. 1, 2019.
Y. Chen, G. Bai, Y. Zhan, X. Hu, and J. Liu, "Path Planning and Obstacle Avoiding of the USV Based on Improved ACO-APF Hybrid Algorithm with Adaptive Early-Warning," IEEE Access, vol. 9, pp. 36829-36839, 2021.
A. Ma’Arif, W. Rahmaniar, M. A. M. Vera, A. A. Nuryono, R. Majdoubi, and A. Çakan, "Artificial Potential Field Algorithm for Obstacle Avoidance in UAV Quadrotor for Dynamic Environment," 2021 IEEE International Conference on Communication, Networks and Satellite (COMNETSAT), pp. 184-189, 2021, doi: 10.1109/COMNETSAT53002.2021.9530803.
I. Suwarno, W. A. Oktaviani, Y. Apriani, D. U. Rijalusalam, and A. Pandey, "Potential Force Algorithm with Kinematic Control as Path Planning for Disinfection Robot," Journal of Robotics and Control (JRC), vol. 3, no. 1, 2022, doi: 10.18196/jrc.v3i1.11528.
F. A. Raheem, S. M. Raafat, and S. M. Mahdi, "Robot Path-Planning Research Applications in Static and Dynamic Environments," Earth Systems Protection and Sustainability, vol. 1, pp. 291–325, 2022, doi: 10.1007/978-3-030-85829-2_12.
S. A. Nagy, M. A. El-Beltagy, and M. Wafa, "Multilevel Monte Carlo by. Using the Halton Sequence," Monte Carlo Methods and Applications, vol. 26, no. 3, pp. 193-203, 2020, doi: 10.1515/mcma-2020-2065.
H. Zhong, M. Cong, M. Wang, Y. Du, and D. Liu, “HB-RRT: A path planning algorithm for mobile robots using Halton sequence-based rapidly-exploring random tree,” Engineering Applications of Artificial Intelligence, vol. 133, p. 108362, 2024, doi: 10.1016/j.engappai.2024.108362.
W. H. Bangyal, K. Nisar, A. A. B. Ibrahim, M. R. Haque, J. J. Rodrigues, and D. B. Rawat, "Comparative Analysis of Low Discrepancy Sequence-Based Initialization Approaches Using Population-Based Algorithms for Solving the Global Optimization Problems," Appl.Sci., vol. 11, p. 7591, 2021.
J. Wang and P. Wu, "An Improved Three-point Method for Power Flow Calculation Based on Halton Sequence," Frontiers in Computing and Intelligent Systems, vol. 4, no. 1, 2023.
N. Kirk and C. Lemieux, "An Improved Halton Sequence for Implementation in Quasi-Monte Carlo Methods," arXiv:2405.15799v1, 2024.
A. Kumar, A. Sahasrabudhe, C. Perugu, S. Nirgude, and A. Murugan, "Kinematics & Dynamics Library for Baxter Arm," arXiv:2409.00867v1, 2024.
A. N. Sharkawy, “Forward and inverse kinematics solution of a robotic manipulator using a multilayer feedforward neural network,” Journal of Mechanical and Energy Engineering, vol. 6, no. 2, 2022.
M. Zavar, "Forward and Inverse Kinematics of 4-DoF SCARA: Using Optimization Algorithms," Journal of Applied Dynamic Systems and Control, vol. 6, no. 3, pp. 25-34, 2023.
R. V. N. Kumar and R. Sreenivasulu, "Inverse Kinematics (IK) Solution of a Robotic Manipulator using PYTHON," Journal of Mechatronics and Robotics, vol. 3, pp. 542-551, 2019.
W. E. Abdul-Lateef, Y. N. Ibrahem-Alothman, and S. A. Gitaffa, "An optimal motion path planning control of a robotic manipulator based on the hybrid PI-sliding mode controller," Bulletin of Electrical Engineering and Informatics, vol. 12, no. 2, pp. 727-737, 2023.
N. A. El-khateeb and R. I. Badr, "Novel PID Tracking Controller for 2DOF Robotic Manipulator System Based on Artificial Bee Colony Algorithm," Electrical, Control and Communication Engineering, vol. 13, no. 1, pp. 55–62, Dec. 2017.
F. Loucif and S. Kechida, “Optimization of sliding mode control with PID surface for robot manipulator by evolutionary algorithms,” Open Computer Science, vol. 10, no. 1, pp. 396-407, 2020.
F. A. Raheem, A. T. Sadiq, and N. A. F. Abbas, “Robot arm free Cartesian space analysis for heuristic path planning enhancement,” Int. J. Mech. Mechatron. Eng, vol. 19, pp. 29-42, 2019.
Q. Chai and Y. Wang, "RJ-RRT: Improved RRT for Path Planning in Narrow Passages," Applied Sciences, vol. 12, no. 23, p. 12033, 2022.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Mohammed Thamer Hameed
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
This journal is based on the work at https://journal.umy.ac.id/index.php/jrc under license from Creative Commons Attribution-ShareAlike 4.0 International License. You are free to:
- Share – copy and redistribute the material in any medium or format.
- Adapt – remix, transform, and build upon the material for any purpose, even comercially.
The licensor cannot revoke these freedoms as long as you follow the license terms, which include the following:
- Attribution. You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- ShareAlike. If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
- No additional restrictions. You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
• Creative Commons Attribution-ShareAlike (CC BY-SA)
JRC is licensed under an International License
