See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/261212571

Design and implementation of a robot for maze-solving with turning

indicators using PID controller

Conference Paper · May 2013

DOI: 10.1109/ICIEV.2013.6572687

CITATIONS READS

2 3,189

5 authors, including:

G.M. Sultan Mahmud Rana Jubayer Rabin

Khulna University of Engineering and Technology University of Colorado
5 PUBLICATIONS   29 CITATIONS    10 PUBLICATIONS   45 CITATIONS   

SEE PROFILE SEE PROFILE

Abu Farzan Mitul

Los Alamos National Laboratory
60 PUBLICATIONS   341 CITATIONS   

SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Dye Sensitized Solar Cells View project

Machine Learning View project

All content following this page was uploaded by Abu Farzan Mitul on 31 May 2016.

The user has requested enhancement of the downloaded file.

 Design and Implementation of a Robot for Maze-
Solving with turning indicators
using PID controller
Abdullah Al Mamun Khan, G.M. Sultan Mahmud Rana, Md. Jubayer Alam Rabin, Abu Farzan Mitul, Md. Shahjahan
Khulna University of Engineering & Technology ,Khulna, Bangladesh
dip_086@yahoo.com, gsmrana@gmail.com,jubayer_1228@yahoo.com, mitulnaya@yahoo.com, mdjahan8@yahoo.com

Abstract— Autonomous navigation is an important feature that design a sensor which can detect these three colors in all
allows a mobile robot to independently move from a point to lighting conditions. Detection of black strip has critical
another without an intervention from a human operator. importance to reach at centre of the maze. More generally the
Autonomous navigation within an unknown area requires the robot is an efficient line follower with the capability of
robot to explore, localize and map its surroundings. By solving detecting indicators for solving a critical circular maze. Here
a maze, the pertaining algorithms and behaviour of the robot PI(D) controller is used not PID. While calculating the
can be studied and improved upon. This paper describes an derivative (D), the change in error can be divided by the time
implementation of a maze-solving robot designed to solve a taken to get the rate of change of error, but it is skipped in
maze with turning indicators. The black turning indicators tell
this robot, because each loop takes almost same time to
the robot which way to turn at the intersections to reach at the
execute.
centre of the maze. Detection of intersection line and turning
indicators in the maze was done by using LDR sensors.
Algorithm for straight-line correction was based on PI(D) II. RELATED WORKS
controller.

Keywords- Autonomous navigation, Mobile Robot, LDR Dang and Song proposed “An Efficient Algorithm for
sensor, PI(D) controller, Embedded Systems Robot Maze-Solving” which was based on flood-fill
algorithm but improved by reducing some steps not needed
in certain cases. As there are channels in the maze where the
robot is forced to go only straight forward, when the robot is
inside these channels, it does not need to perform all four
I. INTRODUCTION
steps of maze-solving which is updating the wall, flooding
In mobile robotics, autonomous navigation is an the maze, determining which turn to be taken and moving to
important feature because it allows the robot to the next cell. To reduce execution time, it only flood the
independently move from a point to another without a tele- maze when there is a turn [4].
operator. Numerous techniques and algorithms have been “Partition-central Algorithm” is another maze-solving
developed for this purpose, each having their own merits and algorithm where the standard 16×16 unit maze is virtually
shortcomings [1-4]. divided into twelve partitions. The robot uses data such as its
Maze-solving – although artificial in terms of the confine direction and its current location to change between
that the robot it subjected to is a structured technique and exploring rules to save more time and optimize the solving
controlled implementation of autonomous navigation which process. A simulation was developed to verify the algorithm.
is sometimes preferable in studying specific aspect of the Test results show that partition–central algorithm has higher
problem [1]. This paper discusses an implementation of a average efficiency when compared to other algorithms [5].
small size mobile robot designed to solve a maze based on
PID controller. Basically this robot is an intelligent line follower robot,
which can change its direction at interaction point according
The maze-solving task is similar to the ones in the to previously given direction. The direction can be given in
MicroMouse competition where robots compete on solving a many ways. For checking the robot performance we have
maze in the least time possible and using the most efficient drawn white line on green surface for directing the robot
way. A robot must navigate from a specific starting point of forward and for turning indication we have used black color
a maze to the center as quickly as possible. Here the centre is small rectangular shape strip. Robot changes its direction at
marked with a big black circle where the robot should stop. It
each intersection of white line according to previous black
knows where the starting location is and where the target
direction indicator. In this way Robot can goes to any
location is, but it does not have any information about how it
could reach at the centre autonomously. The arena is shown desired end point.
is fig.1 which might seem cumbersome at first sight. The
arena is consisted of three different colors which are green as III. THE MAZE AND THE ROBOT
background, white lines for navigation of the robot and black
strips for indicating which side the robot should turn at the The Robot is designed to solve the different type of maze
next intersection. The detection of the black indicators is including rectangular maze or circular maze. Here we
most important and perhaps the most challenging task. The analyzed circular prototype using some indicators which is
prime reason behind this lies in the fact that it is not easy to shown in fig.1 below. The small black indicator indicates the

