Penerapan Algoritma Pledge Untuk Menyelesaikan Maze Pada Line Follower Arif Darmawan#1, Akhmad Hendriawan -1#2, Reesa Akbar-2#3 #
Jurusan Teknik Elektronika, Politeknik Elektronika Negeri Surabaya Kampus PENS-ITS Sukolilo, Surabaya 1
[email protected] [email protected] 3
[email protected]
2
Abstrak — Pledge adalah salah satu algoritma untuk menemukan jalan keluar pada suatu labirin. Pada umumnya algoritma pledge diaplikasikan pada robot wall maze, sehingga untuk penerapan pada robot line maze diperlukan beberapa modifikasi dengan cara melakukan konversi bentuk labirin kedalam sebuah maze. Namun demikian algoritma pledge sendiri memiliki kelemahan pada solusi yang kaku ketika bertemu halangan karena hanya terdapat satu pilihan dalam mengindari halangan. Oleh karena itu pada paper ini menawarkan modifikasi algoritma pledge yang tidak hanya mampu diterapkan pada labirin, tetapi bisa juga menyelesaikan sebuah maze dengan beberapa alternatif yang lebih fleksibel dengan cara memberikan prioritas antara left dan right wall following. Kontrol PID digunakan untuk membantu robot berjalan stabil saat melakukan line following. Hasil akhir yang didapatkan dari paper ini robot mampu memetakan maze dan menemukan jalan keluar dengan keberhasilan sebesar 90%. Kata kunci — pledge, robot line follower, prioritas wall, maze, PID 1.
Pendahuluan Fungsi utama dari line follower robot adalah sebagai robot yang dirancang untuk berjalan mengikuti garis. Namun dalam paper ini, robot tidak hanya bertugas untuk berjalan mengikuti garis saja melainkan juga harus bisa mencari jalan keluar (jalan menuju ke finish) dari suatu maze. Hal ini tentunya membutuhkan sistem kendali yang bisa membuat robot mampu melewati maze dengan baik dan dengan tingkat error seminimal mungkin. Dengan demikian, waktu yang ditempuh untuk mencapai tujuan menjadi lebih efektif. Semakin berkembangnya ilmu dalam bidang robotika semakin menegaskan bahwa kelak kedepannya bidang ini akan semakin dekat dengan kehidupan manusia. Line follower bisa dianggap robot yang sangat sederhana karena hanya berjalan mengikuti garis. Dengan menggunakan mikrokontroller sebagai pusat kontrol dan memori robot diharapkan robot tidak hanya berjalan mengikuti garis, akan tetapi dapat memecahkan dan memberi solusi pada penyelesaian labirin berbentuk garis (maze) [4]. 2.
Latar Belakang Pemecahan maze dengan berbagai cara banyak dilakukan dengan berbagai metode. Dengan digunakannya pledge sebagai metode mapping didapatkan solusi yang lainnya dalam melakukan mapping maze tersebut. Metode lain juga banyak digunakan salah satunya dengan menggunakan maze mapping ataupun dengan flood fill. Masing masing metode menawarkan solusi yang berbeda dengan hasil akhir yang berbeda. Dengan menggunakan maze mapping yang menggunakan wall following sederhana akan mampu memperoleh keseluruhan bentuk maze, robot mampu
1
menemukan finish dengan start dengan sembarang tempat[8]. Flood fill maupun pledge adalah generasi pengembangan dari algoritma maze mapping. Flood fill mempunyai keunggulan penerapannya yang sudah mampu melewati looping. Penerapan algoritma flood fill sebenarnya digunakan pada robot micro mouse dalam kasus mencari titik pusat dari suatu labirin dengan syarat labirin merupakan bentuk persegi sempurna dengan dibagi tiap bidangnya[3]. Robot di start pada lintasan terluar dengan poin terbesar kemudian dilakukan pengurangan poin terhadap tiap-tiap bidang dilewati[7]. Kelemahan pengunaan algoritma wall follower adalah robot tidak mampu menemukan finish apabila terdapat lintasan berbentuk looping. Robot akan menemukan error pada saat mapping sehingga tidak mampu menemukan finish[8]. Sedangkan pada flood fill posisi start robot tidak bisa diubah-ubah dan bentuk dimensi maze harus diketahui terlebih dahulu sebelum robot dijalankan[7]. Pada proyek akhir kali ini digunakan algoritma pledge yang ditujukan untuk mengatasi kelemahan diatas. Algoritma ini merupakan pengembangan mapping turtle geometri yang diaplikasikan pada maze mapping. 3. Teori Penunjang 3.1 Algoritma Pledge Algoritma pledge didesain untuk rintangan melingkar dan memiliki arah awal untuk bergerak maju. Ketika berhadapan dengan rintangan, maka robot akan menggunakan wall follower yang akan menghindari rintangan dengan menghitung jumlah belokan yang ditempuh robot. Ketika robot kembali ke arah awal dan total hitungan belokan adalah
“0”, maka penyelesaian berlanjut sampai bertemu halangan kembali [6]. Berikut ini adalah pseudocode untuk mempermudah pemahaman tentang urutan algoritma pledge. Total_belokan = 0 While (robot menyala) { Berjalan ke arah utama If (bertemu halangan) { Repeat Berjalan dengan metode wall follower Menghitung total belokan yang di tempuh (belok kanan Total belokan + 1, belok kiri Total belokan - 1) Until Total_belokan = 0 } }
Gambar 3.3 Kurva respon sustain oscillation[2]
Penalaan parameter PID didasarkan terhadap kedua konstanta hasil eksperimen Ku dan Pu. Gambar 3.3 adalah respon ssstem ketika didapatkan Pu. Ziegler dan Nichols menyarankan penyetelan nilai parameter Kp, Ti dan Td berdasarkan parameter yang diperlihatkan pada tabel 3.1. Tabel 3.1 Penalaan parameter PID dengan metode osilasi[2]
Tipe Kontroler P PI PID
3.2 Kontrol PID Kontrol untuk mengendalikan kecepatan motor DC pada robot digunakan kontroler PID. Kontroler ini merupakan kombinasi antara kontrol P, I dan D. Dengan menggabungkan ketiga kontroler tersebut, maka akan diperoleh luaran yang cukup ideal dari yang diharapkan. Gambar 3.1 menunjukkan skema kombinasi PID dalam sebuah kontroler untuk motor DC[1].
Kp 0,5.Ku 0,45.Ku 0,6.Ku
Ti
Td
½ Pu 0,5 Pu
0,125 Pu
3.3 Konversi dari labirin ke maze Algoritma ini nantinya akan diterpakan pada maze yang merupakan bentuk 2 dimensi dari labirin. Oleh karena itu konversi dari labirin ke maze dan penerapan algoritmanya mutlak dilakukan. Dalam konversi ke bentuk maze juga diberlakukan batasan-batasan masalah dalam Proyek Akhir ini, yaitu maze hanya mempunyai belokan 900. Sehingga pada akhirnya maze hanya menuju kearah 4 mata angin(utara, barat, timur dan selatan). Berikut adalah langkah-langkah dalam konversi dari labirin ke maze: Memilih labirin yang akan dikonversikan, misal labirin seperti gambar 3.4
Gambar 3.1 Blok diagram kontrol[2]
Keterangan: Putih = ruangan Biru = tembok Titik s = robot start
Metode Ziegler-Nichols[1]
Gambar 3.4 Labirin yang akan dikonversi
Gambar 3.2 kurva respons unit step tangga satuan yang memperlihatkan 25% lonjakan maksimum[2]
Metode yang digunakan untuk penalaan nilai dari Kp, Ki dan Kd adalah dengan metode Ziegler-Nichols. Metode ini memiliki dua cara, yaitu metode osilasi dan metode kurva reaksi. Kedua metode ditujukan untuk menghasilkan respon sistem dengan lonjakan maksimum sebesar 25% seperti yang ditunjukkan pada gambar 3.2. Nilai penguatan proporsional pada saat sistem mencapai kondisi sustain oscillation disebut ultimate gain (Ku). Periode dari Ku disebut ultimate period (Tu)[2].
2
Membuat semua ruangan menjadi dalam bentuk garis, ruangan pada labirin diatas adalah bagian yang berwarna putih. Mendeskripsikan bahwa tembok adalah perbatasan antara warna biru dan putih serta ruangan padat pada bagian yang bagian berwarna biru. Mengabaikan bentuk maze yang berbentuk tidak lurus dengan menggantinya dengan maze yang lurus dengan sudut belok 900. Maka hasil akhir konversi dari labirin ke maze
Gambar 3.5 Hasil konversi
Tembok adalah perbatasan antara warna biru dan putih serta ruangan padat pada bagian yang bagian berwarna biru. Sedangkan hasil konversi seperti pada gambar 3.5, ruangan merupakan garis berwarna hitam sedangkan tembok adalah warna putih. 4
Perancangan Sistem Secara umum, rancangan system yang dibuat adalah tampak pada gambar 4.1 Sistem ini seperti halnya kerja line follower robot pada umumnya, namun diberikan beberapa fitur – fitur tambahan, secara umum penambahan fitur – fitur yang dilakukan adalah, 1. PID kontroler, berguna untuk kontrol gerakan line follower robot, agar dapat berjalan dengan baik, dalam artian tidak banyak berosilasi. 2. Rotary encoder, sebagai sensor untuk mengetahui jarak yang telah ditempuh. 3. Komunikasi serial, digunakan untuk mengirim data error pada kontroler, sehingga error dapat diamati dan dianalisa.
Gambar 4.2 Flowchart algoritma Pledge dan bagian yang dimodifikasi
Perbaikan algoritma pledge akan memodifikasi gerak robot ketika bertemu halangan dengan mampu menerapkan baik right wall following maupun left wall following. Meskipun demikian pemberian prioritas antara left dan right wall following perlu dilakukan sehingga robot line maze nantinya akan lebih fleksibel ketika bertemu halangan. Kontrol PID digunakan untuk membantu robot berjalan stabil saat melakukan line following. 4.2 Kontrol PID Kontrol PID dalam proyek akhir ini digunakan untuk mengontrol posisi robot saat berjalan agar bisa selalu berada di tengah-tengah garis. Luaran yang diberikan adalah berupa nilai untuk pengaturan kecepatan motor. Kontrol untuk mengendalikan kecepatan motor DC pada robot digunakan kontroler PD. Kontroler ini merupakan kombinasi antara kontrol P dan D. Dengan menggabungkan kedua kontroler tersebut, maka akan diperoleh luaran yang cukup ideal dari yang diharapkan seperti gambar 4.3.
Gambar 4.1 Konfigurasi system
4.1 Pledge Penjelasan dari flowchart pada gambar 4.2 adalah sebagai berikut, robot berjalan menuju arah utama, misalnya arah utara sebagai arah utama robot. Arah utama adalah arah dimana robot pertama kali di start. Apabila belum terdapat halangan dan masih tersedia jalan utama maka robot akan terus berjalan kearah utama tersebut. Ketika robot mendapat halangan sehingga tidak mungkin kejalan kearah utama maka robot akan melakukan wall follower sambil melakukan perhitungan total belokan yang dilakukan. Apabila berbelok ke kanan ditambah 1 apabila berbelok ke kiri total belokan dikurangi satu. Robot akan kembali ke jalan utama apabila total belokan yang ditempuh = 1. Proses ini akan terus dilakukan dengan robot akan melakukan mapping terhadap lintasan terus menerus sampai robot menemui garis finish[6].
Gerakan robot berosilasi mengecil
Target Position
Gambar 4.3 Pola gerakan robot berosilasi[5]
Dalam penggunaannya, posisi sensor terhadap garis mengartikan error yang terjadi. Gambar 4.4 adalah gambaran posisi sensor beserta nilai errornya.
3
Gambar 5.3 Grafik hasil pengujian sensor terhadap jarak ketika membaca bidang hitam Gambar 4.4 nilai error berdasarkan posisi sensor
Berdasarkan hasil pengujian pada sensor terhadap ketinggian didapatkan data yang sangat berguna yaitu jarak ideal lantai terhadap robot. Data semakin bagus apabila range nilai ADC antara hitam dan putih semakin lebar. Dalam hasil percobaan range yang didapat diwakili oleh sensor 0 yaitu sebagai berikut.
Dalam aplikasinya, maka peran dari kontroler ini dapat diterapkan dalam program dengan formulasi seperti berikut: pwmKiri = PwmRef + (Kp.error + Kd.(error-old_error) + Ki.(error + ak_error)) pwmKanan = PwmRef - (Kp.error - Kd.(error-old_error) Ki.(error + ak_error)) Ket: PwmRef adalah nilai pwm yang diinginkan pada saat error = 0
5 Pengujian 5.1 Pengujian Sensor terhadap ketinggian Rancangan sensor pada proyek akhir ini, yang digunakan sebanyak 8 (delapan) buah. Masing-masing sensor ini diberi nama dengan sensor(i), dimana i = 0 s.d 7.
Jarak 0mm → 183 – 10 = 173 Jarak 5mm → 190 – 4 = 186 Jarak 15mm → 184 – 10 = 174 Jarak 20mm → 192 – 20 = 172 Jarak 25mm → 200 – 35 = 165 Jarak 30mm → 210 – 91 = 119
Dari perhitungan range jarak, range terjauh pada jarak 5mm. Maka penggunaan sensor nantinya sekitar jarak 5mm – 10mm sehingga mendapatkan kinerja sensor ADC yang maksimal. 5.2 Pengujian kontroller PID Prosedur pengujian pada kontroler ini, mengikuti metode Ziegler dan Nichol, dimana eksperimen ini dilakukan pada suatu sistem hanya dengan kontroler P saja. Gain Proposional Kc dinaikkan secara perlahan sampai batas kestabilan, dimana sistem mulai mengalami osilasi. Dengan mendapatkan nilai Ku (Ultimate Gain) maka Kp, Ki, Kd akan didapatkan. Gambar 5.4 dan Gambar 5.5 merupakan grafik hasil pengujian control PID.
Gambar 5.1 Pengujian sensor berdasarkan jarak/ketinggian
Penjelasan pada gambar 5.1 adalah sensor diukur dengan jarak ketinggian berbeda dengan permukaan yang disensor. Data yang tampil adalah nilai desimal (hasil konversi biner) pada LCD. Berikut adalah data hasil pengujiannya: Gambar 5.2 dan gambar 5.3 adalah gambar grafik yang diperoleh baik terhadap bidang warna hitam ataupun garis putih.
Error Sensor
ERROR 8 6 4 2 0 -2 0
2000
4000
6000
8000
10000
12000
-4 -6
WAKTU
Gambar 5.2 Grafik hasil pengujian sensor terhadap jarak ketika membaca garis putih
Kp = 15, Ki=0, Kd=0
Gambar 5.4 Hasil grafik data error pada nilai Kp=15, Ki=0,Kd=0
4
ERROR 8
dalam menyelesaikan maze dari start sampai finish. Hasil pengamatan gerak robot dapat dilihat pada tabel 5.1.
Error Sensor
Tabel 5.1 Data penyelesaian robot right wall priority
6 4
Percobaan
2
-2
0
2000
4000
6000
8000
10000 12000
-4 -6
WAKTU
Kp = 20, Kd = 50
Gambar 5.5 Hasil grafik data error pada nilai Kp=20, Kd=50
Pengujian ini dilakukan dengan menjalankan line follower robot pada suatu garis lurus, dan posisi awal robot berada pada kondisi yang memiliki error paling besar. Kemudian kontroler akan melakukan aksi yaitu mengatur kecepatan antara motor kanan dan kiri agar dapat mencapai posisi referensi.
Waktu Tempuh
√ √ √ √ √ √
1 2 3 4 5 6 7 8 9 10
0
Penerapan Algoritma Tidak Berhasil Berhasil
0 : 25.47 0 : 26.55 0 : 28.89 0 : 25.73 0 : 27.03 0 : 23.47 √
√ √ √
0 : 27.17 0 : 25.81
Jalan robot dengan memprioritaskan Left Wall Following seperti pada gambar 5.7. Penjelasan left wall priority identik dengan right wall priority. Hanya pemberian prioritas ketika bertemu halangan bebentuk simpangan“T”.
5.3 Pengujian Algoritma Pledge Pengujian ini dimaksudkan untuk keberhasilan robot dalam menemukan jalan keluar. Jalan keluar ini adalah sebagai finish robot yang nantinya digunakan untuk menunjukkan bahwa robot sudah menemukan jalan keluar dan berhenti. Gambar 5.6 menjelaskan robot seharusnya berjalan dengan memprioritaskan Right Wall Following.
9 3
2
8 8
7
6
1 5
4
1
7 6
5
4
Gambar 5.7 Penyelesaian dengan left wall priority
3 2
Table 5.2 adalah hasil pengamatan gerak robot Left Wall Priority.
Gambar 5.6 Penyelesaian dengan right wall priority
Arah utama robot adalah arah dimana robot pertama kali diletakkan. Halangan pertama dijumpai pada simpanan pertama. Karena menggunakan right wall priority maka robot harus berbelok kekiri agar dapat melakukan right wall following pada dinding halangan. Simpangan kedua robot berbelok kekanan akibat masih melakukan right wall following. Counter belokan = 0, robot kembali menemukan arah utama sehingga mampu melewati simpangan tiga, empat dan lima. Keunggulan dari modifikasi algoritma pledge ini dapat dilihat pada simpangan enam. Apabila tidak menggunakan prioritas maka robot akan melakukan right wall following dan aksi robot adalah putar balik. Robot secara fleksibel akan melakukan left wall following dan berbelok kekanan. Robot akan menemukan finish dengan melewati simpangan tujuh dan delapan karena masih melakukan left wall following. Dari pengamatan mapping robot dapat diperoleh apakah robot mampu menyelesaikan lintasan yang diberikan. Selain pengamatan pada gerak robot juga diamati waktu robot
Tabel 5.2 Data penyelesaian robot Left Wall Priority
Percobaan
Penerpaan Algoritma Tidak Berhasil Berhasil
Waktu Tempuh
1 √ 0 : 34.52 2 √ 0 : 36.14 3 √ 0 : 32.99 4 √ 0 : 35.47 5 0 : 36.04 √ 6 √ 0 : 34.47 7 √ 0 : 35.19 8 √ 0 : 32.04 9 √ 0 : 33.53 10 √ 0 : 33.91 Pengujian selanjutnya adalah menggunakan Algoritma pledge dengan random priority. Perbedaan dari keduanya adalah pada metode random robot bisa melakukan Right Wall
5
ataupun Left Wall pada saat robot menemui lintasan berbentuk “T”. Tabel 5.3 adalah hasil dari pengujian random priority. 7 [1]
Tabel 5.3 Data penyelesaian robot Random Wall Priority
Perc
Penerapan Wall priority Left
Right
Penerapan Algoritma Tidak Berhasil Berhasil
[3]
1
√
√
0:25.89
2
√
√
0:27.23
√
0:36.17
3
√
4
√
√
0:24.12
5
√
√
0:25.22
6
[2]
Waktu Tempuh
[4]
[5] [6]
√
7
√
√
0:35.05
8
√
√
0:35.50
9
√
√
0:24.56
10
√
√
0:26.08
[7]
[8]
Dari data yang diperoleh dapat disimpulkan bahwa robot mampu menyelesaikan maze 90% dari 30 pengujian. Pengujian right wall priority mengalami error sebanyak 2 kali dari 10 pengujian. Pengujian left wall priority sukses dalam menyelesaikan maze sebanyak 10 pengujian. Ketika dalam random priority robot melakukan right wall priority sebanyak 7 kali, sedangkan sisanya 3 kali melakukan left wall priority. Robot tidak berhasil melakukan algoritma disebabkan kurang presisi mekanik seperti error yang telah di dapat pada right wall priority. 6
Kesimpulan Output dari pembacaan sensor oleh ADC semakin bagus apabila range nilai ADC antara hitam dan putih semakin lebar. Jarak memiliki range terjauh pada jarak 5mm. Penggunaan sensor nantinya sekitar jarak 5mm – 10mm sehingga mendapatkan kinerja sensor ADC yang maksimal. Nilai Kp=20 dan Kd=50, merupakan nilai setting yang didapat untuk line follower robot yang dibuat pada final project ini, Penggunaan kontroler akan menjaga kestabilan jalan dari robot, sehingga mampu menjaga keakuratan dalam pembacaan jarak oleh rotary encoder, dan juga pembacaan bentuk lapangan oleh sensor garis. Rotary encoder yang digunakan telah dapat berjalan dengan baik, error error rata-ratanya adalah sebesar 0.95%. Pada saat dilakukan pengujian algoritma pledge, masih dijumpai error rata-rata dengan persentase sebesar 10 %, hal ini disebabkan karena pengerjaan mekanik yang kurang baik. Algoritma pledge yang dimodifikasi memiliki 3 kemungkinan prioritas yang dapat digunakan. Right wall priority, left wall priority dan random priority. Tidak ada keunggulan ditiap prioritasnya hanya pengambilan
6
keputusan disaat menemui jalan simpang 3 berbentuk “T” Pustaka Maeda, Y. Kuswadi, Son. M, Nuh. Sulistyo MB. Kontrol Automatik. Politeknik Elektronika Surabaya; 1993 Ogata, Katsuhiko. Teknik Kontrol Automatik. Jilid I edisi kedua – Jakarta. Erlangga:1997 Giessel David ; “Building a Mouse”, UAF MicroMouse Home Page ; 2007 Mishra Swarti, Bande Pankaj ; ”Maze Solving Algorithm for Micro Mouse”, International Conference on Signal Image Technology and Internet Based Systems ; 2008 W Eddy ; ”PID for Line Follower”, Chicago Area Robotics Group ; 2007 Tom Kamphans, Elmar Langetepe, “The Pledge Algorithm Reconsidered under error in sensor and motion”, Departmen of Computer Science , Bonn, Germany Rahman, Abdullah ; ” Penerapan Algoritma Flood Fill untuk Menyelesaikan Maze pada Line Follower Robot”, Tugas Akhir EEPIS-ITS; 2010 Iqbal, Muhammad ; ” Penerapan Algoritma Maze Mapping untuk Menyelesaikan Maze pada Line Follower Robot”, Tugas Akhir EEPIS-ITS; 2009
7
