TELEKONTRAN.
VOL.
NO.
APRIL 2021
DOI : 10.
34010/telekontran.
TELEKONTRAN,
VOL.
NO.
APRIL 2021
p-ISSN : 2303 Ae 2901 e-ISSN : 2654 Ae 7384 Analisa Penggunaan Nilai Bobot Heuristik yang Berbeda pada Algoritma Weighted A* Analysis of the Use of Different Heuristic Weights in the Weighted A* Algorithm Ipan Diana*.
Budi Herdiana Program Studi Teknik Elektro.
Fakultas Teknik dan Ilmu Komputer Universitas Komputer Indonesia Jl.
Dipati ukur No 112.
Bandung Email : ipandiana@mahasiswa.
Abstrak - Path planning merupakan urutan keadaan untuk memindahkan objek dari keadaan awal ke keadaan akhir, serta menghindari daerah yang tidak dapat dilalui.
Objek disini dapat berupa robot, mobil otonom dan yang lainnya.
Algoritma A* merupakan algoritma pencarian jalur yang menggunakan estimasi jarak dengan menggunakan pencarian jalur terdekat untuk mencapai tujuan.
Weighted A* adalah algoritma yang digunakan untuk memecahkan masalah pencarian jalur dengan mengubah nilai bobot pada fungsi heuristiknya.
Tujuan dari penelitian ini yaitu menganalisa perbandingan algoritma Weighted A* dengan algoritma A*, serta menganalisa pengaruh nilai bobot heuristik pada algoritma Weighted A*.
Pengujian yang dilakukan yaitu menggunakan lingkungan maze, narrow, trap, clutter.
Hasil yang didapat pada perbandingan algoritma Weighted A* dan A*, diperoleh algoritma Weighted A* menghasilkan waktu pencarian rata-rata yang lebih baik yaitu sebesar 3,49 detik, sedangkan algoritma A* menghasilkan waktu rata-rata sebesar 4,68 detik.
Tetapi algoritma A* dapat menghasilkan jalur rata-rata yang lebih optimal yaitu 53,90 dibandingkan algoritma Weighted A* yang menghasilkan jalur rata-rata sebesar 53,91.
Dengan strategi yang lebih menekankan pemilihan node yang lebih dekat dengan node goal, maka Weighted A* dapat menghasilkan jalur dengan waktu komputasi yang lebih cepat.
Sedangkan algoritma A* karena memilih node dengan nilai heuristik terkecil, maka dapat menghasilkan jalur yang lebih optimal.
Weighted A* cocok di implementasikan pada sistem yang membutuhkan waktu pencarian jalur yang lebih singkat tapi tidak harus optimal.
Algoritma A* cocok di implementasikan pada sistem yang membutuhkan jalur optimal walaupun waktu pencariannya tidak terlalu Kata kunci : Algoritma A*.
Heuristik.
Perencanaan Jalur.
Rute Terpendek.
Weighted A* Abstract - Path planning is a sequence of states to move objects from the initial state to the final state and avoid impassable areas.
Objects here can be robots, autonomous cars, and others.
The A* algorithm is a path search algorithm that uses distance estimation by using the closest path search to reach the destination.
Weighted A* is an algorithm used to solve the pathfinding problem by changing the weight value in the heuristic function.
The purpose of this study is to analyze the comparison of the Weighted A* algorithm with the A* algorithm and analyze the effect of the heuristic weight value on the Weighted A* algorithm.
The tests carried out are using maze, narrow, trap, clutter environments.
The results obtained in the comparison of the Weighted A* and A* algorithms, the Weighted A* algorithm produces a better average search time of 3.
seconds, while the A* algorithm produces an average time of 4.
68 seconds.
But the A* algorithm can produce a more optimal average path of 53.
90 than the Weighted A* algorithm which produces an average path of With a strategy that emphasizes choosing nodes that are closer to the goal node.
Weighted A* can produce a path with a faster computation time.
While the A* algorithm because it chooses the node with the smallest heuristic value, it can produce a more optimal path.
Weighted A* is suitable to be implemented on systems that require shorter path-finding times but do not have to be optimal.
The A* algorithm is suitable to be implemented in systems that require optimal paths even though the search time is not too fast.
Keywords : A* Algorithm.
Heuristic.
Path Planning.
Shortest Route.
Weighted A* TELEKONTRAN.
VOL.
NO.
APRIL 2021
PENDAHULUAN
Latar Belakang Perencanaan jalur menggambarkan urutan keadaan dalam skenario untuk memindahkan objek dari keadaan awal ke keadaan akhir, serta menghindari daerah yang tidak dapat dilalui .
intangan, zona bahay.
dari ruang pencarian.
Setiap keadaan adalah elemen dari ruang kemungkinan yang dapat diterapkan suatu objek, pada momen lintasannya .
Salah satu pendekatan berbasis sampling pertama yaitu (PRM), dikembangkan oleh Kavraki .
Jenis lain dari algoritma jenis sampling adalah AriadneAos Clew .
Contoh lainnya adalah algoritma Rapidlyexploring Random Tree (RRT) dan RRT*.
Algoritma ini memiliki sifat completeness, optimality dan konvergen menuju nilai optimal .
kemudian ada algoritma Dijkstra.
A* (ASta.
Breadth-Arst Search (BFS).
Depth-Arst Search (DFS).
Dijkstra dirumuskan oleh ilmuwan komputer Edsger W.
DijikstraAos pada tahun 1956 .
Algoritma Dijkstra memecahkan masalah jalur terpendek dengan biaya jalur tepi non-negatif .
Disisi lain, algoritma A* adalah salah satu dari sekian banyak algoritma perencanaan jalur yang mengambil input, mengevaluasi beberapa jalur yang memungkinkan, dan mengembalikan A* adalah algoritma pencarian terbaik pertama yang memodifikasi fungsi heuristik .
Algoritma ini meminimalkan total biaya yang ditempuh, dan dalam kondisi yang tepat akan memberikan solusi terbaik dalam waktu yang Weighted A* (WA*) adalah algoritma yang banyak digunakan untuk memecahkan masalah perencanaan dan pencarian dengan cepat .
Pada WA*, parameter Ea dikalikan dengan sebuah nilai weighted .
dalam memprioritaskan node Weighted dituliskan dengan huruf W, ia merupakan variabel yang terikat untuk solusi yang dihasilkan oleh WA*.
Tinjauan State of Art A* digunakan pada banyak bidang aplikasi.
Akshay dkk telah melakukan penelitian mengenai efisiensi waktu pada algoritma A* untuk aplikasi Dalam penelitiannya, sebuah algoritma harus dirancang untuk memastikan jalur bebas hambatan bagi robot dalam bidang industri.
Modifikasi terhadap algoritma A* disajikan dalam penelitian ini.
Hasil yang didapat yakni dengan algoritma A* menunjukkan pengurangan waktu pemrosesan maksimum sebesar 95% .
Shrawan dan B.
Pal membahas perbandingan algoritma DijkstraAos dan A* untuk kebutuhan pencarian jalur terpendek pada lalulintas dalam Pencarian jalan terpendek sangat penting dalam beberapa kasus khusus seperti pemadam kebakaran, ambulans yang membawa pasien, penangkapan pencuri oleh pihak kepolisian, dll.
Penelitian ini mengatakan bahwa algoritma A* berkinerja lebih baik daripada algoritma DijkstraAos di semua kasus .
engan obstacle dan tanpa obstacl.
Adapun Jordan dan Wheeler membahas pendekatan baru pencarian heuristik dengan suboptimalitas terbatas yaitu op-timistic search.
Pencarian ini menggabungkan aggressively greedy search dengan fase pembersihan.
Dari hasil demonstrasi memperlihatkan bahwa algoritma ini secara konsisten melampaui Weighted A* dalam empat domain benchmark yang berbeda termasuk perencanaan temporal dan pencarian jalur grid .
Eric dan Rong Zhou telah melakukan penelitian mengenai cara mengubah algoritma pencarian heuristik A* menjadi algoritma Anytime A*.
Pendekatan yang diadopsi yaitu menggunakan pencarian heuristik berbobot untuk menemukan solusi perkiraan yang cepat, dan kemudian menemukan solusi yang lebih baik .
Tujuan Tujuan dari penelitian ini adalah untuk menganalisa perbandingan antara algoritma Weighted A* dengan algoritma A*, serta menganalisa pengaruh nilai bobot heuristik pada algoritma Weighted A*.
Parameter yang akan dibandingkan meliputi waktu komputasi, path cost, dan penggunaan memori.
Pengujian dilakukan pada lingkungan maze, narrow, trap dan clutter.
Sistematika Pembahasan Makalah ini diorganisasikan sebagai berikut.
Bagian 2 akan menjelaskan mengenai perancangan program pada aplikasi python.
Bagian 3 akan menyajikan hasil pengujian dan analisa.
Adapun kesimpulkan akan disajikan pada Bagian 4.
II.
METODOLOGI
Algoritma A* A* adalah algoritma pencarian terbaik pertama yang dianggap sebagai versi lanjutan dari algoritma DijkstraAos .
Diperkenalkan pada TELEKONTRAN.
VOL.
NO.
APRIL 2021
tahun 1968 oleh Peter dan Bertram .
Algoritma ini mencoba untuk mengurangi jumlah total keadaan yang akan dijelajahi dengan memasukkan perkiraan biaya heuristik untuk mencapai tujuan dari keadaan tertentu.
A* memiliki dua karakteristik yang membentuk fungsi baru yaitu sebagai berikut:
= yci.
Ea.
Untuk setiap node ycu, total biaya yce.
diberikan sebagai jumlah dari biaya yci.
dan Ea.
yci adalah biaya yang ditempuh dari titik awal node menuju node ycu .
Ea adalah faktor heuristik yang memperkirakan biaya perpindahan dari node ycu menuju node tujuan .
A* diyakini didasarkan pada algoritma yang disebutkan diatas karena A* seperti algoritma DijkstraAos yang menemukan jalur terpendek tanpa gagal dan seperti Greedy Best-First Search yang memperkirakan jarak ke tujuan.
Pseudocode A* diperlihatkan pada Gambar 1.
Weighted A* Untuk masalah pencarian yang sulit.
A* mungkin membutuhkan terlalu lama waktu untuk menemukan solusi yang optimal, dan solusi perkiraan yang relatif lebih cepat dapat lebih Banyak peneliti telah mengeksplorasi efek pembobotan nilai yci.
dan Ea.
dalam memungkinkan A* menemukan solusi optimal dengan upaya komputasi yang lebih sedikit.
Dalam pendekatan ini, fungsi evaluasi node didefinisikan yce A .
= yci.
Ea.
Dimana parameter weight w Ou 1 ditetapkan oleh Heuristik berbobot mempercepat solusi pencarian karena membuat node lebih dekat ke Pencarian heuristik berbobot paling efektif untuk masalah pencarian dengan solusi yang mendekati optimal.
Blok Pemrograman Pertama akan dijelaskan mengenai blok Inisialisasi awal berfungsi untuk memberikan suatu nilai terhadap objek atau Variabel merupakan tempat untuk menyimpan data.
Pemberian nilai variabel dalam python dapat menggunakan simbol = .
ama Pada saat akan membuat variabel baru, kita diharuskan untuk membuat self sebagai parameter pertama.
Keyword self digunakan untuk merepresentasikan setiap objek yang dibuat.
Jika tidak ada self, maka class tidak akan bisa menampung informasi yang terdapat pada objek Gambar 1.
Pseudocode A*.
Algoritma DijkstraAos bekerja sangat baik untuk menemukan jalur terpendek dari satu titik akhir ke titik akhir lainnya, tetapi juga menghabiskan waktu dan sumber daya untuk menjelajahi arah yang tidak terlalu meyakinkan.
Sebaliknya.
Greedy Best-First Search mengeksplorasi arah yang memiliki harapan terbaik, tetapi gagal untuk secara konsisten menemukan jalur terpendek ke tujuan.
Menggabungkan dua algoritma ini.
A* menggunakan jarak dari awal dan perkiraan jarak ke tujuan untuk menghilangkan keterbatasan algoritma konvensional ini.
Gambar 2.
Inisialisasi awal.
TELEKONTRAN.
VOL.
NO.
APRIL 2021
Berdasarkan Gambar 2, pertama-tama dilakukan penambahan library yaitu math dan Library math merupakan salah satu fungsi bawaan pada python yang digunakan untuk melakukan operasi matematika.
Matplotlib adalah library plotting dua maupun tiga dimensi yang menghasilkan visualisasi data statis dan interaktif.
Matplotlib digunakan untuk memvisualisasikan jalur yang dihasilkan oleh algoritma A*.
Selanjutnya, dilakukan penambahan fungsi class dengan nama AStar.
Class merupakan kerangka untuk membentuk suatu objek.
Inisialisasi selanjutnya yaitu untuk titik start dan titik goal, dimana titik awal berada pada koordinat 0,0 sedangkan titik akhir berada pada koordinat 50,50.
Selain itu ada inisialisasi grid_size dengan nilai 2, dan robot_radius dengan nilai 1.
Inisialisasi ini dapat dilihat pada Gambar 3.
Selanjutnya yakni pembuatan program inti.
Ini merupakan bagian utama dari algoritma A*, dimana perhitungan untuk mencari jalur terpendek mulai dilakukan.
Pada program utama ini terdapat beberapa sub-program yang akan digunakan.
Beberapa sub-program tersebut meliputi xy_index, grid_index, heuristic_value, grid_position, direction, verify_node dan final_path.
Berdasarkan Gambar 5, pertama kita membuat sebuah fungsi dengan nama planning.
Fungsi ini memiliki masukkan berupa parameter self, sx, sy, gx, gy seperti tertera pada baris 40.
Kemudian kita insialisasi start_node dan goal_node.
Selanjutnya kita membuat dua buah variabel untuk menyimpan antrian data dari tiap-tiap titik yang diproses.
Unvisited_list digunakan untuk menyimpan titik yang akan dikunjungi, sedangkan visited_list digunakan untuk menyimpan node yang telah Untuk eksekusi pertama, start_node dimasukkan ke unvisited_list.
Pada baris 45 dilakukan proses perulangan Pertama, apabila nilai pada unvisited_list sama dengan nol maka program akan sepenuhnya dihentikan, karena tidak ada data awal yang dapat Kemudian pada baris 48-49 dilakukan perhitungan fungsi cost pada unvisited_list menggunakan rumus: yce = yci Ea .
Pada baris 49, heuristic_value memiliki nilai masukan goal_node unvisited_list.
Proses heuristic_value menghitung jarak dari goal node ke titik start_node dalam peta grid.
Pada baris yang sama, unvisited_list .
cost menghitung jarak dari titik start node ke suatu node yang sedang dikunjungi.
Setelah fungsi cost selesai dihitung, nilai dari yce yang paling kecil akan dijadikan node selanjutnya.
Pada baris 50, current digunakan untuk mengetahui titik node yang saat ini sedang dikunjungi.
Pada baris 51, apabila current node sama dengan goal maka pencarian akan dihentikan.
Sebaliknya, jika current node tidak sama dengan goal maka pencarian akan dilanjutkan.
Proses ini akan membandingkan node x pada titik goal dengan node x pada current node.
Sementara itu, node y pada titik goal akan dibandingkan dengan node y pada current node.
Pada baris 55 dilakukan penghapusan node pada variabel unvisited_list dan pada baris 56, node yang berhasil dihapus tersebut selanjutnya ditambahkan pada visited_list .
Pada bagian 57-60, kemungkinan posisi berikutnya yang akan diambil.
Percobaan gerakan yang dilakukan meliputi arah x .
ergerak ke kanan atau kir.
, arah y .
ergerak ke atas atau bawa.
dan arah diagonal .
ergerak ke Gambar 3.
Inisialisasi titik start, goal, grid_size, robot_radius.
Kemudian dilakukan pembuatan batas pencarian dan juga obstacle.
pertama-tama dibuat variabel ax dan ay dengan tipe array.
Baris 162173 merupakan nilai batasan yang digunakan pada area pencarian, adapun batas tersebut yaitu mulai dari -10 hingga 60 untuk sumbu x maupun y.
Pada baris 174-179 merupakan contoh batasan yang akan digunakan untuk pembuatan obstacle.
Program ini dapat dilihat pada Gambar 4.
Gambar 4.
Inisialisasi titik obstacle.
TELEKONTRAN.
VOL.
NO.
APRIL 2021
tiap sudu.
Jika ada posisi node yang merupakan obstacle maka perhitungan pada arah tersebut akan Selanjutnya menambahkan children .
node yang bebas sebagai selected parent.
apabila children node berada pada visited_list maka node tersebut diabaikan dan pencarian dilakukan ke arah yang lain.
Setelahnya dilakukan perhitungan nilai yci,Ea, dan yce untuk setiap children node yang bebas.
Pada baris 61 dibuat sebuah variabel dengan nama n_id, dengan masukan dari node setelah dilakukan kalkulasi grid_index terlebih dahulu.
Pada baris 62 jika node dalam keadaan tidak aman, maka jangan lakukan aksi apapun dan lanjutkan Pada baris 64, jika children node sudah pernah berada pada visited_list, maka jangan lakukan proses apapun.
Pada baris 66, apabila children node tidak berada pada unvisited_list, maka tambahkan children node kedalam unvisited_list.
Pada baris 71-76 merupakan fungsi untuk menampilkan posisi x dan y pada peta grid, dimana input untuk setiap nilai x dilakukan kalkulasi grid_position terlebih dahulu dengan masukan x dan self.
min_x.
Sementara itu, untuk setiap nilai y dilakukan kalkulasi grid_position terlebih dahulu dengan masukan current.
y dan min_y.
Gambar 5.
Program utama.
TELEKONTRAN.
VOL.
NO.
APRIL 2021
HASIL DAN PEMBAHASAN
Tabel II.
Weighted A* pada lingkungan clutter Perbandingan A* dan Weighted A* Lingkungan clutter Pengujian pertama dilakukan pada lingkungan obstacle clutter.
Pada pengambilan data ini dilakukan pengujian sebanyak sepuluh kali Data yang diambil yaitu waktu, panjang jalur yang dihasilkan, dan memori yang dipakai oleh algoritma.
Pada Gambar 6 dan Gambar 7 diperlihatkan lingkungan pengujian clutter.
Goal Best Worst Mean Weighted A* Path Time Memory .
(MB) 38,87 0,33 53,73 38,87 0,44 54,29 38,87 0,38 53,93 Lingkungan maze Pada percobaan kedua ini dilakukan pengujian algoritma pada lingkungan maze .
Titik start berada di koordinat .
dan titik goal berada di koordinat .
Untuk lebih lengkapnya dapat dilihat pada Gambar 8 dan Gambar 9.
Goal Start Gambar 6.
A* pada Lingkungan pengujian clutter Goal Start Gambar 8.
A* pada Lingkungan pengujian maze Goal Start Gambar 7.
Weighted A* pada Lingkungan pengujian clutter Pengujian clutter dilakukan pada obstacle dengan banyak rintangan yang berantakan.
Titik start berada pada koordinat .
sedangkan titik goal pada koordinat .
Gambar 6 merupakan proses perkembangan algoritma A* dari node pertama sampai node tersebut menjumpai titik goal.
Sedangkan Gambar 7 adalah proses perkembangan algoritma Weighted A*.
Hasil pengujian lebih lanjut dapat dilihat pada Tabel I dan Tabel II.
Tabel I.
A* pada lingkungan clutter Path Time Memory .
(MB) Best 38,87 1,40 53,82 Worst 38,87 1,49 54,09 Mean 38,87 1,45 53,96 Start Gambar 9.
Weighted A* pada Lingkungan pengujian maze Hasil yang diperoleh dari algoritma A* pada lingkungan maze seperti yang diperlihatkan pada Gambar 8 yaitu, pertumbuhan jalur sedikit lebih banyak apabila dibandingkan dengan Weighted A* pada Gambar 9, namun untuk Weighted A* ada sedikit pengambilan jalur yang berbeda dimulai dari koordinat .
dan berakhir di koordinat .
Disini A* lebih memilih jalur yang mengarah ke atas, lalu berbelok.
Sedangkan pada Weighted A* langsung berbelok arah ketika ditemukan adanya celah kosong yang mengarah ke Hasil data pada percobaan ini ada pada Tabel i dan Tabel IV.
TELEKONTRAN.
VOL.
NO.
APRIL 2021
Tabel i.
A* pada lingkungan maze Path Time Memory .
(MB) Best 52,28 4,16 53,76 Worst 52,28 5,02 54,10 Mean 52,28 4,73 53,94 Tabel IV.
Weighted A* pada lingkungan maze Best Worst Mean Weighted A* Path Time Memory .
(MB) 52,87 2,44 53,70 52,87 2,80 54,15 52,87 2,61 53,95 Meskipun A* terlihat lebih banyak melakukan percabangan node saat bekerja, namun path cost yang didapat memperlihatkan kondisi yang Berdasarkan Tabel i, diperlihatkan bahwa nilai path cost Algoritma A* yang didapat sedikit lebih baik apabila dibandingkan dengan Weighted A*.
Namun apabila kita melihat waktu pemrosesan.
Weighted A* jauh meninggalkan A* hampir dua kali lipat untuk perolehan waktu Disini dapat dilihat bahwa A* tidak begitu unggul dalam masalah waktu namun jalur yang didapat akan seoptimal mungkin.
Weighted A* sebaliknya, pada permasalahan waktu algoritma ini bisa sangat cepat dalam pencarian jalur, namun solusi yang diberikan mungkin tidak cukup optimal.
Lingkungan narrow Narrow merupakan lingkungan pengujian dengan bidang sisi yang sempit.
Pengujian ini dilakukan dengan menempatkan memanjang dan berjajar.
Ruang untuk node lewat hanya diperbolehkan satu atau dua node saja.
Titik goal ditempatkan disudut obstacle dengan beberapa penambahan obstacle yang persegi.
Hasil visualisasi dapat dilihat pada Gambar 10 dan Gambar 11.
Berdasarkan Gambar 10 dan Gambar 11 hanya ada satu jalan yang bisa dilewati saat pertama kali node berkembang, yaitu jalan yang berada di sebelah kanan.
kemudian memutar ke sebelah kiri dan seterusnya.
Pada saat mendekati titik goal atau tepatnya berada di koordinat .
jalan yang dapat dilalui ada dua, diperbolehkan ke kanan maupun ke kiri.
Berdasarkan Gambar 10 node yang bergerak ke sebelah kanan cenderung lebih sedikit apabila dibandingkan dengan Weighted A* pada Gambar 11.
selain itu, pada Weighted A* terdapat jalur yang sedikit tidak optimal, tepatnya pada koordinat .
Node yang dikembangkan memilih bergerak ke arah diagonal atas daripada bergerak ke arah kanan.
Ketika jalur ini dipilih sebagai jalur akhir, akibatnya jalur yang akan dilalui akan bergerak terlebih dahulu keatas kemudian kembali lagi Tabel V dan Tabel VI memperlihatkan data dari percobaan ini.
Goal Start Gambar 10.
A* pada Lingkungan pengujian narrow Goal Start Gambar 11.
Weighted A* pada Lingkungan pengujian narrow Berdasarkan Gambar 10 dan Gambar 11 hanya ada satu jalan yang bisa dilewati saat pertama kali node berkembang, yaitu jalan yang berada di sebelah kanan.
kemudian memutar ke sebelah kiri dan seterusnya.
Pada saat mendekati titik goal atau tepatnya berada di koordinat .
jalan yang dapat dilalui ada dua, diperbolehkan ke kanan maupun ke kiri.
Berdasarkan Gambar 10 node yang bergerak ke sebelah kanan cenderung lebih sedikit apabila dibandingkan dengan Weighted A* pada Gambar 11.
selain itu, pada Weighted A* terdapat jalur yang sedikit tidak optimal, tepatnya pada koordinat .
Node yang dikembangkan memilih bergerak ke arah diagonal atas daripada bergerak ke arah kanan.
Ketika jalur ini dipilih sebagai jalur akhir, akibatnya jalur yang akan dilalui akan bergerak terlebih dahulu keatas kemudian kembali lagi Tabel V dan Tabel VI memperlihatkan data dari percobaan ini.
TELEKONTRAN.
VOL.
NO.
APRIL 2021
Tabel V.
A* pada lingkungan narrow Path Time Memory .
(MB) Best 163,69 4,45 53,50 Worst 163,69 4,59 54,10 Mean 163,69 4,50 53,74 mengarah ke dalam area trap, yang pada ujungnya terhalang oleh obstacle Goal Tabel VI.
Weighted A* pada lingkungan narrow Weighted A* Path Time Memory .
(MB) Best 164,52 4,20 53,60 Worst 164,52 4,41 54,04 Mean 164,52 4,33 53,85 Start Gambar 12.
A* pada Lingkungan pengujian trap Goal Waktu terbaik yang diperoleh dalam percobaan ini tidak terpaut jauh.
Berdasarkan Tabel V dan Tabel VI.
Weighted A* memperoleh waktu terbaik di 4,20 detik, sementara waktu eksekusi A* pada lingkungan narrow sebesar 4,45 detik.
Path cost yang diperoleh pada lingkungan narrow ini menghasilkan nilai optimal lebih tinggi untuk algoritma A* dibanding Weighted A*.
Start Gambar 11.
Weighted A* pada Lingkungan pengujian trap Lingkungan trap Lingkungan trap merupakan area pencarian dimana salah satu dari titik start atau titik goal ada disebuah area yang hampir tertutup.
Area ini biasanya berbentuk persegi dimana hanya ada satu jalan untuk masuk dan keluar.
Jalan yang akan dilaluinya pun cukup sempit namun satu atau dua node masih bisa keluar masuk area ini.
Hasil percobaan ini dapat dilihat pada Gambar 12 dan Gambar 13.
Seperti yang terlihat Gambar 10 dan Gambar 11 node yang berkembang sepenuhnya memenuhi area pengujian baik untuk A* pada Gambar 10 maupun Weighted A* pada Gambar 11.
Pada A* node masih sedikit berkembang kearah bawah sedangkan Weighted A* cenderung datar pada saat keluar dari lingkungan trap.
Hasil dari data yang didapat baik untuk A* maupun Weighted A* bisa dikatakan mirip.
Hasil pengujian dapat dilihat pada Tabel VII dan Tabel Vi.
Berdasarkan Tabel VII dan Tabel Vi nilai path cost yang didapat untuk kedua algoritma sama yaitu 54,48.
Baik A* maupun Weighted A* untuk masalah waktu yang dihabiskan dalam lingkungan trap merupakan yang paling tinggi dari semua percobaan yang telah dilakukan.
Ini karena kedua algoritma membuat node baru berdasarkan nilai yce.
Dimana nilai node terkecil ini Tabel VII.
A* pada lingkungan trap
Best
Worst
Mean
Path
54,48
54,48
54,48
Time Memory .
(MB) 7,97 53,85 8,22 54,09 8,07 53,96 Tabel Vi.
Weighted A* pada lingkungan trap Best Worst Mean Weighted A* Path Time Memory .
(MB) 54,48 7,31 53,66 54,48 7,97 54,09 54,48 7,47 53,87 Pengujian perubahan Weighted A* Lingkungan clutter Selanjutnya dilakukan pengujian terhadap perubahan nilai bobot pada fungsi heuristik.
Nilai yang diberikan dari 2 sampai 5.
Hasil pengujian dapat terlihat pada Gambar 12.
TELEKONTRAN.
VOL.
NO.
APRIL 2021
Lingkungan maze Goal Pada lingkungan maze disajikan juga bagaimana Weighted A* bekerja.
Dari hasil pengujian didapatkan jalur yang berbeda arah, untuk nilai W yang berbeda.
Path cost yang didapat memiliki nilai yang berbeda pula.
Semakin tinggi nilai W, path cost yang didapat semakin besar.
Gambar 11 menunjukkan hasil Weighted A* pada lingkungan maze.
Start Goal Gambar 12.
Weighted A* pada lingkungan clutter Pada Gambar 12 diperlihatkan hasil dari penggunaan nilai bobot=3.
Dengan memberikan nilai 3, jalur sedikit berbelok sebelum titik goal Hasil data yang didapat bisa dilihat pada Tabel IX.
Tabel X, dan Tabel XI.
Start Tabel IX.
Pengujian path cost pada lingkungan clutter
Bobot
W=2
W=3
W=4
W=5
Best
38,87
38,87
38,87
38,87
Path cost
Worst
38,87
38,87
38,87
38,87
Gambar 13.
Weighted A* pada lingkungan maze
Mean
38,87
38,87
38,87
38,87
Goal Tabel X.
Pengujian waktu pada lingkungan clutter
Bobot
W=2
W=3
W=4
W=5
Best
0,33
0,34
0,34
0,36
Time .
Worst
0,44
0,38
0,38
0,39
Mean
0,38
0,37
0,36
0,37
Tabel XI.
Pengujian memory pada lingkungan clutter
Bobot
W=2
W=3
W=4
W=5
Memory (MB) Best
Worst
Mean
53,73
54,29
53,93
53,70
54,21
53,92
53,68
54,10
53,91
53,76
54,01
53,90
Berdasarkan Tabel IX path cost yang didapatkan sama untuk semua nilai W yang Pada kasus lingkungan clutter waktu yang diperoleh dari pemberian nilai W yang berbeda berdampak pada waktu proses tercepat yang semakin menurun saat W semakin besar.
Namun waktu rata-rata yang diperoleh dari 10 kali percobaan, didapat adanya penurunan waktu proses saat nilai W semakin besar.
Penggunaan memori untuk algoritma ini ada dibawah 54MB untuk data terbaik dan dibawah 55MB untuk data Start Gambar 14.
Weighted A* pada lingkungan maze Terlihat pada Gambar 13 dan Gambar 14 jalur yang dibuat berbeda arah, yang satu berjalan ke arah atas untuk membuat jalur, kemudian satu lagi bergerak ke arah bawah.
Gambar 13 mempunyai bobot W dengan nilai 3, sementara pada Gambar 14 nilai yang diberikan adalah 5.
Hasil pengujian secara lengkap bisa dilihat pada Tabel XII.
Tabel Xi, dan Tabel XIV.
Tabel XII.
Pengujian path cost pada lingkungan maze
Bobot
W=2
W=3
W=4
W=5
Best
52,87
55,11
74,42
74,42
Path cost
Worst
52,87
55,11
74,42
74,42
Mean
52,87
55,11
74,42
74,42
Tabel Xi.
Pengujian waktu pada lingkungan maze
Bobot
W=2
W=3
W=4
W=5
Best
2,44
2,41
2,25
1,83
Time .
Worst
2,80
2,57
2,52
1,98
Mean
2,61
2,47
2,32
1,90
TELEKONTRAN.
VOL.
NO.
APRIL 2021
Tabel XVI.
Pengujian waktu pada lingkungan narrow Tabel XIV.
Pengujian memory pada lingkungan maze
Bobot
W=2
W=3
W=4
W=5
Memory (MB) Best
Worst
Mean
53,70
54,15
53,93
53,76
54,14
53,95
53,77
54,08
53,91
53,83
54,06
53,92
Bobot
W=2
W=3
W=4
W=5
Mean
4,33
4,07
3,78
3,76
Tabel XVII.
Pengujian memory pada lingkungan narrow Lingkungan narrow Pada lingkungan narrow, waktu yang diperlukan Weighted A* untuk menyelesaikan eksekusi program sedikit agak lama.
4,20 detik untuk waktu tercepat dengan rata-rata sebesar 4.
Hasil pengujian dapat dilihat pada Gambar 15 dan Gambar 16 Goal Start Gambar 15.
Weighted A* pada lingkungan narrow Goal Start Gambar 16.
Weighted A* pada lingkungan narrow
Bobot
W=2
W=3
W=4
W=5
Tabel XV.
Pengujian path cost pada lingkungan narrow
Path cost
Best
Worst
Mean
164,52 164,52 164,52
181,69 181,69 181,69
181,69 181,69 181,69
181,69 181,69 181,69
Memory (MB) Best
Worst
Mean
53,60
54,04
53,85
53,76
54,09
53,88
53,76
54,13
53,96
53,68
54,12
53,93
Pada percobaan di lingkungan ini, nilai path cost yang didapat cukup besar yaitu ada di angka 164,52-181,69.
Ini karena jalur yang dilewati berkelok kelok, serta hanya ada satu jalur saja pada saat awal pencarian dimulai.
Akibat dari jalur yang berbelok, mempengaruhi juga kepada lamanya waktu penyelesaian.
Contohnya dari nilai W=4 dengan W=5, perbedaan waktu yang didapat hanya 0,04 detik saja.
Tidak menunjukkan adanya perbedaan waktu yang terpaut jauh dari perubahan nilai W pada proses ini.
Lingkungan trap Pengujian Weighted A* pada lingkungan trap disajikan pada Gambar 17 dan Gambar 18.
percobaan kali ini, node yang terbentuk memenuhi semua area lingkungan trap untuk semua nilai W yang diujikan.
Pencarian jalur yang berawal dari titik start bergerak ke sudut kanan atas ruang setelah itu node yang terbentuk bergerak kebawah mendekati titik dan keluar area lingkungan trap.
Setelah itu node bergerak menuju sumbu Y dan menemukan titik akhir pencarian.
Nilai W yang diberikan untuk Gambar 15 yaitu W=3.
Jalur yang didapatkan yaitu bergerak kebagian atas.
Gambar 16 juga menghasilkan arah jalur yang sama yaitu berbelok ke kanan pada koordinat .
lalu kearah sumbu Y sampai menemukan titik akhir.
Untuk hasil pengujian bisa dilihat pada Tabel XV.
Tabel XVI, dan Tabel XVII.
Bobot
W=2
W=3
W=4
W=5
Best
4,20
4,00
3,69
3,65
Time .
Worst
4,41
4,16
3,85
3,84
Goal Start Gambar 17.
Weighted A* pada Lingkungan pengujian trap TELEKONTRAN.
VOL.
NO.
APRIL 2021
Goal Start Gambar 18.
Weighted A* pada Lingkungan pengujian trap Berdasarkan Gambar 17 dan Gambar 18 hasil yang terbentuk memiliki kesamaan jalur.
Perubahan nilai W=3 pada Gambar 17 menghasilkan jalur yang tidak terlalu berbeda dengan nilai W=5 pada Gambar 18.
Waktu yang dihasilkan juga tidak terlalu baik untuk pengujian pada lingkungan trap ini.
Hasil pengujian dapat dilihat pada Tabel XVi.
Tabel XIX, dan Tabel XX.
Tabel XVi.
Pengujian path cost pada lingkungan trap
Bobot
W=2
W=3
W=4
W=5
Best
54,48
54,48
54,48
54,48
Path cost
Worst
54,48
54,48
54,48
54,48
Mean
54,48
54,48
54,48
54,48
Tabel XIX.
Pengujian waktu pada lingkungan trap
Bobot
W=2
W=3
W=4
W=5
Best
7,31
7,10
7,15
7,09
Time .
Worst
7,97
7,37
7,34
7,37
Mean
7,47
7,24
7,22
7,23
Tabel XX.
Pengujian memory pada lingkungan trap
Bobot
W=2
W=3
W=4
W=5
Memory (MB) Best
Worst
Mean
53,66
54,09
53,87
53,62
53,98
53,86
53,69
53,98
53,86
53,76
54,09
53,95
Berdasarkan pengujian yang telah dilakukan, diperoleh hasil dimana perubahan nilai bobot heuristik untuk pengujian pada lingkungan trap kurang menunjukkan adanya peningkatan yang Ini dilihat dari waktu yang dibutuhkan saat memproses program dari awal sampai akhir.
Waktu yang didapat dari percobaan pada lingkungan trap merupakan waktu yang paling lama dari beberapa percobaan yang telah 7,97 detik untuk waktu yang paling lama, 7,09 untuk waktu terbaik, dan rata-rata dengan nilai terendah ada di angka 7,22 detik.
Christopher dalam penelitiannya menyebutkan bahwa meskipun dibanyak domain ada tren umum dimana bobot yang lebih besar di Weighted A* mengarah ke pencarian lebih cepat, ada juga domain yang bobotnya lebih besar mengarah ke pencarian yang lebih lambat .
Seperti yang telah di paparkan sebelumnya bahwa waktu yang dihasilkan algoritma Weighted A* pada lingkungan pengujian trap hampir tidak menunjukkan perbedaan yang terpaut jauh dengan algoritma A*.
Kontribusi yang dapat diberikan penulis dari hasil penelitian ini yaitu memberikan pengetahuan tentang hasil penelitian yang telah dilakukan baik kepada engineer, maupn pembaca.
IV.
KESIMPULAN
Berdasarkan hasil pengujian didapatkan algoritma Weighted A* menghasilkan waktu pencarian yang lebih baik daripada algoritma A*.
Tetapi algoritma A* menghasilkan jalur yang lebih optimal dibandingkan algoritma Weighted A*.
Dengan strategi yang lebih menekankan pemilihan node yang lebih dekat dengan node goal, maka Weighted A* dapat menghasilkan jalur dengan waktu komputasi yang lebih cepat.
Sedangkan algoritma A* karena memilih node dengan nilai heuristik terkecil, maka dapat menghasilkan jalur yang lebih optimal.
Penulis sangat mengharapkan pengembangan lebih lanjut dari penelitian ini yaitu dapat diimplementasikan pada hardware.
DAFTAR PUSTAKA