5

BAB II

DASAR TEORI

Pada bab ini akan dibahas mengenai beberapa teori yang digunakan sebagai

acuan dan pendukung dalam merealisasikan perancangan sistem pada skripsi ini.

2.1. Kajian Pustaka

a. Penerapan Algoritma Flood Fill untuk Menyelesaikan Maze pada

Line Follower Robot [1]

Pada jurnal ini, penulis merancang sebuah robot line follower

yang dapat berjalan mengikuti garis dengan menerapkan algoritma

flood-fill sebagai algoritma pencarian jalur terpendek di dalam sebuah

labirin yang berbentuk garis. Algoritma flood-fill merupakan suatu

metode pemecahan masalah dimana penyelesaiannya langsung

mengarah ke solusi. Algoritma flood-fill ini memanfaatkan penilaian

tiap sel dimana harus disesuaikan dengan kondisi lapangan (maze) yang

dihadapi.

Berdasarkan hasil pengujian, penulis menyimpulkan bahwa

algoritma flood-fill yang diterapkan pada robot line follower memiliki

tingkat error sebesar 20 % yang disebabkan oleh pengerjaan mekanik

robot yang kurang baik. Namun algoritma ini bisa dikatakan sudah

dapat berjalan dengan tingkat keberhasilan 80 %.

b. Pencarian Jalur Terpendek untuk Robot Micromouse dengan

Menggunakan Algoritma Backtracking [2]

Pada jurnal ini, penulis merancang sebuah robot micromouse

dengan menerapkan algoritma backtracking sebagai algoritma

pencarian jalur terpendek di dalam sebuah labirin. Algoritma

backtracking merupakan suatu metode pemecahan masalah dimana

mencoba setiap kemungkinan yang ada. Hanya penyelesaian yang

6

mengarah ke solusi saja yang akan dikembangkan lebih lagi hingga

dicapainya penyelesaian akhir.

Berdasarkan hasil pengujian, penulis menyimpulkan bahwa robot

micromouse yang dibuat masih belum dapat menjelajahi semua labirin

dengan baik sehingga robot tidak dapat melakukan pemetaan dengan

baik. Hal tersebut disebabkan oleh body robot yang terlalu besar

sehingga membuat robot mengalami kesusahan saat menjelajahi labirin.

2.2. Penerapan Sensor

Dalam menyelesaikan suatu permasalahan di dalam peta labirin, robot

micromouse membutuhkan sensor – sensor tertentu untuk dapat memetakan isi

dari suatu peta labirin. Beberapa sensor penting yang perlu diterapkan di dalam

robot micromouse adalah sensor dinding, sensor penghitung langkah, dan sensor

penunjuk arah. Penjelasan dari sensor – sensor tersebut adalah sebagai berikut :

1. Sensor Dinding

Sensor dinding sangat diperlukan oleh robot micromouse untuk dapat

mendeteksi dinding – dinding labirin. Sensor yang dapat digunakan untuk

mendeteksi adanya dinding labirin adalah sensor cahaya. Pada umumnya,

sensor ini memanfaatkan pantulan cahaya yang dipancarkan melalui

transmitter untuk diterima oleh receiver pada sensor. Proses pemantulan

cahaya pada sensor cahaya dapat dilihat pada Gambar 2.1.

Gambar 2.1. Proses pemantulan cahaya pada sensor cahaya

7

Gambar 2.2. Pengaruh warna objek terhadap pantulan cahaya [3]

Objek yang digunakan sebagai media pemantulan cahaya harus

memiliki warna dasar putih karena warna putih mampu memantulkan

cahaya. Sedangkan objek dengan warna hitam akan menyerap cahaya yang

telah dipancarkan oleh sensor cahaya [3]. Gambar 2.2 menunjukkan

pengaruh warna objek terhadap pantulan cahaya.

Gambar 2.3. Penempatan Sensor Cahaya

Untuk dapat mendeteksi dinding labirin dari berbagai arah, maka

sensor cahaya perlu ditempatkan pada sisi kanan, kiri dan depan robot.

Dengan demikian robot micromouse mampu mendeteksi dinding pada

bagian kanan, kiri dan depan. Gambar 2.3 menunjukkan penempatan sensor

cahaya pada robot.

2. Sensor Penghitung Langkah

Sensor penghitung langkah sangat diperlukan oleh robot micromouse

untuk menentukan seberapa jauh langkah yang akan ditempuh. Sensor yang

8

dapat digunakan untuk menghitung langkah adalah rotary encoder dimana

merupakan sebuah alat elektromagnetik yang dapat memonitor posisi sudut

suatu poros benda berputar. Pada umumnya, rotary encoder menggunakan

sensor optik yang terdiri dari LED dan photo-transistor untuk menghasilkan

serial pulsa. Sensor optik tersebut dipasang diantara suatu piringan tipis

