1

MacroMouse: A Maze Solving Robot

Final Report
Gagan Awhad, Kris Marose, Xi Qiao, Carl Magnuson
{awhad001, mar0057, qiaox019, magnu213}@[Link]
Department of Computer Science and Engineering
University of Minnesota
Minneapolis, MN 55455

Abstract—This report is based around the robots in- on active range finder sensors, such as laser scanners,
volved in a MicroMouse competition, that is, a robot sonar [3], and infrared sensors. There are other systems
which is able to search and solve a maze. This project based on the sensor fusion approach [4]. The mapping
will focus on the design of such a robot, including the algorithms used can be classified as deterministic based
advantages and disadvantages of different robot designs.
approach or probabilistic based approach which includes
It will also touch on methods for solving a maze, specifically
focusing on a real-time search, where the robot searches
those using methods of Bayesian Probability. Based on
an unknown maze until it finds a goal. The project also different task environments, one may apply indoor map-
includes localization and mapping of the maze in real time. ping algorithms verses outdoor mapping algorithms, as
well as statistical algorithms verses dynamic algorithms
[5].
As the robot is also keeping track of its position, this
I. I NTRODUCTION
project is in fact also related to SLAM (Simultaneous
Research in robotic maze solving problems has been Localization and Mapping). SLAM is a technique in
highly active for the past few decades in both robotics which a robot builds a map of an unknown environment
and artificial intelligence. The general objective for this while keeping track of its position relative to the map
kind of problem is to use a mobile robot to navigate an it is creating [6]. The primary difficulties involved in
unknown or semi-known environment and to accomplish SLAM however is the representation of the virtual world
some specific tasks. Generally, a common task is to nav- versus real world. Any inaccuracies related to error
igate from the starting point, to the goal, and sometimes from the robot’s sensing or odometry propagates into
back to the starting point again. the virtual world and results in an inaccurate map of
One interesting robotics event related to the maze solv- the real world [7]. This project is a subset of SLAM,
ing problem is the MicroMouse robotics competition, where rather than a full scale version, it only deals
which was first held in 1979 in New York, and since with discrete dimensions of cells of the maze. This
then various competitions similar to this have started provides some ability to correct for the inaccuracies of
around the world. Small, self-contained robots are used the robotic system as each cell of a map has pre-set
in the competition which attempt to map, then solve and discrete dimensions that accurately map to the real world
navigate a previously unseen maze. This project isn’t (where the real world is a maze that is).
necessarily attempting to recreate a robot that would be Specifically relating to mazes, there are quite a number
used in this competition, but is attempting to address a of algorithms which have been studied and can be
similar problem - robots mapping and solving mazes. implemented to search for a goal in a maze. Each
different algorithm has its advantages and disadvantages,
II. R ELATED W ORK generally trading algorithm run time for solution opti-
The robotic mapping problem is one of the funda- mization. Simple approaches toward maze solving which
mental problems in the area of mobile robotics. Much also appear somewhat naive would be wall following or
research work has been done on it in the past several random walking. However, given the general randomness
decades [1]. Robotic mapping systems have been imple- of a path in a maze, these simple algorithms are actually
mented using many different kinds of the sensors. Some not that terrible of an approach. Unfortunately they will
systems use a video camera or a stereo camera and fol- almost never provide an optimal solution. There are other
low a vision based approach [2]. Other systems are based more comprehensive approaches to finding paths in a
 2

