Drone Pathfinding Simulator menggunakan Algoritma Iterative Deepening IDA*

Fitria  Sari; Sugiarto  Cokrowibowo; A. Amirul Asnan  Cirua

doi:10.58602/jaiti.v4i4.443

Fitria Sari ^{(Corresponding Author)} Universitas Sulawesi Barat
Sugiarto Cokrowibowo Universitas Sulawesi Barat
A. Amirul Asnan Cirua Universitas Sulawesi Barat

DOI: https://doi.org/10.58602/jaiti.v4i4.443

Keywords: Drone, Pathfinding, IDA*, BFS, Simulasi

Abstract

Penggunaan pesawat tanpa awak atau drone semakin luas untuk pemantauan, pemetaan, inspeksi, dan pengiriman. Salah satu persoalan penting dalam pengoperasiannya adalah menentukan jalur dari titik awal ke tujuan dengan menghindari area terlarang dan rintangan. Penelitian ini merancang Drone Pathfinding Simulator menggunakan algoritma Iterative Deepening A* (IDA*) untuk memperlihatkan proses pencarian jalur pada lingkungan berbasis grid. IDA* dipilih karena menggabungkan estimasi heuristik A* dengan pencarian mendalam berulang sehingga kebutuhan memorinya relatif rendah dibandingkan pencarian yang menyimpan banyak simpul sekaligus. Metode penelitian menggunakan pendekatan rekayasa perangkat lunak melalui identifikasi kebutuhan, pemodelan lingkungan, perancangan algoritma, implementasi simulator, dan pengujian skenario. Peta direpresentasikan sebagai grid dua dimensi yang berisi sel bebas, rintangan, titik awal, dan titik tujuan. Fungsi heuristik Manhattan digunakan untuk gerakan empat arah, sedangkan ambang pencarian diperbarui berdasarkan nilai evaluasi terkecil yang melampaui ambang sebelumnya. Evaluasi dirancang dengan mengukur keberhasilan menemukan jalur, panjang jalur, jumlah simpul yang dikunjungi, waktu komputasi, dan penggunaan memori. Naskah ini menyajikan rancangan sistem dan protokol pengujian yang dapat direplikasi; angka kinerja empiris belum diklaim karena implementasi dan pengukuran pada perangkat nyata perlu dilakukan sebagai tahap lanjutan. Hasil yang diharapkan adalah simulator edukatif untuk memvisualisasikan proses IDA* dan mengevaluasi kelayakannya pada peta statis, dengan batasan bahwa simulator grid dua dimensi belum mewakili seluruh dinamika penerbangan drone sebenarnya.

Downloads

Download data is not yet available.

References

W. Meng, X. Zhang, L. Zhou, H. Guo, and X. Hu, “[1]Advances in UAV Path Planning: A Comprehensive Review of Methods, Challenges, and Future Directions,” Drones, vol. 9, no. 5, pp. 1–46, 2025, doi: 10.3390/drones9050376.

D. Debnath, F. Vanegas, J. Sandino, A. F. Hawary, and F. Gonzalez, “[2]A Review of UAV Path-Planning Algorithms and Obstacle Avoidance Methods for Remote Sensing Applications,” Remote Sens., vol. 16, no. 21, 2024, doi: 10.3390/rs16214019.

Z. Zhang, “3]A review of unmanned aerial vehicle path planning techniques,” Appl. Comput. Eng., vol. 33, no. 1, pp. 234–241, 2024, doi: 10.54254/2755-2721/33/20230275.

D. Alaa, K. Abdelmadjid, and L. Fadhila, “4]Intelligent path planning algorithms for UAVs: Classification, complexity analysis, hybrid ablation insights, and future directions,” Adv. Mech. Eng., vol. 17, no. 7, pp. 1–26, 2025, doi: 10.1177/16878132251355020.

D. Foead, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. Gunawan, “5]A Systematic Literature Review of A*Pathfinding,” Procedia Comput. Sci., vol. 179, no. 2020, pp. 507–514, 2021, doi: 10.1016/j.procs.2021.01.034.

X. Bai, H. Jiang, J. Cui, K. Lu, P. Chen, and M. Zhang, “6]UAV Path Planning Based on Improved A ∗ and DWA Algorithms,” Int. J. Aerosp. Eng., vol. 2021, 2021, doi: 10.1155/2021/4511252.

G. Aiello, K. P. Valavanis, and A. Rizzo, “7]Fixed-Wing UAV Energy Efficient 3D Path Planning in Cluttered Environments,” J. Intell. Robot. Syst. Theory Appl., vol. 105, no. 3, 2022, doi: 10.1007/s10846-022-01608-1.

M. shun Yuan, T. le Zhou, and M. Chen, “8]Improved lazy theta∗ algorithm based on octree map for path planning of UAV,” Def. Technol., vol. 23, pp. 8–18, 2023, doi: 10.1016/j.dt.2022.01.006.

R. E. Korf, “9]Depth-first iterative-deepening. An optimal admissible tree search,” Artif. Intell., vol. 27, no. 1, pp. 97–109, 1985, doi: 10.1016/0004-3702(85)90084-0.

W. Jiang, “10]Analysis of iterative deepening A* algorithm,” IOP Conf. Ser. Earth Environ. Sci., vol. 693, no. 1, 2021, doi: 10.1088/1755-1315/693/1/012028.

Y. He, T. Hou, and M. Wang, “11]A new method for unmanned aerial vehicle path planning in complex environments,” Sci. Rep., vol. 14, no. 1, pp. 1–12, 2024, doi: 10.1038/s41598-024-60051-4.

F. Yang et al., “12]Obstacle Avoidance Path Planning for UAV Based on Improved RRT Algorithm,” Discret. Dyn. Nat. Soc., vol. 2022, 2022, doi: 10.1155/2022/4544499.

Z. Zhang, X. Liu, and B. Feng, “13]Research on obstacle avoidance path planning of UAV in complex environments based on improved Bézier curve,” Sci. Rep., vol. 13, no. 1, pp. 1–10, 2023, doi: 10.1038/s41598-023-43783-7.

M. B. Sushma, B. Mashhoodi, W. Tan, K. Liujiang, and Q. Xu, “14]Spatial drone path planning: A systematic review of parameters and algorithms,” J. Transp. Geogr., vol. 125, no. January, p. 104209, 2025, doi: 10.1016/j.jtrangeo.2025.104209.

A. Sonny, S. R. Yeduri, and L. R. Cenkeramaddi, “15]Q-learning-based unmanned aerial vehicle path planning with dynamic obstacle avoidance,” Appl. Soft Comput., vol. 147, p. 110773, 2023, doi: 10.1016/j.asoc.2023.110773.