978-1-4799-0400-6/13/$31.00 ©2013 IEEE

turning direction at next intersection. the center
c is big black Another microcontroller ATME EGA8A with VUSB firmware
circle which defines the final destinatiion of the robot. is connected on board for Sennsor Debugging purpose with
Though here only circular path is shown but this robot has computer. This is used to anallyze the sensor arrays reading
the capability of solving any kind of maze m with turning on different color strip. The sensors arrays as mentioned
indicators. earlier are consisted of LED’s and
a LDR’s. Depending on the
reflected light the analog voltaage values across the LDR is
changed. The analog values are a then converted to digital
values by using the ADC channnels of AVR microcontrollers.
Block diagram of the motherrboard shown in fig.2. Line
follower sensor which actuallly detects the white line is
connected to the Atmega3288P microcontroller. The line
following algorithm is deveeloped using PID controller
method. Whenever two side black
b detection sensors detects
a black strip the microconntroller connected to these
sensors(ATMEGA32A) sennds a signal to the
ATMEGA328P telling it at whhich side the strip is detected.
ATMEGA328P then stored the value in a variable
depending on the signal pin. From this stored value robot
will decide in which direction it is going to turn at the next
intersection.

Figure. 1. The arena or maze to

t solve

IV. PROCESSING UNIT AND ALG

GORITHM
The whole robot is controlled by two microocontrollers which
communicate with each other by 4bit parallel lines for Figure. 3. Mothherboard layout
fastest data transfer. These two miccrocontrollers are
ATMEGA328P and ATMEGA32A.

16 MHz
Keypadd 2x2 crystal

Motor driver Left

L293D motor
Line follower ATMEGA328P
sensor array Microcontroller
AD
DC Motor driver
L293D
Right
motor
12 MHz crystal
4 bit Parallel
Connection ATMEGA8A Computer
(VUSB firmware) USB (Debugging)
Black detection
sensor arrays
(left and right AD
DC ATMEGA32A
sensor) Microcontroller LCD Display
D

16 MHz
Crystal

Figure 2.Motherboard block diagram

 V. HARDWARE DESIGN colors of the arena and the correesponding digital values of the
The robot has a length of 20 cm, a widthh of 20 cm and a analog voltage across LDR waas taken and plotted as shown
height of 5 cm. As illustrated in Fig 5. in fig.6 & fig.7 below.

Figure 6.Converted Digittal values of analog voltage

across LDR for different collor strip with different color
LEDD’s
Figure 4.The Maze solvingg robot
1000

