bab ii landasan teori - library & knowledge...
Post on 03-Mar-2019
217 Views
Preview:
TRANSCRIPT
9
BAB II
LANDASAN TEORI
2.1 Dasar Teori
2.1.1 Depth First Search
Depth First Search merupakan metode pencarian dengan cara menelusuri node
yang paling dalam pada sebuah tree. Depth First Search menjelajahi node yang
ditemukan lebih dahulu tanpa melihat bobot masing-masing node. Jika belum
mencapaigoal dan tidak ada node yang lebih dalam lagi, maka akan dilakukan
backtracking menuju node lain yang belum dikunjungi.(Luger,2002 ; Russel et al, 1995,
pp75-81).
PadaDepth First Search, ketika sebuah node ditelusuri, seluruh anak cabang dari
node tersebut akan ditelusuri terlebih dahulu sebelum nodelain yang berada pada tingkat
yang sama ditelusuri.
Pseudocode untuk pencarian dengan Depth First Search adalah sebagaiberikut:
begin open:=[Start]; closed:=[];
while open ≠[]do begin remove leftmost state from open, call it X;
if X is a goal then return(success) else begin
generate children of X; put X on closed; eliminate children of X on open or closed; put remaining children on the left end of open
end end; return(failure)
10
end
Gambar 2.1 Ilustrasi Depth-First Search
Pada gambar 2.1, jika kita ingin menemukan node C maka tahap pencarian adalah
sebagai berikut :
1. open = [A]; closed = []
2. open = [B,C,D]; closed = [A]
3. open = [E,F,C,D]; closed = [A,B]
4. open = [K,L,F,C,D]; closed = [A,B,E]
5. open = [L,F,C,D]; closed = [A,B,E,K]
6. open = [F,C,D]; closed = [A,B,E,K,L]
7. open = [M,C,D]; closed = [A,B,E,K,L,F]
8. open = [C,D]; closed = [A,B,E,K,L,F,M]
9. open = [D]; closed = [A,B,E,K,L,F,M,C]
Setelah node C ditemukan, maka pencarian akan berhenti.
Algoritma Depth First Search yang digunakan pada penelitian ini serupa dengan
Depth First Search yang digunakan pada penelitian "Mobile Robot Navigation Using
11
Depth First Search Algorithm" . Modifikasi tipe-tipe percabangan pada algoritma tersebut
akan dibahas lebih lanjut pada Bab 3 Perancangan Sistem.
2.1.2 PID Programming
PID controller (Proposional Integral Derivatif) adalah sebuah generic controller
yang banyak dipakai pada dunia industri. Sebuah PID controller mencoba untuk
memperbaiki kesalahan antara sebuah nilai proses dan nilai setpoint yang diinginkan
dengan menghitung dan melakukan pembenaran sehingga dapat meminimalkan
kesalahan. (dikutip dari "Mobile Robot Navigation Using Depth First Search Algorithm")
PID controller terdiri dari 3 bagian utama, yaitu : Proportional Controller,
Integral Controller, dan Derivative Controller. Proportional menentukan nilai reaksi
terhadap kesalahan saat ini. Derivatif menentukan nilai perubahan kesalahan yang terjadi
dari kesalahan saat ini dengan kesalahan sebelumnya. Integral menentukan hasil
penjumlahan nilai kesalahan yang terjadi. Hasil nilai dari proses PID ditentukan dengan
rumus (2-1) :
(2-1)
Gambar 2.2 PID Controller
12
Secara diskrit rumus(2-1) dapat ditulis :
en = vdes – vactual (2-2)
Rn = KP· en (2-3)
Rn = Rn–1 + KP · (en – en–1) + KI · (en + en–1)/2 (2-4)
Rn = Rn–1 + KP · (en – en–1) + KI · (en + en–1)/2 + KD · (en - 2·en–1 + en–2) (2-5)
dimana : KP merupakan konstanta proporsional.
KI merupakan konstanta integral.
KD merupakan konstanta derivatif.
en merupakan besarnya nilai error saat ini.
Rn merupakan besarnya nilai output saat ini setelah perhitungan.
Pada umumnya, untuk menentukan nilai KP, KD, KI terdapat 2 metode utama yang
sering digunakan, yaitu :
1. Manual tuning
2. Zieger-Nichols
Pada penelitian ini metode yang dipakai adalah manual tuning. Untuk
memperoleh nilai KP, KI, dan KD yang sesuai, maka dilakukan dengan mengikuti
langkah-langkah berikut :
13
1. Tentukan kecepatan yang diinginkan. Kemudian nol-kan nilai KI dan KD.
Tanpa menggunakan konstanta integral dan derivatif, kemudian perlahan-
lahan naikkan nilai KP hingga terjadi osilasi.
2. Setelah sistem mengalami osilasi, turunkan nilai KP menjadi setengahnya.
3. Naikkan nilai KD sedikit demi sedikit sambil mengubah nilai kecepatan dan
amati responnya. Pilihlah nilai dengan respon yang meredam osilasi.
4. Naikkan nilai KI hingga osilasi terjadi. Kemudian atur nilai KI menjadi
sepertiganya.
Gambar 2.3 Respon Sistem PID
Tabel 2.1 Efek dari nilai komponen PID
Parameter Rise Time Overshoot Setting time Steady State Eror
KP Berkurang Bertambah Berubah sedikit Berkurang
KI Berkurang Bertambah Bertambah Hilang
KD Berubah sedikit Berkurang Berkurang Berubah sedikit
2.1.3 Jenis-jenis Sensor
14
Sensor adalah alat yang berfungsi untuk mengukur besaran fisis dan
mengubahnya menjadi sinyal yang dapat dibaca oleh pengamat atau perangkat elektronik.
Dalam penelitian ini, sensor berfungsi sebagai indera bagi sistem navigasi robot. Berikut
ini adalah jenis-jenis sensor yang digunakan pada penelitian ini :
2.1.3.1 Sensor Ultrasonik
Sensor jenis ini dipakai untuk mengukur jarak.Sensor ini bekerja dengan
memancarkan gelombang suara dengan frekuensi 20-500 KHz. Gelombang ini
dapat merambat pada medium padat, cair, dan gas.
Gambar 2.4 Cara Kerja Sensor Ultrasonik
Jika gelombang yang dipancarkan tersebut mengenai suatu objek, maka
gelombang akan dipantulkan dan diterima kembali oleh sensor. Jarak sensor
dengan objek berbanding lurus dengan jeda waktu yang didapat antara
pemancaran gelombang hingga penerimaan gelombang.
(2-6)
15
Cepat rambat gelombang yang dipancarkan sensor ini sekitar 343.8 m/s
pada suhu 25°C. Cepat rambat gelombang ultrasonik bergantung pada suhu,
tekanan, dan kelembaban medium yang dilaluinya.
Ukuran objek memengaruhi hasil bacaan sensor. Objek yang lebih besar
akan memantulkan lebih banyak gelombang dibanding objek yang berukuran
kecil, sehingga sensor memberikan hasil yang lebih presisi.
Demikian juga dengan objek dari material yang lebih padat. Objek cair
atau lunak seperti kayu atau gabus akan menyerap sebagian dari gelombang yang
dipancarkan, sehingga pantulan yang diterima sensor berkurang.
Di bawah ini adalah sensor ultrasonik yang digunakan pada penelitian ini.
Gambar 2.5Parallax PING Ultrasonik
Gelombang ultrasonik yang dipancarkan berkecepatan sekitar 344 m/s
dengan frekuensi 40 kHz. Selama sensor PING tersebut belum menerima
pantulan, maka sensor tersebut akan terus menunggu terjadinya pantulan hingga
18,5 milidetik lamanya. Lebar pulsa tersebut yang akan digunakan untuk
menghasilkan bacaan jarak antara sensor dengan objek. Apabila setelah melewati
waktu tersebut dan belum terdapat pantulan, maka sensor secara otomatis akan
16
berhenti menunggu dan memulai proses berikutnya.Timing diagram dari sensor
ini terlihat pada gambar 2.6.
Gambar 2.6Timing Diagram Parallax PING
2.1.3.2 Sensor inframerah
Inframerah merupakan salah satu gelombang cahaya yang dapat
diaplikasikan sebagai sensor pengukur jarak, dengan memancarkan sinar
gelombang inframerah dengan panjang gelombang yang lebih panjang daripada
cahaya tampak (400-700 nm), akan tetapi lebih pendek daripada microwaves
(~30,000 µm) yaitu sebesar 750 nm sampai dengan 100 µm.
17
Gambar 2.7 Sensor Inframerah
Prinsip kerja inframerah ini sama dengan sensor ultrasonik, di mana
sensor memancarkan gelombang dan dengan bantuan suatu komponen tambahan
sebagai receiver, menangkap kembali gelombang yang dipantulkan. Dengan
demikian diketahui apakah terdapat objek atau tidak di depan sensor, beserta jarak
sensor terhadap objek.
2.1.3.3 Kompas Digital
Kompas digital adalah komponen yang digunakan untuk mengetahui arah
mata angin.Kompas digital ini memberikan nilai dalam bentuk bilangan biner
dengan acuan kutub magnet bumi untuk menunjukkan arah.
Kompas digital memerlukan kondisi ketinggian dan kemiringan yang
stabil terhadap bumi agar dapat bekerja dengan baik.
Kompas digital yang digunakan adalah CMPS10. CMPS10 dapat
mengurangi error yang dihasilkan akibat kemiringan PCB. Kompas ini
menggunakan 3-axis magnetometer, 3-axis accelerometer, dan prosesor 16-bit.
18
Gambar 2.8 CMPS10
CMPS10 memerlukan supply sebesar 3.3-5.0 volt dengan arus sebesar
25mA.Data output yang dihasilkan berupa data nilai kemiringan terhadap sumbu
x,y dan z yang dapat diakses melalui UART dan I2C. Penelitian ini meggunakan
komunikasi serial I2C untuk mengakses CMPS10.
2.1.3.4 UVTron
Gambar 2.9 UVTron Flame Sensor
UVTron adalah komponen yang berfungsi untuk mendeteksi sinar
ultraviolet menggunakan efek fotolistrik logam dan egek gas multiplication. Pada
penelitian ini, UVTron digunakan untuk mendeteksi api, karena api memancarkan
sinar ultraviolet yang lemah. UVTron jenis ini mampu mendeteksi api hingga
19
jarak lebih kurang 5 meter jauhnya, seperti yang terlampir pada datasheet.
UVTron memiliki sensitivitas spektrum antara 185-260 nm. UVTron
membutuhkan supply 300-350 volt DC power.
Agar UVTron dapat mendeteksi api, dibutuhkan sebuah driving circuit
yang berfungsi untuk menaikkan tegangan dan sekaligus memproses sinyal yang
diterima dari UVTron. UVTrondriving circuit yang digunakan pada penelitian ini
mempunyai seri C3704 produksi Hamamatsu.
Gambar 2.10 UVTron Driving Circuit C3704
Gambar 2.11 UVTron Driving Circuit C3704 Diagram
20
Input sebesar 5 V langsung dihubungkan ke bagian High Voltage DC-DC
Converter karena input sudah konstan. Converter mengubah tegangan 5 V
menjadi 350 V untuk mengaktifkan UVTron Flame Sensor. Sinyal output dari
UVTron Flame Sensor kemudian diproses di bagian Signal Processing Circuit.
Modul akan mengeluarkan output berupa pulsa dengan lebar 10 ms apabila sensor
mendeteksi adanya sinar ultraviolet.
2.1.4 Motor DC
Motor merupakan sebuah perangkat elektromagnetik yang mengubah energi
listrik menjadi energi mekanik. Motor bisa digunakan untuk berbagai macam keperluan,
misalnya dijadikan sebagai kipas angin, blower, menggerakkan lengan robot, hingga
aplikasi yang lebih besar, seperti pemutar baling-baling pada helikopteraeromodelling.
Berdasarkan fungsinya, terdapat beberapa macam motor yang biasa digunakan
pada robot, yaitu motor DC untuk aplikasi yang membutuhkan kecepatan tinggi, motor
stepper untuk aplikasi dengan akurasi tinggi, dan motor servo untuk gerakan-gerakan
berupa gerakan sudut. Aktuator pada penelitian ini adalah sebuah motor DC (direct
current), yang berperan sebagai bagian pelaksana dari perintah-perintah yang diberikan
oleh otak robot atau main controller.
Sebuah motor sederhana memiliki 6 bagian, yaitu :
1. Rotor
2. Stator
3. Brushes
21
4. Axle
5. Field magnet
Sebuah motor elektrik mengandung magnetdan magnetism. Sebuah motor
menggunakan magnetuntuk menghasilkan gerakan. Pada magnet, jika berbeda kutub
maka ada saling tarik menarik sedangkan jika bertemu kutub yang sama akan saling tolak
menolak.
Gambar 2.12 Bagian dari motor elektrik
Mekanisme kerja untuk seluruh jenis motor listrik secara umum sama, yaitu:
• Arus listrik dalam medan magnet akan memberikan gaya.
• Jika kawat yang membawa arus dibengkokkan menjadi sebuah
lingkaran/loop, maka kedua sisi loop, yaitu pada sudut kanan medan magnet,
akan mendapatkan gaya pada arah yang berlawanan.
• Pasangan gaya menghasilkan tenaga putar/torsi untuk memutar kumparan.
22
Motor-motor memiliki beberapa loop pada dinamonya untuk memberikan tenaga
putaran yang lebih seragam dan medan magnetnya dihasilkan oleh susunan
elektromagnetik yang disebut kumparan medan.
2.1.5 Driver(H-Bridge)
Rangkaian H-bridge ini berfungsi sebagai penguat arus dan mengatur arah
jalannya arus. Pada gambar 2.13akan memperlihatkan bagaimana H-bridge dapat
mengontrol jalannya arus.
Gambar 2.13 Ilustrasi H-bridge
H-bridge sederhana tersusun atas 4 transistoryang berfungsi sebagai saklar di
mana transistorakan aktif jika basis transistormendapatkan arus dan tegangan yang
cukup. Saklar inilah yang akan mengatur jalannya arus dari VCC menuju ground.
H-bridge memiliki duainput, jika ada tegangan pada in1 atau in2 maka input yang
mendapat tegangan akan berlogika1 dan sebaliknya, jika tidak mendapatkan tegangan
pada kedua input maka in1danin2akan berlogika0. Dengan 2 inputan tersebut, maka kita
23
dapat menggabungkaninput yang diterima menjadi empat buah kombinasi sebagai berikut
:
Tabel 2.2 Kondisi motor berdasarkan H- Bridge
In1 In2 Kondisi
0 0 Motor tidak berputar
0 1 Motor berputar
1 0 Motor berputar
1 1 Motor tidak berputar
Jika in1 dan in2 berlogika 1, motor tidak berputar, namun kondisi seperti ini
berbahaya, karena pada kondisi tersebut semua transistor berada dalam keadaan aktif
sehingga seakan-akan pada rangkaian H-bridge itu terjadi short-circuit antara VCC ke
ground. Hal ini dapat merusak rangkaian karena arus yang mengalir cukup besar.
2.2 Penelitian Sebelumnya
Penelitian dengan judul Mobile Robot Navigation Using Depth First Search
Algorithm yang dilakukan pada tahun 2010 berhasil membangun sebuah fire-fighting
robot dengan platform RP5 yang berbentuk persegi dan menggunakan tracked wheel.
Driver yang digunakan adalah TB6612FNG.
24
Gambar 2.14Platform RP5
Jenis sensor yang digunakan pada penelitian tersebut sama dengan sensor yang
dipakai pada penelitian ini, yang telah dibahas pada subbab 2.1.3, yaitu sensor jarak
ultrasonik, sensor inframerah, fotodiode, kompas digital, UVTron, dan sensor garis.
Algoritma eksplorasi track yang digunakan adalah Depth First Search, dengan
pemodelan tree yang dihasilkan dari pembacaan sensor. Robot menggunakan controller
AVR ATMega128.
Hasil percobaan kecepatan robot mendeteksi api pada penelitian tersebut adalah
sebagai berikut.
Gambar 2.15 Grafik Rata-rata Waktu Deteksi Api Lilin
25
Gambar 2.16 Grafik Rata-rata Waktu Deteksi dan Pemadaman Api Lilin
Gambar 2.17 Grafik Rata-rata Waktu Penyelesaian Misi
26
Gambar 2.18Grafik Persentase Keberhasilan Penyelesaian Misi
2.3 Penelitian Saat Ini
Pada penelitian ini kami memberikan beberapa perbaikan, di antaranya dengan
menggunakan algoritma Median Filter dan Modified Line Maze Algortihm.
2.3.1 Median Filter
Median pada statistika adalah istilah yang mengacu pada sebuah nilai yang berada
di tengah-tengah sekumpulan data. Median merupakan nilai yang memisahkan setengah
dari jumlah data yang memiliki nilai terendah dengan setengah dari jumlah data dengan
nilai tertinggi pada sekumpulan data yang ada.
Nilai median diperoleh dengan mengurutkan data dari yang memiliki nilai terkecil
hingga terbesar, dan kemudian mengambil data yang berada pada urutan tepat ditengah.
Jika jumlah data genap sehingga tidak memiliki data yang berada tepat di tengah, maka
median diambil dari nilai rata-rata dua data yang berada di tengah.
Misalkan sekumpulan data acak seperti yang terlihat pada Tabel 2.3 :
Tabel 2.3 Data Acak
10 20 30 22 8 101 45 67 92 33
Untuk mencari nilai mediannya, nilai data tersebut perlu diurutkan terlebih
dahulumenjadi seperti Tabel 2.4:
Tabel 2.4 Data Hasil Sorting
8 10 20 22 30 33 45 67 92 101
27
Karena jumlah data genap, nilai mediannya adalah nilai rata-rata dari data ke-lima
dan ke-enam, yaitu 30 dan 33. Nilai rata-rata dari kedua data tersebut adalah (30+33)/2 =
31,5.
Median filter adalah filter yang mengambil nilai median dari sekumpulan data
sebagai hasil filter. Data spike menyebabkan robot berasumsi terjadi percabangan
meskipun sebenarnya robot masih berada di lorong. Median filter dapat mengeliminasi
kesalahan pemodelan tree yang disebabkan adanya data spike. Karena median
filtermengambil nilai tengah, maka data spike yang berada pada setengah nilai data
tertinggi tidak digunakan.
2.3.2 Modified Line Maze Algorithm
Sebuah robot maze solver memiliki kemampuan untuk menentukan rute terdekat
dari garis start untuk mencapai garis finish. Pada penjelajahan pertama, robot
mengeksplorasi track untuk menemukan rute terdekat tersebut. Setelah mencapai garis
finish, robot dapat kembali ke posisistart dengan rute terdekat yang sudah dikalkulasi.
Gambar 2.19 Line Maze
28
Untuk dapat menemukan garis finish robot mengeksplorasi maze menggunakan
Left Hand Rule atau Right Hand Rule. Selama perjalanan, robot mencatat setiap
pergerakan yang telahdilakukan, seperti ‘turn right’, ‘turn left’, ‘straight’, atau ‘turn
back’. Setelah menemukan garis finish, robot melakukan subtitusi pada pergerakan-
pergerakan tersebut sehingga diperoleh rute yang paling dekat.
Gambar 2.20 Ilustrasi Modified Line Maze Algorithm
Pada ilustrasigambar 2.20, dengan menggunakan Left Hand Rule, robot akan
berjalan lurus ketika mencapai percabangan pertama. Robot kemudian mencatat bahwa ia
29
telah berjalan ‘straight’ (S). Kemudian robot menemui jalan buntu dan mencatat
pergerakan berikutnya yaitu ‘turn back’ (U). Setelah itu robot berbelok ke kiri dan
mencatat ‘turn left’ (L). Robot kemudian mensubtitusi rute (SUL) dengan rute yang lebih
singkat (R) dan demikian seterusnya hingga mencapai garis finish.
Straight – U-turn – Left → Right
Gambar 2.21 Line Maze Solving
Algoritma ini akan berjalan dengan baik sebatas pada maze yang tidak memiliki
loop. Karena track KRCI memiliki loop, maka harus ditambahkan aturan
tambahan pada algoritma ini. Pembahasan selengkapnya akan dilakukan pada Bab
3 Perancangan Sistem.
top related