maze, however they are usually subject to taking more different views of the maze and data association will be
tome to solve the problem. required. Employing motion estimation techniques will
The most traditional approach is a simple depth first also aid in reducing errors caused by noise in data from
search, however despite guaranteeing a solution if it the robot’s sensors.
exists, it will not necessarily be the shortest solution [8]. The other subproblem is the robotic path planning
The most popular maze searching algorithm that is most problem. The objective in this part is to provide the
commonly used in MicroMouse competitions is Bellman optimized routing choice according to the knowledge
Flooding [9]. This method involves starting from the goal of the map. In this process the robot needs to search
position in a maze, and computing the distance to reach an applicable path to navigate the maze. There are two
that position as you ’flood’ outward from the goal. This strategies for the task at hand. One is to build the
however requires that the entire maze already be known, map first, then search for the path having the complete
which is not the case for this project. It could however information of the map. This can provide the optimal
be applied to quickly find a solution after the robot is solution in terms of distance, but requires the robot to run
finished mapping the maze. through the entire maze to complete the task. Another
way is trying to find the path while the robot is exploring
III. P ROBLEM D ESCRIPTION the maze. In this case the problem will be an on-line path
The goal of this project is to design and implement planning problem. The latter method was implemented
a robotic system which attempts to explore an unknown in this project, but there was not time to implement the
maze, constructs a partial map (or the whole map) for former - making a complete map of the maze and then
the maze , and accomplishes specific maze solving tasks. finding an optimal route between the initial and goal
The most common of tasks would be that of navigation positions. Although, given the current setup, the project
from one point to another. In this, the robot would be is fully able to implement this complete mapping feature.
given a pair of coordinates which indicate the starting
point and the objective point (or goal), respectively. The
IV. M ETHODS
robot is then asked to find an optimized (or a non
optimized) path to connect these two points. The original main choices for a robot were between
Along with the starting point and the objective point, the Pioneer, iRobot, and Explorer; but it has been de-
the robot can also be provided with some information termined that the Explorer will suit this projects needs
about the dimensions of the maze. For simplicity, the best considering the circumstances. The Pioneer may be
maze will be considered to be broken down into indi- much easier to program than the Explorer, however it
vidual cells of standard unit dimensions. Each of these was determined that the sheer size of the Pioneer would
cells will have 0 to 4 walls, and the maze is formed by not fit the specifications of this project. The iRobot
the interconnection of these cells. There will generally on the other hand is easier to program and would not
be at least one path connecting the starting point to present a size issue, however availability and time issues
the objective point, however in the case that there were eliminated its candidacy for the project. Therefore it was
none, the robot would be able to show that there is no initially determined that the Explorer robot, despite the
path leading to the goal. Dividing the maze into cells difficulties that may arise in programming, would be the
implies that the a wall or the absence of a wall, with best fit to the project.
unit dimension can be placed only at discrete intervals The first focus of our work was to familiarize our-
while building the maze. selves with the Explorer robot, set up the build environ-
The proposed task can be broken down into two sub- ment and implement and test simple motion and sensing.
problems. One of them is the robotic mapping problem. There were a number of difficulties however in getting a
Since the maze environment is fairly unknown to the working build environment such as changed and undocu-
robot, (the robot only has a few assumptions about the mented access passwords to online data sources and dead
environment configuration), it needs to explore the maze links to important files. After creating a working build
and record the map. environment the problem was to test simple motion and
Furthermore, in order to record the map information, sensing. Motion was already written into the Explorer
an appropriate approach to describe and store the virtual Player driver, however there was no existing code to read
map needs to be chosen. There are many techniques values from the two infrared sensors mounted on the
which attempt to accurately record a representation of front of the robot. Reading this data would be essential
the real world map [1]. To construct a consistent map, it to localization and decision planning for mapping the
is necessary to have integration of the observations from maze.
 3

We were able to implement the necessary sensing and orientation, and motion primitives were in place
functions in the Explorer Player driver and wrote code to do simple rotations and single cell movement, all
for the Roboaudiostix board which handles the sensor that is required for localization is to keep an updated
I/O to communicate the sensor data to the Player driver (x,y) location and an orientation. Because of the motion
over the i2c bus. However in testing the sensing code primitives it was very easy to keep this position data up
we were receiving nonsense data from the sensors and to date. The motion functions were assumed to correctly
expect there is some fault in the code running on the move the robot between cells without drift so that the
Roboaudiostix. Due to time constraints of the project and calculated position at all times matched the robots’ actual
continuing difficulties in reading sensor data we made position. In the case of the simulation this assumption
the decision to stop work on the Explorer sensing and use held true, and much work was done in the real world
a fully functional and well documented robotic platform trials to keep this assumption true.
- the Pioneer robot. Since the maze is well defined and we have strong
The decision to move to the Pioneer platform changed assumptions of the walls, it’s less difficult to maintain a
many of the physical implementation details. It would map than mapping in an unstructured environment. We
not be possible to build a very large physical maze due use a matrix to record the map, and it is updated by
to the size needed for each cell to fit the Pioneer plus the sensing function on each step. We didn’t consider
some padding room to allow for minor drift and impre- the case of inconsistencies in the map, which is a
cision. The Pioneer does however have the advantage of common issue in a dynamic environment - where the
having a 180 degree laser sensor which is very precise. sensing data at different views could be in disagreement
This became essential in the localization and motion due to moving objects or the errors from the sensor.
problem because as we would find out, its odometry The robot always moves forward to one of the four
is very poor. We also lost some of the direct hardware directions, North, East, South, West, so we only need
control we would have had with the Explorer in moving to be concerned about the walls on these directions.
to the Pioneer which incorporates its own smoothing
We use the data from the laser sensor to detect the
and trajectory to commands its Player driver receives.
range of the front, right and left side walls. The average
There was fortunately a much smaller learning curve to
ranges are calculated to reduce the noise of the sensor.
working with the Pioneer as we were already familiar
If the range is approximately half the size of one cell,
with it from a previous assignment and because it is
a wall on that direction is declared. The threshold is
a popular commercial product with many resources for
chosen carefully, because if the robot is drifts far away
help and information.
from one side of a wall, the wall would be recorded
V. R ESULTS incorrectly and searching may fail as well. One method
A. Simulation Results of error correction that the sensing does is remapping a
cell each time the robot enters it. This method can correct
previous errors but also could introduce new ones. A
voting or averaging algorithm could be useful in the case
of multiple readings in disagreement, or the robot could
simply re-sense a cell if it is noticed that a new reading
is in conflict with a previous one.