yang memiliki lubang – lubang pada bagian lingkaran piringan. Ketika

piringan tersebut berputar, photo-transistor akan mendeteksi cahaya LED

melalui lubang – lubang pada piringan sehingga menghasilkan suatu pulsa

gelombang persegi melalui squaring circuit [4]. Susunan rotary encoder

dapat dilihat pada Gambar 2.4.

Gambar 2.4. Susunan Rotary Encoder [4]

Banyaknya deretan pulsa yang dihasilkan pada satu putaran inilah

yang akan menentukan akurasi dari suatu rotary encoder. Sehingga semakin

banyak jumlah lubang pada piringan, akan semakin banyak deretan pulsa

yang dihasilkan. Jumlah deretan pulsa ini nantinya akan berpengaruh pada

sistem incremental untuk tiap pulsa yang diproses oleh kontroler untuk

menghitung suatu jarak. Dengan begitu, robot lebih akurat dalam

menentukan langkah yang akan ditempuh.

3. Sensor Penentu Arah

Sensor penunjuk arah sangat diperlukan oleh robot micromouse untuk

menentukan arah hadap di dalam peta labirin. Pada peta labirin terdapat 4

arah yang perlu untuk ditentukan, yaitu : utara, selatan, timur, dan barat.

Sensor penunjuk arah yang dapat digunakan adalah kompas dimana

9

merupakan sebuah alat navigasi untuk menentukan arah yang bebas

menyelaraskan dirinya dengan medan magnet bumi secara akurat. Kompas

itu sendiri terbagi menjadi 2 bagian, yaitu : kompas analog dan kompas

digital. Kompas analog menggunakan jarum atau lempengan besi sebagai

penunjuk arah, sedangkan kompas digital menggunakan komponen –

komponen elektronika seperti sensor magnet dimana telah menggunakan

proses digitalisasi [5].

Gambar 2.5. Penempatan Kompas Digital

Pada umumnya, kompas digital merupakan sensor penunjuk arah yang

paling praktis untuk diterapkan pada robot. Kompas digital mampu

menghasilkan suatu nilai sudut dari arah mata angin yang sangat berguna

untuk dijadikan sebagai acuan penunjuk arah pada robot. Acuan penunjuk

arah tersebut dapat digunakan oleh robot untuk menentukan kapan harus

belok kiri, belok kanan, maju lurus, atau berputar balik di dalam peta labirin.

Kompas digital perlu ditempatkan tepat di tengah – tengah robot seperti

pada Gambar 2.5 sehingga proses penentuan arah hadap pada robot menjadi

lebih akurat.

2.3. Perbandingan Algoritma

Pada dasarnya, kedua algoritma yang diterapkan masing – masing memiliki

kelebihan dan kekurangan tersendiri. Perbandingan antara algoritma flood-fill

dengan algoritma backtracking secara teoritis dapat dilihat pada Tabel 2.1.

10

Tabel 2.1. Perbandingan Algoritma

Sulit untuk diimplementasikan Mudah untuk diimplementasikan

Tidak memerlukan informasi tentang

dinding - dinding labirin sehingga tidak

membutuhkan memori penyimpanan

data tambahan

Membutuhkan memori

penyimpanan data tambahan untuk

menyimpan informasi tentang

dinding - dingin labirin

Proses pencarian langsung

mengarah ke solusi akhir

Proses pencarian mencoba semua

kemungkinan yang ada hingga

ditemukannya solusi akhir

Algoritma Flood-Fill Algoritma Backtracking

Dapat menemukan solusi yang

terbaik di antara banyaknya

kemungkinan yang tersedia

Hanya akan menemukan satu solusi

pada setiap pencarian

Proses pencarian memakan waktu

yang relatif cepat

Proses pencarian memakan waktu yang

cukup lama tergantung dari banyaknya

kemungkinan yang tersedia

2.4. Algoritma Flood-Fill

Algoritma flood-fill merupakan modifikasi dari algoritma bellman-ford

yang memetakan setiap sel di labirin dengan nilai tertentu berdasarkan jaraknya

terhadap tempat tujuan. Algoritma ini dapat dianalogikan seperti membanjiri

suatu labirin dengan air yang banyak. Kemudian air akan terus mengalir ke segala

arah yang tidak terhalang oleh dinding hingga mencapai lantai tempat tujuan. Jalur

yang dilewati oleh tetesan air pertama di tempat tujuan merupakan jalur terpendek

untuk mencapai tempat tujuan tersebut [6].

Algoritma flood-fill melibatkan suatu proses penomoran pada setiap sel

dalam labirin dimana nomor – nomor ini merepresentasikan suatu jarak dari

jumlah sel yang harus ditempuh oleh robot hingga mencapai tujuan. Sel tujuan

