MOBILE ROBOT NAVIGATION USING DEPTH FIRST SEARCH ALGORITHM

MOBILE ROBOT NAVIGATION USING DEPTH FIRST SEARCH ALGORITHM Frederick1; Fredy Shuwanto2; Stefen3; Wiedjaja4 3

Jurusan Sistem Komputer, Fakultas Ilmu Komputer, BINUS University, Jln.KH.Syahdan No.9, Kemanggisan/Palmerah, Jakarta Barat 11480 [email protected]

ABSTRACT This research is based on national competition KRCI (Intelligent Robot Contest Indonesia), in which the robot can perform exploration track, look for candles in track and extinguish the candle. In this study focuses on the development of robot algorithms, where the algorithm is a depth-first search. The study also discusses the sensors are used; this is because the sensor as the robot senses. The sensors are IR sensor ranger, PING, UVTron, photodiode, sound activation, and compass. Tests conducted robots, there are 3 phases: testing of sensors, mobile robotic testing, testing the entire system. Results of the study showed that the movement of robots is strongly influenced by the value of the proximity sensor; the introduction of the nodes on the track is also influenced by the proximity sensor. The success rate in exploration robot track and extinguish the candle is 85%. Robot requires an algorithm to estimate sensor data error. Exploration algorithm tracks the robot needs to be developed by using fuzzy logic, neural network or genetic algorithm. Keyword: mobile robot, navigation system, depth-first search, sensor

ABSTRAK Penelitian ini berdasarkan kompetisi nasional KRCI (Kontes Robot Cerdas Indonesia), di mana robot dapat melakukan ekplorasi track, mencari lilin yang ada di track dan memadamkan lilin tersebut. Pada penelitian ini difokuskan pada pengembangan algoritma robot, di mana algoritma yang dipakai adalah depth-first search. Penelitian juga membahas sensor-sensor yang dipakai, hal ini dikarenakan sensor sebagai indra pada robot. Sensor-sensor yang dipakai adalah sensor IR ranger, PING, UV TRON, photodioda, sound activation, kompas. Pengujian robot yang dilakukan terdapat 3 tahap yaitu : pengujian terhadap sensor, pengujian mobile robot, pengujian keseluruhan sistem. Hasil dari penelitian menunjukkan bahwa pergerakan robot sangat dipengaruhi oleh nilai dari sensor jarak, pengenalan node pada track juga dipengaruhi oleh sensor jarak. Tingkat keberhasilan robot dalam melakukan eksplorasi track dan memadamkan lilin adalah 85%. Robot memerlukan suatu algoritma untuk melakukan perkiraan kesalahan data sensor. Algoritma ekplorasi track pada robot perlu dikembangkan dengan menggunakan fuzzy logic, neural network ataupun algoritma genetic. Kata kunci : Mobile robot, sistem navigasi, depth-first search, sensor

Mobile Robot Navigation… (Frederick)

11

