Maze Solving Robot Simulation - Revision history

Xkrep33 at 21:18, 16 January 2016

2016-01-16T21:18:45Z

Xkrep33 at 18:13, 16 January 2016

2016-01-16T18:13:53Z

Xkrep33 at 17:44, 16 January 2016

2016-01-16T17:44:19Z

Xkrep33 at 17:39, 16 January 2016

2016-01-16T17:39:32Z

Xkrep33 at 16:52, 16 January 2016

2016-01-16T16:52:41Z

Xkrep33 at 16:03, 16 January 2016

2016-01-16T16:03:50Z

Xkrep33 at 16:01, 16 January 2016

2016-01-16T16:01:05Z

Xkrep33 at 15:49, 16 January 2016

2016-01-16T15:49:37Z

Xkrep33 at 14:50, 15 January 2016

2016-01-15T14:50:15Z

Xkrep33: Created page with "Introduction =Problem definition= =Method= =Model= =Results= =Conclusion= =Code="

2016-01-15T14:45:56Z

Created page with "Introduction =Problem definition= =Method= =Model= =Results= =Conclusion= =Code="

New page

Introduction

=Problem definition=

=Method=

=Model=

=Results=

=Conclusion=

=Code=

@@ Line 13: / Line 13: @@
 For simulation is used NetLogo software (2D version). NetLogo was chosen as the most appropriate tool for the simulation because it makes it easy to program the robot's behaviour while allowing visualization of his behaviour. NetLogo also allows to customize the user interface. User can test how a robot algorithm works in real-time and simultaneously monitor other indicators.
-===Auto Robot===
+===Autonomous Robot===
 Robot is able to move up, down, left and right (viewed from above). He is able to find the way out without any intervention. Robot is able to move in any environment (maze) where exists at least one possible way out.
@@ Line 42: / Line 42: @@
 ====Visualization====
-The middle section shows the maze and selected the type and number of robots.
+The middle section shows the maze and selected type and number of robots.
 [[File:Xkrep33 Vizualization.PNG]]
@@ Line 122: / Line 122: @@
 [[File:MazeSolvingRobotSimulation.zip]]

@@ Line 1: / Line 1: @@
 One of the typical tasks of the basics of robotics is to build a robot that is able to find his way out of the maze. For this task are used robots that can move along a flat surface, turn and scan the area beneath them at the same time. Maze is represented by a black line on a white surface. The robot moves along the black line, and his aim is to find the end of the maze, which is usually represented by large black rectangle. Task respectively robot is commonly called Line Maze Solving Robot.
