Maze Bot - Ben Axelrod - 04/02/2002

This robot was my first attempt at creating a maze solving robot, called a micromouse. The way a micromouse competition is traditionally held, is that the robot is given a large amount of time to run the maze and find the fastest route. Then it runs this route for time, and the fastest time wins.

This was a real challenge for me.  Not only is this a difficult problem, but I also had to work around many limitations of the Lego RCX.  I had to deal with limited memory and sensing capabilities.  Because of this, my robot can only navigate a 5 x 5 cell maze, and it has no automatic wall sensing abilities. I decided to focus on the maze solving algorithm aspect of this challenge rather than hardware / sensing. So I designed my robot with 3 touch sensors on top so that I can tell it where the walls are when it visits each cell. (Yes, I babysat the robot and pushed its buttons when it visited each cell of the maze...)

I researched a variety of maze solving methods and strategies before finally deciding on an algorithm called A*.  This is a standard AI planning algorithm, and is often used in computer chess programs and other games.  The way it works is the robot puts numbers in all the cells, starting at 1 and going up.  If the the path splits, then so does the number line.  If the robot encounters a number that is much higher than its current cell, it will go back and update the cells with the lower numbers. So basically the number in each cell is the minimum distance to the start cell.  Once the robot finds the goal, it can simply follow the numbers back to the start cell. This path should be the most direct route to the goal.  It is kind of like the story of Hansel and Grettle, the way they put down bread crumbs to find their way out of the forest.

The basic algorithm for my micromouse is this:

while (not in goal)
{
	Check for the existence of walls

	if (in dead end)
	{
		turn 180 degrees
	}
	else if (only one way to go)
	{
		turn in that direction
	}
	else if (there exists a traversable cell that has a value which
		is greater than +- 2 of your current index)
	{
		turn in that direction
	}
	else if (one of the traversable cells has never been visited)
	{
		turn in that direction
	}
	else
	{
		turn randomly
	}
	
	drive forward one cell
	
	if (cell is a faster path)
	{
		take that index number
		turn 180 degrees //to update the old slow path
	}
	else
	{
		update cell
		increment index
	}
}

follow bread crumbs back to the start cell

As you can see, it is pretty simple. You may notice that when the robot finds a slower path that it needs to update, it has to physically turn to it and traverse it to update it's memory with the faster route. Typically, this is something that the robot could do mentally, and not have to retrace it's steps. But this would require storing either some representation of the walls of the maze, or some sort of traversable grid. Both of which I did not have memory for on the RCX.

Here is an example maze where the green cell is the start and the red cell is the goal.

Here is an animation showing how the robot would solve the maze.

Here is that same maze completely filled in with the cell index numbers.  You can see how there are multiple cells with the same number, and from any cell you can simply follow the numbers down to get to the start. (While still obeying the walls of course). Notice how both #5 cells have 2 possible #4 cells to go to, but one is illegal because it is through a wall. The A* method is pretty simple to execute, except when you have more than one path that intersect.  Lets walk though the process of filling in the maze just as the robot would.

We have to assume that the robot will make wrong turns.  So here is one of them.  The robot turned right at the first intersection and then right at the next one, leading it to a dead end.  The way the code works, when the robot moves onto a cell that is one less that the previous cell (meaning that it has just come back from a dead end) it does not change the cell.  Actually, it grabs that cell's number to use as its index.   Example: the robot is on the 8 cell.  It turns and moves onto the 7 cell.  Because the 7 cell is one less than the 8 cell, it does not change its value.  Now the robot grabs the number 7 and is ready to mark the next cell with an 8.  Except that the next one (6) is one less than 7.  It continues like this until it gets to the 5 cell.  On the 5 cell now, the robot has the value 5 and when it moves on to the empty cell above it, marks it with a 6.  This might be a little clearer once you see the next step.

Here the robot has moved up after going through the 5 cell and has stopped at the 9 cell.  It now has a major decision.  It found a cell that is less than 2 minus the current cell.  Meaning that there is a shortcut it should remedy. Following the algorithm above, it now has to move onto this #2 cell.  Just like finding a dead end, it now takes this cell's value and backtracks.  It will now update the old path with a faster path.

Now the robot is done updating the slow route and is at the upper 6 cell.  Now the robot has no real motivation to go anywhere, so it randomly wanders the maze until it finds either a 0 cell or a path that needs to be updated.

This code is not optimal at all. I think it is basically the bare minimum to solve a maze in this manner. Some possible improvements to the code.

• Don't go to goal and do back trace when there are untouched cells left. With the current code, the robot may find a sub optimal path to the goal by chance, and never look for a better one.
• Rule out large portions of the maze if you know the dimensions of the maze and the locations of the start and goal, and hit an edge.
• Store locations of unvisited cells to revisit
• Mentally update portions of maze instead of physically going to them. (This requires storing the wall locations, or an accessibility tree.)

Here is the NQC code.