Analisis Simulasi Penerapan Algoritma D* Pada Slam Untuk Eksplorasi Berbasis Multi-robot

Authors

DOI:

https://doi.org/10.34818/eoe.v7i2.12309

Abstract

Abstrak Sistem navigasi yang biasa dilakukan terkait dengan proses pemetaan atau pembuatan peta sebagai titik acuan. Saat ini sistem navigasi secara konseptual dikenal sebagai SLAM (Simultan Lokalisasi dan Pemetaan), yaitu proses pemetaan sekaligus pelokalan. Selanjutnya SLAM berkembang kembali dan memiliki sistem pencarian jalur eksplorasi untuk mendukung proses pembuatan peta (pemetaan) maupun lokalisasi. Sistem pencarian jalur eksplorasi dibuat dengan menggunakan algoritma tertentu dan terdapat banyak algoritma pencarian jalur eksplorasi yang berhasil dikembangkan. Proses pencarian jalur yang dimiliki algoritma dikhususkan untuk pencarian jalur eksplorasi berdasarkan informasi yang sudah didapat seperti sketsa kasar suatu daerah atau menggunakan LiDAR pada Mobile Robot. Salah satu algoritma pencarian jalur adalah algoritma D *. Proses pencarian jalur dalam algoritma D * masih sangat beragam dalam hasil dan diperlukan aspek tambahan untuk meningkatkan keakuratannya dalam banyak penelitian. Hasil dari penelitian ini adalah membuktikan bahwa algoritma D * mampu mendukung proses pembuatan jalur pada sistem Mobile Robot. Hal ini juga didukung dengan eksplorasi multi robot, setiap robot mampu saling mendukung dengan melanjutkan kegiatan eksplorasi jika salah satu robot berhenti bekerja, hal ini didukung dengan hasil beberapa pengujian simulasi multi robot mampu mengunjungi minimal satu robot. titik tujuan. Simulasi multi robot juga dapat mengunjungi lebih banyak titik tujuan dengan presentasi dua kali lebih banyak daripada simulasi robot tunggal. Dari semua pengujian yang dilakukan, 87% di antaranya membuktikan bahwa area eksplorasi yang berhasil dicapai dalam simulasi multi robot ternyata lebih luas. Sayangnya, simulasi multi robot ini terbebani oleh durasi waktu simulasi yang lebih lama dibandingkan simulasi robot tunggal, yaitu sekitar 69,3%. Algoritma ini mampu mendukung proses pencarian jalur menuju titik tujuan dalam kegiatan eksplorasi. Kata kunci : Algoritma D*, SLAM, Mobile Robot, Navigasi, informasi, pencarian Abstract The usual navigation system is associated with the process of mapping or making maps as a reference point. Nowadays the navigation system is conceptually known as SLAM (Simultaneous Localization and Mapping), which is the process of mapping simultaneously localizing. Furthermore, SLAM developed again and had an exploration path search system to support the process of making maps (mapping) as well as localization. Exploration path search systems are created using certain algorithms and there are many exploration path search algorithms successfully developed. The process of searching for paths owned by the algorithm is specifically for searching for exploration pathways based on information already obtained such as rough sketches of an area or using LiDAR on Mobile Robot. One of the path search algorithms is D * algorithm. The path search process in the D * algorithm is still very diverse in results and additional aspects are needed to improve its accuracy in many studies. The result of this research is to prove that the D * algorithm is able to support the path creation process in the Mobile Robot system. This is also supported by multi-robot exploration, each robot is able to support each other by continuing exploration activities if one of the robots stops working, this is supported by the results of several tests on multi-robot simulations capable of visiting at least one destination point. Multi robot simulation can also visit more points of destination with twice as much presentation than single robot simulation. From all the tests carried out, 87% of them proved that the area of exploration that was successfully reached in the multi robot simulation proved to be wider. Unfortunately, the multi-robot simulation is burdened by the longer simulation time duration than the single robot simulation, which is around 69.3%. This algorithm is able to support the process of finding a path to the destination point in exploration activities. Keywords: : D* Algorithm, SLAM, Mobile Robot, Navigation, information, search

Downloads

Download data is not yet available.

References

[1]Avinash Gautam, & Sudeept Mohan. (2012) “A Review of Research in Multi-Robot Systems”. Department of Computer Science and Information Systems Birla Institute of Technology and Science Pilani, India.

[2]Albina, K., & Lee, S. G. “Hybrid Stochastic Exploration Using Grey Wolf Optimizer and Coordinated Multi-Robot Exploration Algorithms”. IEEE Access, 7, 14246–14255, Februari, 2019.

