IKO42360 ROBOTIKA - GENAP 2010/2011 LAPORAN TUGAS PENGGANTI UTS
Fukushi Fighter
Oleh: Adrianto Santoso
(1205000126)
Fahri Nurul Hidayat
(0706271701)
Faris Al Afif
(0706271733)
M Iqbal Tawakal
(0706271954)
FAKULTAS ILMU KOMPUTER UNIVERSITAS INDONESIA 2011
DAFTAR ISI
BAB I PENDAHULUAN ........................................................................................................................ 4 1.1. Latar Belakang ........................................................................................................................ 4 1.2. Rumusan Masalah................................................................................................................... 4 BAB II STUDI LITERATUR .................................................................................................................... 6 2.1. Locomotion............................................................................................................................. 6 2.1.1. Wheel .............................................................................................................................. 6 2.1.1.1. Roda Standar................................................................................................................. 6 2.1.1.2. Roda Castor................................................................................................................... 7 2.2. Sensor..................................................................................................................................... 7 2.2.1. Sensor Ultrasonik ............................................................................................................. 8 2.2.2. Sensor Warna................................................................................................................... 8 2.2.3. Sensor Sentuh .................................................................................................................. 8 2.2.3. Sensor Suara .................................................................................................................... 9 BAB III METODE RISET ..................................................................................................................... 10 3.1. Spesifikasi Robot ................................................................................................................... 10 3.1.1. Robot Hayate ................................................................................................................. 10 3.1.1. Robot Kazetora .............................................................................................................. 10 3.2. Skenario................................................................................................................................ 11 3.2.1. Skenario 1 (menggunakan Arena Pertama) ..................................................................... 11 3.2.2. Skenario 2 (menggunakan Arena Kedua) ........................................................................ 12 3.2.3. Skenario 3 (Penambahan Sensor Suara) ......................................................................... 13 BAB IV HASIL EKSPERIMEN .............................................................................................................. 14 4.1. Navigasi Robot ...................................................................................................................... 14 4.1.1. Gerakan Maju ................................................................................................................ 14 4.1.2. Fungsi-fungsi Pengecekan dalam Navigasi ...................................................................... 15 4.1.3. Pembacaan Garis dan Persimpangan .............................................................................. 16 4.1.4. Pendeteksian Posisi Tujuan ............................................................................................ 16 4.1.5. Mendeteksi Suara yang Cukup Keras .............................................................................. 17 4.2. Maze Mapping ...................................................................................................................... 18 4.3. Shortest Path ........................................................................................................................ 18 2
4.4. Communication .................................................................................................................... 18 4.4.1. Menemukan Device ....................................................................................................... 19 4.4.2. Inisiasi Sambungan Antar Device .................................................................................... 20 4.4.3. Menyiapkan Pertukaran Data Antar Device .................................................................... 20 4.4.4. Kazetora Menunggu Sambungan dari Hayate ................................................................. 21 4.4.4. Hayate Mengirimkan Data ke Kazetora ........................................................................... 21 4.4.5. Kazetora Menerima Sambungan dari Hayate .................................................................. 22 4.4.6. Kazetora Menerima Data dari Hayate ............................................................................. 22 4.5. Hasil Eksperimen................................................................................................................... 24 4.5.1. Hasil Eksperimen I .......................................................................................................... 24 4.5.2. Hasil Eksperimen II ......................................................................................................... 30 4.5.3. Hasil Eksperimen III ........................................................................................................ 36 BAB V KESIMPULAN ......................................................................................................................... 38 5.1. Kesimpulan ........................................................................................................................... 38 DAFTAR PUSTAKA ............................................................................................................................ 39 LAMPIRAN ....................................................................................................................................... 40 1. Ouput Hasil Running Program untuk Arena Pertama ................................................................ 40 2. Ouput Hasil Running Program Untuk Arena Kedua ................................................................... 50
3
BAB I PENDAHULUAN
1.1. Latar Belakang Jepang mengalami bencana hebat di kuarter awal tahun 2011 ini. Dimulai dari gempa besar dengan skala 9.1 richter, gempa terbesar yang menimpa Jepang setelah The Great Kanto Earthquake tahun 1930. Gempa ini mengakibatkan dua bencana susulan. Yang pertama adalah Tsunami setinggi 10 meter yang menghempas sebelah timur Jepang, dan kemudian kebocoran pembangkit nuklir Fukushima yang mengancam kesehatan pekerja dan masyarakat yang tinggal di sekitarnya. Untuk mengatasi permasalahan nuklir di Fukushima, maka akan diturunkan sebuah tim robot bernama Fukushi Fighter yang terdiri dari 2 buah robot. Robot pertama, yaitu Robot Hayate (疾風 ), berfungsi untuk menjelajahi beberapa kemungkinan jalur menuju tempat kebocoran yang kemudian menentukan jalur terpendek dan kemudian menyampaikan informasi ini ke robot kedua. Robot kedua, yaitu Robot Kazetora (風虎), berfungsi menerima informasi penting dari robot pertama sehingga bisa menuju tempat kebocoran dengan tepat dan cepat. Penjelajahan jalur-jalur menuju tempat tujuan dilkakukan dengan menggunakan Algoritma Maze Mapping dan pencarian jalur terpendek dilakukan dengan menggunakan Algoritma Shortest Path. Kedua robot menggunakan komponen Lego Mindstorm NXTTM. Komunikasi antara dua robot menggunakan protokol bluetooth yang tersedia di Lego Mindstorm NXT.
1.2. Rumusan Masalah Beberapa hal yang dibahas dalam laporan ini adalah sebagai berikut. 1. Bagaimana penerapan Algoritma Maze Mapping dan Shortest Path serta komunikasi antar robot menggunakan bluetooth pada Lego Mindstorm NXT?
4
2. Berapa lama waktu yang dibutuhkan oleh Hayate dan Kazetora ketika berkomunikasi menggunakan bluetooth? 3. Berapa rata-rata waktu tempuh setiap jalur untuk Robot Hayate? 4. Berapa rata-rata waktu tempuh setiap jalur untuk Robot Kazetora? 5. Bagaimana perbandingan waktu tempuh untuk setiap jalur tanpa pengecekan persimpangan dengan jika melakukan pengecekan persimpangan?
5
BAB II STUDI LITERATUR
2.1. Locomotion Sebuah mobile robot membutuhkan mekanisme locomotion untuk bergerak dan menjelajahi lingkungannya. Ada dua mekanisme utama locomotion pada robot. Yang pertama adalah legged (kaki) dan yang kedua menggunakan wheel (roda). Robot yang menggunakan kaki memiliki degree of freedom yang lebih tinggi dibandingkan dengan yang menggunakan roda. Namun implementasi robot yang mampu bergerak dengan kaki memiliki tingkat kesulitan yang jauh lebih tinggi daripada roda. Oleh karena itu, roda menjadi lebih populer dan menjadi pilihan untuk tugas kali ini. 2.1.1. Wheel Locomotion dengan roda adalah mekanisme locomotion paling populer di bidang mobile robots. Kelebihannya dibandingkan alternatif lain (kaki) adalah dengan roda kita tidak perlu memusingkan masalah keseimbangan karena roda memang didesain agar terus menyentuh tanah. Dengan roda bisa dicapai efisiensi dalam pergerakan dengan menggunakan implementasi mekanikal yang sederhana. 2.1.1.1. Roda Standar
6
Roda standar memiliki 2 degree of freedom. 2.1.1.2. Roda Castor
Roda Castor juga memiliki 2 degree of freedom, namun terdapat gerakan tambahan berupa rotasi pada sambungannya dengan badan utama robot.
2.2. Sensor Salah satu hal kemampuan penting yang harus dimiliki Autonomous Mobile Robot adalah kemampuan untuk mendeteksi lingkungannya. Hal ini bisa dilakukan dengan perangkat yang bernama sensor. Sensor dapat digolongkan ke dalam 2 kelompok besar, yaitu Proprioceptive/Exteroceptive dan Passive/Active Sensor. Proprioceptive sensor adalah sensor yang mendeteksi atau mengukur keadaan internal dari robot, seperti suhu prosesor, isi baterai, kecepatan motor, ataupun seperti sensor gyroscope yang mengukur keseimbangan robot berdasarkan kemiringannya. Exteroceptive sensor adalah sensor yang mendapatkan informasinya dari lingkungan sekitar robot, seperti jarak, cahaya, ataupun suara. Passive sensor adalah sensor yang mengukur energi yang masuk ke sensor dari lingkungan sekitar. Contohnya seperti temperatur, kamera, atau bahkan nuklir. Active sensor adalah sensor yang mengirimkan energi ke lingkungan dan kemudian mengukur reaksi dari lingkungan terhadap energi yang diberikan. Karena bisa mempunyai interaksi lebih, sensor 7
tipe aktif memiliki kelebihan dibanding sensor yang sekedar pasif. Namun hal ini juga bisa memberikan kerugian seperti apabila energi yang dikirimkan justru mengganggu apa yang ingin dideteksi, atau jika menggunakan robot lebih dari satu, energi dari robot yang satu bisa merusak hasil perhitungan robot yang satunya. Setiap sensor memiliki beberapa properti masing-masing lainnya yang penting untuk diketahui. 2.2.1. Sensor Ultrasonik
Sensor ultrasonic adalah sensor yang bersifat exteroceptive dan aktif. Sensor ultrasonik mengeluarkan gelombang ultrasonik yang memiliki frekuensi diantara 40 dan 80 kHz. Sensor ultrasonik ini mampu mengukur jarak 0 sampai dengan 255 centimeter dengan ketelitian +/3 centimeter. 2.2.2. Sensor Warna
Sensor warna adalah sensor yang bersifat exteroceptive dan aktif. Sensor ini dapat membaca intensitas cahaya di suatu ruangan dan mengukur intensitas cahaya dari permukaan yang warnanya berbeda. Sensor ini memiliki peran yang penting dalam mendeteksi garis yang diikuti dan mendeteksi persimpangan. 2.2.3. Sensor Sentuh
8
Sensor sentuh bersifat exteroceptive dan pasif. Sensor ini menerima rangsangan fisik berupa sentuhan dari suatu objek. Ketika sensor ini menerima sentuhan/tekanan, maka tombol yang berada di sensor ini akan tertekan, kemudian sensor ini akan mengirimkan impuls ke dalam NXT Brick. 2.2.3. Sensor Suara
Sensor ini bersifat exteroceptive dan pasif. Sensor ini menangkap suara dari lingkungan. Sensor suara mengukur tingkat volume pada skala 0 (tidak ada suara) hingga 100 (suara sangat keras). Sensor suara memungkinkan dapat mengukur tingkat kebisingan dalam satuan dB (desibel) dan dBA (frekuensi sekitar 3-6 kHz dimana telinga manusia berada pada kondisi paling sensitif), serta mengenali pola suara dan mengidentifikasi perbedaan nada.
9
BAB III METODE RISET
3.1. Spesifikasi Robot 3.1.1. Robot Hayate Robot Hayate menggunakan 3 buah roda, yaitu terdiri dari 2 roda yang terhubung dengan aktuator motor dan 1 roda bebas bertipe castor. Robot menggunakan 4 buah sensor, yaitu sensor warna RGB, sensor sentuhan, sensor suara, dan sensor ultrasonik. Sensor warna RGB digunakan untuk mengikuti garis dan mendeteksi persimpangan, sensor sentuhan digunakan untuk aktivasi robot, dan sensor ultrasonik digunakan untuk mendeteksi posisi akhir. Sensor suara digunakan pada salah satu skenario, yaitu untuk mendeteksi suara yang akan membuat robot berhenti sejenak selama beberapa detik dan setelah itu robot kembali melanjutkan perjalananannya. Berikut adalah gambar Robot Hayate.
3.1.1. Robot Kazetora Robot Kazetora juga menggunakan 3 buah roda, yaitu terdiri dari 2 roda yang terhubung dengan aktuator motor dan 1 roda bebas bertipe castor. Robot menggunakan 2 buah sensor, yaitu sensor warna RGB dan sensor suara. Sensor warna RGB digunakan untuk mengikuti garis dan mendeteksi persimpangan. Sensor suara digunakan pada salah satu skenario, yaitu untuk mendeteksi suara yang akan membuat robot berhenti sejenak selama
10
beberapa detik dan setelah itu robot kembali melanjutkan perjalananannya. Berikut adalah gambar Robot Kazetora.
3.2. Skenario 3.2.1. Skenario 1 (menggunakan Arena Pertama) Tampilan dari arena pertama yang memiliki ukuran 7 x 5 satuan dapat dilihat pada gambar berikut.
Cara menyimpan data suatu jalur adalah dengan merepresentasikan jalur sebagai tiga buah titik yang berurutan, dalam hal ini 3 buah titik yang memiliki nilai yang sama. Misalnya pemberian nilai 1 jika titik tersebut jalur dan nilai 0 jika tidak terdapat jalur. Sehingga urutan 11
angka 1 1 1 menandakan ada jalur dan 1 0 1 menandakan tidak ada jalur. Maka, representasi dari arena tersebut setelah Robot menjelajahi semua titik akan seperti matriks di bawah ini. 1110100 1010100 1111111 0010000 1110000 3.2.2. Skenario 2 (menggunakan Arena Kedua) Tampilan dari arena kedua yang memiliki ukuran 9 x 7 satuan dapat dilihat pada gambar berikut.
Sama seperti arena pertama, cara menyimpan data suatu jalur adalah dengan merepresentasikan jalur sebagai tiga buah titik yang berurutan yang memiliki nilai yang sama. Nilai 1 diberikan jika titik tersebut jalur dan nilai 0 diberikan jika tidak terdapat jalur. Maka, representasi dari arena tersebut setelah Robot menjelajahi semua titik akan seperti matriks di bawah ini. 101110111 101000101 111111101 001000101 111011110 100000100 100011100 12
3.2.3. Skenario 3 (Penambahan Sensor Suara) Skenario 3 dapat menggunakan arena pertama maupun arena kedua, dan dapat dilakukan pada Robot Hayate maupun Kazetora. Pada skenario ini menambahkan penggunaan sensor suara. Ketika robot Hayate atau Kazetora sedang berjalan dan tiba-tiba mendeteksi tingkat suara yang lebih tinggi dari yang ditentukan, robot akan berhenti selama beberapa detik, dan setelah itu akan kembali meneruskan perjalanan. Skenario ini menggambarkan situasi nyata ketika tim yang sedang melakukan perjalanan menuju tempat bencana lalu ada gempa susulan (terdengar suara alarm) maka tim akan berhenti sejenak dan akan melanjutkan perjalanan kembali setelah tidak ada lagi gempa susulan.
13
BAB IV HASIL EKSPERIMEN
4.1. Navigasi Robot 4.1.1. Gerakan Maju Potongan kode program untuk gerakan maju adalah sebagai berikut. public void robot_forward() { int error=0; boolean searchIntersection = true; while(searchIntersection) { while ( isLine() ) { LCD.drawString("isLine LCD.refresh(); pilot.forward(); } while ( isOutside() ) { LCD.drawString("isOutside LCD.refresh();
", 0, 0);
", 0, 0);
error = 5; pilot.rotate(error); if (isOutside()) { error = error * -2; pilot.rotate(error); } } while( isIntersection() ) { LCD.drawString("isIntersection", 0, 0); LCD.refresh(); searchIntersection = false; } } pilot.travel(5); } 14
Gerakan maju ini akan terhenti ketika robot sampai di suatu persimpangan, karena nilai searchIntersection menjadi false dan program akan keluar dari loop while. Jika robot sedikit keluar dari garis maka isOutside() akan menghasilkan nilai true yang membuat robot melakukan koreksi posisi untuk kembali bisa berjalan mengikuti garis.
4.1.2. Fungsi-fungsi Pengecekan dalam Navigasi Potongan kode program untuk pengecekan-pengecekan dalam navigasi robot adalah sebagai berikut. private boolean isOutside() { return readColor() == 6; } private boolean isLine() { int colorVal=0; colorVal = readColor(); return (colorVal!=6 && colorVal!=5) ; } private boolean isIntersection() { return readColor() == 5; } private boolean isFinish() { int i = 0, nearCounter = 0; boolean finish = false; for(i=0; i<4; i++) { if( isNear() ) { nearCounter++; } } if( nearCounter>=2 ) { finish = true; } return finish; }
15
Fungsi isOutside() akan mengembalikan nilai true ketika Robot berada di atas area yang bukan garis dan bukan persimpangan, yaitu diwakili oleh area berwarna putih pada arena. Fungsi isLine() akan mengembalikan nilai true jika Robot berada di atas garis yang berwarna hitam, yang merupakan jalur utama yang dilewati robot. Fungsi isIntersection() akan mengembalikan nilai true jika Robot berada di persimpangan, yaitu di atas tanda persegi berwarna merah. Fungsi isFinish()mengembalikan nilai true jika Robot telah mencapai posisi finish, yaitu posisi yang di atas areanya ditutupi oleh suatu objek sebagai atap sehingga fungsi isNear() telah bernilai true.
4.1.3. Pembacaan Garis dan Persimpangan Potongan kode program untuk pembacaan area di bawah robot adalah sebagai berikut. public int readColor() { int colorVal=0; colorVal = cs.readValue(); return colorVal; // BLACK: 1, RED: 5, WHITE: 6 } Fungsi readColor() mengembalikan nilai integer yang mengidentifikasi di atas area apa robot
berada. Nilai 1 menandakan robot berada di atas area berwarna hitam (garis), nilai 5 menandakan robot berada di atas area berwarna merah (persimpangan), dan nilai 6 menandakan robot berada di atas area berwarna putih (bukan di garis dan bukan di persimpangan).
4.1.4. Pendeteksian Posisi Tujuan Potongan kode program untuk pendeteksian posisi tujuan adalah sebagai berikut. private boolean isNear() { int distance; distance = ultra.getDistance(); boolean near = false;
16
if(distance<30) { near = true; } return near; } Fungsi ini bertujuan untuk mengetahui apakah Robot sudah berada pada posisi tujuan atau tidak. Fungsi isNear() mengembalikan nilai true jika robot sudah mencapai posisi tujuan. Posisi
tujuan dikenali dengan cara area tersebut ditutupi oleh suatu objek sebagai atap sehingga hasil pembacaan jarak yang dipancarkan ke arah atas akan menghasilkan nilai yang kecil (jaraknya dekat).
4.1.5. Mendeteksi Suara yang Cukup Keras
Potongan kode program untuk mendeteksi suara yang cukup keras adalah sebagai berikut. private boolean isLoud() { int loudness; loudness = sound.readValue(); boolean loud = false; LCD.drawInt(loudness, 0, 2); LCD.refresh(); if(loudness>65) { loud = true; } return loud; } Fungsi isLoud() akan mengembalikan nilai true ketika kondisi di sekitar robot cukup bising,
dalam hal ini robot mendeteksi tingkat kebisingan di atas nilai 65%.
17
4.2. Maze Mapping Penjelajahan jalur-jalur pada maze menggunakan Algoritma Maze Mapping. Cara yang digunakan adalah dengan menentukan prinsip pemilihan jalur ke kanan. Algoritma ini menyatakan dengan selalu belok ke kanan di setiap persimpangan, maka jika maze tersebut terkoneksi seluruhnya dan memiliki solusi, maka suatu saat pasti akan sampai kepada solusi. Data kondisi ketersediaan jalur di arah kanan, kiri dan depan akan disimpan oleh Robot. Data yang tersimpan akan memberikan informasi jalur-jalur yang menghubungkan posisi awal dengan posisi tujuan. Akan tetapi dengan menggunakan prinsip pemilihan jalur ke kanan, belum mendapatkan informasi jalur terpendek dari maze. Untuk itu, Hayate menerapkan sebuah algoritma depth first search dengan implementasinya menggunakan stack.
4.3. Shortest Path Algoritma Shortest Path yang diimplementasikan cukup sederhana, yaitu dengan menyimpan semua kemungkinan jalur-jalur daru posisi awal ke posisi tujuan. Dari setiap kemungkinan jalur tersebut, kemudian dihitung jumlah langkah total dari posisi awal ke posisi tujuan. Pada akhirnya dilakukan pencarian nilai yang terkecil yang berarti jalur tersebut merupakan jalur terpendek dari posisi awal ke posisi tujuan.
4.4. Communication Komunikasi antara Hayate dengan Kazetora dilakukan melalui protokol Bluetooth. Bluetooth beroperasi pada frekuensi 2.4 hingga 2.485 Gigahertz. Di banyak negara, frekuensi ini tidak dilisensi dan memang dibuka secara luas untuk dipakai. Semua mekanisme untuk melakukan sambungan
bluetooth
sudah
disediakan
oleh
LejosTM,
terutama
dari
package
lejos.nxt.comm. Kedua robot sebelumnya sudah pernah dipasangkan (pairing), sehingga di dalam kode cukup dipanggil nama dari robot yang ingin dihubungkan tanpa perlu mekanisme untuk perkenalan terlebih dahulu. Bagian selanjutnya akan menjelaskan tahaptahap komunikasi bluetooth antara dua robot. 18
4.4.1. Menemukan Device Untuk mengetahui device apa saja yang sudah dikenal oleh suatu NXT Brick, bisa dilakukan dengan menggunakan kode program di bawah ini.
Potongan kode tersebut berguna untuk mengeluarkan daftar dari semua device yang sudah dikenal dan kemudian menampilkannya ke layar NXT. Apabila belum ada device yang dikenal, maka diperlukan proses inquire untuk menemukan device bluetooth lainnya.
Method Bluetooth.inquire akan mencari device bluetooth yang tersedia pada jangkauan. Device yang ditemukan kemudian akan dimasukkan ke dalam daftar.
Setelah ditemukan, untuk melakukan sambungan maka device tersebut perlu ditambahkan ke dalam daftar device yang dikenal oleh NXT seperti tampak pada kode di atas.
19
4.4.2. Inisiasi Sambungan Antar Device Setelah ada device yang ditemukan, tahap selanjutnya adalah melakukan sambungan.
Jika device sudah dikenal sebelumnya, cukup dilakukan dengan memanggil namanya.
Setelah objek berhasil didapat, maka koneksi bisa dimulai dengan menggunakan method connect di kelas Bluetooth.
Jika device tersebut membutuhkan PIN untuk koneksi, maka pin harus disediakan terlebih dahulu sebelum melakukan sambungan.
4.4.3. Menyiapkan Pertukaran Data Antar Device Cara untuk melakukan pertukaran data antar device adalah dengan menggunakan DataInputStream dan DataOutputStream seperti dicontohkan oleh kode di bawah. DataInputStream dis = btc.openDataInputStream(); DataOutputStream dos = btc.openDataOutputStream(); 20
DataInputStream berguna untuk menerima data yang dikirim dan DataOutputStream berguna untuk mengirim data ke device lain.
4.4.4. Kazetora Menunggu Sambungan dari Hayate Untuk menunggu koneksi bluetooth dari device lain dapat dilakukan dengan cara di bawah ini.
NXT brick akan menunggu sampai mendapat sambungan dari device lain.
Kazetora adalah robot kedua dari pasangan Fukushi Fighter ini. Kazetora bertugas untuk menerima sambungan koneksi dari Hayate melalui Bluetooth yang berisi rute jalur terpendek dari maze yang akan ditelusuri. Berdasarkan pesan yang diterimanya, maka Kazetora akan menjelajahi maze sesuai petunjuk yang diberikan.
Dari setelah dinyalakan, Kazetora akan menunggu koneksi Bluetooth dari Hayate melalui kode pada baris ke 60 di atas. Selama menunggu, Kazetora tidak bergerak (idle).
4.4.4. Hayate Mengirimkan Data ke Kazetora Berikut adalah tampilan potongan kode ketika Hayate mengirimkan data ke Kazetora: for (int i = 0; i < clue.size(); i++) { int a = clue.get(i); LCD.drawString("Sending: "+a, 0, 5); dos.writeInt(a); dos.flush(); } dos.writeInt(8); dos.flush(); dos.close();
21
4.4.5. Kazetora Menerima Sambungan dari Hayate
Begitu mendapatkan sambungan Bluetooth, maka Kazetora akan memanggil objek DataInputStream yang merupakan objek yang mengatur pembacaan stream data yang dikirim oleh Hayate. Kelas DataInputStream merupakan bagian dari package java.io.
4.4.6. Kazetora Menerima Data dari Hayate
Pesan yang dikirim oleh Hayate di encode menjadi potongan-potongan angka. Angka-angka itu dibaca terus sampai sebuah karakter sentinel yang disepakati, di sini yang dipakai adalah angka ‘8’. Diluar itu, angka yang dikirim adalah kode rute mana yang harus diambil Kazetora ketika menemui persimpangan. ‘1’ untuk maju terus, ‘2’ untuk belok kanan, dan ‘3’ untuk belok kiri.
Begitu data sudah selesai didapat, Kazetora menutup koneksinya dan kemudian menjalankan method untuk memulai penjelajahan maze dengan petunjuk yang sudah diterima.
22
Method jalan adalah method untuk menelusuri maze dengan petunjuk yang diberikan pada argumennya.
Method ini alur utamanya adalah melakukan iterasi sebanyak petunjuk arah yang diberikan, yang berarti sebanyak persimpangan yang akan ditemukan sepanjang menelusuri maze dari awal sampai akhir.
Sesuai kode, jika Kazetora menemukan persimpangan, dan petunjuk arah adalah angka ‘2’, maka Kazetora akan belok ke kanan, sedangkan jika petunjuk arahnya adalah angka ‘3’, maka dia akan belok kiri. Selain itu, dia akan berjalan lurus. Ketika sedang tidak menemui simpangan, maka algoritma yang berjalan adalah algoritma line following yang sama dengan yang dipakai oleh Hayate.
23
4.5. Hasil Eksperimen 4.5.1. Hasil Eksperimen I Berikut adalah tampilan langkah-langkah pada arena pertama: 1. Kondisi awal robot dan arena
2. Pengecekan rutin ketersediaan jalur ke arah kanan oleh Hayate
3. Pengecekan rutin ketersediaan jalur ke arah depan oleh Hayate
24
4. Pengecekan rutin ketersediaan jalur ke arah kiri oleh Hayate
5. Hayate mencapai kondisi dead-end pertama dan kembali ke persimpangan terakhir yang dilalui (back-track)
6. Hayate mencapai kondisi dead-end kedua dan kembali ke persimpangan terakhir yang dilalui (back-track)
25
7. Hayate menemukan solusi pertama
8. Setelah menemukan solusi pertama Hayate kembali mencari alternatif jalur yang lain
9. Hayate menemukan solusi kedua dan sudah tidak ada lagi alternatif jalur yang lain
26
10. Hayate bergerak maju memberi ruang dan bersiap untuk mengirimkan data
11. Hayate mengirimkan data ke Kazetora
12. Kazetora menerima data
27
13. Kazetora mulai bergerak, pada persimpangan pertama langsung memilih arah ke kanan
14. Kazetora mulai bergerak, pada persimpangan kedua langsung memilih arah ke kanan
15. Kazetora berhasil mencapai tujuan akhir
28
Catatan-catatan waktu: a. Waktu yang dibutuhkan oleh Hayate menemukan solusi pertama (baik solusi tersebut jalur terpendek atau bukan): 2 menit 11 detik = 131 detik. b. Waktu yang dibutuhkan oleh Hayate untuk menjelajahi semua kemungkinan jalur: 3 menit 14 detik = 194 detik. Total jalur yang ditempuh adalah 14 satuan jalur. Rata-rata waktu tempuh untuk setiap jalur adalah: 194 detik/14 satuan jalur = 13.86 detik/satuan jalur. c. Waktu yang dibutuhkan oleh Hayate dan Kazetora untuk pengaktifkaan sambungan dan pengiriman-penerimaan data: 8 detik. d. Waktu yang dibutuhkan oleh Kazetora untuk mencapai daerah tujuan: 21 detik. Total jalur yang ditempuh adalah 4 satuan jalur. Rata-rata waktu tempuh untuk setiap jalur adalah: 21 detik/4 satuan jalur = 5.25 detik/satuan jalur. e. Total waktu yang dibutuhkan: 3 menit 51 detik = 231 detik. f. Perbedaan rata-rata waktu tempuh untuk setiap jalur adalah 13.86 (Hayate, ada pengecekan persimpangan) – 5.25 (Kazetora, tanpa pengecekan persimpangan) = 8.61 detik. Perbandingan waktu 13.86 / 5.25 = 2.64 menggambarkan bahwa waktu tempuh untuk setiap jalur tanpa pengecekan persimpangan 2.64 kali lebih cepat dibandingkan jika melakukan pengecekan persimpangan.
29
4.5.2. Hasil Eksperimen II Berikut adalah tampilan langkah-langkah pada arena kedua: 1. Kondisi awal robot dan arena
2. Pengecekan rutin ketersediaan jalur ke arah kanan oleh Hayate
3. Pengecekan rutin ketersediaan jalur ke arah depan oleh Hayate
30
4. Pengecekan rutin ketersediaan jalur ke arah kiri oleh Hayate
5. Hayate mencapai kondisi dead-end pertama dan kembali ke persimpangan terakhir yang dilalui (back-track)
6. Hayate menemukan solusi pertama
31
7. Setelah menemukan solusi pertama Hayate kembali mencari alternatif jalur yang lain
8. Hayate menemukan solusi kedua dan menganggap tidak mungkin ada lagi jalur yang lebih pendek
9. Hayate bergerak maju memberi ruang dan bersiap untuk mengirimkan data
32
10. Hayate mengirimkan data ke Kazetora
11. Kazetora menerima data
12. Kazetora mulai bergerak, pada persimpangan pertama langsung memilih arah ke depan
33
13. Kazetora mulai bergerak, pada persimpangan kedua langsung memilih arah ke kanan
14. Kazetora mulai bergerak, pada persimpangan ketiga langsung memilih arah ke kiri
15. Kazetora berhasil mencapai tujuan akhir
34
Catatan-catatan waktu: a. Waktu yang dibutuhkan oleh Hayate menemukan solusi pertama (baik solusi tersebut jalur terpendek atau bukan): 2 menit 2 detik = 122 detik. b. Waktu yang dibutuhkan oleh Hayate untuk menjelajahi semua kemungkinan jalur: 3 menit 3 detik = 183 detik. Total jalur yang ditempuh adalah 18 satuan jalur. Rata-rata waktu tempuh untuk setiap jalur adalah: 183 detik/18 satuan jalur = 10.16 detik/satuan jalur. c. Waktu yang dibutuhkan oleh Hayate dan Kazetora untuk pengaktifkaan sambungan dan pengiriman-penerimaan data: 8 detik. d. Waktu yang dibutuhkan oleh Kazetora untuk mencapai daerah tujuan: 23 detik. Total jalur yang ditempuh adalah 6 satuan jalur. Rata-rata waktu tempuh untuk setiap jalur adalah: 23 detik/6 satuan jalur = 3.83 detik/satuan jalur. e. Total waktu yang dibutuhkan: 3 menit 39 detik = 219 detik. f. Perbedaan rata-rata waktu tempuh untuk setiap jalur adalah 10.16 (Hayate, ada pengecekan persimpangan) – 3.83 (Kazetora, tanpa pengecekan persimpangan) = 6.33 detik. Perbandingan waktu 10.16 / 3.83 = 2.65 menggambarkan bahwa waktu tempuh untuk setiap jalur tanpa pengecekan persimpangan 2.65 kali lebih cepat dibandingkan jika melakukan pengecekan persimpangan.
35
4.5.3. Hasil Eksperimen III Tampilan ketika Robot Hayate mendeteksi adanya suara yang lebih keras. Robot kemudian berhenti sejenak selama beberapa detik.
Tampilan ketika Robot Hayate kembali melanjutkan perjalanan setelah berhenti.
Tampilan ketika Robot Kazetora mendeteksi adanya suara yang lebih keras. Robot kemudian berhenti sejenak selama beberapa detik.
36
Tampilan ketika Robot Kazetora kembali melanjutkan perjalanan setelah berhenti.
37
BAB V KESIMPULAN
5.1. Kesimpulan Kesimpulan yang dapat diperoleh dari Hasil Eksperimen adalah: a. Penerapan Algoritma Maze Mapping dan Shortest Path serta komunikasi antar robot menggunakan bluetooth dapat diterapkan pada Lego Mindstorm NXT. b. Waktu yang dibutuhkan oleh Hayate dan Kazetora untuk pengaktifkaan sambungan dan pengiriman-penerimaan data adalah 8 detik baik pada arena pertama maupun kedua. c. Rata-rata waktu tempuh setiap jalur untuk Hayate adalah 13.86 detik/satuan jalur pada arena pertama dan 10.16 detik/satuan jalur pada arena kedua. d. Rata-rata waktu tempuh setiap jalur untuk Kazetora adalah 5.25 detik/satuan jalur pada arena pertama dan 3.83 detik/satuan jalur pada arena kedua. f. Waktu tempuh untuk setiap jalur tanpa pengecekan persimpangan (Robot sudah mengetahui mana jalur yang harus diambil) dibandingkan jika melakukan pengecekan persimpangan (Robot belum mengetahui mana jalur yang harus diambil) adalah 2.64 kali lebih cepat pada arena pertama dan 2.65 kali lebih cepat pada arena kedua.
38
DAFTAR PUSTAKA
Lego Mindstorm NXT Product. Tersedia: http://mindstorms.lego.com/en-us/Products/default.aspx Lejos API. Tersedia: http://lejos.sourceforge.net/nxt/nxj/api/
Siegwart R., & Nourbakhsh, I.R. 2004. Introduction to Autonomous Mobile Robots. London: MIT Press. Wisnu J, et al. 2009. Robot LEGO Mindstroms: Teori dan Praktek. Depok: Fakultas Ilmu Komputer Universitas Indonesia.
39
LAMPIRAN
1. Ouput Hasil Running Program untuk Arena Pertama ----------------123456789 ----------------0000100 0000000 0000000 0000000 0000000 ------------------- new state --- | current pos (Y, X): (0, 4) checking y= 0 and x= 3 | checking y= 1 and x= 4 | Data[1][4] is true A way found to forward. Maze was updated. checking y= 0 and x= 5 | Top Of Stack is: 1 ---stack values[0]: 12 0 4 8 nextMove is 12, from (0, 4) | move to direction 8, (moveForward) ----------------123456789 ----------------0000200 0000100 0000000 0000000 0000000 ------------------- new state --- | current pos (Y, X): (1, 4) checking y= 1 and x= 3 | checking y= 2 and x= 4 | Data[2][4] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 1 ---stack values[0]: 12 1 4 8 nextMove is 12, from (1, 4) | move to direction 8, (moveForward) ----------------123456789 ----------------0000200 40
0000200 0000100 0000000 0000000 ------------------- new state --- | current pos (Y, X): (2, 4) checking y= 2 and x= 3 | Data[2][3] is true A way found to the right. Maze was updated. checking y= 3 and x= 4 | checking y= 2 and x= 5 | Data[2][5] is true A way found to the left. Maze was updated. Top Of Stack is: 2 ---stack values[0]: 11 2 4 8 ---stack values[1]: 13 2 4 8 nextMove is 13, from (2, 4) | move to direction 2, (moveLeft) ----------------123456789 ----------------0000200 0000200 0001210 0000000 0000000 ------------------- new state --- | current pos (Y, X): (2, 5) checking y= 3 and x= 5 | checking y= 2 and x= 6 | Data[2][6] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 2 ---stack values[0]: 11 2 4 8 ---stack values[1]: 12 2 5 2 nextMove is 12, from (2, 5) | move to direction 2, (moveForward) ----------------123456789 ----------------0000200 0000200 0001221 0000000 0000000 ------------------- new state --- | current pos (Y, X): (2, 6) 41
checking y= 3 and x= 6 | checking y= 1 and x= 6 | Top Of Stack is: 1 ---stack values[0]: 11 2 4 8 Dead-end. nextMove is 12, from (2, 6). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 6) move to direction 4, (moveForward) ----------------123456789 ----------------0000200 0000200 0001223 0000000 0000000 ----------------nextMove is 11, from (2, 5). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 5) move to direction 1, (moveRight) ----------------123456789 ----------------0000200 0000200 0001233 0000000 0000000 ----------------nextMove is 11, from (2, 4). Dir: 8 | move to direction 4, (moveRight) ----------------123456789 ----------------0000200 0000200 0001233 0000000 0000000 ------------------- new state --- | current pos (Y, X): (2, 3) checking y= 1 and x= 3 | checking y= 2 and x= 2 | Data[2][2] is true A way found to forward. Maze was updated. checking y= 3 and x= 3 | Top Of Stack is: 1 ---stack values[0]: 12 2 3 4 nextMove is 12, from (2, 3) | move to direction 4, (moveForward) 42
----------------123456789 ----------------0000200 0000200 0012233 0000000 0000000 ------------------- new state --- | current pos (Y, X): (2, 2) checking y= 1 and x= 2 | Data[1][2] is true A way found to the right. Maze was updated. checking y= 2 and x= 1 | Data[2][1] is true A way found to forward. Maze was updated. checking y= 3 and x= 2 | Data[3][2] is true A way found to the left. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 13 2 2 4 nextMove is 13, from (2, 2) | move to direction 8, (moveLeft) ----------------123456789 ----------------0000200 0010200 0122233 0010000 0000000 ------------------- new state --- | current pos (Y, X): (3, 2) checking y= 3 and x= 1 | checking y= 4 and x= 2 | Data[4][2] is true A way found to forward. Maze was updated. checking y= 3 and x= 3 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 12 3 2 8 nextMove is 12, from (3, 2) | move to direction 8, (moveForward) ----------------123456789 ----------------43
0000200 0010200 0122233 0020000 0010000 ------------------- new state --- | current pos (Y, X): (4, 2) checking y= 4 and x= 1 | Data[4][1] is true A way found to the right. Maze was updated. checking y= 4 and x= 3 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 11 4 2 8 nextMove is 11, from (4, 2) | move to direction 4, (moveRight) ----------------123456789 ----------------0000200 0010200 0122233 0020000 0120000 ------------------- new state --- | current pos (Y, X): (4, 1) checking y= 3 and x= 1 | checking y= 4 and x= 0 | Data[4][0] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 ---stack values[2]: 12 4 1 4 nextMove is 12, from (4, 1) | move to direction 4, (moveForward) ----------------123456789 ----------------0000200 0010200 0122233 0020000 1220000 -----------------
44
--- new state --- | current pos (Y, X): (4, 0) checking y= 3 and x= 0 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 2 4 Dead-end. nextMove is 12, from (4, 0). Dir: 2 | --- backtrack state --- | current pos (Y, X): (4, 0) move to direction 2, (moveForward) ----------------123456789 ----------------0000200 0010200 0122233 0020000 3220000 ----------------nextMove is 13, from (4, 1). Dir: 2 | --- backtrack state --- | current pos (Y, X): (4, 1) move to direction 1, (moveLeft) ----------------123456789 ----------------0000200 0010200 0122233 0020000 3320000 ----------------nextMove is 12, from (4, 2). Dir: 1 | --- backtrack state --- | current pos (Y, X): (4, 2) move to direction 1, (moveForward) ----------------123456789 ----------------0000200 0010200 0122233 0020000 3330000 ----------------nextMove is 11, from (3, 2). Dir: 1 | --- backtrack state --- | current pos (Y, X): (3, 2) move to direction 2, (moveRight) ----------------123456789 45
----------------0000200 0010200 0122233 0030000 3330000 ----------------nextMove is 12, from (2, 2). Dir: 4 | move to direction 4, (moveForward) ----------------123456789 ----------------0000200 0010200 0122233 0030000 3330000 ------------------- new state --- | current pos (Y, X): (2, 1) checking y= 1 and x= 1 | checking y= 2 and x= 0 | Data[2][0] is true A way found to forward. Maze was updated. checking y= 3 and x= 1 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 4 ---stack values[1]: 12 2 1 4 nextMove is 12, from (2, 1) | move to direction 4, (moveForward) ----------------123456789 ----------------0000200 0010200 1222233 0030000 3330000 ------------------- new state --- | current pos (Y, X): (2, 0) checking y= 1 and x= 0 | Data[1][0] is true A way found to the right. Maze was updated. checking y= 3 and x= 0 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 4 ---stack values[1]: 11 2 0 4 nextMove is 11, from (2, 0) | move to direction 1, (moveRight) ----------------46
123456789 ----------------0000200 1010200 2222233 0030000 3330000 ------------------- new state --- | current pos (Y, X): (1, 0) checking y= 1 and x= 1 | checking y= 0 and x= 0 | Top Of Stack is: 1 ---stack values[0]: 11 2 2 4 Solution Found. nextMove is 13, from (1, 0). Dir: 8 | --- backtrack state --- | current pos (Y, X): (1, 0) move to direction 2, (moveLeft) ----------------123456789 ----------------0000200 3010200 2222233 0030000 3330000 ----------------nextMove is 12, from (2, 0). Dir: 2 | --- backtrack state --- | current pos (Y, X): (2, 0) move to direction 2, (moveForward) ----------------123456789 ----------------0000200 3010200 3222233 0030000 3330000 ----------------nextMove is 11, from (2, 2). Dir: 4 | move to direction 1, (moveRight) ----------------123456789 ----------------0000200 3010200 3222233 0030000 3330000 47
------------------- new state --- | current pos (Y, X): (1, 2) checking y= 1 and x= 3 | checking y= 0 and x= 2 | Data[0][2] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 1 2 1 nextMove is 12, from (1, 2) | move to direction 1, (moveForward) ----------------123456789 ----------------0010200 3020200 3222233 0030000 3330000 ------------------- new state --- | current pos (Y, X): (0, 2) checking y= 0 and x= 3 | checking y= 0 and x= 1 | Data[0][1] is true A way found to the left. Maze was updated. Top Of Stack is: 1 ---stack values[0]: 13 0 2 1 nextMove is 13, from (0, 2) | move to direction 4, (moveLeft) ----------------123456789 ----------------0120200 3020200 3222233 0030000 3330000 ------------------- new state --- | current pos (Y, X): (0, 1) checking y= 0 and x= 0 | checking y= 1 and x= 1 | Top Of Stack is: 0 Solution Found. All area is explored succesfully. Maze 0120200 48
3020200 3222233 0030000 3330000 Finding shortest path.. Position of source(x: 0 ,y: 4) Position of Destination(x: 0 ,y: 0) (0, 4) -> (1, 4) -> (2, 4) -> (2, 3) -> (2, 2) -> (1, 2) -> (0, 2) -> (0, 1) -> (0, 0)
49
2. Ouput Hasil Running Program Untuk Arena Kedua ----------------123456789 ----------------100000000 000000000 000000000 000000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (0, 0) checking y= 1 and x= 0 | Data[1][0] is true A way found to forward. Maze was updated. checking y= 0 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 0 0 8 nextMove is 12, from (0, 0) | move to direction 8, (moveForward) ----------------123456789 ----------------200000000 100000000 000000000 000000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (1, 0) checking y= 2 and x= 0 | Data[2][0] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 1 0 8 nextMove is 12, from (1, 0) | move to direction 8, (moveForward) ----------------123456789 ----------------200000000 200000000 50
100000000 000000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (2, 0) checking y= 3 and x= 0 | checking y= 2 and x= 1 | Data[2][1] is true A way found to the left. Maze was updated. Top Of Stack is: 1 ---stack values[0]: 13 2 0 8 nextMove is 13, from (2, 0) | move to direction 2, (moveLeft) ----------------123456789 ----------------200000000 200000000 210000000 000000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (2, 1) checking y= 3 and x= 1 | checking y= 2 and x= 2 | Data[2][2] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 2 1 2 nextMove is 12, from (2, 1) | move to direction 2, (moveForward) ----------------123456789 ----------------200000000 200000000 221000000 000000000 000000000 000000000 000000000 -----------------
51
--- new state --- | current pos (Y, X): (2, 2) checking y= 3 and x= 2 | Data[3][2] is true A way found to the right. Maze was updated. checking y= 2 and x= 3 | Data[2][3] is true A way found to forward. Maze was updated. checking y= 1 and x= 2 | Data[1][2] is true A way found to the left. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 13 2 2 2 nextMove is 13, from (2, 2) | move to direction 1, (moveLeft) ----------------123456789 ----------------200000000 201000000 222100000 001000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (1, 2) checking y= 1 and x= 3 | checking y= 0 and x= 2 | Data[0][2] is true A way found to forward. Maze was updated. checking y= 1 and x= 1 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 12 1 2 1 nextMove is 12, from (1, 2) | move to direction 1, (moveForward) ----------------123456789 ----------------201000000 202000000 222100000 001000000 000000000 000000000 000000000 ----------------52
--- new state --- | current pos (Y, X): (0, 2) checking y= 0 and x= 3 | Data[0][3] is true A way found to the right. Maze was updated. checking y= 0 and x= 1 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 11 0 2 1 nextMove is 11, from (0, 2) | move to direction 2, (moveRight) ----------------123456789 ----------------202100000 202000000 222100000 001000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (0, 3) checking y= 1 and x= 3 | checking y= 0 and x= 4 | Data[0][4] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 ---stack values[2]: 12 0 3 2 nextMove is 12, from (0, 3) | move to direction 2, (moveForward) ----------------123456789 ----------------202210000 202000000 222100000 001000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (0, 4) checking y= 1 and x= 4 | checking y= 0 and x= 5 | 53
Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 2 2 Dead-end. nextMove is 12, from (0, 4). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 4) move to direction 4, (moveForward) ----------------123456789 ----------------202230000 202000000 222100000 001000000 000000000 000000000 000000000 ----------------nextMove is 13, from (0, 3). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 3) move to direction 8, (moveLeft) ----------------123456789 ----------------202330000 202000000 222100000 001000000 000000000 000000000 000000000 ----------------nextMove is 12, from (0, 2). Dir: 8 | --- backtrack state --- | current pos (Y, X): (0, 2) move to direction 8, (moveForward) ----------------123456789 ----------------203330000 202000000 222100000 001000000 000000000 000000000 000000000 ----------------nextMove is 11, from (1, 2). Dir: 8 | 54
--- backtrack state --- | current pos (Y, X): (1, 2) move to direction 4, (moveRight) ----------------123456789 ----------------203330000 203000000 222100000 001000000 000000000 000000000 000000000 ----------------nextMove is 12, from (2, 2). Dir: 2 | move to direction 2, (moveForward) ----------------123456789 ----------------203330000 203000000 222100000 001000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (2, 3) checking y= 3 and x= 3 | checking y= 2 and x= 4 | Data[2][4] is true A way found to forward. Maze was updated. checking y= 1 and x= 3 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 3 2 nextMove is 12, from (2, 3) | move to direction 2, (moveForward) ----------------123456789 ----------------203330000 203000000 222210000 001000000 000000000 000000000 000000000 -----------------
55
--- new state --- | current pos (Y, X): (2, 4) checking y= 3 and x= 4 | checking y= 2 and x= 5 | Data[2][5] is true A way found to forward. Maze was updated. checking y= 1 and x= 4 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 4 2 nextMove is 12, from (2, 4) | move to direction 2, (moveForward) ----------------123456789 ----------------203330000 203000000 222221000 001000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (2, 5) checking y= 3 and x= 5 | checking y= 2 and x= 6 | Data[2][6] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 2 5 2 nextMove is 12, from (2, 5) | move to direction 2, (moveForward) ----------------123456789 ----------------203330000 203000000 222222100 001000000 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (2, 6) checking y= 3 and x= 6 | Data[3][6] is true A way found to the right. Maze was updated. checking y= 2 and x= 7 | checking y= 1 and x= 6 | Data[1][6] is true A way found to the left. Maze was updated. 56
Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 13 2 6 2 nextMove is 13, from (2, 6) | move to direction 1, (moveLeft) ----------------123456789 ----------------203330000 203000100 222222200 001000100 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (1, 6) checking y= 1 and x= 7 | checking y= 0 and x= 6 | Data[0][6] is true A way found to forward. Maze was updated. checking y= 1 and x= 5 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 1 6 1 nextMove is 12, from (1, 6) | move to direction 1, (moveForward) ----------------123456789 ----------------203330100 203000200 222222200 001000100 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (0, 6) checking y= 0 and x= 7 | Data[0][7] is true A way found to the right. Maze was updated. checking y= 0 and x= 5 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 57
---stack values[1]: 11 2 6 2 ---stack values[2]: 11 0 6 1 nextMove is 11, from (0, 6) | move to direction 2, (moveRight) ----------------123456789 ----------------203330210 203000200 222222200 001000100 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (0, 7) checking y= 1 and x= 7 | checking y= 0 and x= 8 | Data[0][8] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 0 7 2 nextMove is 12, from (0, 7) | move to direction 2, (moveForward) ----------------123456789 ----------------203330221 203000200 222222200 001000100 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (0, 8) checking y= 1 and x= 8 | Data[1][8] is true A way found to the right. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 11 0 8 2 nextMove is 11, from (0, 8) | 58
move to direction 8, (moveRight) ----------------123456789 ----------------203330222 203000201 222222200 001000100 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (1, 8) checking y= 1 and x= 7 | checking y= 2 and x= 8 | Data[2][8] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 1 8 8 nextMove is 12, from (1, 8) | move to direction 8, (moveForward) ----------------123456789 ----------------203330222 203000202 222222201 001000100 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (2, 8) checking y= 2 and x= 7 | checking y= 3 and x= 8 | Data[3][8] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 ---stack values[2]: 12 2 8 8 nextMove is 12, from (2, 8) | move to direction 8, (moveForward) ----------------123456789 59
----------------203330222 203000202 222222202 001000101 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (3, 8) checking y= 3 and x= 7 | checking y= 4 and x= 8 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 2 6 2 Solution Found. nextMove is 12, from (3, 8). Dir: 1 | --- backtrack state --- | current pos (Y, X): (3, 8) move to direction 1, (moveForward) ----------------123456789 ----------------203330222 203000202 222222202 001000103 000000000 000000000 000000000 ----------------nextMove is 12, from (2, 8). Dir: 1 | --- backtrack state --- | current pos (Y, X): (2, 8) move to direction 1, (moveForward) ----------------123456789 ----------------203330222 203000202 222222203 001000103 000000000 000000000 000000000 ----------------nextMove is 13, from (1, 8). Dir: 1 | --- backtrack state --- | current pos (Y, X): (1, 8) move to direction 4, (moveLeft) 60
----------------123456789 ----------------203330222 203000203 222222203 001000103 000000000 000000000 000000000 ----------------nextMove is 12, from (0, 8). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 8) move to direction 4, (moveForward) ----------------123456789 ----------------203330223 203000203 222222203 001000103 000000000 000000000 000000000 ----------------nextMove is 13, from (0, 7). Dir: 4 | --- backtrack state --- | current pos (Y, X): (0, 7) move to direction 8, (moveLeft) ----------------123456789 ----------------203330233 203000203 222222203 001000103 000000000 000000000 000000000 ----------------nextMove is 12, from (0, 6). Dir: 8 | --- backtrack state --- | current pos (Y, X): (0, 6) move to direction 8, (moveForward) ----------------123456789 ----------------203330333 203000203 61
222222203 001000103 000000000 000000000 000000000 ----------------nextMove is 11, from (1, 6). Dir: 8 | --- backtrack state --- | current pos (Y, X): (1, 6) move to direction 4, (moveRight) ----------------123456789 ----------------203330333 203000303 222222203 001000103 000000000 000000000 000000000 ----------------nextMove is 11, from (2, 6). Dir: 2 | move to direction 8, (moveRight) ----------------123456789 ----------------203330333 203000303 222222203 001000103 000000000 000000000 000000000 ------------------- new state --- | current pos (Y, X): (3, 6) checking y= 3 and x= 5 | checking y= 4 and x= 6 | Data[4][6] is true A way found to forward. Maze was updated. checking y= 3 and x= 7 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 3 6 8 nextMove is 12, from (3, 6) | move to direction 8, (moveForward) ----------------123456789 ----------------203330333 203000303 62
222222203 001000203 000000100 000000000 000000000 ------------------- new state --- | current pos (Y, X): (4, 6) checking y= 4 and x= 5 | Data[4][5] is true A way found to the right. Maze was updated. checking y= 5 and x= 6 | Data[5][6] is true A way found to forward. Maze was updated. checking y= 4 and x= 7 | Data[4][7] is true A way found to the left. Maze was updated. Top Of Stack is: 4 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 4 6 8 ---stack values[3]: 13 4 6 8 nextMove is 13, from (4, 6) | move to direction 2, (moveLeft) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001210 000000100 000000000 ------------------- new state --- | current pos (Y, X): (4, 7) checking y= 5 and x= 7 | checking y= 4 and x= 8 | checking y= 3 and x= 7 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 4 6 8 Solution Found. nextMove is 11, from (4, 7). Dir: 4 | --- backtrack state --- | current pos (Y, X): (4, 7) move to direction 1, (moveRight) ----------------123456789 ----------------63
203330333 203000303 222222203 001000203 000001230 000000100 000000000 ----------------nextMove is 12, from (4, 6). Dir: 8 | move to direction 8, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001230 000000100 000000000 ------------------- new state --- | current pos (Y, X): (5, 6) checking y= 5 and x= 5 | checking y= 6 and x= 6 | Data[6][6] is true A way found to forward. Maze was updated. checking y= 5 and x= 7 | Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 5 6 8 nextMove is 12, from (5, 6) | move to direction 8, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001230 000000200 000000100 ------------------- new state --- | current pos (Y, X): (6, 6) checking y= 6 and x= 5 | Data[6][5] is true A way found to the right. Maze was updated. checking y= 6 and x= 7 | 64
Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 11 6 6 8 nextMove is 11, from (6, 6) | move to direction 4, (moveRight) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001230 000000200 000001200 ------------------- new state --- | current pos (Y, X): (6, 5) checking y= 5 and x= 5 | checking y= 6 and x= 4 | Data[6][4] is true A way found to forward. Maze was updated. Top Of Stack is: 3 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 ---stack values[2]: 12 6 5 4 nextMove is 12, from (6, 5) | move to direction 4, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001230 000000200 000012200 ------------------- new state --- | current pos (Y, X): (6, 4) checking y= 5 and x= 4 | checking y= 6 and x= 3 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 11 4 6 8 Dead-end. nextMove is 12, from (6, 4). Dir: 2 | 65
--- backtrack state --- | current pos (Y, X): (6, 4) move to direction 2, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001230 000000200 000032200 ----------------nextMove is 13, from (6, 5). Dir: 2 | --- backtrack state --- | current pos (Y, X): (6, 5) move to direction 1, (moveLeft) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001230 000000200 000033200 ----------------nextMove is 12, from (6, 6). Dir: 1 | --- backtrack state --- | current pos (Y, X): (6, 6) move to direction 1, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000001230 000000200 000033300 ----------------nextMove is 11, from (4, 6). Dir: 8 | move to direction 4, (moveRight) ----------------123456789 ----------------203330333 203000303 66
222222203 001000203 000001230 000000200 000033300 ------------------- new state --- | current pos (Y, X): (4, 5) checking y= 3 and x= 5 | checking y= 4 and x= 4 | Data[4][4] is true A way found to forward. Maze was updated. checking y= 5 and x= 5 | Top Of Stack is: 2 ---stack values[0]: 11 2 2 2 ---stack values[1]: 12 4 5 4 nextMove is 12, from (4, 5) | move to direction 4, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000012230 000000200 000033300 ------------------- new state --- | current pos (Y, X): (4, 4) checking y= 3 and x= 4 | checking y= 4 and x= 3 | checking y= 5 and x= 4 | Top Of Stack is: 1 ---stack values[0]: 11 2 2 2 Dead-end. nextMove is 12, from (4, 4). Dir: 2 | --- backtrack state --- | current pos (Y, X): (4, 4) move to direction 2, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000032230 000000200 000033300 ----------------67
nextMove is 12, from (4, 6). Dir: 1 | --- backtrack state --- | current pos (Y, X): (4, 6) move to direction 1, (moveForward) ----------------123456789 ----------------203330333 203000303 222222203 001000203 000032330 000000200 000033300 ----------------nextMove is 12, from (2, 6). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 6) move to direction 4, (moveForward) ----------------123456789 ----------------203330333 203000303 222222303 001000203 000032330 000000200 000033300 ----------------nextMove is 12, from (2, 5). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 5) move to direction 4, (moveForward) ----------------123456789 ----------------203330333 203000303 222223303 001000203 000032330 000000200 000033300 ----------------nextMove is 12, from (2, 4). Dir: 4 | --- backtrack state --- | current pos (Y, X): (2, 4) move to direction 4, (moveForward) ----------------123456789 68
----------------203330333 203000303 222233303 001000203 000032330 000000200 000033300 ----------------nextMove is 11, from (2, 2). Dir: 2 | move to direction 8, (moveRight) ----------------123456789 ----------------203330333 203000303 222233303 001000203 000032330 000000200 000033300 ------------------- new state --- | current pos (Y, X): (3, 2) checking y= 3 and x= 1 | checking y= 4 and x= 2 | Data[4][2] is true A way found to forward. Maze was updated. checking y= 3 and x= 3 | Top Of Stack is: 1 ---stack values[0]: 12 3 2 8 nextMove is 12, from (3, 2) | move to direction 8, (moveForward) ----------------123456789 ----------------203330333 203000303 222233303 002000203 001032330 000000200 000033300 ------------------- new state --- | current pos (Y, X): (4, 2) checking y= 4 and x= 1 | Data[4][1] is true A way found to the right. Maze was updated. checking y= 5 and x= 2 | checking y= 4 and x= 3 | Top Of Stack is: 1 69
---stack values[0]: 11 4 2 8 nextMove is 11, from (4, 2) | move to direction 4, (moveRight) ----------------123456789 ----------------203330333 203000303 222233303 002000203 012032330 000000200 000033300 ------------------- new state --- | current pos (Y, X): (4, 1) checking y= 3 and x= 1 | checking y= 4 and x= 0 | Data[4][0] is true A way found to forward. Maze was updated. checking y= 5 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 4 1 4 nextMove is 12, from (4, 1) | move to direction 4, (moveForward) ----------------123456789 ----------------203330333 203000303 222233303 002000203 122032330 000000200 000033300 ------------------- new state --- | current pos (Y, X): (4, 0) checking y= 3 and x= 0 | checking y= 5 and x= 0 | Data[5][0] is true A way found to the left. Maze was updated. Top Of Stack is: 1 ---stack values[0]: 13 4 0 4 nextMove is 13, from (4, 0) | move to direction 8, (moveLeft) ----------------123456789 ----------------203330333 70
203000303 222233303 002000203 222032330 100000200 000033300 ------------------- new state --- | current pos (Y, X): (5, 0) checking y= 6 and x= 0 | Data[6][0] is true A way found to forward. Maze was updated. checking y= 5 and x= 1 | Top Of Stack is: 1 ---stack values[0]: 12 5 0 8 nextMove is 12, from (5, 0) | move to direction 8, (moveForward) ----------------123456789 ----------------203330333 203000303 222233303 002000203 222032330 200000200 100033300 ------------------- new state --- | current pos (Y, X): (6, 0) checking y= 6 and x= 1 | Top Of Stack is: 0 All area is explored succesfully. Maze 203330333 203000303 222233303 002000203 222032330 200000200 100033300 Finding shortest path.. Position of source(x: 0 ,y: 0) Position of Destination(x: 4 ,y: 8) 71
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (2, 5) -> (2, 6) -> (3, 6) -> (4, 6) -> (4, 7) -> (4, 8)
72
