Optimized Graph Search Algorithms for Exploration with Mobile Robot
Abstract
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.
Downloads
References
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.
Copyright (c) 2021 EMITTER International Journal of Engineering Technology
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
The copyright to this article is transferred to Politeknik Elektronika Negeri Surabaya(PENS) if and when the article is accepted for publication. The undersigned hereby transfers any and all rights in and to the paper including without limitation all copyrights to PENS. The undersigned hereby represents and warrants that the paper is original and that he/she is the author of the paper, except for material that is clearly identified as to its original source, with permission notices from the copyright owners where required. The undersigned represents that he/she has the power and authority to make and execute this assignment. The copyright transfer form can be downloaded here .
The corresponding author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors. This agreement is to be signed by at least one of the authors who have obtained the assent of the co-author(s) where applicable. After submission of this agreement signed by the corresponding author, changes of authorship or in the order of the authors listed will not be accepted.
Retained Rights/Terms and Conditions
- Authors retain all proprietary rights in any process, procedure, or article of manufacture described in the Work.
- Authors may reproduce or authorize others to reproduce the work or derivative works for the author’s personal use or company use, provided that the source and the copyright notice of Politeknik Elektronika Negeri Surabaya (PENS) publisher are indicated.
- Authors are allowed to use and reuse their articles under the same CC-BY-NC-SA license as third parties.
- Third-parties are allowed to share and adapt the publication work for all non-commercial purposes and if they remix, transform, or build upon the material, they must distribute under the same license as the original.
Plagiarism Check
To avoid plagiarism activities, the manuscript will be checked twice by the Editorial Board of the EMITTER International Journal of Engineering Technology (EMITTER Journal) using iThenticate Plagiarism Checker and the CrossCheck plagiarism screening service. The similarity score of a manuscript has should be less than 25%. The manuscript that plagiarizes another author’s work or author's own will be rejected by EMITTER Journal.
Authors are expected to comply with EMITTER Journal's plagiarism rules by downloading and signing the plagiarism declaration form here and resubmitting the form, along with the copyright transfer form via online submission.
