2009 International Conference on Future Computer and Communication

Algorithms for Micro-mouse

Manoj Sharma
Kaizen Robeonics
Jaipur, India
manoj.k.sha@gmail.com

Abstract: Robotics is not a new word. It has education from conventional classroom teaching to
attracted people from all phases of life. The failure of hands on projects. Robotic projects are very useful
a project in any field mostly occurs due to incomplete for students who have to deal with an open ended
analysis of problem or improper planning. Such problem, in this way their creativity is stimulated. As
disappointments can be avoided by adapting a proper project incorporates wide range of engineering fields,
approach towards solving a given task. The problem they can convert variety of theoretical study into
of micro-mouse is 30 years old but its importance in practice. Furthermore, students learn teamwork.
the field of robotics is unparalleled, as it requires a To stimulate this learning process in upcoming
complete analysis & proper planning to solve this engineering, a wide range of robotic competitions is
problem. This paper covers one of the most important conducted world wide, and the most sought after
areas of robot, “Decision making Algorithm” or in among them is MICROMOUSE. It is one of the most
lay-man’s language, “Intelligence”. The environment efficient ways to inculcate the true "engineering
around the robot is not known, so it must have values" in students. As mentioned above, the change
decision-making capabilities. For starting in the field in the mode of education is under revolution, as a
of micro-mouse it is very difficult to begin with highly result of which not much students are exposed to the
sophisticated algorithms. This paper begins with very field of robotics.
basic wall follower logic to solve the maze. And In this paper, problem of micro-mouse is
gradually improves the algorithm to accurately solve introduced in section 2. In section 3 we describe the
the maze in shortest time with some more hardware work on robot. The stepwise logic
intelligence. The Algorithm is developed up to some development for robot is discussed in section 4. After
sophisticated level as Flood fill algorithm. that we state result & finally conclude this paper.

1. INTRODUCTION: 2. Micro-Mouse:

Autonomous systems have been used in the Micro-mouse is an autonomous robot designed to
various fields and are even expected in fields such as negotiate a maze in a shortest possible time. It can
patrolling, checking and repairing some troubles. not jump over, fly over, climb, scratch, cut, burn,
Autonomy means capability of navigating the mark, damage, or destroy the walls of the maze. The
environment; navigation, in turn, relies on a maze is composed of multiples of an 18 cm x 18 cm
topological and metric description of the environment unit square. The maze comprises 16 x 16 unit
[6]. squares. The walls of the maze are 5 cm high and 1.2
One of the major components for the creation of cm thick that can have 5% of tolerance. The outside
autonomous robot is the ability of the robot to “plan wall encloses the entire maze. The sides of the maze
its path” and in general the ability to “plan its walls are white, the top of the walls is red, and the
motion”. In a limited or carefully engineered floor is black. The maze is made of wood, finished
environment it is possible to program the robot for all with non-gloss paint. The start of the maze is located
possible combinations of motions in order to at one of the four corners. The start square is bounded
accomplish a specific task [2]. The problem of path on three sides by walls.
planning is not confined to the field of robotics but its
applications exist in various genres. For example, 3. Hardware Module:
molecule folding, assembly/disassembly problems
and computer animations are areas where comparable To fabricate an autonomous system based on
problems arise [7]. various sensors, actuators & a microcontroller, it has
A robot is a mechanical device, which performs to be assembled as hybrid. In order to realize a robot
automated physical tasks, either according to direct system, that can fulfill contest task, flexible in
human supervision, a pre-defined program, or a set of hardware & software is needed to gradually work
general guidelines using artificial intelligence step wise from initial step to final maze solving with
techniques. There is a paradigm shift in engineering high speed for minimize time to complete the task. A

978-0-7695-3591-3/09 $25.00 © 2009 IEEE 581

