BAB II TINJAUAN PUSTAKA
2.1
Simulasi Simulasi adalah proses implementasi model menjadi program komputer
(software) atau rangkaian elektronik dan mengeksekusi software tersebut sedemikian rupa sehingga perilakunya menirukan atau menyerupai sistem nyata tertentu untuk tujuan mempelajari perilaku sistem, pelatihan atau permainan yang melibatkan sistem nyata (realitas). Simulasi merupakan suatu metode eksperimental dan terpakai untuk menjelaskan
perilaku
sistem,
membangun
teori
atau
hipotesis
yang
mempertanggungjawabkan perilaku dari sistem yang diamati, memakai teori-teori untuk meramalkan perilaku sistem yang akan datang, yaitu pengaruh yang akan dihasilkan oleh perubahan-perubahan variabel dan parameter sistem atau perubahan operasinya. Tujuan simulasi adalah untuk pelatihan (training), studi perilaku sistem (behaviour), dan hiburan/permainan (game). Berdasarkan perangkat keras yang digunakan, ada tiga jenis simulasi, yaitu: a. Simulasi Analog adalah simulasi yang implementasinya menggunakan rangkaian elektronika analog, seperti op-amp (operational amplifier) untuk integrasi,
pembanding,
pembalik,
7
penjumlah,
dan
lain-lain.
8
b. Simulasi Digital adalah simulasi yang implementasinya menggunakan komputer digital. c. Simulasi Hybrid adalah simulasi yang implementasinya menggunakan gabungan rangkaian elektronika analog dan komputer digital.
Berdasarkan waktu, simulasi dibedakan menjadi dua, yaitu: a. Simulasi waktu nyata (real-time) adalah simulasi dimana definisi waktu simulasi adalah sama dengan waktu nyata yang ditunjukkan pada jarum (clock) pada umumnya. b. Simulasi offline adalah simulasi dimana definisi waktu simulasi adalah tidak sama (diskalakan) dengan waktu nyata, bisa dipercepat bisa diperlambat.
2.2
Artificial Intelligence Artificial Intelligence (AI) atau kecerdasan buatan merupakan cabang dari
ilmu komputer yang berhubungan dengan otomatisasi tingkah laku cerdas. AI dapat dipandang dari beberapa perspektif, yaitu : a. Perspektif kecerdasan b. Perspektif bisnis c. Perspektif pemrograman d. Perspektif penelitian
9
Aplikasi penggunaan AI dapat dibagi ke dalam tiga kelompok, yaitu: a.
Mundane task Secara harafiah, arti mundane adalah keduniaan. Jadi, AI digunakan untuk melakukan hal-hal yang sifatnya duniawi untuk melakukan kegiatan yang dapat membantu manusia. Contohnya: 1. Persepsi (vision & speech) 2. Bahasa alami (understanding, generation dan translation) 3. Pemikiran yang bersifat common sense 4. Robot control
b. Formal task AI digunakan untuk melakukan tugas-tugas formal yang selama ini manusia biasa lakukan dengan lebih baik. Contohnya: 1. Permainan/game 2. Matematika (geometri, logika, kalkulus, integral, pembuktian) c. Expert task AI dibentuk berdasarkan pengalaman dan pengetahuan yang dimiliki oleh para ahli. Penggunaan ini dapat membantu para ahli untuk dapat menyampaikan ilmu-ilmu yang mereka miliki. Contohnya: 1. Analisis finansial 2. Analisis medical 3. Analisis ilmu pengetahuan 4. Rekayasa (desain, pencarian, kegagalan, perencanaan, manufaktur)
10
Aplikasi AI memiliki dua bagian utama, yaitu: a.
Basis Pengetahuan (knowledge base) yang berisi fakta-fakta, teori, pemikiran dan hubungan antara satu dengan lainnya.
b.
Motor Inferensi (inference engine) yang berisi kemampuan menarik kesimpulan berdasarkan pengalaman.
Gambar 2. 1 Aplikasi Artificial Intelligence
2.3
Teknik Dasar Pencarian Pencarian
atau
pelacakan
merupakan
salah
satu
teknik
untuk
menyelesaikan permasalahan AI. Keberhasilan suatu sistem, salah satunya ditentukan oleh kesuksesan dalam pencarian dan pencocokan. Teknik dasar pencarian memberikan suatu kunci bagi banyak sejarah penyelesaian yang penting dalam bidang AI. Ada beberapa aplikasi yang menggunakan teknik pencarian ini, yaitu: a. Papan game dan puzzle (tic-tac-toe, catur, menara hanoi) b. Penjadwalan dan masalah routing (travelling salesman problem) c. Parsing bahasa dan interpretasinya (pencarian struktur dan arti) d. Logika pemrograman (pencarian fakta dan implikasinya) e. Computer vision dan pengenalan pola f. Sistem pakar berbasis kaidah (rule based expert system)
11
Pencarian adalah proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Ruang keadaaan merupakan suatu ruang yang berisi semua keadaan yang mungkin.
Kondisi suatu pencarian meliputi: a. Keadaan sekarang atau awal. b. Keadaan tujuan-solusi yang dijangkau dan perlu diperiksa apakah telah mencapai sasaran. c. Biaya atau nilai yang diperoleh dari solusi.
Solusi merupakan suatu lintasan dari keadaan awal sampai keadaan tujuan. Secara umum, proses pencarian dapat dilakukan seperti berikut: a. Memeriksa keadaan sekarang atau awal. b. Mengeksekusi aksi yang diperbolehkan untuk memindahkan ke keadaan berikutnya. c. Memeriksa jika keadaan baru merupakan solusi. Jika tidak, keadaan baru tersebut menjadi keadaan sekarang dan proses ini diulangi sampai solusi ditemukan atau ruang keadaan habis terpakai.
12
2.4
Algoritma Pencarian Metode Pencarian
Pencarian Buta
Breadth First Search
Pencarian Terbimbing
Best First Search
Uniform Cost Search Greedy Search Depth First Search Depth Limited Search
A* (A Star) Search
Iterative Deepening Search
Hill Climbing Search
Bidirectional Search
Gambar 2. 2 Metode Pencarian
Terdapat banyak metode pencarian yang telah diusulkan. Berbagai metode yang ada dapat dibedakan ke dalam dua jenis, yaitu Pencarian Buta (blind search) dan Pencarian Terbimbing (heuristic search)
2.4.1 Pencarian Buta (blind search) Pencarian Buta adalah metode pencarian solusi yang tidak memiliki informasi awal untuk mengarahkan pencarian dalam mencapai goal state atau current state (keadaan sekarang). Informasi yang ada hanyalah definisi goal state itu sendiri, sehingga algoritma dapat mengenali goal state bila menjumpainya. Tanpa adanya informasi, maka Pencarian Buta memeriksa node-node secara tidak terarah dan kurang efisien untuk kebanyakan kasus karena banyaknya node yang dikembangkan.
13
Beberapa algoritma yang termasuk Pencarian Buta, antara lain adalah Breadth First Search, Uniform Cost Search, Depth First Search, Depth Limited Search, Iterative Deepening Search, dan Bidirectional Search.
2.4.2 Pencarian Terbimbing (heuristic search) Pencarian Terbimbing adalah metode pencarian yang mempunyai informasi awal tentang cost atau biaya dalam mencapai goal state dari current state. Dengan informasi tersebut, pencarian ini dapat melakukan pertimbangan untuk mengembangkan atau memeriksa node-node yang mengarah ke goal state sehingga secara umum, Pencarian Terbimbing lebih efisien daripada blind search. Beberapa contoh algoritma pencarian yang menggunaan metode ini adalah Best First Search, Greedy Search, A* (A Star) Search, dan Hill Climbing Search.
14
2.5
Maze Maze adalah sesuatu yang sangat rumit dan berbelit-belit. Dalam
kehidupan sehari-hari, Maze dan labirin (labyrinth) seringkali dianggap sama, yaitu sebagai jalan yang kompleks dan membingungkan. Namun, secara teknis, maze dibedakan dari labirin. Labirin memiliki sebuah rute yang berliku tetapi tidak memiliki cabang dan tidak dirancang untuk navigasi yang rumit. Sedangkan Maze memiliki jalur yang bercabang dengan tingkat kerumitan yang lebih tinggi. Dalam prakteknya, maze dapat dibangun dengan dinding dan ruangan, pagar, rumput, batang jagung, jerami, buku, batu warna-warni, batu-bata, rumput atau bidang tanaman seperti gandum atau jagung. Jalur dan dinding yang ada pada maze atau labirin telah ditentukan sebelumnya. Ada banyak jenis dari Maze, diantaranya Standard Maze, Loops and Traps Maze, Block Maze, Number Maze, Picture Maze, dan Turf Mazes and Mizmazes.
Gambar 2. 3 Maze
2.6
Algoritma Maze Solving Maze Solving adalah tindakan mencari rute untuk melalui maze dari awal
sampai akhir. Beberapa metode penyelesaian maze dirancang untuk digunakan di dalam labirin tanpa pengetahuan sebelumnya tentang maze tersebut, sedangkan
15
yang lainnya dirancang untuk digunakan setelah mengetahui bentuk keseluruhan dari maze. Maze yang tidak mengandung perulangan disebut sebagai standard maze atau perfect maze dan ekivalen dengan tree pada teori graf. Karena itulah, maka banyak algoritma maze solving yang berkaitan erat dengan teori graf. Secara intuitif, sebuah maze dapat didefinisikan sebagai sebuah pohon (tree). Ada beberapa algoritma maze solving yang berbeda yang secara otomatis menyelesaikan maze, diantaranya: a. Random Mouse Random
Mouse
adalah
metode
sederhana
yang
dapat
diimplementasikan oleh robot yang tidak cerdas atau bahkan seekor tikus sekalipun. Metode ini, secara sederhana mengikuti jalur yang ada sampai menemukan persimpangan. Pilihan atas persimpangan yang ada diputuskan secara acak. Meskipun secara teoritis, metode tersebut pasti menemukan solusi, ada juga kemungkinan bahwa metode ini tidak mendapatkan solusi apapun. Karena dapat melalui jalur yang sama beberapa kali, metode ini sangatlah lambat. b. Wall Follower adalah metode yang paling terkenal dalam penyelesaian maze. Metode ini juga dikenal dengan aturan tangan kiri (left-hand rule) atau aturan tangan kanan (right-hand rule). Jika maze secara sederhana dihubungkan, sehingga semua dindingnya terkoneksi satu sama lain, maka dengan menjaga satu tangan dengan kontak terhadap salah satu
16
dinding maze, akan ditemukan ujung keluar, atau jika tidak ada, akan berakhir kembali ke jalan masuk. Hal ini dimungkinkan karena apabila semua dinding tersambung, maka akan terbentuk sebuah loop atau lingkaran. Dengan kata lain, ketika mengikuti seluruh dinding, lingkaran tersebut akan menunjukkan jalur dari start ke finish (kondisi untuk algoritma ini ditampilkan pada lampiran). Namun hal ini tidak akan berfungsi dengan baik ketika maze yang dilalui adalah maze yang kompleks. Bahkan metode ini tidak menjamin ditemukannya goal yang berada di bagian tengah lapangan. c. Pledge Algoritma ini dirancang untuk menyelesaikan maze dengan start yang berada di dalam maze. Arah menjadi faktor utama dalam penyelesaian maze dengan algoritma ini karena pendeteksian jalur yang salah diatasi dengan penghitungan arah. Hal ini memungkinkan penyelesaian sebuah maze oleh seorang pemain yang menggunakan kompas dan ingin keluar dari dalam maze. Namun tidak dapat digunakan untuk arah sebaliknya, ketika pemain tersebut mulai dari luar maze dan ingin mencapai goal yang berada di dalam maze. d. Trémaux Algoritma yang ditemukan oleh Charles Pierre Tremaux ini, merupakan metode yang efisien untuk menemukan jalan keluar dari suatu maze. Metode ini dilakukan dengan menggambar garis pada
17
lantai jalur. Semua maze yang telah terdefinisi sebelumnya pasti bisa diselesaikan oleh algoritma ini. Sebuah jalur yang ada dalam sebuah maze, dapat didefinisikan menjadi tiga, yaitu belum dilewati, ditandai satu kali, dan ditandai dua kali. Setiap kali arah dipilih, maka sebuah garis juga digambar di lantai. Di simpang awal, arah dipilih secara acak. Ketika melalui sebuah simpang yang belum pernah dilalui sebelumnya, pilihlah arah secara acak dan tandai jalur tersebut. Ketika menemukan simpang yang bertanda (sudah pernah dilewati) dan tanda yang ditemukan hanya satu, maka kembalilah ke arah sebelumnya dan tandai jalur untuk kedua kalinya. Selain itu, jika menemukan simpang bertanda lebih dari satu, pilih arah dengan tanda yang paling sedikit. Ketika akhirnya solusi dicapai, maka jalur bertanda satu akan menjadi penunjuk jalur pulang ke start. Ketika tidak ada jalan keluar, maka algoritma ini akan membawa kembali ke start ketika semua jalur sudah ditandai dua kali. Setiap jalur akan dilalui tepat dua kali dengan arah yang berbeda. Jalur yang dihasilkan disebut juga Bidirectional Double Tracing (kondisi untuk algoritma ini ditampilkan pada lampiran). e. Dead-End Filling Algoritma ini menyelesaikan maze yang sudah diketahui jalurnya secara keseluruhan. Metode ini dapat digunakan untuk soal maze di kertas atau program komputer, tetapi tidak berguna untuk pemain yang berada di dalam maze yang tidak diketahui polanya. Metode ini dilakukan dengan menemukan seluruh jalan buntu dalam maze dan
18
kemudian mengisi jalur dari setiap jalan buntu sampai simpang pertama ditemukan. Algoritma ini tidak dapat tiba-tiba memotong jalan dari start ke finish karena setiap langkah dari proses mempertahankan topologi dari maze. Pada maze sempurna, setelah algoritma ini selesai dijalankan, akan tersisa jalur langsung dari start ke finish. Sedangkan, pada maze yang memiliki beberapa loop, salah satu jalur yang mungkin dilalui akan tersisa. f. Shortest Path Ketika sebuah maze memiliki banyak solusi, mungkin saja yang diinginkan adalah jalur terpendek dari start ke finish. Algoritma ini menemukan jalur tercepat dengan mengimplementasikan Breadth First search. Hal ini dilakukan dengan menggunakan antrian untuk mengunjungi setiap sel dengan nilai yang berubah dari start ke finish. Setiap sel yang ditemui harus menyimpan nilai jarak dari start atau mengubah nilai karena sel-sel di dekatnya yang bertambah. Ketika lokasi finish ditemukan, jalur pulang ke start sudah dapat terlihat sebagai jalur terpendek.
Dari keseluruhan algoritma tersebut, algoritma Random Mouse, Wall Follower, Pledge dan Trémaux dirancang untuk digunakan tanpa pengetahuan tentang maze. Sementara itu, Dead-End Filling dan Shortest
Path dirancang untuk
menyelesaikan maze yang secara keseluruhan sudah diketahui.
19
2.7
Maze Solving Robot Maze Solving Robot adalah robot yang dibuat untuk menyelesaikan
sebuah maze. Lintasan yang dilalui oleh robot ini dapat berupa garis maupun ruangan yang dibatasi oleh dinding. Ukuran, bentuk dan spesifikasi robot disesuaikan dengan kasus dari maze yang akan diselesaikan.
2.8
Pertandingan Internasional Maze Solving Robot Ada beberapa pertandingan tingkat internasional yang mempertandingkan
Maze Solving Robot, diantaranya yaitu: a. IEEE Micromouse competition IEEE (Institute of Electrical and Electronic Engineers) merupakan sebuah asosiasi yang didedikasikan untuk peningkatan inovasi dan teknologi sehingga bermanfaat bagi manusia. Asosiasi ini dibentuk untuk melayani para profesional yang terlibat dalam semua aspek bidang listrik, elektronik, komputasi dan area yang berhubungan dengan sains dan teknologi yang mendasari peradaban modern. Akar IEEE berawal dari tahun 1884 ketika listrik baru menjadi kekuatan utama dalam masyarakat. Terutama ketika terdapat suatu industri, telegraf, yang menghubungkan dunia dengan sistem komunikasi yang lebih cepat dari transportasi. Area lainnya adalah Tenaga Listrik (power) dan Cahaya yang berasal dari penemuanpenemuan Thomas Alfa Edison dan perintisannya di Pearl Smazet Station di New York.
20
IEEE Micromouse Competition diadakan sekitar bulan April di setiap tahunnya. Kompetisi ini terdiri dari design contest, paper contest dan Micromouse. Peserta yang akan mengikuti kompetisi ini, baik secara individu maupun kelompok, harus terlebih dulu terdaftar sebagai anggota dari IEEE. b. RoboGames RoboGames yang awalnya bernama ROBOlympics telah berkembang menjadi kompetisi robot terbuka yang terbesar di dunia (menurut Guinness Book of World Records). Kompetisi yang dipelopori oleh David Calkins pada tahun 2004 ini, sekarang telah memiliki sekitar 70 kategori perlombaan yang berbedabeda, dengan dua pertiganya adalah pertandingan untuk autonomous robot dan sisanya untuk robot yang dikendalikan dari jarak jauh (dengan remote control). Kategori yang ada terdiri dari Humanoids, Auton Humanoid Challenges, Sumo, Bot Hockey, Combat, Robot Soccer, Junior League, Autonomous Autos, Tetsujin, Art Bots, BEAM, dan Open. Dalam pertandingan ini, Maze/Micromouse merupakan autonomous robot di dalam kategori Open. Pada tahun 2010, peserta dari 39 negara telah berpartisipasi dalam pertandingan ini dan terus mengikutinya sebagai salah satu kesempatan untuk mengembangkan teknologi baru dan menantang diri sebagai seorang engineer. RoboGames juga menyediakan demo noncompetitive dan perbincangan dengan para perancang robot industri dan engineer dari seluruh dunia.
21
Ada 5 tujuan utama dari RoboGames : 1. Menyediakan sarana bagi para pembangun robot untuk saling bertukar pikiran, baik mengenai pembuatan robot, ilmu-ilmu teknis lainnya, maupun budaya dari masing-masing negara. 2. Menyediakan pertandingan yang tidak membedakan peserta amatir dan profesional. Siapapun dapat ikut bertanding di acara ini, tanpa memandang usia, pendidikan, afiliasi, negara asal, jenis kelamin, maupun disiplin akademis. Hal ini dilakukan karena banyak pertandingan robot yang ada hanya diperbolehkan untuk diikuti oleh para mahasiswa dan kalangan akademis lainnya. 3. Menunjukkan
kepada
masyarakat
berbagai
robot
yang
dipertandingkan karena jarang sekali ada pertandingan robot yang menarik bagi masyarakat umum. 4. Memberikan pengakuan dan penghargaan kepada para pembangun robot. Para pemenang di pertandingan ini akan mendapatkan banyak hal, mulai dari medali sampai penghargaan dari kepala negara masing-masing. 5. Mendukung pendidikan di luar ruangan. Selain sebagai penonton, anak-anak juga dapat bertanding dalam kategori Junior League. Pertandingan tingkat umum juga dapat dilihat dengan bebas sehingga dapat dijadikan pelajaran dan semangat untuk menciptakan karya masing-masing.
22
2.9
Matrix Laboratory (MATLAB) MATLAB (Matrix Laboratory) adalah suatu bahasa tingkat tinggi yang
digunakan untuk komputasi teknik. Bahasa ini mengintegrasikan proses komputasi, visualisasi, dan pemrograman dengan environment yang mudah digunakan dengan mengekspresikan masalah dan solusi ke dalam notasi-notasi matematika. Kegunaan umum dari MATLAB diantaranya untuk Matematika dan Komputasi, Pengembangan Algoritma, Akuisisi Data, Pemodelan dan Simulasi, Pembuatan Prototipe, Analisis Data, Eksplorasi, Visualisasi, dan Pengembangan Aplikasi termasuk GUI. MATLAB adalah sebuah sistem interaktif yang elemen data dasarnya adalah
array
yang
tidak
membutuhkan
pengaturan
dimensi.
Hal
ini
memungkinkan penyelesaian banyak masalah komputasi teknik, terutama yang berhubungan dengan formulasi matriks dan vektor. Dalam beberapa kasus, dapat juga dilakukan penulisan program dalam bahasa seperti C dan Fortran. Nama MATLAB merupakan singkatan dari Matrix Laboratory. Awalnya, MATLAB dibuat untuk menyediakan akses yang mudah untuk pengembangan software matriks dalam proyek LINPACK dan EISPACK. Saat ini, MATLAB menggabungkan LAPACK dan BLAS library untuk komputasi matriks. Di lingkungan universitas, MATLAB digunakan sebagai alat pembelajaran standar untuk tahap pengenalan dan lanjut dalam matematika, teknik dan sains. Dalam industri, MATLAB adalah salah satu alat yang dapat dipilih untuk penelitian, pengembangan dan analisis.
23
MATLAB juga memiliki fungsi toolbox yang memungkinkan pengguna untuk belajar dan menerapkan teknologi khusus seperti pemrosesan sinyal, sistem kontrol, jaringan saraf, logika fuzzy, simulasi dan banyak teknologi lainnya.
2.9.1 Lingkungan Kerja Matlab Ketika memulai MATLAB, desktop MATLAB akan ditampilkan sepaket dengan Graphical User Interface yang dapat digunakan untuk mengatur file, variabel, dan aplikasi yang akan diolah dengan menggunakan MATLAB.
Gambar 2. 4 Desktop MATLAB
Komponen-komponen yang disediakan oleh MATLAB, antara lain Command Window, Command History, Start Button dan Launch Pad, Help Browser, Current Directory Browser, Workspace Browser, Array Editor, Editor/Debugger, dan Profiler.
