Perbandingan Algoritma A* dan Particle Swarm Optimization pada Perencanaan Lintasan 3D

Ilmi, Muhammad Faarisul (2023) Perbandingan Algoritma A* dan Particle Swarm Optimization pada Perencanaan Lintasan 3D. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 07111940000138-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2025. Download (3MB) | Request a copy

Abstract

Penelitian ini berfokus pada pencarian metode terbaik untuk menghasilkan lintasan terpendek untuk mencapai titik tujuan yang ditentukan dengan menghindari objek, benda, dan juga rintangan yang ada di lingkungan sekitarnya. Dua pendekatan yang populer dalam masalah path planning yaitu pendekatan deterministik dan meta-heuristik yang keduanya memiliki kelebihan dan kekurangannya masing-masing. Dalam penelitian ini algoritma deterministik yang digunakan yaitu A* dan untuk meta-heuristik yaitu PSO. Pengujian dilakukan dengan memvariasikan nilai weight pada A* yang diatur sebesar 1, 2, dan 3 dan ditambahkan proses post-smoothing dengan metode line-of-sight serta jumlah partikel pada PSO yang diatur sebesar 20, 50, dan 100 pada tiga lingkungan yang berbeda untuk melihat pengaruh dari keduanya pada lintasan yang dihasilkan. Tiga buah nilai digunakan untuk mengevaluasi performa dari masing masing algoritma yaitu panjang lintasan, jumlah node, dan waktu komputasi. Kedua algoritma tersebut dibandingkan dan digunakan untuk mencari lintasan terpendek yang bebas rintangan dari titik awal ke titik tujuan pada lingkungan tiga dimensi. Hasil perbandingkan yang didapat memperlihatkan bahwa algortima A* yang di post-smoothing menghasilkan lintasan yang lebih baik dibandingkan PSO dengan memberikan panjang lintasan yang lebih pendek dan jumlah node yang lebih sedikit.
=====================================================================================================================================
The focus of this study is to seek for the best method for finding an optimal obstacle-free path to reach its destination. Therefore, path planning extremely plays an important role to point out the direction for the robot from the starting point to destination point. Two popular approaches in path planning problems are deterministic and meta-heuristic approaches, both of which have their own advantages and disadvantages. In this study, A* is used for representing deterministic approach while PSO is used for representing meta-heuristic approach. The tests were carried out by varying the weight value in A* which was set at 1, 2, and 3 and added the post-smoothing process with the line-of-sight method afterwards and also the number of particles in the PSO was set at 20, 50, and 100 in three different environments to see the influence of both on the generated path. Both algorithms were assessed in terms of length of the path, number of node, and runtime. The two algorithms are compared and used to find the shortest obstacle-free path from the starting point to the destination point in a three-dimensional environment. The comparison revealed that the post-smoothing A* algorithm produced a better path than PSO by providing a shorter path with fewer nodes.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Perencanaan Lintasan 3D, Algoritma A*, Lingkungan 3D, Penghindaran Rintangan, 3D Path Planning, A* Algorithm, Particle Swarm Optimization, 3D Environment, Obstacle Avoidance
Subjects:	T Technology > TL Motor vehicles. Aeronautics. Astronautics > TL152.8 Vehicles, Remotely piloted. Autonomous vehicles.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Electrical Engineering > 20201-(S1) Undergraduate Thesis
Depositing User:	Muhammad Faarisul Ilmi
Date Deposited:	29 Jul 2023 02:09
Last Modified:	29 Jul 2023 02:09
URI:	http://repository.its.ac.id/id/eprint/99750

Actions (login required)

View Item