Enhanced Informed Probabilistic Road Map Algorithm with Parameter Optimization
DOI:
https://doi.org/10.34010/injuratech.v5i1.16092Keywords:
Path planning, Probabilistic roadmap, Tunning parameter, Time computation, CostAbstract
This paper presents the design and performance testing of the Enhanced Informed Probabilistic Roadmap (EI-PRM) algorithm in path planning in various environments, such as simple environments, dense environments and narrow paths. This research evaluates the effectiveness of the algorithm in terms of solution cost and computation time by testing different parameter configurations, including number of sample points (nsample) and cost scaling factor (). The results show that the EI-PRM algorithm can adjust the sampling strategy based on the available information, resulting in an optimal solution with high efficiency. During the test, in a simple environment with the parameter value of nsample between 200 and 400 and parameter value between 1.2 and 1.4, the best solution cost is 344.93 and the computation time is 1.9 seconds. However, in a denser environment, the optimal solution cost reaches 141,586 with a computation time of 1.16 seconds, a parameter value of nsample 200, and a parameter value of 1.5. Furthermore, the algorithm shows good performance on narrow paths with an optimal solution cost of about 293.39 and the best computation time of 0.38 seconds at a parameter value of nsample 400 parameter 1.3. This research focuses on the importance of parameter optimization and efficient sampling strategies to improve path quality and speed up computation time. In general, the results indicate that the EI-PRM algorithm is effective for path planning under various environmental conditions. The process of the EI-PRM algorithm consists of several steps. First, sample points are created at random. In the second step, the computer will link the example locations to produce a roadmap. In the last step, the shortest path inside an ellipsoid-bounded search area will be determined. The size of the ellipsoid will increase gradually until the best path solution is found. This research is expected to contribute significantly to the development of path planning algorithms that are more efficient, faster and capable of producing high-quality paths in complex environments. This research has the potential to improve applications in transportation and logistics that require optimal path planning in order to reduce operational costs and improve safety.
References
[1] Elbanhawi, M., & Simic, M. (2014). Sampling-based robot motion planning: A review. IEEE Access, 2, 56-77.
[2] Karaman, S., Walter, M. R., Perez, A., Frazzoli, E., & Teller, S. (2011, May). Anytime motion planning using the RRT. In 2011 IEEE international conference on robotics and automation (pp. 1478-1483). IEEE.
[3] Aria, M. (2020). Algoritma Perencanaan Jalur Kendaraan Otonom berbasis Hibridisasi Algoritma BFS dan Path Smoothing. Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali dan Elektronika Terapan, 8(1), 13-22.
[4] Friedrich, C., Csiszar, A., Lechler, A., & Verl, A. (2017). Efficient task and path planning for maintenance automation using a robot system. IEEE Transactions on Automation Science and Engineering, 15(3), 1205-1215.
[5] Tsai, C. C., Huang, H. C., & Chan, C. K. (2011). Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation. IEEE Transactions on Industrial Electronics, 58(10), 4813-4821.
[6] Rasekhipour, Y., Khajepour, A., Chen, S. K., & Litkouhi, B. (2016). A potential field-based model predictive path-planning controller for autonomous road vehicles. IEEE Transactions on Intelligent Transportation Systems, 18(5), 1255-1267.
[7] Qiu, Z., & Liu, C. (2012, July). The motion planning in the automatic generation of mobile phone 3D animation. In Proceedings of the 10th World Congress on Intelligent Control and Automation (pp. 725-731). IEEE.
[8] Sudhakara, P., Ganapathy, V., & Sundaran, K. (2018, March). Trajectory Planning Using Enhanced Probabilistic Roadmaps For Pliable Needle Robotic Surgery. In 2018 International Conference on Recent Trends in Electrical, Control and Communication (RTECC) (pp. 61-64). IEEE.
[9] Ekenna, C., Thomas, S., & Amato, N. M. (2016). Adaptive local learning in sampling based motion planning for protein folding. BMC systems biology, 10, 165-179.
[10] Yang, Y., Pan, J., & Wan, W. (2019). Survey of optimal motion planning. IET Cyber‐systems and Robotics, 1(1), 13-19.
[11] Mashayekhi, R., Idris, M. Y. I., Anisi, M. H., & Ahmedy, I. (2020). Hybrid RRT: A semi-dual-tree RRT-based motion planner. IEEE Access, 8, 18658-18668.
[12] Dijkstra, E. W. (2022). A note on two problems in connexion with graphs. In Edsger Wybe Dijkstra: his life, work, and legacy (pp. 287-290).
[13] Marble, J. D., & Bekris, K. E. (2013). Asymptotically near-optimal planning with probabilistic roadmap spanners. IEEE Transactions on Robotics, 29(2), 432-444.
[14] Guo, Y., Liu, X., Liu, X., Yang, Y., & Zhang, W. (2022). FC-RRT*: An improved path planning algorithm for UAV in 3D complex environment. ISPRS International Journal of Geo-Information, 11(2), 112.
[15] Noreen, I., Khan, A., & Habib, Z. (2016). Optimal path planning using RRT* based approaches: a survey and future directions. International Journal of Advanced Computer Science and Applications, 7(11).
[16] Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2), 100-107.
[17] Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The international journal of robotics research, 30(7), 846-894.
[18] Qureshi, A. H., Mumtaz, S., Iqbal, K. F., Ayaz, Y., Muhammad, M. S., Hasan, O., ... & Ra, M. (2014, March). Triangular geometry based optimal motion planning using RRT*-motion planner. In 2014 IEEE 13th International Workshop on Advanced Motion Control (AMC) (pp. 380-385). IEEE.
[19] Wang, W., Gao, H., Yi, Q., Zheng, K., & Gu, T. (2020, June). An improved rrt* path planning algorithm for service robot. In 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) (Vol. 1, pp. 1824-1828). IEEE.
[20] Yuncheng, L., & Jie, S. (2017, April). A revised Gaussian distribution sampling scheme based on RRT* algorithms in robot motion planning. In 2017 3rd International Conference on Control, Automation and Robotics (ICCAR) (pp. 22-26). IEEE.
[21] Pohan, M. A. R., Trilaksono, B. R., Santosa, S. P., & Rohman, A. S. (2024). Path planning using combined informed rapidly-exploring random tree star and particle swarm optimization algorithms. IEEE Access.
[22] Pohan, M. A. R., Trilaksono, B. R., Santosa, S. P., & Rohman, A. S. (2021). Path planning algorithm using the hybridization of the rapidly-exploring random tree and ant Colony systems. IEEE Access, 9, 153599-153615.
[23] Malik, A. D. A. M., & Pohan, M. A. R. (2022). The development of a path planning algorithm combining the rapidly-exploring random tree algorithm and the particle swarm optimization algorithm. J. Eng. Sci. Technol., 17(6), 3742-3754.
[24] Aria, M. (2020). Path planning algorithm using informed rapidly exploring random tree*-connect with local search. Journal of Engineering Science and Technology Special Issue on INCITEST, 50-57.
[25] Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2014, September). Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In 2014 IEEE/RSJ international conference on intelligent robots and systems (pp. 2997-3004). IEEE.
[26] Pakaya, H. O., & Pohan, M. A. R. (2021). Metode Improved Gaussian Sampling pada Algoritma Rapidly Exploring Random Tree. Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali dan Elektronika Terapan, 9(2), 106-118.
[27] Novosad, M., Penicka, R., & Vonasek, V. (2023). CTopPRM: Clustering topological PRM for planning multiple distinct paths in 3D environments. IEEE Robotics and Automation Letters, 8(11), 7336-7343.
[28] Fauzi, M., & Pohan, M. A. R. (2021). Informed-RRT* using hybrid sampling to finding fast final path solution. Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali dan Elektronika Terapan, 9(2), 94-105.
[29] Sopa, A., & Hartono, R. (2021). Algoritma Rapidly Exploring Random Tree Star Dengan Integrasi Metode Sampling Goal Biassing, Gaussian, Dan Boundary. Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali dan Elektronika Terapan, 9(2), 129-138.
[30] Pohan, M. A. (2022). LabVIEW Libraries untuk Algoritma Perencanaan Jalur Robotik. Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali dan Elektronika Terapan, 10(1), 47-62.
[31] Rahajoeningroem, T., & Gunastuti, D. A. (2024). Studi Performansi Algoritma Perencanaan Jalur Berbasis Informed Rapidly-exploring Random Tree Star. Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali dan Elektronika Terapan, 12(1), 50-67.
[32] Ramba, L. S., & Aria, M. (2020). Design of a voice controlled home automation system using deep learning convolutional neural network (DL-CNN). Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali Dan Elektronika Terapan, 8(1), 57-73.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
