Enhanced Depth First Search Algorithm for Mobile Robot Navigation Johannes Bina Nusantara University,Jakarta,Indonesia, 11480
Nina Karina Wiryanto Bina Nusantara University,Jakarta,Indonesia, 11480 and
Andy Bina Nusantara University,Jakarta,Indonesia, 11480
Abstrak Penelitian ini membahas metode baru dalam eksplorasi dan penyelesaian track bagifire-fighting robot. Robot dibangun berdasarkan kriteria kompetisi fire-fighting robot yang diadakan setiap tahun. Kami mengembangkan sistem navigasi robot menggunakan algoritmaDepth First Search. Pengembangan yang kami lakukan adalah menambahkan algoritma Modified Line Maze untuk menghasilkan rute tersingkat bagi robot untuk kembali ke tempat asalnya setelah berhasil memadamkan. Algoritma Modified Line Mazememungkinkan robot menghindari jalan memutar jika menemukan loop. Robot menggunakan Median Filter untuk menghilangkanpembacaan sensor yang salah ketika menjelajahi track. Percobaan yang dilakukan ditujukan untuk mengetahui waktu yang dibutuhkan robot untuk menyelesaikan tugas, dan tingkat keberhasilan robot. Waktu tercepat yang dibutuhkan robot adalah 48.46 detik dan kesalahan pembacaan data sensor berkurang 99%. Beberapa perubahan juga diberikan dari segi mekanik robot sehingga robot dapat melalui uneven floor dengan mudah. Akurasi dari kompas digitaldipengaruhi oleh medan magnet disekitar robot. Kata Kunci : fire-fighting, mobile robot, depth first search, median filter, modified line maze algorithm
1.
Pendahuluan
Sebuah fire-fighting robot harus memiliki kemampuan untuk mengeksplorasi suatu track, mencari dan memadamkan api, serta kembali ke posisi semula. Track yang dijelajahi bisa berupa track yang sudah dikenali oleh robot sebelumnya, atau track yang baru sama sekali. Hal tersebut mempengaruhi algoritma yang akan diterapkan oleh robot. Jika track sudah diketahui sebelumnya, maka kita dapat memrogram rute-rute yang mungkin dilalui oleh robot, sehingga
robot memiliki pengetahuan tentang keadaan track sebelum memulai eksplorasi. Pada penelitian ini kami akan membahas track yang sudah dikenal oleh robot sebelum memulai eksplorasi, berdasarkan kontes fire-fighting robot yang diadakan di Trinity College, Hartford, Connecticut, Amerika Serikat. Track memiliki empat ruangan yang dibatasi oleh dinding. Sebuah lilin yang menyala akan diletakkan pada salah satu dari empat ruangan yang ada. Robot dapat memulai eksplorasinya dari salah satu ruangan atau pada titik home yang telah ditentukan sebelumnya pada track. Ada beberapa algoritma yang digunakan untuk menyelesaikan track yang berbentuk maze.Algoritma Wall-following adalah algoritma yang paling sering digunakan karena kesederhanaan dan kemudahannya untuk diimplementasi. Pada algoritma ini, robot akan selalu mengikuti, dinding kiri, kanan, atau bergantian dalam menjelajahi track[3]. Kelemahan algoritma ini adalah robot akan selalu memutari suatu loop jika terdapat pada maze dan tidak dapat menyelesaikan eksplorasinya. Algoritma lainnya adalah algoritma Depth First Search, yang akan dibahas lebih dalam pada bab selanjutnya.Depth First Searchadalah algoritma pencarian yang biasa digunakan pada sebuah tree graph.Algoritma ini dapat diimplementasikan pada track dengan cara memodelkan tempat robot memulai pencarian sebagai akar, lorong sebagai percabangan dan ruangan pada maze sebagai titik pada tree graph. Dengan menggunakan Depth First Search, robot dapat kembali ke tempatnya memulai tanpa harus menjelajahi track secara keseluruhan. Masalah yang timbul dari algoritma ini adalah proses pemodelan tree. Proses ini sangat menentukan keberhasilan robot menjelajahi track.Jika robot membuat titik yang salah pada model tree, dapat dipastikan bahwa robot tidak dapat menyelesaikan tugasnya hingga selesai.Kesalahan tersebut disebabkan oleh kesalahan pembacaan sensor. Untuk mengatasi hal ini, kami menggunakan sebuah filter untuk menghilangkan kesalahan pembacaan data sensor.Filter-filter yang dapat digunakan antara lain Kalman Filter, Fuzzy Logic, Hidden Markov Model, Bayessian Filter, Median Filter, dan lainnya. Kami memilih Median Filter karena kemudahan dan efektivitasnya. Robot dengan algoritma Depth First Searchtidak dapat menghindari jalan memutar untuk kembali ke tempat memulai.Hal ini menyebabkan robot melalui jalan yang lebih panjang dan memakan waktu yang lebih lama.Untuk itu kami menggunakan Line Maze Algorithm dan menambahkan beberapa aturan tambahan untuk mengatasi masalah tersebut.
2. Pengendalian Robot 2.1. AlgoritmaDepth First Search Depth First Searchadalah algoritma yang digunakan untuk melakukan pencarian pada sebuah tree graph. Pencarian dimulai dari akar, kemudian menjelajahi titik terdalam sebelum kembali ke tingkat sebelumnya.PadaDepth First Search, ketika sebuah titik dijelajahi, semua turunannya akan dijelajahi terlebih dahulu sebelumtitik dengan tingkat yang sama dijelajahi [4]. Gambar 1 menunjukkan model tree yang didapat dari track.
(a)
(b)
Gambar 1 (a) track dengan titik, (b) tree yang dihasilkan Robot akan memulai eksplorasi dari titik ‘H’ dan menemukan titik pertama, Titik 1. Robot akan mengingat Titik 1 memiliki tiga cabang. Cabang mana yang akan dijelajahi robot terlebih dahulu sudah ditentukan sebelumnya. Robot kemudian berjalan lurus dan menemukan Titik 2. Robot harus mengeksplorasi semua turunan dari Titik 2, yaitu R3, Titik 3, dan R4, sebelum berjalan kembalike Titik 4 dan Titik 5. Begitu juga setelah mengeksplorasi R4, robot berjalan ke Titik 4 dan menjelajahi turunannya yaitu R2, sebelum melanjutkan ke Titik 5.Setiap kali robot memasuki ruangan. Jika robot mendeteksi api, maka robot akan memadamkannya dan menghentikan penjelajahan track, dan kembali ke tempat asalnya.
2.2. Algoritma Modified Line Maze Algoritma ini digunakan untuk menyelesaikan sebuah maze. Umumnya, sebuah robot akan mengeksplorasi track menggunakanRight-Hand RuleatauLeft-Hand Rule. Ketika robot menjelajahi track, robot akan mengingat setiap perbelokan yang dibuat. AlgoritmaLine Maze mengeliminasi perbelokan yang tidak perlu. Proses eliminasi ditunjukkan pada gambar 2.
Gambar 2 Ilustrasi eliminasi perbelokan Berikut ini adalah seluruh aturan eliminasi yang ada pada Algoritma Line Maze
Tabel1. Aturan substitusi pada Line Maze Substitusi Kombinasi u-turn SUS U SUL R L SUR LUS R LUL S LUR U RUS L RUL S RUR U Algoritma Line Mazehanya dapat menyelesaikan maze tanpa loop. Karena track yang kami pakai memiliki loop, maka AlgoritmaLine Maze tidak dapat menghasilkan rute yang tersingkat bagi robot. Untuk itu beberapa aturan ditambahkan untuk mengatasi masalah dengan loop. Aturan yang kami tambahkan adalah aturan spesifik yang dibuat untuk menyelesaikan track tertentu.. untuk menyelesaikan track yang berbeda, harus dibuat aturan yang berbeda pula.Selain itu, metode ini.tidak dapat menyelesaikan suatu track, jika bentuk track terlalu kompleks. Tabel2. Aturan tambahan Kombinasi Substitusi pergerakan LLLLS RL SRRRR LR SLLSLS R SRSRRS L Table 2 menunjukkan aturan yang kami tambahkan untuk menyelesaikan track. Gambar3adalah ilustrasi yang menggambarkan bagaimana aturan tersebut dihasilkan.
Gambar 3. Ilustrasi eliminasi untuk aturan tambahan
2.3. PID Control 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 eminimalkan kesalahan. (dikutip dari "Mobile Robot Navigation Using Depth First Search Algorithm") PID controller terdiri dari tiga bagian utama, yaitu : Proportional Controller, Integral Controller, dan Derivative Controller. Proportional menentukan nilai reaksi terhadap kesalahan saat ini. Integral menentukan hasil penjumlahan nilai kesalahan yang terjadi. ·
(1)
·
1/
·
·
1/
·
(2) /
(3)
2.4. Median Filter Median pada statistika adalah istilah yang mengacu pada sebuah nilai yang berada di tengahtengah 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. Berikut ini adalah sekumpulan data yang difilter menggunakan Median Filter. Tabel3.Contoh distribusi data Raw Data 1 10 10 11 Sorted Data 1 9 10 10 Raw Data 2 10 10 11 Sorted Data 2 9 10 10
10 10 10 10
80 10 80 10
12 11 12 11
9 11 9 11
10 12 10 11
11 80 11 11 12 80
Nilai median dari Data 1 pada Table 3 adalah data yang berada tepat ditengan setelah di urutkan, yaitu 10. Nilai median dari Data 2 adalah 10.5 yang didapat dari hasil rata-rata dua data yang berada ditengah, yaitu (10+11)/2.
3. Perangkat Keras Sebuah robot harus memiliki kemampuan untuk berinteraksi dan mengenali keadaan sekitarnya. Terdapat berbagai macam jenis sensor.Setiap sensor memiliki kegunaan masingmasing untuk membantu robot mengetahui keadaan sekitarnya. Berikut ini adalah sensor-sensor yang digunakan pada robot : 1) Sensor ultrasonik Sensor ultrasonik digunakan untuk mendeteksi jarak suatu objek. Robot menmanfaatkan sensor ini untuk mendeteksi jaraknya dengan dinding. Robot menggunakan lima sensor ultrasonik, masing-masing di depan, kiri, kanan, dan dua di belakang robot. 2) Kompas digital Kompas ini berguna agar robot dapat mengetahui arah mana robot menghadap. Selain itu kompsa digital juga berguna ketika robot melakukan perbelokan, agar robot dapat berbelok kearah yang tepat. 3) IR Ranger IR Ranger adalah sensor yang terdiri atas LED infrared danfotodiode. Like the ultrasonic sensor, IR Ranger digunakan untuk mengetahui jarak dari suatu objek.Robot menggunakan enam buah IR Ranger, yaitu dua buah di kanan robot, dua buahdi kiri robot, dan masing-masing satu pada sudut serong di kiri depan dan kanan depan robot.. 4) Thermal Array Sensor Thermal sensor digunakan untuk mendeteksi panas. Mendeteksi sinar yang dikeluarkan oleh api rentan terhadap kesalahan pembacaan disebabkan oleh interferensi cahaya lain yang bukan berasal dari api. Karena itu kami menggunakan thermal sensor untuk menemukan api pada ruangan dalam track. 5) Sensor garis Digunakan untuk membedakan antara lantai berwana gelap dengan garis putih yang menandakan ruangan, serta lingkaran putih yang menandaklan adanya api, atau titikhome. Sensor ini teriri atas LED Infrared dan fotodiode.
Gambar 4. Konstruksi robot
Gambar 5. Diagram Blok Sistem
4. Hasil Percobaan Percobaan dilakukan untuk mengetahui berapa lama waktu yang dibutuhkan robot untuk mengeksplorasi track, menemukan dan memadamkan api, hingga kembali ke tempat asal robot. Pada setiap percobaan kami meletakkan lilinpada satu ruangan,kemudian mengambil data sebanyak sepuluh kali. Kami meletakkan robot pada tempat yang sama setiap kali memulai percobaan. Posisi api pada setiap ruangan ditentukan secara acak. Hasil percobaan dibandingkan dengan hasil yang diperoleh dari robot yang dibangun pada penelitian yang lalu[5].
300 250 time (s)
200 150
Previous Experiment
100
Current Experiment
50 0 R1
R2
R3
R4
Gambar5.Perbandingan waktu yang dibutuhkan oleh masing-masing robot untuk menyelesaikan tugasnya Waktu yang dibutuhkan robot untuk menyelesaikan tugasnya berkurang secara signifikan.
Namun tingkat keberhasilan untuk api di Ruang 1 turun hingga 20 %. Sedangkan untuk ruangan lainnya tingkat keberhasilan meningkat hingga 100%. 120 100
100 100
100 80
Persentase (%)
100
90 80
80 60
Previous Experiment Current Experiment
40 20 20 0 R1
R2
R3
R4
Gambar6. Perbandingan tingakat kesuksesan dari masing-masing robot
5. Simpulan Depth First Searchmemungkinkan robot untuk mengeksplorasi track, dan kembali ke tempat asalnya secara efisien tanpa harus mengitari keseluruhan track.Algoritma Modified LineMaze memberikan robot kemampuan untuk kembali ke tempat asalnyamelalui rute tersingkat. Depth First Searchsangat bergantung pada model tree yang dibuat oleh robot. Median filter menghilangkan data sensor yang salah, yang menjadi penyebab utama kesalahan pemodelan tree.
Daftar Pustaka [1]Kim SY, Hernandez R. Decision Making Process In A Fire-Fighting Robot: Based Off Of Shepherd University's Vulcan Series. Shepherdstown: Shepherd University. [2]"Fire Fighting Robot Rules and Regulations", [PDF Online Document], Available HTTP: http://prog.trincoll.edu/robot/Rules/Rules2012/rules_2012-final-1-letter.pdf [3]Porterfield J, Behera A, Austin J, Afandi S. Firefighting Robot. Oklahoma: Oklahoma State University. [4]Luger GF, Stubblefield WA. Artificial Intelligence, Structures and Strategies for Complex Problem Solving. 2nd ed. California: The Benjamin/Cummings Publishing Company; 1993 [5]Shuwanto F, Frederick, Stefen. Mobile Robot Navigation Using Depth First Search Algorithm. Jakarta: Binus University; 2010.
Enhanced Depth First Search Algorithm for Mobile Robot Navigation Johannes Bina Nusantara University,Jakarta,Indonesia, 11480
Nina Karina Wiryanto Bina Nusantara University,Jakarta,Indonesia, 11480 and
Andy Bina Nusantara University,Jakarta,Indonesia, 11480
Abstract This paper presents a new approach for fire-fighting mobile robot to solve maze problem in fire fighting robot contest. The mobile robot is built based on the criteria of the competition. We improve the mobile robot navigation using Depth First Search algorithm. Enhancements were made by using Modified Line Maze algorithm to find the shortest path for mobile robot to navigate back to its starting point. The Modified Line Maze algorithm helps mobile robot to solve loop-problem on the track. We also implemented Median Filter algorithm to reject erroneous sensor data while exploring the track.The test conducted consist of 2 stages, which are sensor testing and overall system testing. The fastest time needed for mobile robot accomplished it's task and back to its starting point is 48.46 seconds while the erroneous data due to false reading has been reduced by 99%. Changes have also been made on the mechanics of the mobile robot so it is able to navigate through uneven floor objects easily. The accuracy of the digital compass is highly affected by the surrounding magnetic field. Keyword : fire-fighting, mobile robot, depth first search, median filter, modified line maze algorithm
1.
Introduction
A fire-fighting robot must have the ability to explore a certain track, detect and extinguish fire, and navigate back to its starting position. The track could be either an unknown one, which is highly dependent on the robot's algorithm to explore it or a known map which we can preprogrammed the robot possible trajectories as a prior knowledge[1]. In an unknown track, the problem is more complicated because it has more possibilities of robot exploration trajectories compared to a known track. In this paper, we are going to discuss a known track based on fire
fighting robot contest which is held by Trinity College in Hartford, Connecticut, US. The track consists of four rooms separated by walls. A candle which represents fire will be placed into one of the four rooms. According to the rules, there are two possibilities regarding of the robot starting point, which are arbitrary start and non-arbitrary start[2]. In arbitrary start, the robot will be placed in one of four rooms as the starting point, while in non-arbitrary start, the robot will be placed on a fixed point located outside the four rooms of the track. There are several algorithms used to explore maze-type track. Wall following algorithm is the most common because the algorithm is simple and easy to be implemented. In wall following algorithm, the robot will always follow left wall or right wall or both of it[3]. In spite of its simplicity, this algorithm has a drawback. The robot cannot know its current position on the track and the robot would stuck if there is a loop Another algorithm that can be used is Depth First Search algorithm, which will be further discussed in this paper. Depth First Search is an algorithm for traversing a tree graph. We implemented this algorithm for exploring track by modeling the intersections of the track with nodes, the hall as branches, and home point as root. By using Depth First Search algorithm, the robot is able to travel back to starting point by reversing explored path. A problem in using Depth First Search algorithm is the tree modeling process. This process is very essential on determining the successfulness of track exploration. If the robot generates a wrong node or branch, it is highly unlikely that the robot will be able to travel back after it finish it's task. In our previous experiment, the robot often generates false node because of erroneous reading from its sensors. To overcome this problem, we implement a filter to reject erroneous readings. Many filtering techniques could be used such as Kalman Filter, Fuzzy Logic, Hidden Markov Model, Bayessian Filter, Median Filter, etc. We chose Median Filter due to its simplicity in programming with satisfactory results. Another shortcoming in Depth First Search Algorithm is the inability to avoid looping path while getting back to the start point. This results in further route and waste of time. We use Line Maze Algorithm and add a few rules to avoid the loop travelling while getting back to the start point.
2. Robot Control 2.1. Depth First Search Algorithm Depth First Search Algorithm is an algorithm for traversing or searching a tree. The searching starts at the root and explores as far as possible along each branch before backtracking. In Depth First Search, when a node is examined, all of its children and their descendants are examined before any of it siblings. Depth First Search goes deeper into the search space whenever this is possible. Only when no further descendants of a node can be found are its siblings considered [4]. Figure 1 shows a tree obtained from the tree modeling process.
(a)
(b)
Fig. 1 (a) Track with nodes, (b) Result tree The robot will start track exploration from the point ‘H’ and then it will find the first node, Node 1. The robot then memorizes that Node 1 has three branches. To which branch the robot goes first has already defined earlier. In this case the robot goes straight to Node 2. The robot has to explore all descendants of Node 2, which is R3, Node 3, and R4, before backtracking to Node 4 and Node 5. Likewise, after examining R4, the robot goes to Node 4 and examines its descendant, R2, before going to Node 5.Whenever the robot enters a room it checks for fire. If fire is detected, robot will extinguish it and stop the exploration.
2.2. Modified Line Maze Algorithm This is an algorithm widely used in maze solving. Usually a robot would explore a maze using Right-Hand Rule or Left-Hand Rule from the starting point to reach the destination. While the robot exploring the maze, it will memorize every turns it has made. Line Maze Algorithm will then eliminate every wrong turn to obtain the shortest route. The eliminating process is illustrated in Figure 2.
Fig 2. Illustration of Line Maze Algorithm Here are all the possible u-turn combinations and the elimination rules.
Table 1. Line Maze Algorithm Rules Substitute u-turn Combination SUS U SUL R L SUR LUS R LUL S LUR U RUS L RUL S RUR U Line Maze Algorithm can only handle mazes with no loops. As the track does have a loop, we can't implement this algorithm to our mobile robot directly. Some additional rules have to be added in order to deal with the loop. The rules we add are specific rules, designed to solve a specific track, in this case the contest track. To solve another track, whole new rules have to be determined. Moreover, this algorithm might give no solution if the track or maze you work with is relatively complex. Table 2. Specific Rule Addition Movement Substitute combination LLLLS RL SRRRR LR SLLSLS R SRSRRS L Table 2 shows specific additional rules to solve the track. Figure 3 is the two illustrations of how we obtain the rules.
Fig 3. Illustrations of the addition rules
2.3. PID Control Proportional-integral-derivative controller, usually called PID controller, is an advanced generic control loop mechanism. It is used widely and has become industry standard. The proportional controller results in an equilibrium state of speed. This equilibrium point is not always the desired speed. (1) The difference between the equilibrium point and the desired speed is called the steady-state error. The higher the Kp the smaller the steady-state error, but the oscillation is also greater. Integral controller is rarely used alone. It is mostly used in combination with proportional controller or proportional and derivative controller. Integral controller reduces the steady-state error of proportional controller without increasing the oscillation in the transient state. (2) Derivative controller, just like the integral controller, is usually used in combination with proportional controller or proportional and integral controller. Derivative controller shortens the transient time needed to reach the equilibrium state in proportional controller without increasing the oscillation. (3) We only use the proportional controller combined with integral controller, because the short transient time is not a significant issue in our mobile robot control system.
2.4. Median Filter Median is a numerical value separating the higher half of a data distribution from the lower half. The median of a list of data can be found by sorting all the data from lowest value to highest value or vice-versa and picking the middle data. If the number of data is even, the median value is obtained by averaging two middle data. Half of the data will be lower than the median, and the other half of the data will be higher than the median. This filter does not need a complex computational process, but it works properly on our mobile robot to eliminate false sensor readings, hence prevent false tree modeling. Median Filter takes the middle value of a sorted distribution data as the output value. We use this filter to eliminate false data read by sensors, where the false data often cause the false tree modeling. Here is an example of a distribution of data filtered using Median Filter. Table 3.Example of a distribution of data Raw Data 10 10 11 10 80 12 1 Sorted 9 10 10 10 10 11 Data 1 Raw Data 10 10 11 10 80 12 2 Sorted 9 10 10 10 10 11 Data 2
9
10 11
11 12 80 9
10 11 11
11 11 12 80
The median value from Data 1 in Table 3 is the middle data, which is 10. The median value from Data 2 is 10.5 obtained from calculation (10+11)/2.
3. Hardware Design The robot must be able to notice its surrounding and interact with its environment. Sensors come in a great variety of types. Each sensor is able to contribute to the task of environmental perception. Here are some sensors used in our mobile robot : 1) Ultrasonic sensor An ultrasonic sensor used to determine the distance of an object. There are five ultrasonic sensors each one on the left, the front, and the right side of the robot, the rest two are on the back side of the robot. 2) Digital Compass This is essential for the robot to be able to determine what degree it is heading. 3) IR Ranger IR Ranger light sensor is simply an infrared LED and a photodiode build in pairs. Like the ultrasonic sensor, IR Ranger used to measure the distance of an object. Six IR Rangers are used, two on the left side, two on the right side, and two on oblique degree. 4) Thermal Array Sensor Thermal sensor is used to detect heat. Instead of detecting rays, which is susceptible to environmental lighting condition, we use thermal sensor for fire scanning in each room. 5) Line sensor This is used to distinguish between the dark floor and a white line or a white circle. It is made from infrared LED and a photodiode.
Fig 4. Construction of the robot
Fig 5. System block diagram
4. Experimental Result The experiment is held to test how much time is spent by the robot from its start point to find and extinguish the fire and navigate back to its starting point. In each experiment, we put the fire in a certain room and collect ten data of fire position in selected room. We use a fixed starting point for every test. The fire positions in each room are set randomly. The result is compared to the time needed by the previous experiment [5].
Fig 5.Comparison of time spent by each robot to finish their task The time spent by the robot to finish its task has decreased significantly. But the success rate of finishing the task drops for fire placement in Room 1. For the rest of the rooms, the success
rate is slightly increases.
Fig 6.Comparison of success rate of the robots
5. Conclusion Depth first search is efficient for the mobile robot in finding fire and getting back to the starting point without spending much time exploring the whole track. Combined with modified line maze algorithm, this mobile robot is able to get back to its starting point using the shortest path available. Depth first search is highly dependent on tree model built while exploring the track. Median filter eliminates erroneous data of the sensors which is the main cause of the false tree model.
References [1]Kim SY, Hernandez R. Decision Making Process In A Fire-Fighting Robot: Based Off Of Shepherd University's Vulcan Series. Shepherdstown: Shepherd University. [2]"Fire Fighting Robot Rules and Regulations", [PDF Online Document], Available HTTP: http://prog.trincoll.edu/robot/Rules/Rules2012/rules_2012-final-1-letter.pdf [3]Porterfield J, Behera A, Austin J, Afandi S. Firefighting Robot. Oklahoma: Oklahoma State University. [4]Luger GF, Stubblefield WA. Artificial Intelligence, Structures and Strategies for Complex Problem Solving. 2nd ed. California: The Benjamin/Cummings Publishing Company; 1993 [5]Shuwanto F, Frederick, Stefen. Mobile Robot Navigation Using Depth First Search Algorithm. Jakarta: Binus University; 2010.