See discussions, stats, and author profiles for this publication at: [Link]

net/publication/355170025

Autonomous Maze Solving Robotics: Algorithms and Systems

Article · October 2021

DOI: 10.18178/ijmerr.10.12.668-675

CITATIONS READS

21 7,433

6 authors, including:

Shatha Ali Alamri Shuruq Alshehri

University of Tabuk University of Tabuk
3 PUBLICATIONS 48 CITATIONS 2 PUBLICATIONS 36 CITATIONS

SEE PROFILE SEE PROFILE

Wejdan Alshehri Hadeel Alamri

2 PUBLICATIONS 36 CITATIONS 2 PUBLICATIONS 36 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Tareq Alhmiedat on 11 October 2021.

The user has requested enhancement of the downloaded file.

 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

Autonomous Maze Solving Robotics: Algorithms

and Systems
Shatha Alamri1, Shuruq Alshehri1, Wejdan Alshehri1, Hadeel Alamri1, Ahad Alaklabi1,
and Tareq Alhmiedat 1,2
1
Faculty of Computers & Information Technology, University of Tabuk, Tabuk, Saudi Arabia
2
Industrial Innovation & Robotics Center, University of Tabuk, Tabuk, Saudi Arabai
Email: {salaamrei, s_alshehri, [Link], [Link], [Link]}@[Link]，
[Link]@[Link]

Abstract—In robotics, autonomous movement is an robot tests several paths to create a map of the maze, and
important feature that enables the robot to move stores paths and routes and then runs the autonomous
independently from one location to another. Autonomous robot through the maze area along the most efficient route.
movement within an unknown area requires the robot to The solver robot knows the source-point and the
carry out investigations. The concept of solving a maze has
destination-point in the maze area, but it does not have
an important place in the field of robotics, and is based on
one of the most important areas of robotics, the Decision-
any information about the maze area structure or
Making Algorithm. In this paper, we discuss and analyse obstacles between the two locations. The implementation
existing maze solving algorithms, and investigate the recent of autonomous vehicles ranges from employing robots to
development of autonomous maze solving robotic systems. carry goods through factories, office buildings and other
In addition, the work presented in this paper guides the workspaces to using robots in dangerous situations or
researcher and developer for choosing an adequate maze difficult to reach locations such as bomb sniffing, finding
solving algorithm to develop an efficient maze solving humans in wreckage, fire-fighting, in emergency
robotic system for a certain scenario. situations [2].
Recently, various autonomous maze solving
Index Terms—maze, autonomous robot, maze solving, solver
robot, maze solving algorithms
algorithms and techniques have been developed for this
purpose, each one with its own advantages and
shortcomings. The existing maze solving algorithms and
I. INTRODUCTION systems have been reviewed in [3-5]. However, the work
presented in this paper is different because the recent
Autonomous mobile robot navigation plays a critical deployment of maze solving algorithms and systems are
role in diverse applications, including: warehouse robots, considered. Moreover, we discuss and analyse the
self-driving vehicles, smart wheelchairs and personal performance of existing autonomous maze solving
assistant robots. In many situations, autonomous robots robotic algorithms and systems. The main contributions
are the best option for various missions. Autonomous of this work lies on the following aspects:
navigation is a critical task in mobile robotics because it 1. Research and categorize the existing maze
enables the mobile robot to independently perform solving algorithms.
movement tasks to get from one point to another. 2. Research the recent developed maze solving
Autonomous mobile robot is an intelligent vehicle that is robotic systems.
capable of travelling through several locations (point of 3. Evaluate the efficiency for the recent developed
interest), either following a predefined trajectory, or maze solving robotic systems.
navigate itself in a specific area. In both cases, the mobile This paper is divided into six sections. Section 2
robot has to avoid obstacles and move forward to presents a discussion of the potential applications for
destination point [1]. autonomous maze solving robotic systems. A
One interesting topic in robotics is autonomous maze classification and analysis of the existing maze solving
solving, where an autonomous robot tries to solve a maze algorithms are presented in Section 3. In Section 4, the
in the shortest time possible in the most efficient way. existing autonomous maze solving robotic systems are
The key mission of an autonomous maze solving robot is presented and discussed. Section 5 presents a discussion
to reach a target location by navigating through a maze and analysis of the existing autonomous maze solving
area. Maze solving robot is one of the most popular robotic algorithms and systems. And finally, Section 6
independent robots, where the solver robot is self-reliant draws conclusions.
and can move through a maze from the source-point to
the destination-point. It follows the shortest route and II. ROBOTIC APPLICATIONS
take the least time possible. To achieve this goal, a solver
The possible applications for maze solving vehicles
range from simple tasks such as transferring goods
 through factories, office buildings, classrooms and other
Manuscript received February 17, 2021; revised April 12, 2021.

© 2021 Int. J. Mech. Eng. Rob. Res 668

doi: 10.18178/ijmerr.10.12.668-675
 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

workspaces, to hazardous tasks in difficult to reach areas Maze solving algorithms

like evacuating people from dangerous buildings, bomb
sniffing, etc. Autonomous maze solving robotic systems
can be applied to:
Known environment Unknown environment
 Manufacturing: robots can be used to transport algorithms algorithms