-The robot is driven by preloaded algorithm. There are many different algorithms and their modifications. One of the basic algorithms is Left Hand Rule or Right Hand Rule. The algorithm works as follows, a robot prefers left movement before moving forward. If this rule cannot be applied, then prefers forward move instead right move. The algorithm works for all mazes that cannot contain infinite loop, which the robot is not able to solve.
+The robot is driven by preloaded algorithm. There are many different algorithms and their modifications. One of the basic algorithms is Left Hand Rule or Right Hand Rule. The algorithm works as follows, the robot prefers left move before moving forward. If this rule cannot be applied, then prefers forward move instead of right move. The algorithm works for all mazes that cannot contain infinite loop, which the robot is not able to solve.
-Algorithm Left Hand Rule (Right Hand Rule) is used for example for the initial exploration of the maze (for more information see for example this presentation: https://www.pololu.com/file/0J195/line-maze-algorithm.pdf). robot passes through the maze and finds its end. During a trip through the maze memorizes all the steps. Stored step data is then robot able to optimize and find the shortest route to the destination. During the second stage the robot can avoid the blind paths and solve the maze using shorter way. As part of this simulation is implemented only the first part - finding way out of the maze. This video shows how the process works: https://www.youtube.com/watch?v=Z0LIO0tEZG4.
+Algorithm Left Hand Rule (Right Hand Rule) is used for example for the initial exploration of the maze (for more information see for example this presentation: https://www.pololu.com/file/0J195/line-maze-algorithm.pdf). Robot passes through the maze and finds its end. During a trip through the maze memorizes all the steps. Stored step data is then robot able to optimize and find the shortest route to the destination. During the second stage the robot can avoid the blind paths and solve the maze using shorter way. As part of this simulation is implemented only the first part - finding way out of the maze. This video shows how the process works: https://www.youtube.com/watch?v=Z0LIO0tEZG4.
 ==Problem Definition==
-The primary goal is to create an autonomous robot which is Able to find way out of the maze. The robot is programmed and his movements cannot be interfered after he starts. The robot must be driven by a non-trivial algorithm that includes randomly generated numbers. The robot must be able to find a way out of maze in a finite time. It means he should not get into an endless cycle of no return.
+The primary goal is to create an autonomous robot which is Able to find way out of the maze. The robot is programmed and his movements cannot be interfered after he starts. The robot must be driven by a non-trivial algorithm that includes randomly generated numbers (solution for endless loop situations). The robot must be able to find a way out of maze in a finite time. It means he should not get into an endless cycle of no return.
 Secondary objective is to determine what is the difference between a primitive robot and the robot uses a smarter algorithm. Primitive robot is e.g. such a robot who moves only straight forward and if he encounters an obstacle turns left.
@@ Line 47: / Line 47: @@
 ====Statistics====
-Statistics show three main indicators. The first indicates the number of robots who remain in the maze. This indicator captures all the robots who have not found their way out of the maze yet. The second indicator is a graphical representation of the number of robots remaining in time. The third indicator is the average number of steps that robots needed to solve the maze. All indicators are shown, after running a simulation.
+Statistics show three main indicators. The first indicates the number of robots who remain in the maze. This indicator captures all the robots who have not found their way out of the maze yet. The second indicator is a graphical representation of the number of robots remaining in maze during the time elapsed. The third indicator is the average number of steps that robots needed to solve the maze. All indicators are shown, after running a simulation.
 [[File:Xkrep33 Statistics.PNG]]
 ==Results==
-The results are shown in the table. The table contains two figures for both types of robots. Indicator Number of robots remained means how many robots remained in maze when one type of robot solved the maze. If there were more than one robot at the beginning, so it means that all robots of one typy solved the maze. Second indicator Average number of steps shows how many steps all robots of one type made when robots of one type solved the maze. If robots of some type were stuck in infinite loop situation then numbers are provided in brackets.
+The results are shown in the table. The table contains two figures for both types of robots. Indicator Number of robots remained means how many robots remained in maze when one type of robot solved the maze. If there were more than one robot at the beginning, so it means that all robots of one type solved the maze. Second indicator Average number of steps shows how many steps all robots of one type made on average when they solved the maze. If robots of some type were stuck in infinite loop situation, then numbers are provided in brackets.
-There were thousand of robots of each type at the beggining of each simulation.
+There were one thousand of robots of each type at the beginning of each simulation.
 {| class="wikitable"
@@ Line 112: / Line 112: @@
 ==Conclusion==
-Simulation was done in all seven mazes. Simulation was always done with a sample od thousand robots of each type (two thousand robots at once). The proposed algorithm of intelligent robots were proved. Robots using a smart algorithm base on Left Hand Rule algorithm and generating random numbers, have always been able to solve the maze. Only in one case (maze No. 6) were primitive robots faster than intelligent one. Even in this case, however, all intelligent robots solved the maze. The primary objective of the simulation, which was to create autonomous robot that does not fall into an infinite loop, was achieved.
+Simulation was done in all seven mazes. Simulation was always done with a sample of thousand robots of each type (two thousand robots at once). The proposed algorithm of intelligent robots was proved. Robots using a smart algorithm base on Left Hand Rule algorithm and generating random numbers, have always been able to solve the maze. Only in one case (maze No. 6) were primitive robots faster than intelligent one. Even in this case, however, all intelligent robots solved the maze. The primary objective of the simulation, which was to create autonomous robot that does not fall into an infinite loop, was achieved.
 The results table clearly shows that primitive algorithm was not very effective. In six of the seven cases, the robots who used this algorithm, get into an endless loop with no return. Only in one case, all primitive robots get out of the maze, and even faster than so called intelligent. It was rather a coincidence, because the maze No. 6 is the only one that could be resolved only by moving straight with combination of left turning in case of an obstacle.
-It can be said that the algorithm used for intelligent robots was relatively effective and above all its results were very stable. The only exception was a maze No. 7. Maze No. 7 is essentially infinite space with one exit in the middle. But this maze were also solvable for intelligent robots.
+It can be said that the algorithm used for intelligent robots was relatively effective and above all its results were very stable. The only exception was a maze No. 7. Maze No. 7 is essentially infinite space with one exit in the middle. But this maze was also solvable for intelligent robots.
 ==Code==

@@ Line 3: / Line 3: @@
 The robot is driven by preloaded algorithm. There are many different algorithms and their modifications. One of the basic algorithms is Left Hand Rule or Right Hand Rule. The algorithm works as follows, a robot prefers left movement before moving forward. If this rule cannot be applied, then prefers forward move instead right move. The algorithm works for all mazes that cannot contain infinite loop, which the robot is not able to solve.
-Algorithm Left Hand Rule (Right Hand Rule) is used for example for the initial exploration of the maze. The robot passes through the maze and finds its end. During a trip through the maze memorizes all the steps. Stored step data is then robot able to optimize and find the shortest route to the destination. During the second stage the robot can avoid the blind paths and solve the maze using shorter way. As part of this simulation is implemented only the first part - finding way out of the maze. This video shows how the process works: https://www.youtube.com/watch?v=Z0LIO0tEZG4.
+Algorithm Left Hand Rule (Right Hand Rule) is used for example for the initial exploration of the maze (for more information see for example this presentation: https://www.pololu.com/file/0J195/line-maze-algorithm.pdf). robot passes through the maze and finds its end. During a trip through the maze memorizes all the steps. Stored step data is then robot able to optimize and find the shortest route to the destination. During the second stage the robot can avoid the blind paths and solve the maze using shorter way. As part of this simulation is implemented only the first part - finding way out of the maze. This video shows how the process works: https://www.youtube.com/watch?v=Z0LIO0tEZG4.
 ==Problem Definition==
@@ Line 53: / Line 53: @@
 ==Results==
 The results are shown in the table. The table contains two figures for both types of robots. Indicator Number of robots remained means how many robots remained in maze when one type of robot solved the maze. If there were more than one robot at the beginning, so it means that all robots of one typy solved the maze. Second indicator Average number of steps shows how many steps all robots of one type made when robots of one type solved the maze. If robots of some type were stuck in infinite loop situation then numbers are provided in brackets.
 {| class="wikitable"

@@ Line 22: / Line 22: @@
 The environment is adapted to the possibilities of the NetLogo. Environment is represented by the World in NetLogo. The World consists of black, grey and green patches. Black patches represent the path where robot can move. Grey patches represent walls, the robot cannot enter them and finally the green patches are the door out of the maze.
-The attached archive contains seven different mazes. Environments vary to demonstrate that the robot is able to avoid infinite loop situations. Maze was created using the Pac-Man Level Editor, which is part of the Library Models in the NetLogo program. Editor has been adapted for the needs of this simulation in accordance to the Creative Commons license. The revised editor served only as a tool for quick creating of a various environments, for the simulation itself is not necessary, therefore the editor is not part of the archive.
+The attached archive contains seven different mazes. Environments vary to demonstrate that the robot is able to avoid infinite loop situations. Maze was created using the Pac-Man Level Editor, which is part of the Library Models in the NetLogo program. Editor has been adapted for the needs of this simulation in accordance to the Creative Commons license. The revised editor served only as a tool for quick creating of a various environments, for the simulation itself is not necessary, therefore the editor is not part of the archive. Size of all seven mazes is 31 x 31 patches.
 ==Model==
@@ Line 55: / Line 55: @@
 {| class="wikitable"
 ! style="font-weight: bold;" |
 ! colspan="2" style="font-weight: bold;" | Intelligent robots
 ! colspan="2" style="font-weight: bold;" | Primitive robots
 |-
-| style="font-weight: bold;" | Maze no.
+| style="font-weight: bold;" | Maze No.
 | style="font-weight: bold;" | Number of robots remained
 | style="font-weight: bold;" | Average number of steps
@@ Line 109: / Line 110: @@
 ==Conclusion==
 ==Code==

@@ Line 52: / Line 52: @@
 ==Results==
 ==Conclusion==
 ==Code==

@@ Line 38: / Line 38: @@
 ====Settings====
 Settings consists of five control elements. Three of the five elements are the chooser type and allow to set up one of the seven mazes, setting robot type and number of robots. Mazes are stored in separated files and they need to be stored in the same folder as the file with nlogo extension. There are three combination of robot type. The maze can display separately each of the two types (intelligent and primitive) robots, or both types simultaneously. Selecting the number of robots adjusts how many instances of each type of robot will be displayed in the visualization. In the case that is shown more than one instance of robot, robots are not interact each other. Displaying multiple robots simultaneously serve only for better understanding of the behaviour of intelligent and primitive robot in shorter time. The remaining two buttons is used to apply the selected settings and run the entire simulation.
-[[File:xkrep33_Settings.jpg]]
 ====Visualization====
 The middle section shows the maze and selected the type and number of robots.
-[[File:xkrep33_Visualization.jpg]]
 ====Statistics====
 Statistics show three main indicators. The first indicates the number of robots who remain in the maze. This indicator captures all the robots who have not found their way out of the maze yet. The second indicator is a graphical representation of the number of robots remaining in time. The third indicator is the average number of steps that robots needed to solve the maze. All indicators are shown, after running a simulation.
-[[File:xkrep33_Statistics.jpg]]
 ==Results==