A Simulation-Based Study of Maze-Solving-Robot Navigation for Educational Purposes

Ismu Rijal Fahmi; Dwi Joko Suroso

doi:10.18196/jrc.v3i1.12241

Authors

Ismu Rijal Fahmi Universitas Gadjah Mada
Dwi Joko Suroso Universitas Gadjah Mada http://orcid.org/0000-0003-3418-7259

DOI:

https://doi.org/10.18196/jrc.v3i1.12241

Keywords:

Robot simulation, Maze-solving robot, Random mouse, Wall follower, Pledge, Tremaux, Dead-end filling

Abstract

The point of education in the early stage of studying robotics is understanding its basic principles joyfully. Therefore, this paper creates a simulation program of indoor navigations using an open-source code in Python to make navigation and control algorithms easier and more attractive to understand and develop. We propose the maze-solving-robot simulation as a teaching medium in class to help students imagine and connect the robot theory to its actual movement. The simulation code is built for free to learn, improve, and extend in robotics courses or assignments. A maze-solving robot study case is then done as an example of implementing navigation algorithms. Five algorithms are compared, such as Random Mouse, Wall Follower, Pledge, Tremaux, and Dead-End Filling. Each algorithm is simulated a hundred times in every type of the proposed mazes, namely mazes with dead ends, loops only, and both dead ends and loops. The observed indicators of the algorithms are the success rate of the robots reaching the finish lines and the number of steps taken. The simulation results show that each algorithm has different characteristics that should be considered before being chosen. The recommendation of when-to-use the algorithms is discussed in this paper as an example of the output simulation analysis for studying robotics.

Author Biographies

Ismu Rijal Fahmi, Universitas Gadjah Mada

Department of Nuclear Engineering and Engineering Physics

Dwi Joko Suroso, Universitas Gadjah Mada

Department of Nuclear Engineering and Engineering Physics

References

J. C. Giger, N. Piçarra, P. Alves-Oliveira, R. Oliveira, and P. Arriaga, “Humanization of robots: Is it really such a good idea?,” Human Behavior and Emerging Technologies, vol. 1, no. 2. pp. 111–123, 2019.

F. Gul, W. Rahiman, and S. S. Nazli Alhady, “A comprehensive study for robot navigation techniques,” Cogent Engineering, vol. 6, no. 1. 2019.

A. M. J. Sadik, M. A. Dhali, H. M. A. B. Farid, T. U. Rashid, and A. Syeed, “A comprehensive and comparative study of maze-solving techniques by implementing graph theory,” Proc. - Int. Conf. Artif. Intell. Comput. Intell. AICI 2010, vol. 1, no. November, pp. 52–56, 2010.

A. Halma, E. Bovenkamp, and J. van Oorschot, “RoboMind Challenges Maze Solving,” RoboMind Academy, 2012. .

Si. F. R. Alves, J. M. Rosario, Hu. F. Filho, L. K. . RIncon, and R. A. . Yamasaki, “Conceptual Bases of Robot Navigation Modeling, Control and Applications,” Adv. Robot Navig., vol. 1, no. June, pp. 3–28, 2011.

F. Rubio, F. Valero, and C. Llopis-Albert, “A review of mobile robots: Concepts, methods, theoretical framework, and applications,” Int. J. Adv. Robot. Syst., vol. 16, no. 2, pp. 1–22, 2019.

J. Biswas and M. Veloso, “WiFi localization and navigation for autonomous indoor mobile robots,” Proc. - IEEE Int. Conf. Robot. Autom., pp. 4379–4384, 2010.

F. Fraundorfer et al., “Vision-based autonomous mapping and exploration using a quadrotor MAV,” IEEE Int. Conf. Intell. Robot. Syst., pp. 4557–4564, 2012.

D. J. Suroso, P. Cherntanomwong, P. Sooraksa, and J. Takada, “Location fingerprint technique using Fuzzy C-Means clustering algorithm for indoor localization,” in TENCON 2011 - 2011 IEEE Region 10 Conference, 2011, pp. 88–92.

D. J. Suroso, M. Arifin, and P. Cherntanomwong, “Distance-based Indoor Localization using Empirical Path Loss Model and RSSI in Wireless Sensor Networks,” J. Robot. Control, vol. 1, no. 6, pp. 199–207, 2020.

