Optimized Graph Search Algorithms for Exploration with Mobile Robot

  • Aydın GULLU Electronics and Automation Department, Ipsala Vocational School, Trakya University, Edirne, Turkey
  • Hilmi KUŞÇU Department of Mechanical Engineering, Faculty of Engineering, Trakya University, Edirne, Turkey
Keywords: Optimized graph search, Real environment exploration, Dijkstra, Mobile Robot


Graph search algorithms and shortest path algorithms, designed to allow real mobile robots to search unknown environments, are typically run in a hybrid manner, which results in the fast exploration of an entire environment using the shortest path. In this study, a mobile robot explored an unknown environment using separate depth-first search (DFS)  and breadth-first search (BFS) algorithms. Afterward, developed DFS + Dijkstra and BFS + Dijkstra algorithms were run for the same environment. It was observed that the newly developed hybrid algorithm performed the identification using less distance. In experimental studies with real robots, progression with DFS for the first-time discovery of an unknown environment is very efficient for detecting boundaries. After finding the last point with DFS, the shortest route was found with Dijkstra for the robot to reach the previous node. In defining a robot that works in a real environment using DFS algorithm for movement in unknown environments and Dijkstra algorithm in returning, time and path are shortened. The same situation was tested with BFS and the results were examined. However, DFS + Dijkstra was found to be the best algorithm in field scanning with real robots. With the hybrid algorithm developed, it is possible to scan the area with real autonomous robots in a shorter time. In this study, field scanning was optimized using hybrid algorithms known.


Download data is not yet available.


Brass, P., I. Vigan, and N. Xu, Shortest path planning for a tethered robot. Computational Geometry, 2015. 48(9): p. 732-742. DOI: https://doi.org/10.1016/j.comgeo.2015.06.004

Moore, E.F., The shortest path through a maze. 1959: Bell Telephone System.

Zhan, F.B. and C.E. Noon, Shortest path algorithms: an evaluation using real road networks. Transportation Science, 1998. 32(1): p. 65-73. DOI: https://doi.org/10.1287/trsc.32.1.65

Zelinsky, A., A Mobile Robot Exploration Algorithm. Ieee Transactions on Robotics and Automation, 1992. 8(6): p. 707-717. DOI: https://doi.org/10.1109/70.182671

Adorni, G., et al., Vision-based localization for mobile robots. Robotics and Autonomous Systems, 2001. 36(2): p. 103-119. DOI: https://doi.org/10.1016/S0921-8890(01)00138-5

Nüchter, A., et al., 6D SLAM—3D mapping outdoor environments. Journal of Field Robotics, 2007. 24(8‐9): p. 699-722. DOI: https://doi.org/10.1002/rob.20209

del Rosario, J.R.B., et al. Modelling and Characterization of a Maze-Solving Mobile Robot Using Wall Follower Algorithm. in Applied Mechanics and Materials. 2014. Trans Tech Publ.

Cai, Z., L. Ye, and A. Yang. FloodFill Maze Solving with Expected Toll of Penetrating Unknown Walls for Micromouse. in High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS), 2012 IEEE 14th International Conference on. 2012. IEEE. DOI: https://doi.org/10.1109/HPCC.2012.209

Dain, R.A., Developing mobile robot wall-following algorithms using genetic programming. Applied Intelligence, 1998. 8(1): p. 33-41. DOI: https://doi.org/10.1023/A:1008216530547

Hanafi, D., Y.M. Abueejela, and M.F. Zakaria, Wall follower autonomous robot development applying fuzzy incremental controller. Intelligent Control and Automation, 2013. 4(01): p. 18. DOI: https://doi.org/10.4236/ica.2013.41003

Kwek, S. On a simple depth-first search strategy for exploring unknown graphs. in Workshop on Algorithms and Data Structures. 1997. Springer. DOI: https://doi.org/10.1007/3-540-63307-3_73

Everitt, T. and M. Hutter, Analytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search, in AI 2015: Advances in Artificial Intelligence. 2015, Springer. p. 157-165. DOI: https://doi.org/10.1007/978-3-319-26350-2_14

Everitt, T. and M. Hutter, Analytical Results on the BFS vs. DFS Algorithm Selection Problem: Part II: Graph Search, in AI 2015: Advances in Artificial Intelligence. 2015, Springer. p. 166-178.

Everitt, T. and M. Hutter, A topological approach to meta-heuristics: analytical results on the BFS vs. DFS algorithm selection problem. arXiv preprint arXiv:1509.02709, 2015. DOI: https://doi.org/10.1007/978-3-319-26350-2_15

Potamias, M., et al. Fast shortest path distance estimation in large networks. in Proceedings of the 18th ACM conference on Information and knowledge management. 2009. ACM. DOI: https://doi.org/10.1145/1645953.1646063

Bihlmaier, A., L. Winkler, and H. Worn. Automated planning as a new approach for the self-reconfiguration of mobile modular robots. in Robot Motion and Control (RoMoCo), 2013 9th Workshop on. 2013. IEEE. DOI: https://doi.org/10.1109/RoMoCo.2013.6614585

Ryu, H. and W.K. Chung, Local map-based exploration using a breadth-first search algorithm for mobile robots. International Journal of Precision Engineering and Manufacturing, 2015. 16(10): p. 2073-2080. DOI: https://doi.org/10.1007/s12541-015-0269-9

Subramanian, M.B., K. Sudhagar, and G. RajaRajeswari, Optimal Path Forecasting of an Autonomous Mobile Robot Agent Using Breadth First Search Algorithm. 2014.

Tarjan, R., Depth-first search and linear graph algorithms. SIAM journal on computing, 1972. 1(2): p. 146-160. DOI: https://doi.org/10.1137/0201010

Dijkstra, E.W., A note on two problems in connexion with graphs. Numerische mathematik, 1959. 1(1): p. 269-271. DOI: https://doi.org/10.1007/BF01386390

Electronics, P.R.a. Pololu 3pi Robot. 2016 [cited 2016 02.01.16]; Available from: https://www.pololu.com/product/975.

Costa, H., et al. A mixed reality game using 3Pi robots—“PiTanks”. in Information Systems and Technologies (CISTI), 2015 10th Iberian Conference on. 2015. IEEE.

Ribeiro, M.I. and P. Lima, Kinematics models of mobile robots. Instituto de Sistemas e Robotica, 2002: p. 1000-1049.

Mireles Jr, J., Kinematic models of mobile robots. Automation and Robotics Research Institute, University of Texas at Austin, 2004.

Siegwart, R., I.R. Nourbakhsh, and D. Scaramuzza, Introduction to autonomous mobile robots. 2011: MIT press.

How to Cite
GULLU, A., & KUŞÇU, H. (2021). Optimized Graph Search Algorithms for Exploration with Mobile Robot . EMITTER International Journal of Engineering Technology, 9(2), 222-238. https://doi.org/10.24003/emitter.v9i2.614