items and tools from one location to another in a
fast and accurate manner across a complicated Wall-follower
terrain, where paths must first be explored to Lee’s algorithm Dead-end
accomplish the delivery. The Flexible algorithm
Tremaux
Manufacturing System (FMS) that employs
autonomous robots are currently dominated by Soukup algorithm Maze-router
the use of Automatic Guided Vehicle (AGV) [6, algorithm
Random mouse
7].
 Home automation: domestic robots are designed Hadlock algorithm Flood-fill
algorithm Pledge
to assist human with tasks including: lawn
moving, vacuum cleaning, and home monitoring. Heuristic search
A mobile robot can be used as a vacuum cleaner, algorithm
navigating itself effectively around the house
whilst simultaneously cleaning [8]. Figure 1. Classification of maze solving algorithms
 Traffic control: this is a real example of maze A. Known-Maze Enviroments-Based Maze Solving
solving technology that enables fire fighters or Algorithms
paramedics to find the best route to an
emergency [9]. Therefore, appropriate traffic This section describes the maze solving algorithms
control is a critical issue in highway work zone which can be deployed with known maze environments,
safety, in order to control the robotic system to where the solver robot can see the whole maze at once.
safely travel from one location to another one 1) Dead-end filling algorithm
[10]. Dead-end algorithm works well in known mazes,
 Rescue operations: rescue missions usually start where it fills all dead ends, leaving only the correct paths
with a search in the unknown environment unfilled. By employing this method, the solver robot first
before reaching the region where victims can be finds all the dead ends in the maze and then fills in the
located. As rescuers progress along a particular path from each dead end up to the first junction. This
path, therefore, they are required to report their algorithm scans the maze in an empty order, finds the
location to the mission headquarters. This will dead ends and closes the associated paths [13].
help the rescuer to reach the final destination. 2) Maze routing algorithm
Mobile robots have been employed widely in the Maze routing algorithm finds the possible paths
search and rescue operations, such as searching between any two points in the maze area. This algorithm
victims in dangerous areas which is harmful for only works in known mazes where the maze area is
human, as to offer observation data for map already recognized and stored. The maze routing
building [11, 12]. algorithm is able to explore the possible paths between
the source and destination points and identify the shortest
path between them [14].
III. MAZE SOLVING ALGORITHMS 3) Flood-fill algorithm
Flood-fill algorithm assigns a distance value between
In any maze solving system, the first stage is to any point (intersection) and the centre-point (destination).
compile a maze solving algorithm. This section discusses The flood-fill algorithm floods the maze when the robot
existing maze solving algorithms which may be reaches a new node [15].
employed in an autonomous maze solving robotic system. 4) Lee’s algorithm
There are various maze solving algorithms which aim to The Lee's algorithm offers a simple solution for maze
find the path between the source-point and the routing problems based on breadth first search strategy,
destination-point. In this section, we classify the maze and it is able to explore the possible paths between any
solving algorithms into two categories according to the two points if exit, and guarantees the minimum path.
deployment of the solver robotic system. The categories Through the Lee's algorithm, (a) an initial point is added
are as follows: known environment algorithms (solver to the queue, (b) then valid neighbouring cells are added
robot has a prior knowledge about the maze area), to the queue, (c) next the queue element is removed from
unknown environment algorithms (solver robot solves the the queue and continue to the next element. The steps (a)-
maze with no prior knowledge of the maze area). Fig. 1 (c) are repeated till the queue is empty [16].
shows the classification of maze solving algorithms. 5) Soukup algorithm
Soukup algorithm combines both the breadth first and
depth first search algorithms. Through the Soukup

© 2021 Int. J. Mech. Eng. Rob. Res 669

 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