900
A. Sensor Array 860
90
79 820
Sensors are the first requirement in thhe process of line 800
following. There are many sensors one can use for line 700 730
700 720
following – IR LED and a Photodiode, LED D and LDR (Light
630 640
Dependent Resistor), etc. The selection ofo sensors is based 600
on response time, sensitivity and ambient liight protection. 550 540
460
500 470 500
IR LED and photodiodes give good responnse time. But they 360 450
Orange
400
have two drawbacks, both of which can bee dealt with – they LED
350 Red LED
can sense only between two contrasting coolors and they are 300
easily affected by ambient light. 250 240 240
Green
200 LED
150 Blue LED
LDRs (photoresistors) are excellent in terrms of sensitivity, 100
they can sense not only between two contrrasting colors (one White
LED
dark and one light) but also between tw wo primary colors. 0
Some competitions make the line folloowing tougher by Black Deep Light White
having a white line on a colored surface like green. In such Strip green green Strip
Strip Sttrip
cases LDRs are the sensors to be used. Buut there is one big
disadvantage in using LDRs - their slow response time. A
LDRs reaction time is around 0.1s.
Figure 7.curve showing thhe different values of digital
voltage across LDR with multiple
m colors Led’s. Here
horizontal axis represents coloors of different strips. Vertical
axis represents the converted diigital values of analog voltage
across thhe LDR
Two arrays of sensor are used to detect the three colors. For
green and white line detection LDR with orange LED’s are
used as it is quite clear from fig.7, for orange LED digital
Figure 5. Circuit diagram of a singgle sensor voltage values across LDR diiffers notably. For green and
black detection LDR with greeen LED’s are used. This is
Here, fig.5 only shows one sensor thatt is a single cell of because the above chart of fig.77 shows that for differentiating
sensor array. The line following sensoor circuit actually between green and black, greenn LED is the best option as for
consisted of five such cells. For black indiccation detection the green LED the digital valuees of voltage has significant
sensor array consisted of four cells witth different color differences.
LED’s.
For three color detection the process of designing the B. Motor Drive
sensors is quite tedious. For color deteection the analog The two dc motor of the robott was driven by two H-bridge
voltage across the LDR in converted to digital values by motor driver integrated circuitt(IC) called L293D. L293D is
using A/D conversion process. Here foor different color actually a current amplifier which takes a low current
LED’s the digital values of voltage across the LDR varies in control signal as input and proovides higher current signal as
wide range. For successful detection of thrree colors we have output. This higher current siggnal is responsible for driving
to choose the specific LDR and LED pair which have the motor in any desiredd direction (clockwise or
significant difference of converted digital voltage
v values for a anticlockwise). The IC can be used to drive two DC motor
particular color strip. To solve the maze by b using the black
simultaneously but here a sinngle IC is used to drive one
turn indicator the sensor cell was placeed above different
motor for protecting the IC froom overheating. The speeds of
the dc motor were varied by varying the duty cycle of the For proper operation of the robot the tuning of PID
PWM signal. By reversing the polarity of the PWM signal controller has significant importance.
the polarity of the motor voltage can also be changed. As a
result due to change in polarity the direction of motor Configure Calib
Line following Ports and rate
rotation also get reversed. The enable pin of the IC must be sensors pin mode
PWM for dc
sens
high for it to operate. motor speed
(ATmega328p initializatio or
control
) n

Read indication
signal for
C. PWM for DC motor Speed control Read line Store indicator indicator
There are three kind of PWM generation mode in AVR sensor signal (left or detector
Mega series microcontroller. right) microcontroller
(ATmega32)
1. Fast PWM Mode
2. Phase Correct PWM Mode Yes
Turn left or
Clear
3. Phase and Frequency Correct PWM Mode Intersectio right or forward
stored
according to
As the frequency used for DC motor control is fixed, we n found? indicator
stored indicator
signal
have used Phase Correct PWM mode for PWM generation. signal
No

ƒ _IO Calculate
ƒpwm = robot position
Send
. . Calculat
PWM
Calcul signal
e robot
Yes ate P, to the
position
ƒpwm represent Frequency of PWM. we have used 50Hz deviatio
I, D motor
PWM Signal to control our selected DC gear motor. Is robot value driver
n
above s
ƒ _IO Represent Microcontroller operating Frequency. We
have used 16 MHz external Crystal. No
N represents the prescaler divider of AVR series Right Turn right
Left
microcontroller (1, 8, 64, 256, or 1024). until get
TOP is calculated for requires frequency of PWM (ƒpwm) and Last line? back to
Turn left
line
set it to Register of ATmega 328 microcontroller

For DC motor control we have taken the variable as

