-
Upcoming Events
-
Feb6Mon
-
Apr14Sat
-
Tag Archives: maze
Finishing the new maze floor
The walls and posts arrived and so it was time to finish the maze floor.
Painting the floor
Once the panels dried out, it was time to paint them.
Making the floor
Now that I had the layout, the next step was to cut and drill the plywood. While there are many techniques for doing this, I ended up getting help from a friend who has access to water jet cutters to … Continue reading
Designing a maze floor
Given standard sizes for plywood, here is a pattern I used to make a maze floor.
How many walls do you need for a square maze?
At the Japanese contest, Peter said there is a closed form solution for the maximum number of walls a legal micromouse maze can have.
Adachi micromouse maze solving algorithms
Going through some old notes, I came across reference to the micromouse maze solving methods described some time ago by Adachi in Japan. While these are apparently quite well known in Japan, they are, as far as I can tell, almost completely unknown in the West. At least, I can’t find any description of them in English anywhere on the web. After a lot of hard work with the Google translator and some assistance from Lem Fugitt, I think I have them pieced together…
Of course, the methods described here are not actually unknown in the West. What I mean is that the descriptions given by Adachi are unknown. Adachi was a member of the Fukuyama Microcomputer Club and made a presentation outlining these search algorithms in 1984 while still a student. He describes four methods that can be employed by a micromouse when searching the maze. Efficient searching is particularly important because of two kinds of penalty imposed by the various sets of rules. One of these is the search time penalty found in the UK rules. Here a fixed proportion of the total time spent in the maze is added to each run time. Clearly, the less time spent searching for the best route, the less will be the penalty. Other rules, may severely limit the total time allowed in the maze. Although there may not be a specific time-related penalty, a micromouse needs to get the search done quickly to avoid running out of time to perform the speed runs. In Japan, each mouse is only allowed a limited number of runs between the start and finish. Here it is vital to ensure that the start is only re-visited when the mouse is ready to do a performance run.
Here is my interpretation of the four methods. If I have any of it wrong, or you have improved descriptions to offer, please get in touch.
Adachi Method 0
The micromouse makes repeated runs back and forth between start and goal. On each pass, the mouse is simply looking for the best route from where it is to the current target. When the maze solver shows a route from start to goal that does not pass through any unexplored cells, the shortest route has been found.
This can be very time consuming. It may be that the mouse determines the best route shortly after setting out from the start yet it must travel all the way to the goal and back. Note that the best route back may not be the same as the best route there. Furthermore, the mouse is using precious runs and will almost certainly run out of runs under the Japanese rules.
Adachi Method 1
Here the mouse is trying to find unexplored cells on the calculated best route from start to goal. The method requires that, at each decision point, the maze is solved twice. First, it calculates the best route from start to goal. Having done that, it must then determine a route from the current mouse position to the unexplored cells on the previously calculated rout. The route calculations should not be too time consuming with a modern processor. As the shortest route from start to goal may change as the mouse explores, it could find itself looking for unexplored cells in different routes and thus waste time. I can’t picture a case where this would be a problem and will need to do some testing to see that in action.
Adachi Method 2
This method essentially corrects the major shortcoming of method 0 – the need to visit the start and goal on each pass. The micromouse still alternates between searching for the start and the goal but, as soon as the path to the current target is optimal, the direction reverses and the mouse looks for the other target. The distance travelled while searching should reduce. It would seem that the mouse will need to cease searching when the path to both goal and start from the current mouse position is optimal. I would expect this to work well if the route is recalculated in every cell.
Adachi Method 3
[I don't really understand this one]
First use method 0 to find the goal. Once the goal has been found, switch to method 1. This seems to be an optimisation of method 1 using a faster initial search.
Once again, if you have any suggestions relating to these, please let me know.
Decimus the wall follower
We often tell beginners that they can learn a lot by building a non-contact wall following micromouse. If it can keep track of where it is and knows when it is in the centre of the maze, most of the hard problems have been solved. To get to that stage, you need working sensors, reliable motor control and good information about the maze and the mouse’s position in the maze…
Beginners often get hung up about the whole maze thing. the issues of solving it in particular. These fears are often unfounded as the maze handling is relatively easy. Once you know how it is done, it is just a bit of software that you can run on your PC to test it out. Most maze builders seem to do that.
The challenges in building a micromouse lie in things like building reliable mechanicals, implementing good control algorithms for the motors and having good sensors. The motor control could be the hardest part of the software. There are any number of examples of how to make a digital servo or positioner. They all overlook a key feature of the mouse controller. First, you don’t know where a move will finish when you start it. That makes most of the servo algorithms nearly useless. Second, there are two wheels (on most mice) that need to be controlled together to give the mouse a reliable position and rotation.
Decimus, of course, has been designed from the start as a full maze-solving micromouse. However an essential part of the commissioning of a mice is, I believe, putting it through the wall-follower stage. The early phases of making a mouse require that you test each of the subsystems independently and then start to get them to work together. Once you are able to get the mouse moving, you need to link in the sensors to provide steering control in the maze.
Eventually, there will come a time when the mouse is able to run a maze. This is most easily accomplished if there is a command processor that can take a string of commands such as FWD4, L90, FWD4, R90 and so on. By planning for this end, you create the means by which the mouse will do everything else.
Following a wall is just a simplified case of the exploration of an unknown maze. With Decimus, I do that by giving the mouse a single command to move forward 1 square. Half way through the move, the sensors can see into the next cell and are able to detect any walls. The map can then be updated and a decision made as to what the mouse will do next. For the wall follower, we just look to see if the mouse can turn left. If so, the move is allowed to finish and a pair of moves, L90, FWD1, is sent to the command processor and we loop back. If there is a wall ahead and to the left but we can turn right, the commands will be R90, FWD1. Walls on all three sides need the command pair R180, FWD1. Walls to either side and none ahead are easily dealt with by directly manipulating the distance the mouse thinks it has left to travel in its single-square move. Simply add the length of one square to the final position and the mouse will carry on as if nothing had happened.
Here is a short video of Decimus following the left wall in this fashion until it reaches its target square. At the target square, it pauses for half a second and then follows the left wall to the start.
For a full solver, the only difference in this behaviour is that, having recorded the walls and updated the map, the mouse will need to solve the maze and use the information from that to decide which way to turn.
Add to Google