DOI 10.1109/ICFCC.2009.38
modular approach has thus been adopted. The I. Maze Interpretation:
problem of micro-mouse is modeled in five modules; The maze is interpreted in the form of a two
chassis drive system, sensors, and controller & dimensional array, with each cell having its own
energy system modules. coordinates. Rows and columns distinguish the array,
The chassis & drive system module is made up of rows denoted by 'R' and columns denoted by 'C'
2 toys & 1 ball transfer with differential wheel hence, the increment and decrement in R and C will
steering system. The sensor module is made up of signify different cells. Now, the movement of the
LDR & White LED pair to provide collision free micro mouse on the maze is purely cell wise
movement of robot. It works on the principal of MAPPING.
reflection of light from the wall of maze.
The controller module contains a microcontroller II. The Wall Follower Algorithm:
AT89s52. It is take input from sensors & operate Here, we are developing the WALL FOLLOWER
actuator according to the decision making algorithm LOGIC. This works on the rule of following either
stored in microcontroller of micro-mouse. The energy left wall or right wall continuously until it leads to
system module is use to drive the whole robot. We the center. The micro mouse senses the wall on the
use two battery packs of four 1.2V, 2300mA GP left or right, and follows it to wherever it leads until
batteries one for sensor & microcontroller circuit and the center is reached. This simple logic used for
other for actuator circuit. solving the maze is mathematically demonstrated by
the following approach.
4. Software Module:
III. A mathematical approach:
Intelligent behavior of a robot can be achieved Here, we have an array of 16 rows and 16
only if the robot is capable of learning. Real robot columns. If the array is denoted by M, then each cell
path planning becomes even more complicated due to is represented by M[R][C]. We assume the present
the fact that the shape of the robot has to be taken position of array as M2[R2][C2] , the previous
into account [2]. position as M1[R1][C1], and the next position as
M3[R3][C3]. Now we proceed as follows:
A. Sensor interface to control the motion:
If R2-R1>0, then it is currently moving straight,
Among the many innate physical abilities of upwards through the maze array.
humans, motor control is the skill that is most often If R2-R1<0, then it is currently moving straight,
taken for granted, as it seems to require very little downwards through the maze array.
conscious effort on our part. Only when a particular If C2-C1>0, then it is currently moving rightwards,
motor skill is impaired or is lost then one begin to through the maze array.
fully appreciate the difficulty of motor control. It If C2-C1<0, then it is currently moving leftwards,
comes as no surprise that these exact same through the maze array.
difficulties are encountered, indeed, even magnified,
when attempting to endow robots with a movement-
generation capability like that of humans [4].
The motion of robot is dependent on sensors. In
our robot we use three sensors; one in front second in
left & third in right direction. When any sensor
senses the presence or absence of wall in any of three
directions it affects the motion of robot according to
the algorithm used. The algorithm used for maze
solving is uses the output of sensors as input to
control the motion of robot.

B. Step Wise Algorithm Development:

Figure 1. Left wall follower: solvable maze
The maze problem has an extra complication,
which is not apparent when one consider for the first The time taken by the robot can be calculated. If
time. For each of the cells and a specific goal we assume the cell to cell movement time to be 2.5
position, there is more than one equally good sec. and the turning time to be 1 sec. then the total
direction [2]. time taken by the robot is (140×2.5) + (27×1) = 377
sec. for reaching the centre of this maze.

582
 (The IEEE standards are followed for designing this
sample maze.)

Figure 2. Left wall follower: unsolvable maze

The above maze is not being solved using the left

wall follower logic. This is one of the drawback of
this logic. Figure 5. Left wall follower sample maze solved by the
described logic: white line shows the path followed by robot.

Figure 3. Right wall follower: solvable maze

Figure 6. Right Wall Follower logic solving the sample maze:
white line shows the path followed by robot.
The above maze is solved using the right wall
follower logic. The total time taken by the robot is
V. Problems encountered:
(124×2.5) + (25×1) = 335 sec. for reaching the center
The above algorithm though seems to be simple
of the maze.
and efficient, it has enormous loopholes. The biggest
is its inefficiency to stop the execution by itself.
Another of its drawbacks is the "absence of
intelligence" in the device. It does not have the
ability to detect its position and direction, and
determine whether or not, during is course of path
finding, it has reached the center or not. Hence, it
does not have any intelligence.
As the above maze was not being solved by the
wall follower logic, we discovered a flaw in our
algorithm, and decided to develop it to an advance
level so that it was capable of solving any kind of
maze. Hence, the conclusion is to use a higher end
algorithm like flood fill, for better solving of maze.
Figure 4. Right wall follower: unsolvable maze We proceed towards

IV. Practically Implemented Wall Follower Logic: VI. Flood Fill algorithm:
The above wall follower logic has been The speed of robot to find its path, affected by the
implemented on a sample realistic maze of 5x5 units. applied algorithm, acts as the main part in the present

583
project. The flood-fill algorithm involves assigning
values to each of the cells in the maze where these
values represent the distance from any cell on the
maze to the destination cell. The destination cell,
therefore, is assigned a value of 0. If the mouse is
standing in a cell with a value of 1, it is 1 cell away
from the goal. If the mouse is standing in a cell with a
value of 3, it is 3 cells away from the goal. Assuming
the robot cannot move diagonally [3].
The maze is represented as a 16x16 array in the
memory. The centre is given the value (0, 0). All
cells in its immediate viscinity are assigned 1, the
cells next to it as 2, and so on. The array is divided Figure 8. Formation of array temp [4]
into 4 symmetrical regions and then the assignment is
done. After this, the array is ready for further
Upper left quarter, loop decrements the column, processing, which includes the deciding of which
increments the row: R = R + j, C = C - i, i, j vary path to be taken and which values in the map to be
from 0 to 8. changed.
Upper right quarter, loop increments the column, The maze after being flooded is then traversed
increments the row: R = R + j, C = C + i, i, j vary and the map of the maze is updated after every
from 0 to 8. traversal. Every time a new cell is traversed, it
Lower left quarter, loop decrements the column, creates the array described above and decides the
decrements the row: R = R - j, C = C - i, i, j vary lowest value nearby that can be traversed. The path
from 0 to 8. followed is always from a higher value to a lower
Lower right quarter, loop increments the column, value.
decrements the row: R = R - j, C = C + i, i, j vary
from 0 to 8.