algorithm, the line search is first conducted toward the solve a maze. The solver robot travels around the maze
destination-point, and then an expansion is processed to aiming to find the destination point. A solver robot
'bubble' around the wall as soon as the line search detects follows a straight line until an obstruction is reached,
a wall. The Soukup algorithm is 10-50 times faster than where there is a choice of more than one path
the Lee's algorithm [17]. (intersection-point). At this point, the robot makes a
6) Hadlock algorithm random decision as to which path it takes. It continues
Hadlock algorithm is a shortest path algorithm for grid straight ahead until it comes to the next intersection. At
graphs. Hadlock algorithm is an enhancement of Lee's each intersection, the solver robot randomly turns right or
algorithm which reduces the processing time through the left, however, it never goes back along the path it came
expansion phase by biasing the search in the target's path. from. This method can be implemented by an
The Hadlock algorithm uses a value known as detour unintelligent robot [23].
value, which is the path from the source to a grid-point 4) Pledge algorithm
that reveals the number of grids that this path has The wall follower algorithm is a part of the Pledge
detoured away from the target-point. Hadlock algorithm algorithm solution. The Pledge algorithm is a maze
guarantees that a shortest-path connection will be found if traversing algorithm used when the walls are disjointed
exist [18]. and there are obstacles present. The robot keeps the
7) Heuristic search algorithm obstacle either on its left or right-hand side, and keeps
The heuristic search algorithm is based on the concept track of all turns using a counter, where a right-turn
of ‘greedy best first’ search, which is like the breadth- increases the counter and a left-turn decreases the counter.
first search. The heuristic search algorithm explores When the counter reaches zero, the solver robot has
multiple paths in parallel, and the best-first focuses on traversed the obstacle and it continues on its path for the
paths which are closest to the goal. The distance from the right-hand side algorithm. The solver robot always begins
goal serves as a heuristic to direct the search. The major by turning left, then for every movement it applies the
drawback for the heuristic algorithm is its space following logic: if there is no obstacle on the right, it
complexity, since it stores all generated nodes in memory. moves right; if there is an obstacle on the right, but no
obstacle in front, it moves forward; if there are obstacles
B. Unknown-Maze Enviroments-Based Maze Solving
on the right and in front, then it turns left. The solver
Algorithms
robot will continue this way, counting each turn until the
The following algorithms can be deployed in unknown counter reaches zero again [24, 25].
environments where the solver robot has no prior The above algorithms guarantee to solve different
knowledge of the maze area. These algorithms include types of maze with no prior knowledge of the maze
wall follower, Tremaux’s algorithm, random mouse and environment. However, whenever multiple paths exist
Pledge. these algorithms do not offer the shortest path possible
1) Wall-follower algorithm between the source and destination points.
The wall follower is the most common maze solving
algorithm, where its main idea is to follow walls in the IV. AUTONOMOUS MAZE SOLVING ROBOTIC SYSTEMS
maze area. The solver robot observes the right or left wall
and moves throughout the maze area until it finds the way Various autonomous maze solving robotic systems
out. There are two possible rules in the wall follower, the have been proposed recently. Each system employs one
left-hand rule and right-hand rule. The turning priority of the maze solving algorithms discussed earlier. In this
will be either to the left or to the right depending on the section, we discuss the existing autonomous maze solving
rule chosen [19, 20]. robotic systems. In addition, we categorize the existing
2) Tremaux’s algorithm systems into two categories based on the navigation
This algorithm requires drawing lines on the floor to method employed: camera-based systems and sensor-
mark a path. It is guaranteed to work with all mazes that based systems, as presented in Fig. 2.
have well defined passages. Tremaux’s algorithm works Autonomous maze
according to the following rules: if a junction that has no solving robotic systems
marks (unvisited), then choose an arbitrary unmarked
path, follow it and then mark it as visited. If a junction
Camera-based
has one mark, turn around and return along that path, systems
marking it a second time as visited. This situation can
occur when the robot reaches a dead end. If a junction has
Sensor-based
more than one mark, arbitrarily choose one of the systems
remaining paths with the fewest marks, follow that path
Line follower
and mark it as visited. However, when the robot finally
systems
reaches the destination, paths marked just once will
indicate a way back to the start [21, 22]. Wall follower
3) Random mouse algorithm systems
Random mouse algorithm can be implemented using
any robot, and works in the same way as a mouse would Figure 2. Classification of autonomous maze solving robotic systems

© 2021 Int. J. Mech. Eng. Rob. Res 670

 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

A. Camera-Based Systems maintaining the integrity of the potentials. The designed

