PERBANDINGAN ALGORITMA FLOOD-FILL DENGAN ALGORITMA BACKTRACKING DALAM PENCARIAN JALUR TERPENDEK PADA ROBOT MICROMOUSE Oleh Febryan Sutejoningtyas NIM : 612009009
Skripsi Untuk melengkapi salah satu syarat memperoleh Gelar Sarjana Teknik Program Studi Teknik Elektro Fakultas Teknik Elektronika dan Komputer Universitas Kristen Satya Wacana Salatiga
Oktober 2015
INTISARI
Robot Micromouse didesain untuk menyelesaikan permasalahan dalam mencari jalan keluar dari suatu labirin baik itu labirin sempurna (perfect maze) maupun labirin tidak sempurna (imperfect maze). Agar robot mampu menyelesaikan permasalahan dengan proses yang cepat dan efisien, dibutuhkan algoritma pencarian jalur terpendek untuk diimplementasikan dalam robot micromouse. Dengan sekian banyaknya algoritma pencarian jalur terpendek yang ada, tidak semua algoritma mampu menyelesaikan permasalahan – permasahan yang ada di dalam suatu labirin secara efisien. Robot micromouse ini memiliki sebuah sistem kontrol yang hanya terdiri dari satu bagian utama, yaitu kontrol utama dimana memiliki peran penting dalam melakukan pengontrolan terhadap keseluruhan sistem pada robot, seperti sistem navigasi dan sistem gerak. Dalam sistem navigasi robot, kontrol utama menerima segala data keluaran dari sensor dinding, kompas digital dan rotary encoder. Data yang diterima oleh kontrol utama berupa data mentah baik analog maupun digital yang kemudian diolah sehingga dapat digunakan oleh robot sebagai penunjuk jalan. Dalam sistem gerak robot, kontrol utama mengirimkan perintah – perintah khusus terhadap kontrol aktuator untuk mengontrol segala pergerakan motor DC. Kecepatan motor dan arah perputaran motor ditentukan berdasarkan sistem navigasi robot. Pengujian dilakukan dengan membandingkan kinerja antara algoritma flood-fill dengan algoritma backtracking dalam pencarian jalur terpendek. Berdasarkan hasil pengujian, algoritma flood-fill memiliki kinerja yang lebih efisien daripada algoritma backtracking dalam mencari jalur terpendek pada peta labirin khususnya dalam menangani imperfect maze dimana total sel terpendek pada maze 2 terpaut sebanyak 26 sel, sedangkan pada maze 3 terpaut sebanyak 36 sel.
i
ABSTRACT
Micromouse robot is designed for resolving problems in finding a way out of a maze either perfect maze or imperfect maze. So that the robot is able to resolve problems quickly and efficiently, it needs the shortest path search algorithms to be implemented in the micromouse robot. With the many existing of the shortest path search algorithms, not all algorithms are able to resolve problems that are in a maze efficiently. This micromouse robot has a control system which only consist of one main part, it is the main control which has an important role in controlling the whole robot’s system such as navigation system and motion system. In the robot’s navigation system, the main control receives all of the data output from wall sensors, digital compass, and rotary encoder. Data received by the main control is a raw data either analog or digital which is processed so that it can be used by robot as a guide. In the robot’s motion system, the main control send specific commands to actuator control for controlling the movements of the DC motors. The motor speed and the direction of the motor rotation are determined based on robot’s navigation system. Testing done by comparing the performance between the flood-fill algorithm and the bactracking algorithm in the search of the shortest path. Based on the testing results, the flood-fill algorithm has performance that is more efficient than the backtracking algorithm in finding the shortest path in the maze especially in handle of imperfect maze which the difference among the shortest total cell in maze 2 is 26 cell, while in maze 3 is 36 cell.
ii
KATA PENGANTAR
Puji dan syukur penulis ucapkan kepada Tuhan Yesus Kristus yang tidak pernah meninggalkan penulis selama menempuh pendidikan sampai sekarang sehingga penulis dapat menyelesaikan perancangan serta penyusunan skripsi ini. Penulisan skripsi ini diajukan untuk memenuhi salah satu syarat memperoleh gelar Sarjana di Fakultas Teknik Elektronika dan Komputer Universitas Kristen Satya Wacana. Pada kesempatan ini penulis juga hendak mengucapkan terima kasih kepada berbagai pihak yang baik secara langsung maupun tidak langsung telah membantu penulis dalam menyelesaikan skripsi ini : 1. Tuhan Yesus yang selalu memberikan jalan terbaik sehingga penulis dapat menyelesaikan skripsi ini. 2. Papa Rudy Yus Hendratno dan mama Nur Megawati, kedua orang tua yang selalu mendoakan penulis dalam segala hal dan selalu mendukung penulis terutama dalam hal finansial untuk membiayai segala keperluan yang dibutuhkan oleh penulis dalam menyelesaikan skripsi ini. 3. Bapak Deddy Susilo, M. Eng dan Bapak Darmawan Utomo, M. Eng selaku pembimbing I dan pembimbing II, terima kasih atas bimbingan dan saran yang telah diberikan kepada penulis selama mengerjakan skripsi ini. 4. Seluruh staff dosen, karyawan dan laboran FTEK yang telah memfasilitasi penulis selama belajar di FTEK UKSW. 5. Kakakku Yudi yang selalu memberikan dukungan, masukan, dan saran yang sangat bermanfaat sehingga penulis dapat menyelesaikan perkuliahan sampai pada akhirnya dapat menyelesaikan skripsi akhir ini. 6. Seluruh keluarga besar FTEK 2009 sebagai teman seperjuangan yang selalu memberi dukungan kepada penulis. 7. Kakak – kakak angkatan atas yang pernah memberikan pelajaran – pelajaran yang sangat berharga selama belajar di FTEK UKSW.
iii
8. Teman – teman sekitar yang pernah memberikan bantuan dalam menyelesaikan permasalahan – permasalahan yang muncul saat mengerjakan skripsi ini. 9. Berbagai pihak yang tidak dapat dituliskan satu persatu, penulis mengucapkan terima kasih. Penulis menyadari bahwa skripsi ini masih jauh dari kata “sempurna”, oleh karena itu penulis sangat mengharapkan kritik maupun saran dari pembaca sekalian sehingga skripsi ini dapat berguna bagi kemajuan teknik elektronika.
Salatiga, Oktober 2015
Penulis
iv
DAFTAR ISI
INTISARI................................................................................................................. i ABSTRACT ............................................................................................................ ii KATA PENGANTAR ........................................................................................... iii DAFTAR ISI ............................................................................................................v DAFTAR GAMBAR ............................................................................................ vii DAFTAR TABEL .................................................................................................. ix BAB I PENDAHULUAN ........................................................................................1 1.1.
Tujuan .......................................................................................................1
1.2.
Latar Belakang ..........................................................................................1
1.3.
Batasan Masalah........................................................................................2
1.4.
Sistematika Penulisan ...............................................................................3
BAB II DASAR TEORI ..........................................................................................5 2.1.
Kajian Pustaka ..........................................................................................5
2.2.
Penerapan Sensor ......................................................................................6
2.3.
Perbandingan Algoritma ...........................................................................9
2.4.
Algoritma Flood-Fill ..............................................................................10
2.5.
Algoritma Backtracking ..........................................................................14
BAB III PERANCANGAN SISTEM ....................................................................17 3.1.
Gambaran Sistem ....................................................................................17
3.2.
Perancangan Peta Labirin ........................................................................19
3.3.
Perancangan Mekanik Robot ..................................................................23
3.4.
Perancangan Perangkat Keras .................................................................25
3.4.1.
Sistem Kontrol ..................................................................................25
3.4.2.
Perangkat Keras Elektronik...............................................................26
3.5.
Perancangan Perangkat Lunak ................................................................34
3.5.1.
Flowchart Program Utama ................................................................34
3.5.2.
Flowchart Algoritma Flood-Fill .......................................................35
3.5.3.
Flowchart Algoritma Backtracking ..................................................38
BAB IV PENGUJIAN DAN ANALISIS ..............................................................40
v
4.1.
Pengujian Sensor Dinding (Photodiode dan LED) .................................40
4.2.
Pengujian Kompas Digital HMC5983L ..................................................41
4.3.
Pengujian Rotary Encoder ......................................................................43
4.4
Pengujian Algoritma Pencarian Jalur Terpendek ....................................44
4.4.1.
Pengujian Algoritma Flood-Fill........................................................45
4.4.2.
Pengujian Algoritma Backtracking ...................................................50
4.4.3.
Perbandingan Kinerja Algoritma ......................................................55
BAB V KESIMPULAN DAN SARAN .................................................................57 5.1.
Kesimpulan .............................................................................................57
5.2.
Saran Pengembangan ..............................................................................58
DAFTAR PUSTAKA ............................................................................................59 LAMPIRAN A TAHAPAN PROSES KERJA ALGORITMA FLOOD-FILL PADA MAZE 1 ......................................................................................................60 LAMPIRAN B TAHAPAN PROSES KERJA ALGORITMA BACKTRACKING PADA MAZE 1 ......................................................................................................66
vi
DAFTAR GAMBAR
Gambar 1.1. (a) Contoh labirin sempurna, (b) Contoh labirin tidak sempurna .......1 Gambar 2.1. Proses pemantulan cahaya pada sensor cahaya ...................................6 Gambar 2.2. Pengaruh warna objek terhadap pantulan cahaya ...............................7 Gambar 2.3. Penempatan Sensor Cahaya ................................................................7 Gambar 2.4. Susunan Rotary Encoder .....................................................................8 Gambar 2.5. Penempatan Kompas Digital ...............................................................9 Gambar 2.6. Ilustrasi pembangkitan nilai awal pada peta labirin 5 x 5 .................11 Gambar 2.7. Bentuk Kondisi Lapangan .................................................................12 Gambar 2.8. Ilustrasi proses pembaharuan nilai sel...............................................13 Gambar 2.9. Struktur pohon akar Depth-First Search ...........................................14 Gambar 2.10. Ilustrasi proses runut-balik pada peta labirin 5 x 5 .........................15 Gambar 2.11. Pohon solusi proses runut-balik dan pencarian jalur terpendek ......16 Gambar 3.1. Blok Diagram Sistem ........................................................................17 Gambar 3.2. Rancangan Peta Labirin 10 x 10 .......................................................19 Gambar 3.3. Dinding Adjustable............................................................................20 Gambar 3.4. Posisi Start dan Finish ......................................................................21 Gambar 3.5. Bentuk Variasi Peta Labirin ..............................................................21 Gambar 3.6. Bentuk Realisasi Peta Labirin 10 x 10 ..............................................22 Gambar 3.7. Kerangka Robot ................................................................................23 Gambar 3.8. Bentuk Realisasi Robot Micromouse ................................................24 Gambar 3.9. Kontroler Arduino UNO ...................................................................26 Gambar 3.10. Konfigurasi Pin Arduino UNO .......................................................27 Gambar 3.11. Rangkaian Sensor Cahaya ...............................................................28 Gambar 3.12. Konfigurasi Pin 74HC4051 .............................................................29 Gambar 3.13. Sensor Magnet HMC5983L ............................................................30 Gambar 3.14. Roda Piringan Rotary Encoder .......................................................31 Gambar 3.15. Rangkaian Rotary Encoder .............................................................31 Gambar 3.16. Driver Motor TB6612FNG .............................................................32 Gambar 3.17. Konfigurasi Pin EEPROM AT24C512 ...........................................34 Gambar 3.18. Flowchart Program Utama ..............................................................35 vii
Gambar 3.19. Flowchart Algoritma Flood-Fill .....................................................36 Gambar 3.20. Flowchart Algoritma Backtracking ................................................38 Gambar 4.1. Grafik Perubahan Nilai Keluaran Sensor Dinding ............................40 Gambar 4.2. Grafik Hasil Keluaran Sensor Magnet HMC5983L..........................41 Gambar 4.3. Tempat Uji Coba : (a) Maze 1, (b) Maze 2, (c) Maze 3 ....................44 Gambar 4.4. Run-Test Pertama Algoritma Flood-Fill pada Maze 1 ......................46 Gambar 4.5. Run-Test Kedua Algoritma Flood-Fill pada Maze 1 .........................47 Gambar 4.6. Run-Test Ketiga Algoritma Flood-Fill pada Maze 1 ........................47 Gambar 4.7. Run-Test Pertama Algoritma Flood-Fill pada Maze 2 ......................47 Gambar 4.8. Run-Test Kedua Algoritma Flood-Fill pada Maze 2 .........................48 Gambar 4.9. Run-Test Ketiga Algoritma Flood-Fill pada Maze 2 ........................48 Gambar 4.10. Run-Test Pertama Algoritma Flood-Fill pada Maze 3 ....................48 Gambar 4.11. Run-Test Kedua Algoritma Flood-Fill pada Maze 3 .......................49 Gambar 4.12. Run-Test Ketiga Algoritma Flood-Fill pada Maze 3 ......................49 Gambar 4.13. Run-Test Pertama Algoritma Backtracking pada Maze 1 ...............52 Gambar 4.14. Run-Test Kedua Algoritma Backtracking pada Maze 1 ..................52 Gambar 4.15. Run-Test Ketiga Algoritma Backtracking pada Maze 1 ..................52 Gambar 4.16. Run-Test Pertama Algoritma Backtracking pada Maze 2 ...............53 Gambar 4.17. Run-Test Kedua Algoritma Backtracking pada Maze 2 ..................53 Gambar 4.18. Run-Test Ketiga Algoritma Backtracking pada Maze 2 ..................53 Gambar 4.19. Run-Test Pertama Algoritma Backtracking pada Maze 3 ...............54 Gambar 4.20. Run-Test Kedua Algoritma Backtracking pada Maze 3 ..................54 Gambar 4.21. Run-Test Ketiga Algoritma Backtracking pada Maze 3 ..................54
viii
DAFTAR TABEL
Tabel 2.1. Perbandingan Algoritma .......................................................................10 Tabel 3.1. Tabel Keterangan Mekanik Robot ........................................................25 Tabel 3.2. Tabel Spesifikasi Pololu Micro Metal Gearmotors ..............................25 Tabel 3.3. Kegunaan Pin Arduino UNO ................................................................27 Tabel 3.4. Fungsi Kontrol H-Bridge pada TB6612FNG........................................33 Tabel 4.1. Hasil Pengujian Arah pada Kompas Digital .........................................42 Tabel 4.2. Hasil Pengujian Jumlah Penghitungan pada Rotary Encoder ...............43 Tabel 4.3. Hasil Pengujian Algoritma Flood-Fill pada Maze 1 .............................45 Tabel 4.4. Hasil Pengujian Algoritma Flood-Fill pada Maze 2 .............................45 Tabel 4.5. Hasil Pengujian Algoritma Flood-Fill pada Maze 3 .............................45 Tabel 4.6. Hasil Pengujian Algoritma Backtracking pada Maze 1 ........................50 Tabel 4.7. Hasil Pengujian Algoritma Backtracking pada Maze 2 ........................50 Tabel 4.8. Hasil Pengujian Algoritma Backtracking pada Maze 3 ........................51 Tabel 4.9. Hasil Perbandingan Kinerja Algoritma .................................................55
ix