Figure9. Maze solved through flood fill algorithm

The above maze is solved using the flood fill

logic. The total time taken by the robot is (50×5) +
Figure 7. An actual maze as depicted in the memory of the (16×1) = 266 sec. for reaching the center of this
micro mouse. maze.
Formation of array temp [4] for each cell: each
cell is interpreted as an array cell of a 2-d array and is
represented with a value, R and C, which represents a
row and column, respectively. The values, therefore,
of the neighboring cells are as shown in the diagram.
The values of the cell arrays are as according to the
index values assigned to a 16x16 array in the
computer memory. Initially the value of the first cell
is assigned as, R=1, C=1.
The values of the neighbors are stored in the
above array. After the values are stored in the array
as shown in figure 8, they are sorted using any kind Figure10. Sample maze solved through flood fill algorithm
of sorting. We have used here selection sort. White line shows the path followed by robot.

584
5. Result: [3] Babak Hosseini Kazerouni, Mona Behnam Moradi and
Pooya Hosseini Kazerouni;”Variable Priorities in Maze-
Motion planning is a key requirement of Sloving Algorithms for Robot’s Movement”, 2003.
autonomous robots. When given a task to fulfill, the
[4] Sung-Hee Lee, Junggon Kim, F.C.Park, Munsang Km,
robot has to plan its actions including collision-free and James E.Bobrow;”Newton-Type Algorithms for
movement of actuators or the whole robotic platform. Dynamics-Based Robot Movement Optimization”, Digital
A comparative study on the path length & time Object Identifier, 2004.
performance of the robot with regards to different
algorithms is also done. Both simulation and real [5] Horst-michael gross, Alexander Koenig; “Robust
tests are performed. Omniview-basad Probilistic Self-loalization for Mobile
The problem encountered in wall follower Robots in Large Maze-like Environments”, proceedings of
algorithm either left wall or right wall follower is the 17th International Conference on Pattern Recognition,
solved by flood fill algorithm. The comparison of ICPR-2004.
different algorithms is shown in table 1. [6] Shinichiro Yano, Manabu Noda, Hisahiro Itani,
Masayuki Natsume, Haruhiko Itoh and Hajime Hattori,
Table 1. Comparison of Different Algorithms Tadashi Odashima, Kazuo Kaya, Shinya Kataoka and
Hideo Yuasa, Xiangjun Li, Mitsuhiro Ando, Wateru
Left wall Right wall Flood fill Nogimori and Takahiro Yamada; “A Study of Maze
Follower Follower Algorithm Searching With Multiple Robots System”, 7th International
Cell to cell 140 124 50 Symposium on MicroMachine and Human Science, 1996.
movements
[7] Frank Lingelbach; “Path Planning using Probabilistic
turns 27 25 16 Cell Decomposition”, International Conference on Robotics
& Automation, 2004.
Time taken 377 335 266
(in sec.) [8] Javier Antich and Alberto Ortiz; “Extending the
potential Fields Approach to Avoid Trapping Situations”,
Elaborated analyses of the above algorithms give CICYT-DPI-2001.
us the base to proceed in path planning of intelligent
devices capable of navigation. [9] Gorden Mc Comb, Myke Predko,“Robot Builder’s
Bonanza”, Mc-Graw Hill, 2006.
6. Conclusion: [10] Thomas Braunl; “Embedded Robotics mobile robot
design and applications with Embedded systems”, Springer
The speed of robot to find its path, affected by the 2006.
applied algorithm, acts the main part in the present
projects that are concerned with robot navigation.
While there is no limitation to improve the
algorithms, there are some restrictions on developing
robot’s mechanic or electronic. Developing an
algorithm is usually cheaper than the other parts.

7. Acknowledge:

The team is grateful to Prof. Rabinder Henry, Mr.

Pankaj bande of International Institute of Information
Technology, Pune and Lucky krishnia student of
RCEW, Jaipur for some useful discussions. Team is
also thankful to our friends for their help.

8. References:

[1] Roland Buchi, Gilles Caprari, Vladimir Vuscovic,

Roland Siegwart; “A Remote Controlled Mobile Mini
Robot”, 7th International Symposium on MicroMachine and
Human Science, 1996.

[2] Dimitris C. Dracopoulos;”Robot Path Planning for

Maze Navigation”, 1998.

585