The image-processing-based solving robot systems robotic system consists of five infrared proximity
require capturing the entire image of the maze area using detectors which detect the presence of the walls. I.
a digital camera in order to analyse and process the Elshamarka, & S. Abu Bakar [33] presented a maze
maze’s paths, determine the possible paths between the solving robot algorithm designed to solve a maze based
source and destination points, and identify shortest path on the flood-fill algorithm. The algorithm consists of four
possible. M. Aqel et al. [26] proposed a maze solving main stages: Mapping, Flooding, Updating and Turning.
robotic system which is based on image processing Three ultrasonic sensors are deployed in order to estimate
technique and artificial intelligence algorithm. The entire the distance to the walls surrounding the robotic system.
image of the maze is captured using a web camera and I. Arya et al. [34] presented an autonomous robotic
then the maze solving process is performed completely system to navigate the unknown terrain and then explore
outside the maze by a computer. the maze using multiple experimental mapping and
The work presented in [27] includes the design and navigation algorithms based on ultrasonic sensors. This
development of a maze solving robotic system based on work [35] introduced the concept of robot maze solving
image processing and path finding techniques. O. Kathe using the virtual maze environment. F. Annaz. examined
et al. revealed that the proposed system works faster the performance of various types of robots within various
because the maze’s data are acquired beforehand rather board algorithms, where two maze solving algorithms
than travelling through the maze cell by cell. A. Chandak were implemented to solve mazes generated by users: a
et al. [28] proposed a wave-front based algorithm to primary navigation algorithm for systematic discovery
create a path for a robot to travel through an indoor and a proximity algorithm for optimized rescue.
environment. The 4-points and 8-points connectivity- The work presented in [36] includes the design and
based algorithms are presented for the purpose of path development of an autonomous navigation robot, which
generation. is based on the Left Straight Right Back (LSRB)
B. Rahnama et al. [29] introduced a maze solving algorithm and the Right Straight Left Back (RSLB)
algorithm which avoids the robot having to go through a algorithm. The developed robotic system employs
long navigation process. This algorithm is based on infrared and ultrasonic sensors for navigation. I.
image processing and shortest path algorithms. The Elshamarka & A. Saman [37] designed a maze solving
proposed system works efficiently because of the pre- robotic system using the flood-fill algorithm. The
processing of the maze image data rather than going designed solver robot was able to detect walls using
through the maze cell by cell. In reference [30], N. ultrasonic rangefinder sensors and was able to learn the
Barnouti et al. employed A* search algorithm to maze, find all possible paths and solve the maze using the
investigate the shortest path between the source and shortest path possible.
destination points through images that represent a map or The work presented in [38] includes the design and
a maze. The proposed algorithm was tested through development of an intelligent robotic system that is able
different maze environments. to solve the maze using the shortest possible distance,
The work presented in [31] includes a wireless where the maze area is divided into cells. The robot first
navigation mobile robotic system for path planning and navigates the area of interest and then finds the possible
trajectory execution within an indoor maze environment. paths between the source-point and the destination-point.
The proposed system is based on a camera in order to J. Su et al. [39] developed a half-size micro-mouse for
capture live images for the mobile robot within the maze international contests and mobile robot education. The J.
area. K. Lutvica et al. have developed an image Su et al. developed two new algorithms for enhancing the
processing and analysis algorithm which is able to resolution of position and velocity estimations and a
determine the robot's position and orientation based on time-based diagonal maze solver.
colour markers recognition. The results confirmed the C. Wu et al. [40] proposed a modified route-searching
robustness and effectiveness of the implemented robotic algorithm to find all potential paths in an unknown maze
system. area. The maze area is thought of as divided into grids,
where each grid has a maximum of four directions. In
B. Sensor-Based Systems addition, the C. Wu et al. presented a modified searching
Existing sensor-based maze solving robotic systems algorithm based on the traditional depth-first graph
can be classified into two sub-categories: rangefinder and traversal method.
line-follower. The former employs rangefinder In [41], R. Kumar et al. proposed an autonomous maze
technologies (such as infrared and ultrasonic sensors) to solving robot with independent mapping and localization
measure the distance between the solver robot and the operations, based on deploying three infrared sensors.
facing wall, whereas the later employs colour (light The designed robotic system was tested and solved out
intensity) sensors to follow the line drawn on the floor in the maze successfully without any interruption with walls
order to explore the correct path to the destination points. and objects. On the other hand, a wall follower-based
The rangefinder systems are discussed first. The work maze solving robotic system is presented in reference
presented in reference [32] provides experimental and [42]. The mobile robot was capable of solving the maze
simulated results for an efficient maze solving algorithm and calculating the total distance travelled to reach the
which provides locally optimized path choices while

© 2021 Int. J. Mech. Eng. Rob. Res 671

 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

final destination. The mobile robot was equipped with the flood-fill algorithm is able to explore the path
ultrasonic sensors in order to detect the presence of walls. between the source-point and destination-point with no
The work presented in [43] includes the design and requirements or pre-assumptions, in addition, the flood-
development of an autonomous solver robot system fill algorithm finds the shortest path to the centre of the
which combines the Pledge algorithm with the Flood-fill maze. However, the flood-fill algorithm requires the
algorithm, named as MazeRobot, and consists of maze area to be divided into cells, which requires a large
ultrasonic range-finder sensors to detect the presence of memory and is expensive to update.
walls and wheel rotation decoders to estimate the The maze routing algorithm [14] is able to find the
travelled distance. possible paths between any two points in the maze area,
L. Bienias et al. [44] proposed a maze exploration and guarantees to find the connection between 2
algorithm that consists of two main phases: the terminals if exist, and promise to find out the shortest-
exploration of the whole maze area where all possible path possible. However, maze routing algorithm is slow
paths are determined, and then the runtime process. The and requires large memory size for dense layout. On the
proposed system integrates two maze solving algorithms: other hand, the Soukup is an efficient maze routing
Wall-follower, and Tremaux's algorithms, and real solving algorithm, but it has three minor disadvantages:
experiments were conducted using Arduino-robot (1) the initial and the target points have to be specified, (2)
platform with proximity and rotation sensors. the routes are suboptimal when the maze area becomes
The rest of this section discusses the line follower congested, and (3) the algorithm cannot guarantee the
systems. Norbert-Brendan, K. & Marius, T.C. [45] obtained path is the shortest one.
proposed a line follower-based maze solving robotic The maze solving algorithms for unknown
system based on the left-hand rule and dead-end filling environments were discussed. These include: wall
algorithms. The designed robotic system was able to offer follower, Tremaux’s algorithm, random mouse and
a reasonable solution. In [46], S. Sakib et al. proposed a Pledge. The wall follower algorithm [19, 20] is easy to
line follower algorithm for exploring and solving any implement, there is no need to know the robot’s location
kind of maze. The proposed maze mapping system is and orientation in the maze, and it only needs to follow
based on a coordinate system where the paths are the wall. However, the wall follower algorithm does not
calculated using the Dijkstra algorithm. work in every maze, especially those containing loops.
The work presented in [47] includes the design and On the other hand, Tremaux’s algorithm [21, 22] always
development of a line maze solver robot based on a finds a path to the destination-point and is able to explore
depth-first search algorithm. The robot was able to solve the direct path to the destination-point. However, in
out a non-loop maze in an average time of 84.97 seconds robotics, it is hard to implement Tremaux’s algorithm and
and a loop-maze in an average of 63.40 seconds. On the large mazes require large memory space to store the
other hand, R. Musridho et al. [48] proposed a line maze visited paths.
solving algorithm to explore and solve a maze area made Random mouse algorithm does not record where the
up of curved and zigzag lines. The new algorithm robot has been, but only decides where to go next. The
successfully solved the maze with a curved and zigzag solver robot could wander for hours when taking wrong
structure. turns and there is a strong possibility that the robot will
A. Khan et al. [49] proposed an autonomous maze not find the exit in the time allocated. Although this
solving robot with turning indicators and the ability to method would always eventually find the solution, this
navigate itself through any environment. The work algorithm can be extremely slow. Therefore, random
presented in [50] includes a simple autonomous robotic mouse algorithm is inefficient in terms of speed and
system (Lego Ev3) with limited on-board resources to accuracy.
employ a line follower maze solving algorithm. Wall follower algorithms can solve mazes when the
entrance and exit are on the outer walls of the maze.
V. DISCUSSION However, wall follower algorithms fail to solve the maze
if the robot starts inside the maze area. The Pledge
For any solver robot, the navigation process is the algorithm can solve this problem, since it is designed to
main task that intends to explore the possible paths
circumvent obstacles and requires a random direction to
between the source and destination points, and may then
go through. The Pledge algorithm allows a robot with
employ routing algorithms to find out the shortest path compass to find the path from any point in the maze area
between any two points [51]. In this paper, the maze to the exit. However, this algorithm will not work in
solving algorithms have been divided into two categories:
reverse, i.e., finding a path from the exit to the entrance.
algorithms for known environments and algorithms for
The Pledge algorithm is more powerful than wall
unknown environments. This section analyses the follower algorithm and can solve mazes that wall
existing maze solving algorithms and evaluates the follower cannot.
existing solver robot systems.
Table I presents a comparison of the maze solving
The dead-end filling algorithm [13] finds all the dead
algorithms discussed earlier. The maze solving
ends in the maze area in order to explore the path from algorithms have been compared according to the
the source-point to destination-point. However, the dead- following issues:
end algorithm is inefficient in robotics, since the robot
has to look at the entire maze at once. On the other hand,