[3]Jason T.P. Tse, Stephen C.F.Chan & Grace Ngai. (2010) “An Introduction to the Multi-Modal Robot (MuMoMuRo) Control System”. Department of Computing. The Hong Kong Polytechnic University Hong Kong SAR, China.

[4]H. Jacky Chang, “P-SLAM: Simultaneous Localization and Mapping With Environmental-Structure Prediction”, IEEE Transaction On Robotics, vol. 23, No. 2, April 2007.

[5]Ivan Maurovic, Marija Seder, Kruno Lenac, Ivan Petrovic, “Path Planning for Active SLAM Based on the D* Algorithm With Negative Edge Weights,” IEEE Transaction On Systems, 2017.

[6]Pip Tools, “Algoritma Extended Kalman Filter”. Pip Tools, 11 Desember 2015. [Online]. Tersedia : https://piptools.net/algoritma-extended-kalman-filter/ [Diakses: 23 September 2019].

[7]Pip Tools. “Algoritma Kalman Filter”. Pip Tools, 9 Desember 2015. [Online]. Tersedia: https://piptools.net/algoritma-kalman-filter/ [Diakses: 23 September 2019].

[8] Hongjian Wang, Jing Wang, Liping Qu, Zhenye Liu, “Simultaneous Localization and Mapping Based on Multilevel-EKF,” Proceedings of the 2011 IEEE International Conference on Mechatronics and Automation, 2255-2258, August. 7 -10, 2011.

[9] Wikipedia. “Extended Kalman Filter”. Wikipedia, 19 September 2019. [Online]. Tersedia: https://en.wikipedia.org/wiki/Extended_Kalman_filter [Diakses: 23 September 2019].

[10] Wikipedia. “Jacobian Matrix and Determinant”. Wikipedia, 21 September 2019.[Online].Tersedia https://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant [Diakses: 23 September 2019].

[11] Wikipedia. “Model Pedictive Control”. Wikipedia, 17 September 2019. [Online]. Tersedia: https://en.wikipedia.org/wiki/Model_predictive_control [Diakses: 28 September 2019].

[12] Cindy Leung, Shoudong Huang, Gamini Dissanayake, “Active SLAM using Model Predictive Control and Attractor based Exploration” Proceedings of the 2006 IEEE/RSJ, 5027-5031, 9-15 October , 2006.

[13] J.D. Hedengren; R. Asgharzadeh Shishavan; K.M. Powell; T.F. Edgar (2014). "Nonlinear modeling, estimation and predictive control in APMonitor". Computers & Chemical Engineering. 70 (5): 133–148.

[14] Wikipedia. “D*”. Wikipedia, 10 September 2019. [Online]. Tersedia: https://en.wikipedia.org/wiki/D* [Diakses: 2 Oktobber 2019].

[15] Stentz, Anthony (1994), "Optimal and Efficient Path Planning for Partially-Known Environments", Proceedings of the International Conference on Robotics and Automation: 3310–3317, CiteSeerX 10.1.1.15.3683

[16] Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659, CiteSeerX 10.1.1.41.8257

[17] Hart, P.; Nilsson, N.; Raphael, B. (1968), "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Trans. Syst. Science and Cybernetics, SSC-4 (2): 100–10

[16] Koenig, S.; Likhachev, M. (2005), "Fast Replanning for Navigation in Unknown Terrain", Transactions on Robotics, 21 (3): 354–363, CiteSeerX 10.1.1.65.5979

[17] Koenig, S.; Likhachev, M. (2002) “D*Lite”

[18] Han, S. D., & Yu, J. (2020). “DDM: Fast Near-Optimal Multi-Robot Path Planning Using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics”, IEEE Robotics and Automation Letters, 5(2), 1350–1357. doi:10.1109/lra.2020.2967326

[19] Carter,Mancini, Bruce,Ron (2009). Op Amps for Everyone. Texas Instruments. pp. 10–11. ISBN 978-0080949482.

Downloads

Published

2020-08-01

Issue

Pages

4591-4600

Section

Program Studi S1 Teknik Komputer

How to Cite

Najib, N. R., Jati, A. N., & Ruriawan, M. F. (2020). Analisis Simulasi Penerapan Algoritma D* Pada Slam Untuk Eksplorasi Berbasis Multi-robot. EProceedings of Engineering, 7(2), 4591-4600. https://doi.org/10.34818/eoe.v7i2.12309