ƒ _IO = 16 MHz
N = 256
Figure 8. Program Flow Chart
TOP = ICR1 = 625 (back calculated to get 50Hz PWM)
From above equation we get ƒpwm = 50Hz The first, Proportional term simply provides a control
signal proportional to the size of the error. A control system
OCR1A and OCR1B register is used respectively to left and can use this term alone but only if it responds very quickly
right motor PWM signal duty cycle control i.e speed control. to the steering output, and the robot is relatively slow
moving. Otherwise the best one can get is a mouse
OCR1x = TOP = ICRx = 625 means 100% non inverting wandering from side to side as it goes along tracing out a
duty cycle i.e full speed sine wave shaped track. The steering signal calculated by the
OCR1x = 0 means 0% non inverting duty cycle i.e zero microcontroller is . A simple 8-bit x 8-bit multiply
speed is performed followed by an addition to the base PWM
value controlling the motor speed of the left-hand wheel.
The robot steers to the left as this wheel is slowed down
D. Moving in various Line with a PID Controller
relative to the right hand wheel, and to the right as it is
driven faster than the right-hand wheel. A typical value for
There are many algorithms for controlling a line following
is likely to be less than 1.0.
robot. Among these PID is most easy to implement. PID
controllers taken into account the previous error accumulate
The Differential or derivative term is necessary for
the errors and then helps the robot to come back to target
smooth straight-line performance. If the P term makes the
position for more precise operation without much deflection.
robot behave as if it had coil springs mounted between itself
The following fig.9 shows the flowchart of the algorithm
and the walls on each side, then the D term provides the
used for PID controller.
‘shock-absorbers’ or dampers. This gives a measure of how
fast the error is changing as the robot moves along. The
The equation for PID controller is,
control signal now becomes: .
The Integral term may be omitted if the drive systems on
each side of the robot are evenly matched so that the wheels
revolve at the same speed when the same PWM signal or
Where C=control (steering) effort, e= measured lateral voltage value is applied to each motor. If not, which is very
error from center line and K= tuning constants. likely, and then we will have a steering ‘bias’. With no
control system, the robot will travel in a circle whose robot. It calculates the deviation of the position of the robot
diameter depends on the size of the bias. With a PD with respect to the target position while running. The
controller, the mouse will travel in a straight line, but at a controller upon calculating the error of the position send
fixed offset from the centre line. The I term is used to commands to the motor to turn and come back to target
remove this offset, and is derived from: I = I + e, in other position. If the robot is out of the line the error will be large
words, an accumulator function. The control signal now so the PID controller will tell the robot to take a continuous
becomes: . The value for I will turn for finding the line.
rapidly increase and then stabilize at a constant level as e
reduces to zero.

White Line
1 2 3 4 5
Figure 12. Sensor Array
Figure 9. Robot tracking a circular line using Here fig.12 shows the sensor cell positions designated by
Proportional controller (Green) and PID controller (blue) . 1,2,3,4,5. Here 3 is the target position which is specially
Here, in fig.9,10 and fig.11 it is clearly demonstrated that, indicated by the bulk arrow. If the robot is anywhere other
robot with PID controller has less deflection in comparison than the target position then it will calculate the error value
with its predecessor proportional controller. from equation (1)
Error = target position – current position ……. (1)
After calculating the error it will calculate and set the
values of P, I and D from following equations.
P = Error * Kp ……...….. (2)
I = I + Error ………….... (3)
I = I * Ki ………...... (4)
D = Error – Previous error... (5)
Figure 10. Robot tracking a sinusoidal line using
Proportional controller (Green) and PID controller (blue). By adding the corresponding values of P, I ,D it will
calculate the speed correction required for the motor to take
the robot back to target position.
Correction = P + I + D …… (6)
The next step is to add this correction term to the left and
right motor speed.
For tuning first the integral term is eliminated from PID
calculation. Then the kp and kd terms were tuned until it can
follow a straight or gently curved line without oscillation.
Figure 11: Robot tracking an arc line using Proportional The values of the constant obtained by this process can be
controller (Green) and PID controller (blue). used for one specific track. For different track with different
types of turn and curved path the values will vary for stable
operation. The integral term is useful where some external
It can be clearly seen from the above pictures that without force is constantly working against the robot. The I term acts
PID control the robot oscillates a lot about the line, wasting to shrink the value of error to zero over time by progressively
valuable time and battery power. It is clear that there is a increasing the motor power while error is not zero.
maximum speed beyond which the algorithm cannot be used. VI. RESULTS & DISCUSSION
Otherwise the robot will overshoot the line. A robot with PID
control will follow the line as shown in the above figures. The snapshots of the robot while travelling through the
The first requirement in implementing PID for a line line maze is shown here. The robot was tested during night
follower is calculating the error of the robot. To calculate under fluorescent light and during daytime under sunlight.
the error the controller will need to know the current Under fluorescent lamp the robot reach at centre quite
position of the robot with respect to the line. There are a easily. It is seen that sometime the robot misses the black
turn indicators under sunlight and fail to reach at the centre.
number of ways of knowing this. The PID controller
It is due the fact that at sunlight the intensity of LED’s is not
technique was applied to smooth operation of the robot. The as effective as fluorescent light. It was easily solved by
controller helps to keep the robot in a specific target using some sort of black cover around the robot. The black
position. It continuously checks the current position of the tape or cover will absorb the light and won’t let pass and
disturb the sensor LED’s. With black cover over it the robot
successfully reach at the centre of the maze during sunlight.
Here in fig.13 the robot is at starting position. Then while
travelling it finds a black indicator at right side. So at next
intersection it takes right turn as shown in fig.15. by
continuously turning with the help of turning indicators the
robot finally reaches at the centre as shown in fig.17. the
algorithm was so developed that the robot while getting the
big black circle will eventually stop. That means it take the
big black circle as the centre or final destination. Figure 17. Robot stops at final destination

