A Method of Enhancing Rapidly-Exploring Random Tree Robot Path Planning Using Midpoint Interpolation
Source abstract
Abstract
It is difficult to guarantee optimality using the sampling-based rapidly-exploring random tree (RRT) method. To solve the problem, this paper proposes the post triangular processing of the midpoint interpolation method to minimize the planning time and shorten the path length of the sampling-based algorithm. The proposed method makes a path that is closer to the optimal path and somewhat solves the sharp path problem through the interpolation process. Experiments were conducted to verify the performance of the proposed method. Applying the method proposed in this paper to the RRT algorithm increases the efficiency of optimization by minimizing the planning time.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · Robotics and Sensor-Based Localization · Robotic Locomotion and Control
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science and Engineering, Dongguk University, Seoul 04620, Korea
Department of Artificial Intelligence, Dongguk University, Seoul 04620, Korea
Funding
National Research Foundation of Korea · The Ministry of Trade, Industry and Energy of Korea · Ministry of SMEs and Startups · Ministry of Science and ICT, South Korea
References (21)
Show source-provided references
1. Lindner, L., Sergiyenko, O., Moises, R.L., Ivanov, M., Julio, C.R.Q., Daniel, H.B., Wendy, F.F., Vera, T., Fabian, N.M.R., and Mercorelli, P. (2017, January 19–21). Machine Vision System Errors for Unmanned Aerial Vehicle Navigation. Proceedings of the IEEE International Symposium on Industrial Electronics, Edinburgh, UK.10.1109/ISIE.2017.8001488 ↗
2. Sergiyenko, O., Wendy, F.F., and Mercorelli, P. (2020). Machine Vision and Navigation, Springer. [1st ed.].10.1007/978-3-030-22587-2 ↗
3. Abdi, A., Adhikari, D., and Park, J.H. (2021). A novel hybrid path planning method based on q-learning and neural network for robot arm. Appl. Sci., 11.10.3390/app11156770 ↗
4. Schwab, K. (2017). The Fourth Industrial Revolution, Crown Business. [1st ed.].
5. Wang, X., Luo, X., Han, B., Chen, Y., Liang, G., and Zheng, K. (2020). Collision-free path planning method for robots based on an improved rapidly-exploring random tree algorithm. Appl. Sci., 10.10.3390/app10041381 ↗
6. Randomized kinodynamic planning10.1177/02783640122067453 ↗
7. Kuffner, J.J., and LaValle, S.M. (2000, January 24–28). RRT-Connect: An Efficient Approach to Single-Query Path Planning. Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, USA.
8. Improved RRT-connect algorithm based on triangular inequality for robot path planning10.3390/s21020333 ↗
9. Visibility graph based spatial path planning of robots using configuration space algorithms
10. The approximate cell decomposition with local node refinement global path planning algorithm: Path nodes refinement and curve parametric interpolation10.1023/A:1008034314006 ↗
11. Warren, C.W. (1989, January 14–19). Global Path Planning using Artificial Potential Fields. Proceedings of the International Conference on Robotics and Automation, Scottsdale, AZ, USA.
12. LaValle, S.M. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning, Springer.
13. Sampling based algorithms for optimal motion planning10.1177/0278364911406761 ↗
14. 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 IEEE/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, USA.10.1109/IROS.2014.6942976 ↗
15. Klemm, S., Oberländer, J., Hermann, A., Roennau, A., Schamm, T., Zollner, J.M., and Dillmann, R. (2015, January 6–9). RRT*-Connect: Faster, Asymptotically Optimal Motion Planning. Proceedings of the IEEE International Conference on Robotics and Biomimetics, Zhuhai, China.10.1109/ROBIO.2015.7419012 ↗
16. Islam, F., Nasir, J., Malik, U., Ayaz, Y., and Hasan, O. (2012, January 5–8). Rrt*-smart: Rapid Convergence Implementation of rrt* towards Optimal Solution. Proceedings of the IEEE International Conference on Mechatronics and Automation, Chengdu, China.
17. Quick-RRT*: Triangular inequality based implementation of RRT* with improved initial solution and convergence rate10.1016/j.eswa.2019.01.032 ↗
18. Jung, J.-W., So, B.-C., Kang, J.-G., Lim, D.-W., and Son, Y. (2019). Expanded Douglas–Peucker polygonal approximation and opposite angle based exact cell decomposition for path planning with curvilinear obstacles. Appl. Sci., 9.10.3390/app9040638 ↗
19. Jung, J.-W., So, B.-C., Kang, J.-G., and Jang, W.-J. (2019, January 1–3). Circumscribed Douglas-Peucker Polygonal Approximation for Curvilinear Obstacle Representation. Proceedings of the IEEE 2019 7th International Conference on Robot Intelligence Technology and Applications (RiTA), Daejeon, Korea.10.1109/RITAPP.2019.8932794 ↗
20. Kinodynamic model identification: A unified geometric approach10.1109/TRO.2020.3047515 ↗
21. Mobile robot path planning with surrounding point set and path improvement10.1016/j.asoc.2017.03.035 ↗