PENDAHULUAN Autonomous dan semi-autonomous mobile robot telah menjadi pusat perhatian pada beberapa tahun ini, hal ini dikarenakan autonomous robot memegang peranan penting pada beberapa aplikasi seperti pertanian, petambangan, eksplorasi luar angkasa, kesehatan dan robot servis serta misi militer. Sebuah autonomous robot memiliki kemampuan untuk mendapatkan informasi terhadap lingkungan sekitar, dapat bekerja sendiri tanpa campur tangan manusia. Salah satu masalah utama dari autonomous robot adalah pengetahuan tentang lingkungan, di mana robot tidak dapat mengetahui keadaan lingkungan sekitar. Robot autonomous untuk dapat mengetahui lingkungan sekitar memerlukan sensor sebagai indera bagi robot. Robot dapat mengetahui lingkungan sekitar dibantu dengan adanya data dari sensor sehingga robot dapat mengambil keputusan bagaimana harus bertindak. Kontes Robot Indonesia (KRI) dan Kontes Robot Cerdas Indonesia (KRCI) adalah salah satu contoh kompetisi robot yang paling bergengsi di Indonesia yang diadakan setiap tahun. Juara nasional KRI dan KRCI akan menjadi wakil Indonesia di ajang kontes robot internasional AsiaPasifik Broadcasting (ABU) ROBOCON, di mana untuk tahun 2010 akan diadakan di Egypt. Untuk KRCI, dibagi menjadi beberapa divisi untuk robot berkaki dan robot beroda yang mempunyai misi yang berbeda- beda, seperti menjelajahi track dan memadamkan lilin. Berdasarkan informasi tersebut maka diputuskan untuk membuat robot beroda (wheeled robot) yang sesuai dengan kriteria KRCI. Robot yang dimaksud adalah robot yang dapat mengetahui jarak, bergerak dengan roda, menjelajahi track yang sudah ditentukan, dapat mendeteksi api, mematikan lilin api, dan balik ke home. Pada penelitian ini berpusat pada algoritma dari robot di mana robot akan ditempatkan pada track yang telah ditentukan. Track yang digunakan adalah track yang dipakai pada KRCI 2009. Penelitian ini mencoba algoritma yang cocok untuk robot agar robot dapat mengitari seluruh track dari KRCI. Target dari robot adalah mematikan lilin yang tidak ditentukan letaknya dan robot dapat kembali ke tempat awal robot memulai perjalanan setelah menemukan dan mematikan lilin.

PEMBAHASAN Depth-First Search (DFS) Depth-first search adalah sebuah teknik pencarian dengan menelusuri titik yang terdalam dari sebuah tree. Teknik depth-first search (DFS) mengunjungi seluruh leaf pada tree yang ada terlebih dahulu tanpa melihat bobot yang ada pada masing-masing leaf. Setelah leaf pada bagian tertentu telah dikunjungi dan belum mendapatkan goal maka akan dilakukan backtracking menuju leaf lainnya yang belum dikunjungi, seperti pada Gambar 1.

Gambar 1 Teknik pencarian depth-first search

12

Jurnal Teknik Komputer Vol. 18 No.1 Februari 2010: 11- 18

Algoritma DFS akan menggambarkan kondisi track berdasarkan percabangan yang dilalui menjadi sebuah tree. Posisi root dimulai pada titik home yang terdapat pada track, di mana mobile robot memulai penjelajahannya. Pada gambar 2 menunjukkan track serta percabangan yang ada. Track tersebut mempunyai empat ruangan yang berbeda ukurannya. Masing-masing ruangan diberi label R1, R2,R3 dan R4. Posisi home terdapat pada titik H pada gambar 2. Mobile robot akan menghadapai sebanyak tujuh node untuk menjelajahi keseluruhan track tersebut dari root atau home.

Gambar 2 Track yang dijelajahi mobile robot

Gambar 3 Tree pada track

Platform Robot Platform robot menentukan bentuk robot, mekanik, jumlah roda atau kaki yang digunakan, bahan yang digunakan untuk platform. Platform yang akan digunakan pada penelitian ini adalah produk keluaran dari pololu robotics & electronics yaitu RP5 yang berbentuk persegi dan menggunakan tracked-wheel. Platform robot ini terbuat dari plastik dan berwarna abu-abu gelap dengan dikontrol oleh dua motor. Platform tersebut mempunyai spesifikasi dan ukuran panjang 18 cm dengan lebar 14 cm dan tinggi 6 cm. Berat platform dengan motor adalah 425 gram.

(a)

(b)

Gambar 4 (a) Mobile robot tampak samping (b) Mobile robot tampak depan

Motor Motor berfungsi untuk menggerakkan robot tersebut. Motor terbagi menjadi beberapa jenis yang mempunyai kelebihan dan kekurangan masing-masing tergantung pemakaian. Motor yang dipakai di mobile robot ini adalah motor DC dengan spesifikasi 7.2 volt, 210mA pada kondisi tanpa beban dan pada kondisi puncak akan menggunakan arus maksimal 2.4 A. Motor DC ini