VII. CONCLUSION
This paper concentrates on designing an autonomous
robot to solve a maze with indicators. It has the intelligence
of automatically navigate itself in any environment. Here it is
demonstrated that PID controller is superior to proportional
controller in terms of deflection. The LDR sensors
outperformed the conventional IR sensors for the detection of
three colors. Though the mapping of line is not performed
here but it can be implemented in future, which will certainly
Figure 13. Robot in starting Position
increase the applicability of the robot. This robot can also
used as a line follower with obstacle avoidance simply by
adding a sonar sensor at front. A video camera can also be
added to navigate it remotely by a human operator. By
adding proper kind of sensors it can be sent to anywhere,
where it is considered dangerous for human being like
detection of biochemical leaks or neuclear radiation. With
more improved sensor some constrains like disability to
detect indicators at daylight can be eliminated.
Phototransistors can be used to design more advanced
sensors.
REFERENCES
Figure 14. Robot finding an indicator
[1] Verner, I.M. and D.J. Ahlgren, Robot contest as a laboratory for
experiential engineering education. J. Educ. Resour. Comput., 2004.
4(2): p. 2.
[2] Mishra, S. and P. Bande. Maze Solving Algorithms for Micro Mouse.
in Signal Image Technology and Internet Based Systems, 2008. SITIS
'08. IEEE International Conference on. 2008.
[3] Mishra, S. and P. Bande. Maze Solving Algorithms for Micro Mouse.
in Signal Image Technology and Internet Based Systems, 2008. SITIS
'08. IEEE International Conference on. 2008..
[4] Kendre, S. S., P. V. Mulmule, et al. Navigation of PIC based Mobile
Robot using Path Planning Algorithm. International Journal of
Computer Applications. 2010
[4] Dang, H., J. Song, and Q. Guo, An Efficient Algorithm for Robot
Figure 15. Robot at T intersection choosing a right turn Maze-Solving, in Proceedings of the 2010 Second International
Conference on Intelligent Human-Machine Systems and Cybernetics
according to previous black indicator. - Volume 02. 2010, IEEE Computer Society. p. 79-82.
[5] Cai, J., et al., An Algorithm of Micromouse Maze Solving, in
Proceedings of the 2010 10th IEEE International Conference on
Computer and Information Technology. 2010, IEEE Computer
Society. p. 1995-2000.
[6] Wyard-Scott, L. and Q.H.M. Meng. A potential maze solving
algorithm for a micromouse robot. in Communications, Computers,
and Signal Processing, 1995. Proceedings., IEEE Pacific Rim
Conference on. 1995.
[7] Jianping, C., et al. A micromouse maze sovling simulator. in Future
Computer and Communication (ICFCC), 2010 2nd International
Conference on. 2010.

Figure 16. Robot crossing a T intersection.

View publication stats