BAB I PENDAHULUAN
1.1 Latar Belakang Masalah Robot adalah mesin yang dapat melakukan kegiatan seperti yang manusia dan binatang lakukan, sehingga membutuhkan persepsi, aksi dan kecerdasan tersendiri yang diprogram di dalamnya untuk menyamai kelakuan makhluk hidup. Persepsi didapatkan melalui sensor, aksi dikerjakan dengan motor, dan kecerdasan diprogram dalam unit mikrokontroler yang menghubungkan sensor dan motor. Robot yang canggih bahkan memiliki sistem kontrol (mikrokontroller yang di program) yang tidak hanya menghasilkan aksi berdasarkan pengetahuan yang tersimpan di ’otak’-nya, melainkan juga belajar memperoleh pengetahuan baru secara otomatis dari pengalamannya sendiri. Maze atau labirin sendiri merupakan suatu permainan mencari jalan keluar dari suatu daerah yang memiliki jalan berliku-liku dan membutuhkan algoritma untuk dapat menyelesaikannya. Labirin (istilah untuk maze dalam bahasa Indonesia) dibangun dengan konstruksi memiliki dinding dan ruangan, dibangun diatas sebidang tanah dengan menggunakan bahan tanaman pagar, gambut, tanaman jagung, rumput kering atau jerami, buku-buku, papan kayu, dan dinding batu. Labirin dalam wilayah yang cukup besar biasanya dimanfaatkan sebagai objek wisata. Tetapi untuk labirin robot yang diperlombakan biasanya menggunakan dinding papan sebagai pembatas ruangan. Masalah labirin bukanlah hal asing lagi dalam keseharian, labirin yang secara tidak sengaja terbentuk banyak kita jumpai, misalnya gang-gang atau jalan kecil dipemungkiman yang padat, dimana sering ditemukan adanya jalan buntu. Seringkali labirin ini menyesatkan bagi orang yang baru disuatu daerah. Salah satu hal menarik yang lain dari labirin adalah mencari rute terpendek dari berbagai pilihan jalur yang bisa digunakan. Dalam kehidupan nyata, hal ini bisa diaplikasikan pada GPS sistem. 1
Di wilayah Amerika Serikat, ada suatu kompetisi robot yang sangat terkenal dan telah berusia sekitar 30 tahun. Kompetisi tersebut biasa dikenal dengan micromouse, dan hingga saat ini telah mengalami beberapa perubahan kecil dalam aturan permainannya. Pencapaian atau ‘goal’ dari kompetisi robot yang satu ini sangat sederhana, sebuah robot harus bergerak dari salah satu sudut ‘maze’ (labirin) menuju ke tengah secepat mungkin dengan algoritma yang paling efektif. Salah satu contoh bentuk labirin yang diperlombakan dapat dilihat pada gambar 1.1.
Gambar 1.1 Salah satu contoh labirin yang diperlombakan
Banyak metode yang dikembangkan manusia untuk menyelesaikan masalah labirin ini, antara lain Wall Follower, Backtracker (backtracking), A*, dan Collision Solver. Sedikit menyerupai kasus pada perlombaan micromouse, penulis akan membandingkan dua algoritma yang akan digunakan untuk menyelesaikan kasus labirin, dengan dua algoritma tersebut diharapkan mampu untuk menentukan algoritma yang efektif dalam penyelesaian kasus labirin dengan menggunakan mobile robot. Perlu digaris bawahi bahwa maze yang digunakan adalah maze yang memiliki hanya satu penyelesaian, baik itu apakah dengan cara mengitari semua ruangan atau pun langsung menuju ke tujuan (goal).
1.2 Perumusan Masalah Berdasarkan uraian pada latar belakang, masalah yang didefenisikan untuk tugas akhir ini adalah menganalisa implementasi metode wall follower (right or
2
left hand algorithm) dan algoritma backtracking pada robot lego NXT untuk pencarian rute terpendek pada labirin. Sehingga diakhir Tugas Akhir, penulis dapat menyimpulkan metode yang tepat dan efektif dalam menyelesaikan kasus labirin dengan menggunakan mobile robot. Berikut ini deskripsi klasifikasi dari perfect maze yang akan digunakan : a) 2D : maze standar tanpa overlapping , gang ataupun jembatan. b) Non-hypermaze : hanya satu jalan keluar/penyelesaian c) Normal Topology : topologi menggambarkan geometri ruang yang ada didalam maze. d) Ortogonal Tesselation : merupakan kotak persegi panjang standar dimana sel memiliki bagian-bagian yang berpotongan di sudut kanan. e) Perfect routing : memiliki jalur yang semuanya dapat diakses, tidak ada close circuits dan tidak memiliki loops. Berikut ini adalah deskripsi dari mobile robot yang akan digunakan : a) Jenis mobile robot adalah Lego Mindstorms NXT, untuk lebih detail mengenai spesifikasi teknikal dapat dilihat pada tabel 2.1. b) Jenis sensor yang digunakan : i.
Light sensor
ii.
Ultrasonic sensor Tabel 1.1 Spesifikasi dari Lego Mindstorms NXT (1)
Part
Detail
-
Motor Port
3 output : port A, B dan C
-
Sensor Port
4 input : port 1, 2 ,3 dan 4
-
USB port
Konesi
ke
komputer
desktop
dengan
menggunakan kabel USB, juga tersedia wireless bluetooth connection -
Loudspeaker
-
NXT button
- orange button : ON/Enter/Run
3
Tabel 1.1 (Sambungan) Part
Detail - Light Grey Arrow : moving menu - Dark Grey Arrow : Clear/ Go back
-
NXT display
-
Technical Specifications
Sebagai layar tampilan menu •
32-bit ARM7 microcontroller
•
256 Kbytes FLASH, 64 Kbytes RAM
•
8-bit AVR microcontroller
•
4 Kbytes FLASH, 512 Byte RAM
•
Bluetooth wireless communication (Bluetooth Class II V2.0 compliant)
•
USB full speed port (12 Mbit/s)
•
4 input ports, 6-wire cable digital platform (One port includes a IEC 61158 Type 4/EN 50 170 compliant expansion port for future use)
•
3 output ports, 6-wire cable digital platform
•
100 x 64 pixel LCD graphical display
•
Loudspeaker - 8 kHz sound quality. Sound channel with 8-bit resolution and 2-16 KHz sample rate.
•
Power source: 6 AA batteries
1.3 Batasan Masalah Batasan-batasan yang didefenisikan dalam pembangunan mobile robot untuk menyelesaikan kasus labirin ini adalah : a) Labirin yang digunakan adalah tipe “perfect maze”, sesuai dengan yang dituliskan pada Perumusan Masalah. b) Mobile robot yang digunakan hanya Lego Mindstorms NXT.
4
c) Pembangunan labirin menggunakan 2 alternatif, yaitu permanen dengan menggunakan papan tipis dan yang kedua dengan menggunakan batu bata yang disusun. d) Pemetaan tree pada robot, dimulai saat robot berjalan. e) Untuk mencari jalan keluar digunakan dua metode yaitu wall follower dan algoritma backtracking.
1.4 Hipotesis Algoritma backtracking akan lebih cepat dalam menyelesaikan kasus labirin yang memiliki tipe perfect maze. Hal ini dikarenakan pada algoritma backtracking mobile robot tidak perlu terus mengikuti dinding seperti pada wall follower, tetapi langsung mencari path terakhir (posisi awal) sebelum kesalahan menggunakan pohon algoritma.
1.5 Tujuan Penelitian Tujuan utama dari Tugas akhir ini adalah membangun sistem kontrol robot yang dapat menyelesaikan masalah labirin secara efektif. Dengan menggunakan dua algoritma yaitu backtracking dan metode wall follower, diharapkan ditemukan salah satu metode yang lebih cepat dan efisien. Secara terperinci mobile robot harus dapat menyelesaikan masalah berikut : a) Melakukan pemetaan terhadap lingkungan disekitarnya dengan menggunakan sensor yang ada pada mobile robot. b) Mobile robot mampu berjalan tanpa menabrak pembatas dikedua sisi robot. c) Menggunakan metode wall follower dan algoritma backtraking untuk menyelesaikan masalah maze tersebut. d) Membandingkan kedua metode yaitu algoritma backtracking dan metode wall follower dengan menggunakan analisis komputasi algoritma Big O.
5
1.6 Metode / Pendekatan Dalam penyusunan tugas akhir ini akan digunakan metodologi berikut ini: a) Studi literatur, dilakukan dengan cara mempelajari literatur-literatur baik yang berupa buku (textbook), jurnal dan artikel ilmiah, maupun website yang berhubungan dengan pembangunan kecerdasan buatan pada robot, khususnya pada Lego Mindstorm NXT. b) Analisis dan Perancangan Robot, yang terdiri dari: a. Membangun prototype mobile robot untuk menyelesaikan masalah maze menggunakan Lego Mindstorm NXT. b. Melakukan pemrograman dengan menggunakan tools RobotC yang memudahkan penulis dalam menganalisa kerja robot dan algoritma yang diterapkan. c) Analisis dan Perancangan Algoritma, dilakukan perancangan algoritma mapping dan path-planning yang sesuai dengan tugas robot yang telah dispesifikasikan. d) Implementasi dan Pengujian Algoritma, dilakukan berdasarkan hasil perancangan algoritma di atas. e) Pengujian Robot, dilakukan dengan men-download program ke dalam
NXT, dengan menggunakan perangkat lunak RobotC. f) Analisis Hasil dan Penarikan Kesimpulan, yaitu dengan memaparkan hasil dari penggunaan algoritma backtracking dan wall follower serta menarik kesimpulan setelah membandingkan kedua metode tersebut dengan komputasi algoritma Big-O.
1.7 Sistematika Penulisan Adapun sistematika penulisan tugas akhir adalah sebahagai berikut : 1. BAB I PENDAHULUAN, berisikan penjelasan mengenai latar belakang rumusan masalah, tujuan, batasan masalah, metodologi, serta sistematika pembahasan yang digunakan untuk menyusun laporan tugas akhir.
6
2. BAB II TINJAUAN PUSTAKA, berisi dasar-dasar teori yang digunakan dalam analisis, perancangan dan implementasi tugas akhir. 3. BAB III ANALISIS DAN PERANCANGAN SISTEM, yang membahas analisis tentang perancangan prototipe robot dengan LEGO NXT, penerapan algoritma backtracking dan metode wall follower kedalam system. 4. BAB IV IMPLEMENTASI DAN ANALISIS SISTEM, yang berisi perancangan prototipe robot dengan LEGO NXT dan implementasi algoritma ke dalam robot menggunakan RobotC serta hasil analisis perbandingan kedua metode yang digunakan yaitu algoritma backtracking dan metode wall follower, dengan menggunakan analisa komputasi algoritma Big-O. 5. BAB V KESIMPULAN DAN SARAN, berisikan kesimpulan dan saran yang didapatkan selama pelaksanaan Tugas Akhir.
7