akhir yang ingin dicapai diberi nomor 0 dan sel yang berjarak n sel dari tempat

tujuan akhir akan diberi nomor n. Nomor – nomor tersebutlah yang nantinya dapat

digunakan oleh robot dalam proses pencarian jalur terpendek.

11

Berikut adalah tahap – tahap dari algoritma flood-fill, yaitu :

a. Pembangkitan nilai awal untuk masing – masing sel

Nilai awal ditentukan dengan asumsi bahwa terdapat jalur yang saling

menghubungkan antara sel satu dengan sel tetangga lainnya dan masih

belum ada dinding labirin yang menghalangi jalur tersebut. Di sini, hanya

ada 4 arah yang menjadi patokan dalam menghubungkan jalur antar sel,

yaitu utara, selatan, timur dan barat. Proses pembangkitan nilai sel ini

dimulai dari sel tujuan akhir dimana akan bernilai 0, sedangkan sel – sel

tetangga yang terhubung dengan sel tujuan akhir tersebut akan bernilai 1.

Kemudian sel – sel tetangga selanjutnya akan bernilai 2, 3, 4 dan seterusnya

hingga semua sel terisi. Apabila dilihat polanya, setiap sel yang menjauhi

sel tujuan akhir akan memiliki penambahan nilai sebesar satu dari nilai sel

sebelumnya dan itu merepresentasikan jumlah sel yang harus ditempuh

untuk dapat mencapai sel tujuan. Ilustrasi pembangkitan nilai awal dapat

dilihat pada Gambar 2.6.

Gambar 2.6. Ilustrasi pembangkitan nilai awal pada peta labirin 5 x 5 [1]

12

b. Pembaharuan pemetaan dinding

Pada tahap ini, akan dilakukan proses pemetaan dinding berdasarkan

informasi tentang kondisi lapangan. Kondisi lapangan ini mengacu pada

dinding – dinding penghalang dimana tiap – tiap sel memiliki 4 dinding

penghalang di bagian utara, selatan, timur dan barat. Bentuk kondisi

lapangan dapat dilihat pada Gambar 2.7. Dalam hal ini, ketiga sensor robot

akan bekerja sebagai pencari informasi terhadap dinding – dinding labirin

di sekitar robot di dalam suatu sel. Semua informasi mengenai dinding –

dinding labirin tersebut untuk sementara akan disimpan di dalam suatu

array. Kemudian setelah proses pemetaan dinding – dinding labirin

berakhir, semua informasi mengenai dinding labirin di dalam array tersebut

akan disimpan di dalam suatu memori sehingga dapat diakses kapan pun

saat dibutuhkan. Proses pemetaan dinding ini nantinya akan mempengaruhi

nilai – nilai awal pada tiap sel.

Gambar 2.7. Bentuk Kondisi Lapangan

c. Pembaharuan nilai sel

Pada tahap ini, nilai – nilai awal pada tiap sel akan diperbaharui

dengan tujuan untuk menyesuaikan nilai sel terhadap kondisi lapangan yang

ada. Nilai – nilai awal tersebut perlu diperbaharui apabila robot menemukan

13

jalur pada sel terkecil yang dituju terhalang oleh dinding penghalang atau

sel tujuan lain memiliki nilai yang lebih besar dari pada nilai sel robot

berada. Untuk menyesuaikan nilai – nilai sel tersebut, maka nilai sel robot

berada perlu diubah dengan melakukan proses pembangkitan ulang terhadap

nilai – nilai sel tersebut. Ilustrasi proses pembaharuan nilai sel dapat dilihat

pada Gambar 2.8.

Gambar 2.8. Ilustrasi proses pembaharuan nilai sel [1]

Berdasarkan gambar di atas, robot mulai berjalan dari posisi start

menuju sel yang bernilai lebih kecil dari sel robot berada. Proses

pembaharuan nilai sel terjadi saat robot berada pada sel bernilai 2 dimana

jalur pada sel tujuan selanjutnya yang bernilai 1 terhalang oleh dinding pada

bagian timur. Saat itu juga nilai pada sel robot berada berubah menjadi 4

dan robot mulai berbalik arah berjalan menuju sel tujuan yang nilainya lebih

kecil dari sel robot berada. Setelah robot berjalan dan berada pada sel yang

bernilai 1, pada saat itu robot akan menuju sel tujuan yang bernilai 0 pada

bagian utara. Namun karena sel tujuan tersebut terhalang oleh dinding dan

sel tujuan lainnya bernilai 2 dimana lebih besar dari nilai sel robot berada,

dilakukan pembaharuan nilai sel kembali. Saat itu juga nilai sel robot berada

berubah menjadi 3 dan robot dapat melanjutkan perjalanan menuju sel yang

ada di bagian timur yang bernilai 2 dimana lebih kecil dari nilai sel robot

