Which Way Do We Go, Which Way Do We Go…

Some further thoughts about micromice and mazes during the preliminary maze exploration phase ...

As the mouse moves from one cell to the next it will face some decisions. In this drawing, for example, the mouse has just entered a new cell. It knows that there is an opening to the east (it's current right) and it can intuit that there is a wall on the left even though it hasn't moved far enough into the cell to prove that as a certainty. Transitions from one cell to the next are a real concern that eventually will have to be dealt with since in spite of the rigorously defined maze construction specification there are likely to be deviations. The floor of the maze might be more slippery than we expect, or there may be non-trivial gaps in the floor between cells, and certainly between adjoining walls.

In any case, after some finite movement into the cell, the micromouse should be able to make some solid observations of it's new environment.

In the drawing the mouse has yet to determine the cell state directly in front of it. A question that needs to be considered is whether or not directional decisions should be taken on partial information. Should the mouse move to the center of the cell, then decide whether to move north or east, or should it first determine if there is an opening to the north first?

It would be tempting to just assume that given the choice the mouse should always move in a straight line directly ahead until it encounters a wall. At that point it should turn - if possible - or backtrack until it can turn. After all, turns take time, and we want to explore the maze as quickly and as efficiently as possible.

However, if we assume for a moment that the mouse moves to the cell center, then executes a 90 degree turn so that it can proceed to the east, an interesting thing happens. In making the turn it's 'left' wall sensor array moves into position to sense whether or not a wall exists to the north. If there is an opening there, it will probably, but not necessarily, come back to explore that path at some later point. If, on the other hand, a wall exists, it just needs to update it's maze configuration data in memory.

An alternative approach, perhaps more better, would be to design the front sensor so that it extends far enough ahead to sense the presence of a wall while the mouse is centered in the cell. If that turns out to be more effective, then it might make sense to outfit the mouse with a rear sensor as well so that it can move in either direction without having to make any 180 degree turns.

If we use a triple wall sensors on both the left and right sides of the mouse it should be relatively easy to keep the mouse centered in the maze channels. If the sensor arrays are adjusted correctly then only the center sensor in each array should indicate the presence of a wall. If the mouse starts to drift towards one wall or the other, the sensor states will change, and the mouse can course correct to compensate. If all three sensors in a single array indicate no wall, we may (hopefully) have sensed an opening.

There should be an added benefit to using triple sensor arrays. Since the outermost sensor on each side of the mouse overhangs the wall on its side, it should (yet to be proven) also sense the presence or absence of walls in adjoining cells!

For example, in this diagram the mouse moved only in a north direction from the start cell until it encountered a wall. During that movement it gathered complete state information on the 11 cells it transversed, plus partial state information for the 11 adjoining cells to the east.

This implies that we may not have to physically transverse each of the 251 active cells (256 total cells minus the start and finish cells) in order to map the maze. Depending on the maze layout, this may represent a considerable time advantage.

Another question that deserves more thought is the priority of turn directions given a choice. It may be effective to give priority to moving directly ahead or behind over making a turn. But, given a choice between a left or right turn, which direction should the mouse favor?

It seems apparent, though I might change my mind later, that the turn priorities should vary based on the mouse's relative location in the maze. Visualize the maze divided into four quadrants - green, blue, red, and yellow. It may be that the best strategy in the blue quadrant is to prioritize turns in a east/south/west/north order while in the yellow quadrant the best strategy might be exactly the opposite. After some experimentation and analysis more complex segmentation may suggest itself.

Of course all of this assumes unlimited computing power, speed and available memory - which is never the case. When we get around to making the hard design/implementation decisions the algorithms may have to be simplified or eliminated completely - but that's the way it is in the real world. You never have enough time, money, and resources for ideal solutions, so design compromises are part and parcel of life as an engineer - even for the hobbyist engineer like me.


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>