Fig. 1. Simulation Run

Localization in the simulation was done in a simple

manner. As the robot was aware of its initial position Fig. 2. Incorrect Wall Sensing
 4

A simple function for motion was used which took than other search algorithms (there is always a chance
a North/South/East/West position as well as the robots that most optimum path is chosen randomly) there exists
current orientation and moved it to the desired position. a high possibility of the robot getting caught up in
In this way all of the other functions in the maze solving infinite loops.
program could assume a maze of discrete segments and There are many existing algorithms to find the shortest
not have to account for the continuous world in which the path form the initial position to the final position, for
robot operated. The goTo Player function was used in the example the Bellman flooding or the A* search. However
simulation to accomplish the task of movement, and the they can be used only when the whole maze is known
motion function updated global position and orientation to the algorithm a prior to searching it, so they do not
variables used by the search functions in the program. apply directly to this project.
The advantage of the goTo function was that all the The algorithm that we extensively used was a modified
motion primitives involved in moving the robot were version of the online Depth First Search. It was a
taken care of by this function. This greatly simplified complete search and therefore it would find a goal if
one area of programming the robot in the simulation, one existed or search the whole maze if it did not. It was
but it was later found to not port to the Pioneer like we also modified to be ’online’ so that it avoided shifting
expected, which is discussed in greater detail further on search between the nodes at different branches of the
in this report. trees. Also, when confronted between a choice of two
As a maze is discrete and its dimensions also well directions for the next move moving between two cells
defined, the simplest virtual representation of it is a it choses the one that is closest to the goal using the
two dimensional array of individual cell structures. The manhattan distance as a heuristic.
program for this project was written in C++, an object
oriented programming language, so we were able to take B. Experimental Results
advantage of this and write classes for each cell as well
as the maze itself, keeping all cell and maze mutators
and other functions specific to each class. This provided
for an environment which was much easier to envision,
which in turn made the remainder of the programming
a less difficult task. More specifically, this higher level
abstract of the maze allowed for a much easier process
of designing the search algorithm.
The main structures used in the program were a simple
position structure, as well as a cell and maze class. The
position structure simply contained x and y coordinate
information for referencing a position in the maze. As
well it also maintained an absolute orientation direction Fig. 3. Real World Run
of North, South, East, or West; relating to the direction in
which an instance of the position structure was pointing. In order to implement the project into the real world
Each cell class contained information on what the known we had to build a maze of a size that was big enough for
status of its four walls were (unknown, not present, or the robot as well as complex enough to demonstrate the
present). The cell class also provided for retrieval and maze solving capabilities. The maze was 12ft. x 12ft.
mutating of each of these values. Finally, the maze class with each cell having the 3ft x 3ft dimensions, which
contained all relevant information to the maze itself, produced a 4x4 maze. It was built using the cardboard
including width, height, starting position, goal position, from boxes used for transporting goods, as well as some
and the two dimensional array of cells - the virtual 6ft wooden boards running around the edge of the maze.
representation of the maze. All walls were approximately 1ft tall, which was enough
In each cell, the robot has to choose from the possible for the SICK laser range finder on the Pioneer to detect
directions one that will lead it to the next state. The the walls.
choice can be made based on priority. The priority The main problem we discovered when trying to
is given by what is known as the search algorithm. implement the project on the Pioneer was that the goTo
The simplest search algorithm is the random search, in Player function could not be implemented onto the Pi-
which the priority is given randomly. Though for certain oneer. This function highly simplified the simulation by
situations this can be useful and even more successful allowing for telling the robot to go to given coordinates.
 5