berada. Selanjutnya robot berjalan hingga mencapai finish tanpa ada

pembaharuan nilai sel kembali.

d. Menentukan sel tujuan selanjutnya

Setelah melakukan proses penomoran – penomoran terhadap nilai tiap

– tiap sel, akan ditentukan sel tujuan selanjutnya yang akan menjadi jalur

14

tujuan robot. Proses ini akan membandingkan antara nilai sel robot berada

dengan nilai sel – sel tetangga yang ada di sekitarnya. Sel – sel tetangga

yang memiliki nilai terkecil dari yang lainnya akan menjadi sel tujuan

selanjutnya. Apabila ditemukan lebih dari satu sel terkecil yang sama besar

nilainya, maka akan dipilih sel tujuan yang memiliki jalur lurus / tidak

bebelok sehingga mempercepat proses pencarian jalur terpendek.

e. Bergerak menuju ke arah sel tujuan selanjutnya

Setelah sel yang akan dituju ditentukan, maka robot akan berjalan

sejauh satu sel menuju arah sel tujuan tersebut. Pada proses ini robot akan

melakukan manuver terlebih dahulu kearah sel yang dituju, kemudian

dilanjutkan dengan robot berjalan menuju sel tersebut. Ini adalah tahap akhir

proses dari algoritma flood-fill dan keseluruhan proses ini akan diulang

secara berulang – ulang sampai ditemukannya nilai yang mengindikasikan

sel tujuan akhir.

2.5. Algoritma Backtracking

Algoritma backtracking atau runut-balik merupakan sebuah algoritma yang

secara sistematis mencari solusi persoalan di antara semua kemungkinan yang

ada. Hanya pencarian yang mengarah ke solusi saja yang akan dikembangkan.

Algoritma ini didasarkan pada algoritma Depth-First Search (DFS), sehingga

pencarian solusinya dilakukan dengan cara menelusuri suatu struktur yang

berbentuk pohon berakar secara preorder. Proses ini dicirikan dengan ekspansi

simpul terdalam terlebih dahulu sampai tidak ditemukan lagi suksesor dari suatu

simpul [2]. Struktur pohon akar Depth-First Search dapat dilihat pada Gambar

2.9.

Gambar 2.9. Struktur pohon akar Depth-First Search

15

Berikut adalah prinsip dari pencarian solusi dengan metode runut-balik, yaitu :

Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan

pembentukan yang dipakai adalah mengikuti aturan pencarian mendalam

(DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup (live

node). Simpul hidup yang sedang diperluas dinamakan simpul-E (Expand-

node).

Tiap kali simpul-E diperluas, lintasan yang dibangun olehnya bertambah

panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka

simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node).

Jika pembentukan lintasan berakhir dengan simpul mati, maka proses

pencarian diteruskan dengan membangkitkan simpul anak yang lainnya. Bila

tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi

dilanjutkan dengan melakukan runut-balik ke simpul hidup terdekat (simpul

orangtua). Selanjutnya simpul ini menjadi simpul-E yang baru.

Pencarian dihentikan apabila telah menemukan solusi atau tidak ada lagi

simpul hidup untuk runut-balik.

Gambar 2.10. Ilustrasi proses runut-balik pada peta labirin 5 x 5

Untuk mempermudah proses pencarian solusi, dapat digunakan sebuah

fungsi rekursif dimana secara implisit menyimpan semua langkah. Pertama – tama

16

robot akan menelusuri lorong labirin, ketika menemukan percabangan jalur maka

robot akan memilih salah satu dari jalur yang tersedia. Apabila jalan yang dipilih

ternyata merupakan jalan buntu, maka robot akan melakukan proses runut-balik

ke percabangan tadi dan kemudian memilih jalur yang lainnya. Ilustrasi proses

runu-balik dapat dilihat pada Gambar 2.10. Proses ini tentu saja akan membuat

robot mencoba semua kemungkinan jalur yang ada. Dengan menjelajahi semua

sel dalam labirin, pada akhirnya robot akan dapat menemukan tempat yang dituju

dan mampu menentukan jalur terpendek yang harus dilewatinya.

Gambar 2.11. Pohon solusi proses runut-balik dan pencarian jalur terpendek

Proses tersebut dapat digambarkan melalui pohon solusi yang terlihat pada

Gambar 2.11 dimana simpul – simpul yang berwarna hijau adalah jalur yang

dilewati oleh robot. Jalur buntu yang ditemukan oleh robot dinyatakan pada

simpul berwarna merah dan ditandai dengan angka 0. Tempat tujuan akhir robot

dinyatakan pada simpul berwarna biru. Jalur yang belum dijelajahi dinyatakan

pada simpul berwarna abu – abu dan dapat diabaikan saat robot melakukan proses

pencarian jalur terpendek.