13

merupakan bawaan dari platform yang dipakai. Motor DC ini menggunakan driver motor TB6612FNG.

Sensor Sensor merupakan komponen yang digunakan untuk melakukan sense terhadap lingkungan sekitar robot. Sensor memiliki banyak jenis tergantung fungi-fungsinya. Fungsi-fungsi sensor antara lain, dapat berguna untuk mengetahui jarak, mengukur tingkat kelembaban, mengukur suhu, mendeteksi obyek atau garis dan lain sebagainya. Komponen sensor sangat penting untuk mobile robot. Sensor yang digunakan pada mobile robot ini yaitu: (1) Kompas, digunakan untuk mengetahui arah dan perputaran daripada mobile robot; (2) IR ranger, sensor pengukur jarak yang digunakan pada mobile robot ini dengan memanfaatkan inframerah; (3) PING Ultrasonik, sensor pengukur jarak yang digunakan pada mobile robot yang bekerja dengan ultrasonik; (4) Photodioda, untuk mengetahui arah api; (5) UVTron, sensor yang mendeteksi sinar UV yang dihasilkan oleh lilin; (6) Sensor Garis, untuk mengetahui apakah terdapat ruangan atau tidak, serta lingkaran home dan lingkaran api. Sensor garis ini memanfaatkan inframerah dan photodioda.

Controller Pada mobile robot, program dari algoritma yang digunakan akan ditampung pada sebuah controller. Controller yang digunakan disini adalah produk Atmel, yaitu AVR ATMEGA128.

Tipe-tipe Node Penggambaran tree oleh mobile robot dilakukan dengan terlebih dahulu dikenalkan tipetipe percabangan yang terdapat pada track yang akan dilalui mobile robot.

Gambar 5 Jenis-jenis node yang ada pada track: (a) Tipe 1 (b) Tipe 2 (c) Tipe 3 (d) Tipe 4 (e) Tipe 5 (f) Tipe 6

Node atau tipe percabangan ini dapat dikenali dengan menggunakan sensor jarak yang berupa PING ultrasonik dan IR ranger. Sensor A yang merupakan sensor PING yang terletak di bagian depan mobile robot untuk mengecek jalur yang terdapat di depan mobile robot. Sensor kanan dan sensor kiri menggunakan sensor jarak IR Ranger yang diberi labe sensor C untuk sensor sebelah kanan dan sensor D untuk sensor sebelah kiri. Tabel 1 Ilustrasi cara sensor jarak mengenali tipe percabangan A(sensor depan) 0 1 0 1 0 1

14

C(sensor kanan) 0 0 1 1 0 1

D(sensor kiri) 1 1 0 0 0 1

Tipe Node 1 2 3 4 5 6


Diagram alir Algoritma Robot

Gambar 6 Diagram Alir Algoritma Mobile Robot

Gambar 6 merupakan diagram alir dari robot, menggambarkan robot memulai penjelajahan track dari home sampai dengan menemukan lilin pada salah satu ruangan track dan mematikan api dari lilin tersebut, kemudian kembali ke home. Pada awalnya robot mulai menjelajahi lorong (maze) dari track dengan bantuan dari sensor jarak sebagai indra penglihatan. Pada robot terdapat 3 sensor utama yang digunakan untuk menentukan tipe dari percabangan yaitu sensor depan (sensor A), sensor kanan (sensor D), dan sensor kiri (sensor C). Sensor-sensor tersebut akan terus mengecek apakah terdapat percabangan atau tidak. Jika terdapat percabangan, maka robot akan


15

