Implementasi Metode Simulated Annealing pada Robot Mobil untuk Mencari Rute Terpendek Thiang, Dhany Indrawan Jurusan Teknik Elektro, Universitas Kristen Petra Surabaya 60236, Indonesia e-mail:
[email protected]
Abstract— Makalah ini memaparkan tentang implementasi metode simulated annealing pada sebuah robot mobil mandiri untuk mencari rute terpendek. Karena robot mobil dikontrol dengan menggunakan mikrokontroler, maka metode simulated annealing juga diimplementasi pada mikrokontroler yang sama. Mikrokontroler yang digunakan dalam aplikasi ini adalah mikrokontroler AT89S51 yang merupakan salah satu mikrokontroler keluarga MCS51. Pada aplikasi ini, awalnya, robot diberitahu informasi peta, posisi start dan posisi tujuan. Dengan menggunakan metode simulated annealing, robot akan mencari rute terpendek dari posisi start sampai posisi tujuan, kemudian robot akan bergerak sesuai dengan rute yang telah didapat. Pengujian telah dilakukan dengan variasi posisi start dan posisi tujuan. Hasil pengujian menunjukkan bahwa metode simulated annealing berhasil diimplementasi pada level mikrokontroler. Robot dapat mencari rute terpendek dengan metode simulated annealing dan robot dapat bergerak mengikuti rute yang telah didapatkan. Kata kunci—simulated mikrokontroler, AT89S51
I.
annealing,
robot
mobil,
PENDAHULUAN
Pada penelitian sebelumnya[1], telah berhasil diimplementasi metode hill climbing pada level mikrokontroler dengan aplikasi. Metode hill climbing diimplementasi pada sebuah robot mobil untuk mencari rute terpendek. Namun dari hasil penelitian tersebut, terdapat kelemahan yaitu tidak kepastian metode hill climbing dapat menemukan solusi yang diinginkan. Kadang metode hill climbing menghasilkan rute yang tidak dapat mencapai posisi tujuan. Karena itu, penelitian ini merupakan penelitian lanjutan untuk mendapatkan hasil yang lebih baik. Metode yang dipilih utnuk menggantikan metode hill climbing adalah metode simulated annealing yang pada dasarnya merupakan pengembangan dari metode hill climbing. Tujuan utama dari penelitian ini adalah mengimplementasikan metode-metode sistem cerdas pada platform mikrokontroler. Beberapa metode sistem cerdas yang telah berhasil diimplementasikan pada platform mikrokontroler antara lain fuzzy logic[2], algoritma genetika[3], termasuk hill climbing[1]. Dan kali ini metode yang akan diimplementasikan adalah simulated annealing. Selain itu, tentunya diharapkan metode simulated annealing dapat memberikan hasil yang lebih baik dari penelitian sebelumnya[1] yang menggunakan metode hill climbing. Dalam penelitian ini, mikrokontroler yang dipilih untuk implementasi metode simulated annealing adalah
mikrokontroler keluarga MCS51 yaitu mikrokontroler AT89S52. Alasan pemilihan mikrokontroler ini adalah karena mikrokontroler ini sangat populer dan tersedia banyak di Indonesia, serta harganya yang tidak terlalu mahal. Dengan demikian diharapkan penelitian ini dapat memberikan kontribusi yang positif untuk penelitianpenelitian selanjutnya dalam mengimplementasikan metodemetode kecerdasan buatan pada level mikrokontroler khususnya mikrokontroler keluarga MCS51. II.
METODE SIMULATED ANNELALING
Simulated annealing adalah salah satu algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan simulated annealing adalah masalah-masalah optimisasi kombinatorial,di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu. Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, dimana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum. Simulated annealing berjalan berdasarkan analogi dengan proses annealing tersebut. Simulated annealing memanfaatkan analogi antara cara pendinginan dan pembekuan metal menjadi sebuah struktur crystal dengan energi yang minimal (proses penguatan) dan proses pencarian untuk tujuan minimal. Berikut adalah algoritma metode simulated annealing: 1. Evaluasi keadaan awal. Jika tujuan maka KELUAR (pencarian solusi selesai). Jika tidak lanjutkan dengan keadaan awal sebagai keadaan sekarang.
2. Inisialisasi BEST_SO_FAR untuk keadaan sekarang. 3. Inisialisasi suhu (T) sesuai dengan annealing schedule. 4. Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan kekondisi sekarang. a. Gunakan operator yang belum pernah digunakan untuk menghasilkan keadaan baru. b. Evaluasi kondisi baru dengan menghitung: ∆E = nilai sekarang – nilai keadaan baru i. Jika kondisi baru tujuan (pencarian solusi selesai).
maka
(1)
KELUAR
ii. Jika bukan tujuan, namun nilainya lebih baik dari sekarang, maka jadikan keadaan tersebut sebagai keadaaan sekarang. iii. Jika nilai kondisi baru tidak lebih baik daripada keadaan sekarang, maka tetapkan kondisi baru sebagai keadaan sekarang dengan probabilitas: p’ = e -∆E /T
(2)
dalam kondisi ini juga generate random number dengan range [ 0 , 1 ]. Jika random number lebih kecil dari p’ maka solusi diterima. Jika random number lebih besar dari p’ abaikan (solusi tidak diterima) c.
Gambar 1. Mekanik penggerak robot mobil.
Sensor
Komparator
Mikrocontroller AT89S51
Perbaiki T sesuai dengan annealing schedule
5. BEST_SO_FAR adalah solusi yang dicari. Perbedaan antara metode simulated annealing dan metode simple hill climbing adalah: •
Simulated annealing memilki annealing schedule
•
Pada metode simulated annealing solusi yang jelek masih ada kemungkinan untuk diterima
•
Nilai keadaan sekarang adalah nilai yang terbaik sepanjang proses berlangsung. Kemudian jika keadaan yang baru yang lebih jelek daripada keadaan sekarang (karena kurang beruntung dalam penerimaan solusi), keadaan yang baru tersebut masih bisa digunakan. III.
Driver
Motor Gambar 2. Diagram blok perangkat keras robot.
Sensor cahaya yang digunakan adalah sepasang LED dan LDR. Karena output dari sensor LDR berupa sinyal analog, maka untuk merubah menjadi digital digunakan rangkaian komparator. Output rangkaian ini hanya mempunyai 2 state yaitu low dan high yang menunjukkan warna hitam dan putih. berikut gambar 3 dan 4 menunjukkan gambar rangkaian sensor dan komparator.
DESKRIPSI SISTEM
A. Perangkat Keras dan Mekanik Robot Mobil Bentuk dasar robot terbuat dari kayu tebal 3mm dan berbentuk oval 14,5cm x 11cm. Robot dilengkapi dengan 2 buah roda dan sebagai penggerak digunakan 2 buah motor DC dengan masing-masing motor memiliki sebuah gear box. Gambar 1 menunjukkan gambar mekanik penggerak robot. Robot mobil dirancang untuk bergerak mengikuti garis. Karena itu robot mobil dilengkapi dengan sensor cahaya. Secara umum, diagram blok perangkat keras robot dpat dilihat pada gambar 2. Gambar 3. Rangkaian sensor
Tabel 1. Tabel koneksi mikrokontroler dengan sensor dan driver motor
Gambar 4. Rangkaian komparator
Output sensor akan dibaca oleh mikrokontroler sebagi informasi untuk mengendalikan robot mobil bergerak mengikuti garis putih. Sebagai penggerak robot mobil, digunakan 2 buah motor DC, masing-masing roda digerakkan oleh satui motor DC. Rangkaian driver motor DC yang digunakan adalah rangkaian H-Bridge. Rangkaian HBridge ini menggunakan transistor TIP 41 dan TIP 42. berikut gambar 5 menunjukkan gambar rangkaian driver motor DC.
B. Perangkat Lunak Secara umum cara kerja sistem robot mobil untuk mencari rute terpendek adalah seperti yang ditunjukkan pada gambar 7. Start
Tentukan Start dan tujuan
Mencari rute dengan simulated annealing
Gambar 5. Rangkaian driver motor DC
Mikrokontroler yang digunakan sebagai pengendali dari robot mobil adalah mikrokontroler AT89S51. mikrokontroler ini termasuk mikrokontroler keluarga MCS51. rangkaian mikrokontroler ini dirancang sederhana yaitu berupa rangkaian single chip, tanpa ada memori eksternal. Berikut gambar 6 menunjukkan gambar rangkaian mikrokontroler yang digunakan dan tabel 1 menunjukkan tabel koneksi mikrokontroler dengan rangkaian sensor dan rangkaian driver.
Gambar 6. Rangkaian single chip mikrokontroler
Bergerak menuju tujuan sesuai rute dengan tracking garis
End Gambar 7. Diagram blok sistem kerja robot mobil
Gambar 8. Peta area lintasan robot mobil
Pertama-tama posisi start dan tujuan robot ditentukan kemudian robot akan secara otomatis menentukan rute dari start sampai tujuan dengan metode simulated annealing. Setelah mendapatkan rute, robot akan berjalan secara tracking line menuju ke tujuan sesuai dengan rutenya. Area untuk peta telah didefinisikan terlebih dahulu. Gambar 8 menunjukkan area peta yang digunakan. Secara detail flowchart perangkat lunak yang telah dirancang dapat dilihat pada gambar 9.
RAM bukan nilai ouput port yang sesungguhnya. karena itu perlu diubah menjadi output port. Barulah ttersebut dapat menelusuri jalur yang telah didapat. tersebut merupakan jalur terpendek menuju tujuan diinginkan. IV.
Oleh robot Jalur yang
HASIL PENGUJIAN
Pengujian sistem telah dilakukan dengan variasi posisi start dan posisi tujuan untuk melihat performans sistem apakah dapat mencari rute terpendek. Beberapa pengujian yang dilakukan antara lain posisi start (0,5) dan posisi tujuan (0,2), posisi start (0,0) dan posisi tujuan (0,5), posisi start (2,0) dan posisi tujuan (4,5), posisi start (0,4) dan posisi tujuan (1,0), posisi start (1,0) dan posisi tujuan (4,0). Berikut gambar 10 sampai gambar 14 menunjukkan rute dari hasil pengujian yang didapatkan oleh robot mobil dengan menggunakan metode simulated annealing.
Gambar 10. Rute hasil pengujian dengan psosi start (0,5) dan posisi tujuan (0,2)
Gambar 9. flowchart perangkat lunak robot mobil
Pemetaan merupakan hal yang penting yang pertama kali dilakukan dalam alur program. Berhasil atau tidaknya pencarian benda ataupun penentuan jalur terpendek tidak lepas dari pemetaan ini. Dengan pemetaan ini maka seluruh area yang ada akan digambarkan. Hasil yang didapat dari pemetaan tersebut akan dijadikan acuan untuk menghitung kuadrat jarak lurus setiap titik yang ada pada area terhadap titik tujuan. Nilai hasil perhitungan jarak yang didapat tersebut akan disimpan di dalam alamat RAM mikrokontroler. Nilai tersebut kemudian akan dianalisa dengan menggunakan metode simulated annealing. Dengan metode ini maka akan didapatkan rute yang terpendek menuju titik tujuan. Namun, rute ini masih berupa alamat
Gambar 11. Rute hasil pengujian dengan psosi start (0,0) dan posisi tujuan (0,5)
Bila melihat hasil pengujian yang telah dilakukan seperti yang ditunkukkan oleh gambar 10 sampai gambar 13, terlihat bahwa dengan menggunakan metode simulated annealing, robot mobil berhasil mencari rute terpendek. dan robot mobil juga dapat bergerak mengikuti rute yang telah didapatkan. Tetapi pada hasil pengujian yang ditunjukkan oleh gambar 14, metode simulated annealing terjebak pada rute yang sama sehingga robot hanya bergerak berputarputar saja pada area tertentu. V.
Gambar 12. Rute hasil pengujian dengan psosi start (0,2) dan posisi tujuan (4,5)
KESIMPULAN
Dari hasil pengujian yang telah dilakukan dapat diambil kesimpulan bahwa metode simulated annealing berhasil di terapkan untuk pencarian rute terdekat pada robot mobil. Tetapi masih terdapat kemungkinan bahwa simulated annealing tidak dapat memberikan hasil yang terbaik seperti hasil pengujian yang ditunjukkan oleh gambar 14. Pada penelitian ini simulated annealing telah berhasil diimplementasikan pada level mikrokontroler. REFERENSI [1]
[2]
[3]
[4] [5] Gambar 13. Rute hasil pengujian dengan psosi start (0,4) dan posisi tujuan (1,0)
Gambar 14. Rute hasil pengujian dengan psosi start (1,0) dan posisi tujuan (0,4)
Thiang, Handry Khoswanto, Felix Pasila, Hendra Thelly, “Aplikasi Metode Hill Climbing pada Standalone Robot Mobil untuk Mencari Rute Terpendek”, Prosiding Seminar KOMMIT 2008, Depok, 2008. Thiang, Anies Hannawati, Resmana Lim, Hany Ferdinando, “PetraFuz: a Low Cost Embedded Controller Based Fuzzy Logic Development System”, Proceeding of The Fourth Asian Fuzzy Systems Symposium (AFSS 2000), Tsukuba Science City, Jepang, Juni 2000. Thiang, Ronald Kurniawan, Hany Ferdinando, “Implementation of Genetic Algorithm on MCS51 Microcontroller for Finding the Shortest Path”. Proceeding of Seminar of Intelligent Technology and Its Applications (SITIA 2001), ITS-Surabaya, May 2001 Rich, Elaine. Artificial Intelligence. New York: McGraw-Hill, 1991. AT89S51 Datasheet. San Jose, CA: Atmel Corporation, 1995.
