APF-IRRT*: An Improved Informed Rapidly-Exploring Random Trees-Star Algorithm by Introducing Artificial Potential Field Method for Mobile Robot Path Planning
Source abstract
Abstract
An Informed RRT* (IRRT*) algorithm is one of the optimized versions of a Rapidly-exploring Random Trees (RRT) algorithm which finds near-optimal solutions faster than RRT and RRT* algorithms by restricting the search area to an ellipsoidal subset of the state space. However, IRRT* algorithm has the disadvantage of randomness of sampling and a non-real time process, which has a negative impact on the convergence rate and search efficiency in path planning applications. In this paper, we report a hybrid algorithm by combining the Artificial Potential Field Method (APF) with an IRRT* algorithm for mobile robot path planning. By introducing the virtual force field of APF into the search tree expansion stage of the IRRT* algorithm, the guidance of the algorithm increases, which greatly improves the convergence rate and search efficiency of the IRRT* algorithm. The proposed algorithm was validated in simulations and proven to be superior to some other RRT-based algorithms in search time and path length. It also was performed in a real robotic platform, which shows that the proposed algorithm can be well executed in real scenarios.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Robotics and Sensor-Based Localization · Optimization and Search Problems
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Anhui Key Laboratory of Detection Technology and Energy Saving Devices, School of Electrical Engineering, Anhui Polytechnic University, Wuhu 241000, China
Key Laboratory of Advanced Perception and Intelligent Control of High-End Equipment, Ministry of Education, Wuhu 241000, China
Funding
Key Program of Natural Science Foundation of Anhui Provincial Education Department · Priming Scientific Research Foundation for the Introduction Talent in Anhui Polytechnic University · Advance Research Program for National Science Foundation in Anhui Polytechnic University · Anhui Polytechnic University
References (29)
Show source-provided references
1. A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance10.1007/s10846-009-9383-1 ↗
2. A survey on coverage path planning for robotics10.1016/j.robot.2013.09.004 ↗
3. Heuristic approaches in robot path planning: A survey10.1016/j.robot.2016.08.001 ↗
4. Path Planning for A Robot Manipulator Based on Probabilistic Roadmap and Reinforcement Learning
5. Sampling-based robot motion planning: A review10.1109/ACCESS.2014.2302442 ↗
6. A survey of motion planning and control techniques for self-driving urban vehicles10.1109/TIV.2016.2578706 ↗
7. A review of motion planning techniques for automated vehicles10.1109/TITS.2015.2498841 ↗
8. Zammit, C., and van Kampen, E.J. (2018, January 8–12). Comparison between A-star RRT algorithms for UAV path planning. Proceedings of the 2018 AIAA Guidance, Navigation, and Control Conference, Kissimmee, FL, USA.10.2514/6.2018-1846 ↗
9. Koubaa, A., Bennaceur, H., Chaari, I., Trigui, S., Ammar, A., Sriti, M.F., Alajlan, M., Cheikhrouhou, O., and Javed, Y. (2018). Introduction to Mobile Robot Path Planning. Robot Path Planning and Cooperation, Springer International Publishing. [1st ed.].10.1007/978-3-319-77042-0 ↗
10. Castro, D., Leandro, N., and Jonathan, T. (2002). Artificial Immune Systems: A New Computational Intelligence Approach, Springer International Publishing. [1st ed.].
11. Finding shortest paths on real road networks: The case for A*10.1080/13658810801949850 ↗
12. Fuzzy algorithms10.1016/S0019-9958(68)90211-8 ↗
13. Javad, A., and Mansour, J. (2015, January 7–9). Adaptive motion planning with artificial potential fields using a prior path. Proceedings of the 2015 3rd RSI International Conference on Robotics and Mechatronics (ICROM), Tehran, Iran.
14. A Comparative Study of Artificial Bee Colony Algorithm
15. A genetic algorithm tutorial
16. LaValle, S.M., and Kuffner, J.J. (2019, August 08). Rapidly-Exploring Random Trees: A New Tool for Path Planning. Available online: https://www.cs.csustan.edu/~xliang/Courses/CS4710-21S/Papers/06%20RRT.pdf.
17. Sampling-based algorithms for optimal motion planning10.1177/0278364911406761 ↗
18. Gammell, J.D., Srinivasa, S.S., and Barfoot, T.D. (2014, January 14–18). Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, USA.10.1109/IROS.2014.6942976 ↗
19. Informed sampling for asymptotically optimal path planning10.1109/TRO.2018.2830331 ↗
20. RRT-connect: An efficient approach to single-query path planning
21. Wu, Z., Meng, Z., Zhao, W., and Wu, Z. (2021). Fast-RRT: A RRT-based optimal path finding method. Appl. Sci., 11.10.3390/app112411777 ↗
22. Brunner, M., Brüggemann, B., and Schulz, D. (2013, January 6–10). Hierarchical rough terrain motion planning using an optimal sampling-based method. Proceedings of the 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, Germany.10.1109/ICRA.2013.6631372 ↗
23. A learning-based multi-RRT approach for robot path planning in narrow passages10.1007/s10846-017-0641-3 ↗
24. Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate10.1016/j.eswa.2019.01.032 ↗
25. Finding a high-quality initial solution for the RRTs algorithms in 2D environments10.1017/S0263574719000195 ↗
26. Hybrid RRT: A semi-dual-tree RRT-based motion planner10.1109/ACCESS.2020.2968471 ↗
27. Potential functions based sampling heuristic for optimal path planning10.1007/s10514-015-9518-0 ↗
28. Pseudo-bacterial potential field based path planner for autonomous mobile robot navigation
29. Mobile robot path planning using membrane evolutionary artificial potential field10.1016/j.asoc.2019.01.036 ↗