berhenti dan melakukan pengecekan tipe percabangan. Setelah tipe percabangan telah ditentukan, maka robot dapat melakukan aksi dari tipe percabangan tersebut. Robot akan bergerak kembali, diikuti dengan pengecekan garis. Jika tidak terdapat garis, maka robot akan kembali melakukan penelusuran track. Jika terdapat garis, maka robot telah memasuki pintu salah satu ruangan. Sebelum melakukan penelusuran terhadap suatu ruangan, robot melakukan pengecekan api terlebih dahulu. Jika tidak terdapat api dalam ruangan, maka robot keluar dari ruangan, sedangkan jika terdapat api dalam ruangan maka robot akan mendekati api tersebut dan mulai memadamkan api. Setelah api telah dipadamkan, robot akan keluar dari ruangan dan tidak melanjutkan penelusuran track, akan tetapi langsung kembali ke home.

Hasil Percobaan Percobaan pertama tanpa menggunakan api lilin pada track, data yang dicatat adalah waktu yang dibutuhkan untuk mencapai setiap ruangan pada track, waktu yang dibutuhkan untuk kembali ke home dan status keberhasilan mobile robot dan keterangan status yang diperoleh. Pengujian ini diulang sebanyak 10 kali. Data percobaan diperlihatkan dalam rata-rata waktu yang diperlukan untuk eksplorasi track tanpa api lilin dan tingkat keberhasilan ada pada gambar 7.

Gambar 7 (a) Grafik rata-rata waktu eksplorasi track tanpa api lilin (b) Presentase keberhasilan eksplorasi track tanpa api lilin

Tingkat keberhasilan ini dilihat dari eksplorasi mobile robot mencapai tiap ruangan. Persentase keberhasilan pada ruangan keempat tidak maksimal dikarenakan garis ruangan tidak terdeteksi oleh robot. Percobaan berikutnya merupakan percobaan dengan memberikan satu api lilin pada salah satu ruangan secara acak. Untuk setiap ruangan dilakukan perulangan sebanyak lima kali dengan posisi lilin yang sama. Data yang diperoleh adalah waktu yang dibutuhkan mobile robot untuk mencapai, mendeteksi dan memadamkan api lilin tersebut dan kembali ke home. Data yang diperoleh juga dapat dilihat tingkat keberhasilan mobile robot untuk menyelesaikan tugasnya. Rata-rata waktu yang diperlukan untuk eksplorasi dan memadamkan api lilin dapat dilihat pada grafik gambar 8a. Tingkat keberhasilan mobile robot memadamkan api dan kembali ke home dapat dilihat pada grafik Gambar 8b.

Gambar 8 (a) Grafik rata-rata waktu yang dibutuhkan untuk eksplorasi track dan memadamkan api lilin (b) Presentase keberhasilan eksplorasi track, mematikan api lilin dan balik ke home

16


Tingkat keberhasilan tidak mencapai 100% keberhasilan dikarenakan garis ruangan yang tidak terdeteksi, adanya pengenalan node yang salah dan tidak terdeteksi adanya api pada ruangan.

Gambar 9 Grafik perbandingan rata-rata waktu untuk kondisi ada dan tanpa api lilin

Gambar 10 Grafik perbandingan presentasi keberhasilan untuk kondisi ada dan tanpa api lilin

PENUTUP Dari hasil penelitian yang telah dilakukan maka dapat disimpulkan, bahwa kegagalan mobile robot dalam eksplorasi track dapat dikarenakan kesalahan pengenalan node oleh mobile robot dapat terjadi, posisi api terkadang masil gagal untuk dideteksi. Waktu yang dapat dicapai oleh mobile robot dapat dipengaruhi oleh jarak api lilin terhadap home, lamanya mobile robot mendeteksi api lilin dalam suatu ruangan dan lamanya mobile robot melakukan pemadaman api lilin. Kinerja sensor jarak yang terkadang kurang stabil yang mengakibatkan kontroller menerima data yang kurang tepat. Kerja sensor yang kurang stabil ini disebabkan karena ada posisi-posisi tertentu di mana jarak mobile robot terhadap dinding yang terlalu dekat sehingga melebihi batas minimum jarak di mana sensor dapat bekerja dengan baik. Hal ini mengakibatkan data dari sensor menjadi tidak akurat. Peletakan objek di depan api mengakibatkan api tidak dapat terdeteksi oleh sensor UVTron. Hal ini disebabkan karena pemberian sudut pendeteksian api yang kecil pada UVTron untuk memperoleh posisi api yang tepat. Waktu tercepat yang dapat dicapai mobile robot untuk menyelesaikan tugas yaitu 58 detik (ruangan 1). Waktu terlama yang dapat dicapai mobile robot untuk menyelesaikan tugas yaitu 178 detik (ruangan 4).