F. Y. M. Adiyatma, A. E. Kurniawan, D. J. Suroso, and P. Cherntanomwong, “Performance Comparison of Several Range- based Techniques for Indoor Localization Based on Received Signal Strength Indicator,” vol. 7, no. 1, pp. 40–53, 2021.

P. Cherntanomwong and D. J. Suroso, “Indoor localization system using wireless sensor networks for stationary and moving target,” 2011 8th Int. Conf. Information, Commun. Signal Process., no. 1, pp. 1–5, 2011.

O. Michel, “WebotsTM: Professional Mobile Robot Simulation,” vol. 1, no. 1, pp. 39–42, 2004.

E. Rohmer, S. P. N. Singh, and M. Freese, “V-REP: A versatile and scalable robot simulation framework,” IEEE Int. Conf. Intell. Robot. Syst., pp. 1321–1326, 2013.

J. Collins, S. Chand, A. Vanderkop, and D. Howard, “A review of physics simulators for robotic applications,” IEEE Access, vol. 9, no. i, pp. 51416–51431, 2021.

S. Van Der Walt, S. C. Colbert, and G. Varoquaux, “The NumPy array: A structure for efficient numerical computation,” Comput. Sci. Eng., vol. 13, no. 2, pp. 22–30, 2011.

J. D. Hunter, “Matplotlib: A 2D graphics environment,” Comput. Sci. Eng., vol. 9, no. 3, pp. 99–104, 2007.

F. Pedregosa et al., “Scikit-learn: Machine learning in Python,” J. Mach. Learn. Res., vol. 12, pp. 2825–2830, 2011.

L. Major, T. Kyriacou, and O. P. Brereton, “Systematic literature review: Teaching novices programming using robots,” IET Semin. Dig., vol. 2011, no. 1, pp. 21–30, 2011.

T. Sotiropoulos, H. Waeselynck, J. Guiochet, and F. Ingrand, “Can robot navigation bugs be found in simulation? An exploratory study,” Proc. - 2017 IEEE Int. Conf. Softw. Qual. Reliab. Secur. QRS 2017, pp. 150–159, 2017.

J. R. B. del Rosario et al., “Modelling and characterization of a maze-solving mobile robot using wall follower algorithm,” Appl. Mech. Mater., vol. 446–447, no. November 2013, pp. 1245–1249, 2014.

A. Zarkasi, H. Ubaya, C. Deri Amanda, and R. Firsandaya, “Implementation of ram based neural networks on maze mapping algorithms for wall follower robot,” J. Phys. Conf. Ser., vol. 1196, no. 1, 2019.

I. Elshamarka and A. Bakar Sayuti Saman, “Design and Implementation of a Robot for Maze-Solving using Flood-Fill Algorithm,” Int. J. Comput. Appl., vol. 56, no. 5, pp. 8–13, 2012.

S. Tjiharjadi, M. C. Wijaya, and E. Setiawan, “Optimization maze robot using A* and flood fill algorithm,” Int. J. Mech. Eng. Robot. Res., vol. 6, no. 5, pp. 366–372, 2017.

R. Balogh and D. Obdržálek, “Using Finite State Machines in Introductory Robotics,” Adv. Intell. Syst. Comput., vol. 829, no. April, pp. 85–91, 2019.

R. Hussain, T. Zielinska, and R. Hexel, “Finite state automaton based control system for walking machines,” Int. J. Adv. Robot. Syst., vol. 16, no. 3, pp. 1–14, 2019.

Ł. Bienias, K. Szczepański, and P. Duch, “Maze Exploration Algorithm for Small Mobile Platforms,” Image Process. Commun., vol. 21, no. 3, pp. 15–26, 2017.

L. K. Li, “Implementation of the Trémaux Maze Solving Algorithm to an Omnidirectional Mobile Robot,” in International Conference on Electronics, Information and Communication, 2018, pp. 1–3.

Y. F. Hendrawan, “Comparison of Hand Follower and Dead-End Filler Algorithm in Solving Perfect Mazes,” J. Phys. Conf. Ser., vol. 1569, p. 022059, 2020.

J. Y. Hii, J. Lee, and Y. Chuah, “Optimization and Simulation of A Navigation Robot in Mazes,” Int. J. Eng. Res. Technol., vol. 10, no. 05, pp. 222–227, 2021.