08-16-2017, 10:29 PM
POWERHOUSE OPERATION, MAINTAINANCE
Micromouse Algorithm Guide:
Here is a tutorial on common algorithms which are used to solve the micromouse maze.
Bellman Method (FloodFill)
The idea is to start at the goal and fill the maze with values which represent the distance from each cell to the goal. When the flooding reaches the starting cell then you can stop and follow the values downhill to the goal.
The simple flooding algorithm works like this:
Start with an array of bytes with one byte representing each cell in the maze.
Put the value 0 into the cell that you are aiming for.
Go through all the cells and make sure that each one has a value that is just one more than its smallest accessible neighbour.
Repeat that last step until you have not changed the value in the starting cell.
Notice that there is no need to pre-initialise the map contents. This algorithm can take a considerable number of iterations. Worst case would see you doing all 256 cells a couple of hundred times. Say that it took you ten instructions per cell (it would be more than that I expect) and each one takes 0.5 microseconds, you might need around 0.25 seconds to solve the maze. In practice, the algorithm will run for as many iterations as there are cells in the longest path. This is likely to be only 20 to 50 cells and so you should be done in much less time. Even so, you don't want to be doing that any more often than you have to. In practice, you only have to when you come to a junction - i.e. a cell with three or four exits. At all other times, your action is predetermined and there is no decision to make.
To save a bit of time, a number of designers divide up their flooding algorithm and do just a bit of it as a time delay routine. Dealing with just one cell is a simple enough task and could be made to run in a fixed time regardless of content. Use this as a time delay in your speed control loop and with any luck, by the time you get to a junction, the maze has been solved in the background. If the solver has not finished then just finish the job while you are waiting to see which way to go.
Modified FloodFill
Mostly programmers use some form of the floodfill method by modifying certain features of the algorithm.
Here is one such illustrated algorithm.
The maze cells are mapped into system memory in the fashion shown in the figure below.
As the cells are mapped with the numbers as shown in the figure, at each cell the robot is expected to take three decisions.
Move to cell which it has gone to least
Move to the cell that has minimum cell value
If possible the robot must try to go straight.
It is evident that these three conditions if followed at each cell position the robot will reach the centre of the maze designated as '0'. The mapping of the cell values in the memory requires huge memory, thus an alternative method was adopted to generate the cell values at runtime.
The robot may be designed to move each cell by exact distance and then the sensor reading is read by the processor. Based on the values and applying the three criteria discussed earlier the robot decides its next action. At every junction if only one side is sensed open then the robot has to move only into that cell. Decision comes into play only when there are two or three sides that are open to navigate. The robot records each location value as it proceeds towards the center. To come back to the starting point it just traces the path back from the memory map.
Tremaux's Algorithm
In about 1882, a fellow called Tremaux described a process for solving any maze. It was described in terms of a physical maze.
What he said was this:
As you walk down the maze, draw a line on one side, say the left, of the path.
When you come to a new junction, take any path.
At a dead end, or a previously visited junction, turn around and walk back the way you came.
If you are on a previously walked path and you come to a previously visited junction, take any new path if there is one available.
Never go down a paths marked on both sides.
Gaston Tarry Method:
In 1895, Tarry published a method for solving mazes. You will need a sack of rocks.
When entering a cell for the first time, place three rocks at the entrance.
If this is not your first visit, place only one rock
Pick an exit according to the following rules, in order:
0 rocks - not been there before, drop two rocks and carry on
1 rock - we have come in from there and we can leave that way. Drop one rock and leave.
3 rocks - This is how we got here in the first place. Only leave that way if there is no other choice.
2 rocks - We have been out that way before so don't go that way again.
Only drop rocks if there are none already except as directed above.
This method will find a route but not all routes. It may not visit all the maze and will not automatically find the shortest route.
Wall Following:
Ask almost anyone how to get out of a maze and they will describe some form of wall following. Keep your hand on one wall and keep going, sooner or later you will get to the exit. This would be fine except for two things.
Firstly, you may have to visit almost the entire maze before you find the exit so this can be a very slow technique.
Secondly, the maze may have islands in it. Unless all the walls are eventually connected to the outside, you may wander around forever without reaching the exit.