Musing about Mazes

Maxwell, at least in his current incarnation, is never going to be a micromouse competitor. He's too big to fit within the maze channels. That doesn't bother me much since I didn't plan on him competing anyway. Still, I think he will turn out to be a great development and learning platform. If, at some point in the future, I get the urge to try my hand at building a competitive micromouse then a lot that I learn by building Maxwell will certainly apply.

Flipping that around the other way, a lot of my thinking and musing about mazes and micro-mice will apply to my experiences with Maxwell. I always enjoyed mazes as a kid, and I'm still enthused by the challenge of a good maze. A real, honest to goodness, challenge would be to build an autonomous robot capable of solving a complex maze all by itself. That could be great fun, even if I don't enter it in any public contests.

A good place to start is with the official micromouse competition guidelines. There's already a lot of information on the web and in books, so I don't have to totally reinvent the wheel.

The official micromouse maze is based on a grid of squares, 16 by 16. The start square is located in one of the corners - for my purposes it doesn't matter which corner since from the mouse perspective they are all effectively the same. I may reference direction from time to time as north, east, south, and west - but that's purely a convenience for my limited human brain. It may turn out that I avoid thinking in terms of left, right, forward, and backward at the macro level of the maze. Those conventions are probably best dealt with at the local or micro, mouse level. At the macro level I want the robot to go north, or east. At the micro level the logic should figure out how it needs to turn, or not turn, to go in the direction I want it too.

The 'finish' squares for the micromouse maze are always the four squares directly in the middle. It hasn't always been this way. In the very early competitions, almost thirty years ago, the finish square(s) could be anyplace. But in order to make things more challenging, especially for the wall following robots, the finish squares were defined to be in the middle.

It's interesting that a lot of the micromouse designs center around the regular grid array. They often use the walls to keep themselves centered in the channels. The robots that don't have a way to accurately determine their relative position sometimes recalculate where they are relative to the maze walls. It has occurred to me that given their dependency on the maze being repeatable and predictable - at least in terms of its dimensions if not its layout, the most difficult maze for them to solve might be one with no internal walls at all.

There are quite a few strategies for solving mazes. Most of them have been covered in some detail on the internet. Right now my favorite approach is the flood-fill, which seems to have several different variations. The basic concept is that you create an array in the robot's memory representing the maze cells. You fill each cell with a number representing its relative distance from the finish squares. In the beginning you (actually the robot) have no idea of where the walls are, so your initial array might look something like the diagram above.

If you could march directly from the start cell to the closest finish cell, it would take seven steps or moves. Pretty straight forward, but non-trivial nevertheless.

If you visualized this array as a topographical map, you could easily imagine the robot moving like water flowing downhill, or as a small marble rolling down the slope to the center.

But, life is never that simple. If it was, it would be totally boring. Mazes have to have walls, and with walls comes complexity. I've overlayed the array with a micromouse maze that was actually used for events in the 1980's. This particular maze is fairly simple and easy to understand. Over the years the competition mazes have gotten progressively more complex and challenging. This maze is a good place to start while we put off the more difficult conundrums until later. After all, you have to be able to walk before you can run, and we haven't even begun to crawl yet.

The next task is to develop a workable procedure for updating the array as the mouse explores the cells. There may be multiple paths, and later we may have to develop a way of determining the most attractive path - but first we have to have a way to place a relative weight in each cell. It's worth mentioning however that we're not necessarily looking for the 'shortest' path to the finish. We want to determine the most efficient path even if it is a little longer in terms of total distance - i.e. cells traversed. The primary reason behind making this distinction is that our robot is going to be much more effective at moving forward in a straight line then he (or she) is at turning at corners. Cornering involves deceleration, turning, alignment, then acceleration. All of that takes precious time. Say, for example, we have two paths to chose from. Path A consists of moving forward one cell, making a turn, then moving 19 cells. Path B consists of moving forward 10 cells, turning, then moving an additional 10 cells. It turns out that path A is going to be measurably more efficient than path B in spite of the fact that both of them involve moving a total of 20 cells. The extreme case would be a series of 20 move/turns.

Let's assume, for the moment, that we can develop a working algorithm to fill each cell with a value that corresponds to its distance from the finish. The result would look like this figure. The robot's run begins in the start cell (red) and subsequently moves from cell to cell based on decreasing the distance between it and the finish (yellow cells). I've colored the cells for one obvious path in green, but there are other alternative paths. Notice that, at least for this particular maze, there are several different sub-paths that can be taken along the way without increasing the total distance traveled.

Looking at it from the 3D perspective, we can easily visualize water running down the path, or our marble bouncing from cell to cell just like it was part of some complex Rube Goldberg contraption.

As I mentioned before, there are alternative paths that the robot could take to transverse the maze. In this figure I've highlighted the major alternative path in a lighter shade of green. Following the robot's path from the start cell, when he gets to the cell marked 44 a decision has to be made between the two '43' cells. Both choices offer the same total distance to the goal, but only one will be faster.... I suspect, though I haven't taken the time to prove it rigourously yet, that the upper path (light green) will turn out to be more efficient. I can see that at some point I'm going to have to give a lot of thought to optimization strategies.

It's not clear to me yet whether or not I need to keep track of which cells have which walls in place. Perhaps, if I'm lucky, that level of detail will work itself out at the micro modeling level and will end up b eing reflected in the macro level array cells. I have considered using a cell_wall array as well where the values in each cell are a simple byte bit map with a 1 representing a wall and 0 representing an opening. This would result in a figure of '0101' representing a cell with walls on it's east and west sides and open to the north and south. If I can avoid having to keep track of the walls/openings it would be better, but at least I have a strategy for doing it if it turns out to be necessary.


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>