Since this did not work on the Pioneer, we had to instead not always guaranteed to have a wall next to it, but more
manually design our own functions for the motion of the often than not there is at least one wall for some of its
robot. forward motion that it will be able to base this correction
Since the maze cells are discrete in size and since off of, so in the long run, it will help the robot stay more
there are only four possible directions the robot can on track. As it turns out in the end these corrections did
face, this simplified the movement functions, but did not indeed help the robot more accurately navigate the maze.
necessarily make it a simple task to program. As the We also found that the Pioneer seems to be a bit
robot will only be facing north, south, east, or west; a particular depending on the path it is taking through the
simple turn function to the left or right that rotates the maze. That is to say, it did not always accurately run
robot 90 degrees provided for all the turns the robot made through the maze if you simply arbitrarily place it at
in the maze. Similarly, a forward motion function was a different starting point with a different goal. This of
designed that moved the robot forward one single cell course was not a problem in the simulation, so the theory
length. behind the project was repeatable, but error involved
Unfortunately, on account of the inaccuracies of the in the odometry for the Pioneer did not always allow
odometry in the robot, simply relying on preset timed for repeatability. The settings for rotation and forward
movements was not enough to accurately navigate the motion instead had to be tweaked slightly for the path it
robot through the maze. As the odometry is inaccurate was currently trying to solve.
and unreliable, although the Pioneer thinks it is going One interesting and beneficial consequence of the
straight or turning for a set number of degrees, in reality maze structure and backtracking that takes place in a
there is some error. This error accumulates and in the search is it’s ability to be somewhat self correcting for
case of forward motion, the robot tends to drift to one drift. As the robot explored one section of the maze and
direction or the other. In order to account for this error, returned to the position it entered that section from, the
we programmed the robot to adjust the angle of its drift accumulated exploring the section in one direction
forward motion depending on its relative position to a was minimized by drift which took place as the robot
nearby wall. Essentially, it relies on the accurate and backtracked out of the section. We found that this is not
more reliable laser range finder to gauge distances which a solution to the problem of accumulated drift, but that
provides for more precise movement. it did lesson the impact of cumulative drift in certain
All of the motion corrections were implemented in circumstances.
the forward motion function. First, so that the robot
accurately moves single cell distances, the robot uses VI. F UTURE W ORK
its distance to the next cell in front of it to determine
There are many possible directions from which future
when to stop its forward motion. Basically the robot
work could proceed from this project. While we were
needs to stop when it is centered in the next cell, so
able to successfully solve a maze in simulation and in
when the range reading from directly ahead of it reaches
the real world, there are many improvements that could
half a cell (or a modulus of half a cell), it will know
be made in order to correct for drift, be able to solve a
that it has traveled far enough forward. As it actually
larger or more complex maze, or utilize multiple robots
turns out, the SICK laser on the Pioneer is located
to solve a maze in parallel.
slightly forward on the robot, so the values dictating
when it must stop needed to be decreased a bit so that it
moved slightly further forward. We have also included
some other tweaks to forward motion such as slowing
down after it has crossed a threshold so that it does not
overshoot its destination.
The other correction implemented into the forward Fig. 4. Drift Example
motion function was designed to account for the drift
that accumulated on account of odometry error. The idea The drift accumulated throughout the experiments was
is simple - as the robot drifts to either the left or right, by far the biggest factor keeping the robot from solving
turn slightly to head back towards being aligned with the maze in any given trial. One possible improvement to
the center of the cell. This was done by looking to the compensate for the drift could be an improved rotation
left and right of the robot with the laser and checking if primitive. Such a function could act similar to the
the robot was less than half a cell away (including some previous one in that it will rotate as near to 90 degrees
marginal room for error). It can be noted that the robot is as possible, but would improve upon it by using laser
 6

