1
PERENCANAAN JALUR TERPENDEK PADA ROBOT NXT DENGAN OBSTACLE DINAMIS MENGGUNAKAN ALGORITMA D* Wahris Shobri Atmaja 1) , Diah Puspito Wulandari, ST.,Msc 2), Ahmad Zaini , ST., MT. 3) Jurusan Teknik Elektro ITS Surabaya, Jurusan Teknik Elektro ITS Surabaya, Jurusan Teknik elektro ITS Surabaya 1)
[email protected]
ABSTRACT - In computation world, many algorithm used to find shortest path from two node on the matrix or map. One from many searching algorithm is A* algorithm. A* algoritm same like Djikstra algoritm, but A* algorithm has heuristic function. A* Algorithm must have optimal solution because equal the shortest path from start and the shortest path from goal with static obstacle that has been planning. D* usually called “Dynamic A*” because the algorithm update the cost if found dynmic obstacle as the A* algorithm runs. With Mindstorms NXT and D* algorithm, Ever make mobile robot with pass the test and succes until goal we want without touch the static obstacle. And then the mobile robot same can finish although any dynamic obstacle because used D* algorithm. The successful of robot to finish with 50 time trial is 84%. Keyword : Robotic, NXT Mindstorms, A*, D*
I. PENDAHULUAN Robot saat ini telah banyak dimanfaatkan oleh industri-industri di dunia dalam upaya meningkatkan efisiensi dan efektifitas berbagai aktifitas kerja manusia. Salah satu teknologi robot yang terkenal saat ini adalah LEGO NXT dengan nama NXT Mindstorms. NXT merupakan salah satu tool yang bis dimanfaatkan dalam dunia pendidikan untuk mempelajari pembuatan robot dan pengendaliannya. Untuk mempelajari pembuatan robot dapat dilakukan dengan mendesain menggunakan semua bagian yang sudah disediakn oleh NXT mindstorms untuk menjadi bentuk robot yng diinginkan. Selain itu juga dapat mempelajari program untuk mengendalikan robot dengan software yang sudah disediakan juga oleh NXT mindstorms.
Dalam dunia komputasi, sangat banyak algoritma yang dapat digunakan untuk mencari jarak tependek dari dua titik yang terdapat pada suatu matriks (peta). salah satu dari algoritma pencari pasangan titik terdekat itu ialah algoritma A*. Algoritma A* sangat mirip dengan algoritma Djikstra, namun ia memiliki fungsi heuristik tambahan. Algoritma A* juga terkenal sebagai algoritma yang pasti memberikan hasil yang optimal karena menjumlahkan jarak terpendek dari start dan jarak terpendek dari goal dengan konfigurasi map dan obstacle yng sudah di tentukan. Sedangkan algoritma D* adalah algoritma A* dengan update nilai saat A* berjalan karena itu D* biasa disebut “Dynamic A*”. Algoritma ini berguna untuk mengatasi perubahan konfigurasi map karena adanya obstacle dinamis sehinggal merepresentasikan pada kondisi real. Dalam tugas akhir inilah, akan dibuat suatu Mobile Robot dengan NXT mindstorms yang dapat merencanakan suatu jalur terpendek agar robot sampai pada tempat tujuan yang diinginkan meskipun ada obstacle statis dan dinamis karena menggunkan algoritma D*
II.
DASAR TEORI
2.1 ALGORITMA A* A* (dibaca "A bintang"/"A star") adalah algoritma pencarian graf/pohon yang mencari jalur dari satu titik awal ke sebuah titik akhir yang telah ditentukan. Algoritma A* menggunakan pendekatan heuristik h(x) yang memberikan peringkat ke tiap-tiap titik x dengan cara memperkirakan rute terbaik yang dapat dilalui dari titik tersebut. Setelah itu tiap-tiap titk x tersebut dicek satu-persatu berdasarkan urutan yang dibuat dengan pendekatan heuristik tersebut. Maka dari itulah algoritma A* adalah contoh dari best-first search.
2
Algoritma ini pertama kali ditemukan pada tahun 1968 oleh Peter Hart, Nils Nilsson dan Bertram Raphael. Dalam tulisan mereka, algoritma ini dinamakan algoritma A. Penggunaan algoritma ini dengan fungsi heuristik yang tepat dapat memberikan hasil yang optimal, maka algoritma inipun disebut A*. Dalam ilmu komputer, A* adalah algoritma komputer yang banyak digunakan dalam pathfinding dan traversal grafik, proses merencanakan jalur efisien tercepat antara titik, yang disebut node. Tercatat untuk kinerja dan ketepatan, menikmati digunakan secara luas. Peter Hart, Nils Nilsson, dan Bertram Raphael pertama kali menjelaskan algoritma ini pada tahun 1968. Ini adalah perluasan dari algoritma 1959 Edsger Dijkstra. Sebuah algoritma untuk mencapai kinerja yang lebih baik (berkenaan dengan waktu) dengan menggunakan heuristik. Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list, closed list, nilai (cost), goal, halangan (unwalkable).
Gambar 2.1.1 Pemberian nilai A* Dalam setiap simpul atau kotak terdapat 3 parameter nilai yaitu nilai F, G, dan H Dimana rumus dasar nilai A* adalah F(n) = G(n) + H(n) (1) F = Nilai total G = Nilai jarak terpendek dari start H = Nilai jarak terpendek dari goal Selain terdapat 3 parameter nilai juga terdapat koordinat titik yang akan untuk menentukan arah dan posisi robot berada. Dimana pada gambar diatas menunjukkan nilai koordinat (0,0). Begitu juga untuk semua kotak yang lain.
Starting point adalah sebuah terminologi untuk posisi awal sebuah benda. A adalah simpul yang sedang dijalankan dalam algortima pencarian jalan terpendek. Simpul adalah petak-petak kecil sebagai representasi dari area pathfinding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan. Closed list adalah tempat menyimpan data simpul sebelum A yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan. Nilai (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai perkiraan dari sebuah simpul ke goal. Goal yaitu simpul yang dituju. Halangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh A. Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil. Perhatikan Gambar dibawah ini :
Gambar 2.1.2 Proses awal pencarian A* Diawali dengan menempatkan A pada starting point, kemudian memasukkan seluruh simpul yang bertetangga dan tidak memilik atribut rintangan dengan A ke dalam open list. Kemudian mencari nilai H terkecil dari simpul-simpul dalam open list tersebut. Kemudian memindahkan A ke simpul yang memiliki nilai H terkecil. Simpul sebelum A disimpan sebagai parent dari A dan dimasukkan ke dalam closed list. Jika terdapat simpul lain yang bertetangga dengan A (yang sudah berpindah) namun belum termasuk kedalam anggota open list, maka masukkan simpul-simpul tersebut ke dalam open list. Setelah itu, bandingkan nilai G yang ada dengan nilai G sebelumnya (pada langkah awal, tidak perlu dilakukan perbandingan nilai G). Jika nilai G sebelumnya lebih kecil maka A kembali ke posisi awal. Simpul yang pernah dicoba dimasukkan ke dalam closed list. Hal terebut dilakukan berulang-ulang hingga terdapat solusi
3
atau tidaka ada lagi simpul lain yang berada pada open list.
mungkin karena di kota Manhattan di Amerika, jarak dari dua lokasi umumnya dihitung dari blokblok yang harus dilalui saja dan tentunya tidak bisa dilintasi secara diagonal. Perhitungannya dapat ditulis sebagai berikut: h(n) = abs(n.x-tujuan.x) + abs(n.y-tujuan.y) (2)
Gambar 2.1.3 Proses akhir pencarian A* Keterangan gambar : Kotak hijau = Starting point Kotak hitam = Halangan Kotak merah = Goal Hijau tepi = Open list Biru tepi = Closed list Nilai tiap kotak = Nilai F, G, H Lingkaran merah = Jalur terpendek 2.1.1 Fungsi Heuristik untuk A* Seperti yang telah disebutkan diatas, fungsi heuristik sangat berpengaruh terhadap kelakuan algoritma A*: • Apabila h(n) selalu bernilai 0, maka hanya g(n) yang akan berperan, dan A* berubah menjadi Algoritma Dijkstra, yang menjamin selalu akan menemukan jalur terpendek. • Apabila h(n) selalu lebih rendah atau sama dengan nilai perpindahan dari titik n ke tujuan, maka A* dijamin akan selalu menemukan jalur terpendek. Semakin rendah nilai h(n), semakin banyak titik-titik yang diperiksa A*, membuatnya semakin lambat. • Apabila h(n) tepat sama dengan nilai perpindahan dari n ke tujuan, maka A* hanya akan mengikuti jalur terbaik dan tidak pernah memeriksa satupun titik lainnya, membuatnya sangat cepat. Walaupun hal ini belum tentu bisa diaplikasikan ke semua kasus, ada beberapa kasus khusus yang dapat menggunakannya. • Apabila h(n) kadangkala lebih besar dari nilai perpindahan dari n ke tujuan, maka A* tidak menjamin ditemukannya jalur terpendek, tapi prosesnya cepat. • Apabila h(n) secara relatif jauh lebih besar dari g(n), maka hanya h(n) yang memainkan peran, dan A* berubah menjadi BFS.
Hal lain yang harus diperhatikan adalah seberapa cepat fungsi heuristik dapat dikomputasi. Selalu akan ada trade-off antara akurasi dari fungsi heuristik dan waktu yang dibutuhkannya untuk mengomputasinya. Nampaknya bagus jika fungsi heuristik yang digunakan sangat akurat, dilihat dari berbagai macam percobaan bahwa jika heuristik yang digunakan sempurna maka A* akan selalu melewati jalur yang tepat dan akan selalu memberikan optimum global. Namun, heuristik yang sempurna semacam itu tidak ada (dan tidak akan pernah ada), dan bahkan untuk mendekatinya saja akan memerlukan tambahan komputasi yang tidak ringan. Seringkali dalam aplikasinya heuristik yang memberikan hasil yang sangat akurat namun lambat, kurang disenangi dibanding heuristik yang tidak begitu optimal namun memberikan hasil dengan cepat. Maka dari itu, pemilihan heuristik sangat bergantung pada tujuan penggunaan A*. Jika hasil yang dibutuhkan adalah optimum global, maka fungsi heuristik yang digunakannya haruslah "sempurna", sedang jika yang dibutuhkan adalah hasil yang cepat dan tidak harus jalur terpendek, maka lebih bijak menggunakan heuristik yang lebih ringan. 2.2 ALGORITMA D* D* adalah algoritma A* dengan halangan yang dinamis. Algoritma ini seperti algoritma A* tetapi dapat mendeteksi halangan saat A* nya jalan. Algoritma pencarian D diperkenalkan oleh Anthony Stentz pada tahun 1994. Nama D* berasal dari istilah “ Dynamic A* Untuk lebih jelasnya lihat gambar dibwah ini :
Gambar 2.2.1 Proses awal pencarian D* Heuristik yang paling umum digunakan adalah jarak Manhattan. Fungsi heuristik ini hanya akan menjumlahkan selisih nilai x dan nilai y dari dua buah titik. Heuristik ini dinamakan Manhattan
4
bergerak maka akan di lanjutkan sesuai dengan A* yang pertama seperti gambar 2.2.3. Akan tetapi bila halangan diam, maka posisi terakhir saat mendeteksi halangan akan dijadikan sebagai start baru dan akan dilakukan proses pencarian A* kedua dengan goal yang sama seperti gambar 2.2.4 dan gambar 2.2.5. III. DESAIN DAN IMPLEMENTASI 3.1 DESAIN ROBOT Gambar 2.2.2 Halangan pada jalur A* 3.1.1 Desain robot NXT
Gambar 2.2.3 Halangan dinamis pada jalur A* Gambar 3.1.1 Desain robot NXT
Gambar 2.2.4 Posisi Start pada A* kedua
Desain robot NXT dibuat seperti gambar diatas. Yaitu robot berbentuk sepertu mobil atau anjing dengan 2 roda pada bagian depan dan satu roda bebas pada bagian belakang. Roda bebas ini digunakan untuk mengurangi adanya gesekan pada roda saat berjalan agar robot bisa berjalan lurus. Sedangkan 2 roda bagian depan dihubungkan dengan 2 buah motor untuk mengatur pergerakan robot baik maju atau belok. Sensor yang digunakan adalah sensor ultrasonic dengan penempatan depan. Sensor ini digunakan untuk mendeteksi adanya obstacle saat robot berjalan. Semua proses pengaturan dilakukan oleh NXT dengan tampilan layar LCD. 3.1.2 Desain Maze
Gambar 2.2.5 Proses akhir Pencarian A* kedua Diawali dengan proses akhir pencarian A* yang dijadikan sebagai proses awal pencarian D* seperti gambar 2.2.1. Pada saat menjalankan A* yang pertama, tiba-tiba ada halangan pada jalur A* maka sensor akan mendeteksi halangan tersebut seperti gambar 2.2.2. Setelah mendeteksi halangan pada jalur A* akan di tunggu apakah halangan tersebut diam atau bergerak. Kalau halangan
Gambar 3.1.1 Desain Maze
5
Desain maze yang dibuat adalah suatu lantai dengan luas 240cm x 240cm. dimana terdri dari 8 ubin vertikal dan 8 ubin horizontal. Dengan masing2 ubin berukuran 30cm x 30cm. Posisi tampilan awal maze baik posisi start, obstacle, dan goal seperti pada gambar diatas. Posisi tersebut dapat dirubah sesuai dengan yang diinginkan.
4.2
Pengujian Sistem meliputi : A. Pengujian respon NXT terhadap algoritma D* B. Pengujian waktu robot untuk berjalan C. Pengujian Prosentase keberhasilan robot
3.2 IMPLEMENTASI
Pengujian respon NXT terhadap algoritma D* ini digunakan untuk mencari tau seberapa cepat mikrokontroller pada NXT memproses algoritma D* yang sudah dibuat. Percobaan dilakukan sebanyak 10 kali dengan posisi start dan goal yang sama tetapi halangan berbeda-beda. Baik halangan yang mudah maupun halangan yang sulit. Selengkapnya lihat table dibawah ini :
A. Pengujian respon NXT terhadap algoritma D*
Tabel 4.2.1 Pengujian respon NXT terhadap algoritma D*
Gambar 3.2.1 Kemampuan robot NXT Robot NXT mindstorms yang dibuat memiliki kemampuan untuk belok dari 0 sampai 360 derajat. Dengan posisi awal (default) robot menghadap ke kanan. Posisi ini digunakan untuk menyimpan koordinat awal robot serta arah robot kedua parameter tersebut digunakan agar robot dapat berjalan dan mengetahui arah selanjutnya dengan benar. IV. PENGUJIAN 4.1
Pengujian Sistem Pada bagian ini akan membahas pengujian dan analisa sistem yang telah dirancang. Smua pengujian dilakukan dalam kondisi baterai NXT yang terisi penuh. dan pada maze seperti gambar dibawah ini :
Percobaan
Koordinat Start
1 2 3 4 5 6 7 8 9 10
2,3 2,3 2,3 2,3 2,3 2,3 2,3 2,3 2,3 2,3
Koordinat Goal
Halangan
6,3 0 6,3 1 6,3 2 6,3 3 6,3 4 6,3 5 6,3 6 6,3 7 6,3 8 6,3 9 RATA-RATA =
Waktu (detik)
2,3 2,4 2,8 3,5 4,4 5,5 5,9 7,2 9,7 11,5 5,52
B. Pengujian Waktu robot untuk berjalan Pengujian Waktu robot untuk berjalan dari satu ubin ke ubin yang lain baik maju lurus, maju diagonal maupun belok di gunakan untuk menghitung berapa lama waktu yang dibutuhkan robot untuk menghindari obstacle dinamis yang bergerak sehingga robot tidak menabraknya. Selengkapnya lihat table dibawh ini : Tabel 4.2.2 Pengujian waktu robot berjalan maju Percobaan Gerakan maju Waktu(detik) 1 lurus 1,98 2 diagonal 2,54 RATA-RATA = 2,26
Gambar 4.1.1 Maze pengujian sistem
Tabel 4.2.3 Pengujian waktu robot berjalan belok Percobaan Gerakan belok Waktu(detik) 1,35 1 450 1,66 2 900 2,29 3 1350 2,79 4 1800 5 2,34 2250 0 1,89 6 270 0 1,48 7 315 RATA-RATA = 1,97
6
C. Pengujian prosentase keberhasilan robot Pengujian prosentase keberhasilan robot dilakukan sebanyak 50 kali dengan posisi start dan posisi goal berbeda-beda. Begitu juga dengan obstacle nya. Baik jumlah maupun kesulitannya berbeda-beda. Hal ini dilakukan untuk mengetahui seberapa bagus robot NXT dalam memproses lgoritma D* dan menjalankannya. Selengkapnya lihat table dibawah ini : Tabel 4.2.4 Pengujian prosentase keberhasilan robot Percobaan
Koordinat Start
Koordinat Goal
Halangan
Keterangan
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
1,7, 2,5 3,3 5,3 1,3 2,3 5,3 7,3 1,3 6,3 5,7 1,3 5,5 6,6 6,3 7,3 2,4 1,4 3,3 1,3 2,3 4,3 3,3 4,3 3,3 2,3 3,3 2,6 2,4 1,3 2,3 2,6 1,3 6,3 5,2 6,3 7,3 2,3 2,5 1,3 2,7 5,1 2,5 2,2
2,3 4,3 7,3 3,3 6,3 5,3 3,2 4,5 4,3 1,3 1,5 7,5 1,2 0,4 3,4 1,1 5,6 7,7 5,1 6,3 7,3 2,3 4,3 7,3 3,3 6,3 6,3 3,2 4,5 4,3 1,3 1,5 7,5 1,2 0,4 3,4 1,1 5,6 7,7 5,1 6,3 7,3 3,4 1,1
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 2 0
Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Tidak Berhasil
Berhasil Berhasil Berhasil Berhasil Berhasil Tidak Berhasil
45 46 47 48 49 50
5,3 3,3 1,2 2,1 4,3 1,1
5,6 7,7 5,1 6,3 7,3 7,7
RATA-RATAKEBERHASILAN
Berhasil Berhasil Berhasil Tidak Berhasil Tidak Berhasil
= 42/50 x 100% =
V.
Berhasil
1 2 0 1 2 2
84%
KESIMPULAN
1) Rata-rata respon NXT terhadap algoritma D* dengan start dan goal yang sama tetapi dengan halangan yang berbeda-beda baik yang mudah maupun sulit adalah 5,52 detik 2) Rata-rata waktu robot untuk berjalan adalah : a. Maju = 2,26 detik b. Belok = 1,97 detik Dari rata-rata tersebut dapat disimpulkan bahwa obstacle dinamis yang bergerak minimal 4,5 detik untuk pindah dari satu ubin ke ubin yang lain. Karena gerakan robot untuk maju 2 ubin adalah 4,52 detik 3) Prosentase keberhasilan robot untuk sampai ke goal dengan 50 kali percobaan dengan posisi start, posisi goal, dan halangan dinamis yang berbeda-beda adalah 84%
Berhasil Berhasil
VI. DAFTAR PUSTAKA
Berhasil Berhasil Berhasil Tidak Berhasil
Berhasil Berhasil Tidak Berhasil
Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Berhasil Tidak Berhasil
Berhasil Berhasil Tidak Berhasil
Berhasil Berhasil
[1] http://www.nxtprograms.com/ [2] http://bricxcc.sourceforge.net/nbc/ [3] A* searchalgorithm,http://en.wikipedia.org/ wiki/A_search_algorithm, Wikipedia, tanggal akses 2 januari 2010 pukul 13.00WIB. [4] Patrick Lester, A* Pathfinding for Beginners, http://www.gamedev.net/reference/articles/art icle2003.asp, 2003. [5] Stentz, A. 1995. The focussed D* algorithm for real-time re-planning. In Proceedings of the International Joint Conferenceon Arti?cial Intelligence, 1652–1659.