© 2021 Int. J. Mech. Eng. Rob. Res 672

 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

 Memory size: the total size of memory required TABLE I. A COMPARISON BETWEEN THE MAZE SOLVING
ALGORITHMS
to process the maze solving algorithm through
the robotic processor. Maze Memory Implement Algorithm Obtain
Solving size ation with Complexity the
 Implementation with robotics: the ability to Algorith robotics shortes
implement the maze solving algorithm in robotic m t path
systems. Dead-end Large Hard O(PN) ×
 Algorithm complexity: this measures the amount Maze Large Medium O(r×c) √
routing r: rows
of time it takes to run the maze solving c: columns
algorithm.

Known environment algorithms

Flood-fill Large Medium O(r×c) √
 Obtain the shortest path: can the maze solving
algorithm find the shortest path in the maze area Lee's Large Medium O(r×c) √
(requires
when more than one path exists between the grid
source and destination points. structure)
In section 4, we discussed the existing solver robot Soukup Large Medium O(r×c) ×
systems and placed them into two main categories based (requires 10-50 times
grid faster than
on the method used to solve the maze: camera-based structure) Lee’s
systems and sensor-based systems. algorithm
The existing image processing-based maze solving Hadlock Large Medium O(r×c) √
robotic systems [26-31] reduce the total time required to (requires
solve the maze. In addition, they offer efficient path grid
structure)
planning and achieve reliable navigation in small Heuristic Large Hard O(bd)
environments (for instance 2 m × 2 m). However, image d: depth of
processing-based solutions require a camera to capture solution
the maze area. Moreover, an efficient processor and b: the
branching
memory are required in order to process and analyse the factor
captured images and explore the possible paths. Finally, Wall- Medium Easy O(n2) ×
image processing-based systems are inapplicable in large follower n: # of
maze areas and real situations where it is impossible to junctions in
the maze area
capture the maze area.
Unknown environment algorithms

Sensor-based systems are efficient solutions in terms Tremaux’ Large Hard O(n2) ×
of cost and reliability. The rangefinder-based robotic s n: # of
systems [32-40] employ rangefinder sensors to determine junctions in
the maze area
the distance between the robot and the wall. These
systems are easy to implement, inexpensive and efficient. Random Low Easy O(n2) ×
The line follower maze solving robotic systems [45, 46, mouse n: # of
47, 48, 49, 50] are similar to the wall follower systems, junctions in
the maze area
however they differ in the technology used in the
navigation process, since the line follower systems are Pledge Medium Medium O(n2) ×
based on sensing the colour placed on the floor in order to n: # of
junctions in
determine the direction of the solver robot. These systems the maze area
are efficient in terms of cost, but they fail in
environments with no light source. Table II presents a
comparison between the existing solver robot systems TABLE II. A COMPARISON BETWEEN THE MAZE SOLVER ROBOT
where the systems are evaluated according to the SYSTEMS
following issues: Maze solver Efficiency Maze System Cost
1. Efficiency: this evaluates the productivity of the technique Area Complexity
maze solver robotic system in all environments. Camera- high Small Requires High
2. Maze area: this assesses the efficiency of the based efficiency areas processing for
systems in small the captured
solver robot in any size environment in order to areas images
accomplish the mission that the solver robot
Rangefinder Efficient in Any Sensing data can Low
designed to. systems areas with maze be processed
3. Robot solver Complexity: this measures the walls area using any
solver robot design and implementation. The size microcontroller
requirement for complicated sensors increases
the complexity of the solver robot design. Line follower Efficient in Any Sensing data can Low
4. Cost: the maze solver robot cost plays a systems areas with maze be processed
significant role on the total efficiency of the lines drawn area using any
size microcontroller
maze robotic solver system.