17

Untuk penelitian lebih lanjut diharapkan adanya pengembangan algoritma dalam memproses data dari sensor agar kesalahan dalam pendeteksian node dapat diperkecil. Adanya pengembangan teknik untuk memfokuskan sudut dari UVTron sehingga mobile robot dapat mendeteksi posisi api lilin dengan baik dan adanya pengembangan algoritma eksplorasi track dengan menggunakan fuzzy logic, genetic algorithm atau dengan metode flood-fill sehingga waktu yang dapat dicapai dan tingkat keberhasilan menjadi lebih baik.

DAFTAR PUSTAKA Ahlgren D.J. (2001). Fire-Fighting Robots and First Year Engineering Design: Trinity College Experience, Proc.31st ASEE/IEEE Frontiers in Education Conference, 2001, S2E-6, pp 1-6 vol3 Dept. of Eng., Trinity Coll., Hartford, CT. Braunstingl, R.; Sanz, Pedro; Ezkerra, Jose Manuel (1995), Fuzzy Logic Wall Following of a Mobile Robot Based on The Concept of General Perception. Clark, R., El-Osery, A., Wedeward, K., & Bruder, S. (2004). A Navigation and Obstacle Avoidance Algorithm for Mobile Robots Operating in Unknown, Maze-Type Environments. Intelligent Systems and Robotics Group, New Mexico. Cinthya H.S, Cecilia; Susanto, Rudy; Sungkono, Alvin (2005), Pengembangan Sistem Navigasi Dengan Umpan Balik Pada Mobile Robot, BINUS University, Jakarta. Luger, George F(2002), Artificial Intelligence Structures And Strategies for Complex Problem Solving Fourth Edition, Pearson Addison Wesley, England. Mulianto, Budiyanto; Rahardjo,Valentinus(2006), Integrasi dan Evaluasi Sistem Navigasi Menggunakan Pattern Recognition pada Mobile Robot, BINUS University, Jakarta. Noborio, H; Yamamoto, I; Komaki, T (2000), Sensor-Based Path-Planning Algorithms for a Nonholomic Mobile Robot, Proc.2000 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp917-924 vol.2, Dept.Engineering Informatics, Osaka ElectroCommunication Univ, Japan Luo, R.C.; Lin, T.Y.; Hsu, T.Y.; Wang, P.K. (2005), Multisensor Controlled Obstacle Avoidance and navigation of Intelligent Security Robot, Industrial Electronics Society, 2005. IECON 2005, 31st Annual Conference of IEEE, pp6, Dept.of Electr. Eng., Nat. Chung Cheng Univ., Ming-Hsuing, Taiwan. Russel, Stuart; Norvig, Peter(2003), Artificial Intelligence : A Modern Approach Second Edition, Prentice Hall, USA. Tong Feng; Xu LuFeng; Tong Daoling (2002), An Ultrasonic Obstacle Avoidance System for Fire Fighting Robot, Intelligent Control and Automation 2002, Proc.4th IEEE World Congress, pp1219-122 vol2, Dept. of Radio Eng., Southeast Univ., Nanjing.

18


MOBILE ROBOT NAVIGATION USING DEPTH FIRST SEARCH ALGORITHM

Recommend Documents