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.