© 2021 Int. J. Mech. Eng. Rob. Res 673

 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

VI. CONCLUSION & FUTURE WORK [9] M. L. Delle-Monache, J. Sprinkle, R. Vasudevan, and D. B. Work,
“Autonomous vehicles: From vehicular control to traffic control,”
Several maze solving algorithms have been proposed HAL-Inria, 2019.
with diverse structure and efficiency. However, there is [10] S. M. Farritor and M. E. Rentschler, “Robotic highway safety
markers,” in Proc. ASME 2002 International Mechanical
no perfect maze solving algorithm for this purpose. The Engineering Congress and Exposition, pp. 833-839, American
deployment of a certain maze solving algorithm depends Society of Mechanical Engineers Digital Collection, January, 2002.
on several factors including: area size, area complexity, [11] N. Ruangpayoongsak, H. Roth, and J. Chudoba, “Mobile robots
area structure, deployment cost and complexity. In this for search and rescue,” in Proc. IEEE International Safety,
Security and Rescue Rototics, Workshop, 2005, pp. 212-217, June,
paper, we investigated the maze solving algorithms and 2005.
categorized them in terms of the deployed maze [12] H. Sugiyama, T. Tsujioka, and M. Murata, “Coordination of
environment into two categories. In addition, we rescue robots for real-time exploration over disaster areas,”
discussed the recent deployment of maze solving robotic in Proc. 2008 11th IEEE International Symposium on Object and
Component-Oriented Real-Time Distributed Computing (ISORC) ,
systems and a critical analysis is presented, in order to 2008, pp. 170-177,.
guide researchers and developers for choosing the most [13] H. Abelson and A. DiSessa, Turtle Geometry: The Computer as a
suitable maze solving algorithm. Medium for Exploring Mathematics, MIT press. 1986.
[14] M. Fattah, A. Airola, R. Ausavarungnirun, N. Mirzaei, P. Lileberg,
J. Plosial, S. Mohammadi, T. Pahikkala, O. Mutlu, H. Tenhunen,
CONFLICT OF INTEREST "A low-overhead, fully-distributed, guaranteed-delivery routing
algorithm for faulty network-on-chips," in Proc. the 9th
The authors declare that there is no conflict of interest. International Symposium on Networks on Chip. ACM. 2015.
[15] A. Glassner, "Graphics gems I". San Francisco: Morgan
AUTHOR CONTRIBUTIONS Kaufmann Publishers Inc. 1990.
[16] C. Y. Lee, “An algorithm for path connections and its
Ms. Shatha reviewed the recent developed maze applications,” IRE Transactions on Electronic Computers, vol. 3,
solving algorithms. Ms. Shuruq conducted the research pp. 346-365, 1961.
[17] J. I. R. I, Soukup, “Fast maze router,” in Proc. the 15th Design
on the existing maze solving robotic system, whereas Ms. Automation Conference, pp. 100-102, IEEE Press, 1978.
Wejdan discussed the maze solving algorithms, Ms. [18] F. O. Hadlock, “A shortest path algorithm for grid
Hadeel discussed the maze solving robotic systems, and graphs,” Networks, vol. 7, no. 4, pp. 323-334. 1977.
Ms. Ahad performed a comparison study among the [19] D. Hanafi, Y. Abueejela, and M. Zakaria, "Wall follower
autonomous robot development applying fuzzy incremental
existing robotic systems, and Dr. Tareq Alhmiedat wrote controller," Intelligent Control and Automation, vol. 4, no. 01,
the paper. p.18, 2013.
[20] M. Al-Khawaldah, O. Badran, and I. Al-Adwan, "Exploration
ACKNOWLEDGMENT algorithm technique for multi-robot collaboration," Jordan
Journal of Mechanical and Industrial Engineering, vol. 5, no. 2.
The authors wish to thank the Industrial Innovation pp. 177-184. 2011.
[21] Public conference, December 2, 2010 – by professor Jean
and Robotics Center at the University of Tabuk. Pelletier-Thibert in Academie de Macon (Burgundy – France) –
(Abstract published in the Annals academic, March 2011 –
REFERENCES ISSN 0980-6032) Charles Tremaux (1859–1882) Ecole
Polytechnique of Paris (X:1876), French engineer of the telegraph.
[1] C. Wang, L. Meng, S. She, I. M. Mitchell, T. Li, F. Tung, W. Wan, 2010.
M. Q. H. Meng, C. W. De Silva, “Autonomous mobile robot [22] E. Lucas,"Récréations Mathématiques," vol. I, 1882.
navigation in uneven and unstructured indoor environments,” [23] M. Babula, “Simulated maze solving algorithms through unknown
in Proc. 2017 IEEE/RSJ International Conference on Intelligent mazes,” Organizing and Program Committee, vol. 13, 2009.
Robots and Systems (IROS), pp. 109-116, September, 2017. [24] D. Abelson. Turtle Geometry: The computer as a medium for
[2] A. Saman and I. Abdramane, "Solving a reconfigurable maze exploring mathematics,” 1980.
using hybrid wall follower algorithm," International Journal of [25] S. Papert, "Uses of technology to enhance education," MIT
Computer Applications, vol. 82, no. 3. 2013. Artificial Intelligence Memo, no. 298, 1973.
[3] S. Mishra and B. Pankaj, "Maze solving algorithms for micro [26] M. Aqel, A. Issa, M. Khdair, M. ElHabbash, M. AbuBaker, and M.
mouse," in Proc. 2008 IEEE International Conference on Signal Massoud, "Intelligent maze solving robot based on image
Image Technology and Internet Based Systems, pp. 86-93, 2008. processing and graph theory algorithms," International
[4] B. Gupta and S. Sehgal, "Survey on techniques used in Conference on Promising Electronic Technologies (ICPET), pp.
autonomous maze solving robot," in Proc. 2014 5th International 48-53. 2017.
Conference-Confluence: The Next Generation Information [27] O. Kathe, T. Varsha A. Jagtap, and G. Gidaye, "Maze solving
Technology Summit, 2014, pp. 323-328. robot using image processing," IEEE Bombay Section Symposium
[5] N. Kumar and S. Kaur, “A review of various maze solving (IBSS), pp. 1-5. 2015.
algorithms based on graph theory,” International Journal for [28] A. Chandak, G. Ketki, G. Shalaka, A. Sumeet & P. Kulkarni.
Scientific Research & Development, vol. 6, no. 12, 2019. "Path planning for mobile robot navigation using image
[6] R. C. Arkin and R. R. Murphy, “Autonomous navigation in a processing," International Journal of Scientific & Engineering
manufacturing environment,” IEEE Transactions on Robotics and Research, vol. 4, no. 6, pp, 1490-1495, 2013.
Automation, vol. 6, no. 4, pp. 445-454. 1990. [29] B. Rahnama, A. Elçi, and S. Metani, "An image processing
[7] P. J. Costa, N. Moreira, D. Campos, J. Gonçalves, J. Lima, P. L. approach to solve labyrinth discovery robotics problem," in Proc.
Costa, “Localization and navigation of an omnidirectional mobile The 36th Annual Computer Software and Applications Conference
robot: The robot@ factory case study,” IEEE Revista pp. 631-636, 2012.
Iberoamericana de Tecnologias del Aprendizaje, vol. 11, no. 1, pp. [30] N. Barnouti, S. Al-Dabbagh, M. Naser, "Pathfinding in strategy
1-9, 2016. games and maze solving using A search algorithm," Journal of
[8] H. Sahin and L. Guvenc, “Household robotics: Autonomous Computer and Communications, vol. 4, no. 11, p. 15. 2016.
devices for vacuuming and lawn mowing [applications of [31] K. Lutvica, J. Velagić, N. Kadić, N. Osmić, G. Džampo, and H.
control],” IEEE Control Systems Magazine, vol. 27, no. 2, pp. 20- Muminović, "Remote path planning and motion control of mobile
96, 2007. robot within indoor maze environment," International Symposium
on Intelligent Control (ISIC), pp. 1596-1601, 2014.