readings in order to position itself more precisely to 90 be done on using motors that would be have a higher
degrees. By making small rotations and observing the accuracy and are still capable of high velocities. One of
left and right wall distances the function could look for a the possibilities would be using the Explorer instead of
local minimum in the wall distance on both sides, which the Pioneer.
should be the situation in which the robot is aligned After implementing sensing on an Explorer, it could
perfectly parallel to its side walls. In this way very be an exciting platform for maze solving problems. Due
accurate 90 degree turns should be possible, even in the to its size it would be simpler to implement and test
case where the robot has undershot or overshot forward large maze structures then with a Pioneer robot. Because
motion, or has a slightly incorrect orientation prior to of the smaller mass of the Pioneer, it could make a
the rotation. high velocity search of a maze structure more feasible
Another motion improvement could take place in the without risking damage to the robot or the environment
forward motion function. By determining the number from accidental collisions. Due to the onboard wireless
of cells to either side of the robot using the laser, the communication capabilities, the Explorer could be well
forward movement could be compensated with a small suited for multi-agent maze search problems as well.
angle to keep the distance on either side of ratios of cell One very interesting prospect for research would be
sizes. We implemented a simple version of this which decreasing the cell size in the maze and relaxing some
would apply compensation when the robot is following of the other experimental constraints until this problem
a wall to either side, but a version of the function as is similar to common SLAM problems being looked at.
described above may have superior results. Given slow Theoretically speaking, as the cell size reaches zero, the
enough velocities such a method should be able to keep problem opens up into full-scale SLAM. The same or
the robot nearly perfectly aligned in the center of a maze similar techniques as we used for the maze solving could
cell. Implementing this in addition to the improved turn then be applied to the SLAM problem to see what their
function described above is expected to solve much of effectiveness is versus standard SLAM techniques.
the drift error and localization issues which we struggled
VII. C ONCLUSIONS
with.
Implementing better search algorithms could be a From our research we have learned some key lessons.
major advantage especially in situation where time is a The transition from a simulated model to real world test-
major cost. The easiest way to increase the data available ing is not a trivial one, and exposes many factors which
to the search algorithms can be done by scanning the were not or could not be accounted for in the simulation.
walls of the cells that the robot may not have visited yet The hard constraints of the real world mean that what
lie in the range scanning range of the SICK lasers. This is theoretically possible and shown in a simulation may
can save us the time of having the robot explore some not be necessarily feasible to implement in practice.
cells, and allows it to make better informed decisions The biggest challenge in our transition from simula-
during the course of the search. The more information tion to the real world was of that of accurate movement
that can be plotted by the robot, the more effective the and localization. Due to the constraints of the Pioneer
searching can be done. robot, we solved the maze at a fairly low speed and did
The search algorithm can also be enhanced by making not do more advanced scanning of cells to look ahead
it enough to detect and avoid getting into areas which multiple positions as was possible in the simulation.
can by guarantee not have the goal. One such situation The localization issue was the biggest factor we had
is when the algorithm tries to get the robot to search into to deal with once we moved to the physical world. If this
an area which is surrounded by all four sides by scanned problem were solved we could have much easier motion
cells and the goal lies outside it. By that we can know primitives and drift compensation, have more precise and
that there is no path that escapes out of this area to the useful sensing and solved the maze at a higher speed with
goal and thus can be avoided. Given that the robot knows essentially no risk of a collision. This project attempted
the dimensions of the maze, a segmentation algorithm to minimize the difficulties of localization by leveraging
could be very effective - avoiding many possible routes the discrete structure of the maze, something which did
by attempting to segment off the goal location from the simplify the problem, but did not eliminate the problem
majority of the maze recursively. of localization.
Apart from that, though the use of SICK lasers has R EFERENCES
been highly beneficial, using a different and better-
[1] S. Thrun, “Robotic mapping: A survey,” in Exploring Artificial
suited-for-the-task mechanical design than that of the Intelligence in the New Millenium, G. Lakemeyer and B. Nebel,
Pioneer can definately be looked into. Research can also Eds. Morgan Kaufmann, 2002, to appear.
 7

[2] D. Murray and C. Jennings, “Stereo vision based mapping and

navigation for mobile robots,” in Proceedings of the 1997 IEEE
Conference on Robotics and Automation, 1997, pp. 1694–1699.
[3] S. Thrun and A. Bucken, “Learning maps for indoor mobile robot
navigation,” Artificial Intelligence, vol. 99, pp. 21–71, 1998.
[4] S. Thrun, A. Bucken, W. Burgard, D. Fox, T. Frohlinghaus,
D. Hennig, T. Hofmann, M. Krell, and T. Schmidt, Map learning
and high-speed navigation in RHINO. Cambridge, MA, USA:
MIT Press, 1998.
[5] J. del R. Millan, The Handbook of Brain Theory and Neural
Networks, 2nd ed. MIT Press, 2002.
[6] H. Durrant-Whyte and T. Bailey, “Simultaneous localisation and
mapping (slam): Part i the essential algorithms,” Robotics and
Automation Magazine, June 2006.
[7] M. Dissanayake, [Link], S. Clark, H. Durrant-Whyte, and
M. Csorba, “A solution to the simultaneous localisation and map
building (slam) problem,” IEEE Transactions on Robotics and
Automation, vol. 17, no. 3, pp. 229–241, June 2001.
[8] C. S. Ananian and G. Humphreys, “Theseus: A maze-solving
robot,” May 1997, independent Work Presented to the Depart-
ment of Electrical Engineering at Princeton University.
[9] (2008, December) Maze solving. Online. [Online]. Available:
[Link]