ALGORITMA A*(STAR)

 

IMPLEMENTASI PENCARIAN ALGORITMA A*(STAR) DALAM MENCARI RUTE TERPENDEK

 

Algoritma A-Star merupakan gabungan antara algoritma pencarian Uniform Cost dan Greedy-Best First. Algoritma Uniform cost digunakan untuk mencari biaya yang paling rendah untuk dimulai dari titik awal hingga akhir,sedangkan algoritma Greedy-best first digunakan untuk memberikan estimasi biaya dari titik awal hingga akhir dengan menggunakan fungsi heuristik. Salah satu implementasi dari algoritma A-Star digunakan untuk mencari jalur tercepat. Pada penelitian ini algoritma A-Star digunakan pada navigasi robot hexapod untuk mencari jalur tercepat. Hexapod robot merupakan salah satu jenis robot, dimana pergerakan robot ini dibantu dengan menggunakan enam kaki. Prinsip kerja dari robot dalam penelitian ini yaitu robot akan bergerak sesuai grid yang telah dipetakan dalam arena dengan memanfaatkan algoritma A-Star dan dengan bantuan dari sensor kompas dan ultrasonic. Sensor kompas digunakan untuk navigasi arah gerak robot dimana didapat dari algoritma A-Star. Sensor ultrasonic digunakan untuk mendeteksi halangan yang ada didepan, ketika terdapat halangan maka robot akan menghindar dan akan melakukan kembali perhitungan jalur tercepat lagi. Metodologi yang digunakan dalam penelitian ini dengan menggunakan metoda iteratif. Hasil yang didapat pada penelitian ini yang telah diuji sebelumnya didapat bahwa algoritma A-Star dapat digunakan pada robot hexapod untuk mendapatkan jalur tercepat dalam mencapai tujuan.

 

Dalam bahasan kecerdasan buatan sebuah software/ hardware disebut cerdas jika memiliki kemampuan untuk searching, reasoning, planning dan learning.

 

Lalu apa itu searching,reasoning,planning, dan learning ?

 

1.      Teknik Searching 

Teknik ini digunakan untuk pencarian rute optimum untuk memandu seseorang di perjalanan. 

Contoh: 

Penggunaan komputer yang dilengkapi Global Positioning System (GPS).

Si penumpang tinggal menyebut tempat tujuan, lalu sopir memasukkan tempat tujuan tersebut ke dalam komputer. 

 

2.      Teknik reasoning

 

teknik ini digunakan untuk melakukan penalaran terhadap suatu masalah yang dialami manusia. 

Dalam teknik ini, pengetahuan menjadi basis utamanya. 

 

Contoh : 

Software permainan catur yang disebut HITECH adalah system KB pertama 

yang berhasil mengalahkan grandmaster dunia, Arnold Danker. 

 

3.      Teknik Planning

Teknik ini digunakan untuk melakukan perencanaan terhadap suatu masalah yang hendak diselesaikan. 

Di dunia manufaktur dan robotic, teknik planning memainkan peranan yang sangat penting. 

 

Contohnya : 

 

Optimum-AIV adalah suatu planner (software yang menggunakan teknik planning) yang digunakan oleh 

European Space Agency untuk assembly atau perakitan, integration atau penggabungan dan verification (AIV) pesawat terbang. 

Software tersebut digunakan untuk membuat perencanaan dan untuk memonitor eksekusi terhadap perencanaan-perencanaan tersebut.

 

4.      Teknik Learning

Teknik ini digunakan untuk membuat mesin-mesin otomatis melalui proses pembelajaran dan pelatihan sedemikian rupa hingga bisa menjadi cerdas layaknya manusia. 

Teknik ini telah diterapkan pada berbagai bidang, seperti transportasi, speech processing, computer vision, robotics dan sebagainya. 

Contohnya: 

 

Sebuah mobil bisa berjalan sendiri tanpa disetir oleh manusia. 

Hal ini dimungkinkan karena sistem pengendali otomatis telah dirancang sedemikian rupa dengan jaringan syaraf tiruan (JST) yang dilatih dengan berbagai gambar kondisi jalan raya yang ditangkap melalui kamera yang diletakkan di mobil.

 

Gambar di bawah ini adalah sebuah graf simetris tak berarah yang menggambarkan kondisi jalan raya di suatu kota. Terdapat 8 simpul yang menyatakan persimpangan jalan dengan posisi-posisi koordinat dua dimensi (x,y). Setiap busur memiliki 2 atribut, angka pertama menyatakan panjang jalan sebenarnya (dalam satuan kilo meter), dan angka yang berada dalam tanda kurung, menyatakan kecepatan maksimum yang diperbolehkan untuk setiap kendaraan yang melalui jalan tersebut (dalam satuan km/jam). Seorang pimpinan satuan pemadam kebakaran, yang berada di persimpangan S, bermaksud memadamkan api di sebuah gedung yang terletak di persimpangan G. Dia menggunakan mobil pemadam kebakaran dengan kecepatan maksimum 90 km/jam. Bantulah petugas tersebut menemukan rute jalan dengan total waktu tercepat dari S ke G dengan menggunakan Metode A*.

 

Jawaban :

Karena arenanya terbuka hanya 1 simpul, maka S adalah best node nya.

 

F(A) = 5+90=95

F(B) = 10+90=100

F(C)= 5+60=65

 

 

Selanjutnya adalah menentukan node kembali. Seperti yang kita ketahui bahwa node yang terbaik adalah F(C) = 65, closed = S, Open = A,B,C .

 

F(B)=SC+CB+HB

        = 5+4+90=99

F(F)=SC+CF+HF

        =5+12+50=67

 

Langkah kedua C dengan biaya terkecil (65) terpilih menjadi Best Node dan dipindahkan ke Closed. Semua suksesor di C dibuka yaitu B dan F dan dimasukan ke open.

F(B) Jika starting point dari C = 99

F(B) sebelumnya adalah 100

B berganti parent dari S ke C

Open = (A,B,C,F)

Closed = (C,S)

F menjadi titik awal karena merupakan best node dari opened list/closed list maka langsung dihitung nilainya

F(E)=SE+FE+HE

        =5+5+100=109

F(G)=CF+FG+HG

        =12+5+40=57

Hasil akhirnya yaitu :

Jalur terpendek melalui : S>C>F>G dengan nilai 57

Opened list akhir ; (A,B)

Closed list akhir : (S,C,F)

Daftar pustaka :

http://jnte.ft.unand.ac.id/index.php/jnte/article/view/545

https://www.indonesiana.id/read/23641/jenis-jenis-kecerdasan-buatan

http://kepoankuyah.blogspot.com/2020/11/implementasi-algoritma-astar-dalam.html