© 2021 Int. J. Mech. Eng. Rob. Res 674

 International Journal of Mechanical Engineering and Robotics Research Vol. 10, No. 12, December 2021

[32] L. Wyard-Scott, and M. Meng, "A potential maze solving [49] A. Khan, G. Rana, M. Rabin, F. Mitul, and M. Shahjahan, "Design
algorithm for a micromouse robot," in Proc. IEEE Pacific Rim and implementation of a robot for maze-solving with turning
Conference on Communications, Computers, and Signal indicators using PID controller," in Proc. 2013 International
Processing. Proceedings, pp. 614-618, 1995. Conference on Informatics, Electronics and Vision (ICIEV),
[33] I. Elshamarka and S. Abu Bakar, "Design and implementation of a 2013, pp. 1-6.
robot for maze-solving using flood-fill algorithm," International [50] C. Saranya, M. Unnikrishnan, S. Ali, D. Sheela, and V.
Journal of Computer Applications, vol. 56, no. 5, 2012. Lalithambika, "Path planning algorithm for maze: Design and
[34] I. Arya, G. Fiona K. Sohum, M. Karan, R. Daniella B. Jacob implementation in LEGO mindstorms rover," in Proc. 2017
"Autonomously solving mazes with robots," Thesis for Bachelor International Conference on Inventive Computing and Informatics
of Science in Electronics and Telecommunication Engineering, (ICICI), 2017, pp. 189-193.
2017. [51] T. A. Alhmiedat, A. Abutaleb, and G. Samara, “A prototype
[35] F. Annaz, "A mobile robot solving a virtual maze navigation system for guiding blind people indoors using NXT
environment," International Journal of Electronics, Computer and Mindstorms,” International Journal of Online and Biomedical
Communications Technologies, vol. 2, no. 2. 2012. Engineering (iJOE), vol. 9, no. 5, pp. 52-58. 2013.
[36] A. Islam, F. Ahmad, and P. Sathya, "Shortest distance maze
solving robot," IJRET: International Journal of Research in Copyright © 2021 by the authors. This is an open access article
Engineering and Technology, vol. 5, no. 7. 2016. distributed under the Creative Commons Attribution License (CC BY-
[37] I. Elshamarka and A. Saman, "Design and implementation of a NC-ND 4.0), which permits use, distribution and reproduction in any
robot for maze-solving using flood-fill algorithm," International medium, provided that the article is properly cited, the use is non-
Journal of Computer Applications, vol. 56, no. 5, 2012. commercial and no modifications or adaptations are made.
[38] S. Tjiharjadi, C Wijaya, and E. Setiawan, "Optimization maze
robot using A* and flood fill algorithm," International Journal of
Mechanical Engineering and Robotics Research, vol. 6, no. 5. Shatha Alamri is a Teaching Assistant in the Department of Computer
2017. Science, and she has been involved in the Industrial Innovation &
[39] J. Su, X. Cai, C. Lee, and C. Chen. "The development of a half- Robotics Center at the University of Tabuk, Tabuk, Saudi Arabia, 2018.
size micromouse and its application in mobile robot education," Her main research in the field of AI and robotics. Ms. Shatha is
in Proc. 2016 International Conference on Advanced Robotics and currently completing her master's degree in computer science at King
Intelligent Systems (ARIS), 2016, pp. 1-6. Saud University, Riyadh, Saudi Arabia.
[40] C. Wu, D. Liaw, and H. Lee, "A method for finding the routes of
mazes," in Proc. 2018 International Automatic Control
Conference (CACS), 2018, pp. 1-4. Shuruq Al-Shehri, is a Teaching Assistant in the Department of
[41] R. Kumar, P. Jitoko, S. Kumar, K. Pillay, P. Prakash, A. Sagar, R. Computer Science, in the Faculty of Computers & Information
Singh, and U. Mehta, "Maze solving robot with automated Technology, at the University of Tabuk. She received a BSc degree in
obstacle avoidance," Procedia Computer Science, vol. 105, pp. Computer Science from the Faculty of Computers and Information
57-61. 2017 Technology, University of Tabuk , Tabuk , Saudi Arabia , 2019.
[42] S. Chua, J. Dominguez, J. Limqueco, E. Lu, S. Que, J. Rosario,
and D. Abuan, "Development of a maze solving mobile robot
capable of tracking the distance it traversed," Advanced Science Wejdan Alshehri has completed her BSc degree in the Department of
Letters, vol. 24, no. 11, pp. 8640-8646. 2018. Computer Science from the Faculty of Computers & Information
[43] S. Tjiharjadi, “Design and implementation of flood fill and pledge Technology, at the University of Tabuk, Saudi Arabia, 2019.
algorithm for maze robot,” International Journal of Mechanical
Engineering and Robotics Research, vol. 8, no. 4, 2019.
[44] L. Bienias, K. Szczepański, & P. Duch. “Maze exploration Hadeel Alamri has completed her BSc degree in the Department of
algorithm for small mobile platforms,” Image Processing & Computer Science from the Faculty of Computers & Information
Communications, vol. 21, no. 3, pp.15-26. 2016. Technology, at the University of Tabuk, Saudi Arabia, 2019.
[45] K. Norbert-Brendan and T. C. Marius, "Autonomous line maze
solver using artificial intelligence,” in Proc. 15th International
Conference on Engineering of Modern Electric Systems (EMES), Ahad Alaklabi has received BSc degree in Computer Science from the
2019, pp. 133-136. Faculty of Computers and Information Technology, University of
[46] S. Sakib, A. Chowdhury, S. Ahamed, and S. Hasan, "March. maze Tabuk , Tabuk , Saudi Arabia , 2019.
solving algorithm for line following robot and derivation of linear
path distance from nonlinear path," in Proc. 16th International Tareq Ahmiedat is an Associate Professor in the
Conference on Computer and Information Technology, pp. 478- Department of Computer Science, and the head of
483. 2014. Robotics & Artificial Intelligence Unit, in the
[47] A. Hidayatullah, A. Jati, and C. Setianingsih, "Realization of Industrial Innovation & Robotics Center at
depth first search algorithm on line maze solver robot," in University of Tabuk, Tabuk, Saudi Arabia. His
Proc. 2017 International Conference on Control, Electronics, research interests include tracking mobile targets
Renewable Energy and Communications (ICCREC), 2017, pp. through Wireless Sensor Networks, robot
247-251. navigation and orientation, and robot vision
[48] R. Musridho, F. Yanto, H. Haron, and H. Hasan, "Improved line systems. Dr. Alhmiedat has been involved in
maze solving algorithm for curved and zig-zag track," in Proc. 7th various research projects including: SafetyNET, IndoorTrack, Diabetic
ICT International Student Project Conference (ICT-ISPC), 2018, Robot (SARA), and WSN environment monitoring.
pp. 1-6.

© 2021 Int. J. Mech. Eng. Rob. Res 675

View publication stats