Download pdf
A comprehensive review of bug algorithms in path planning
- 1 Department of Mechanical Engineering, The Hong Kong Polytechnic University, Hong Kong, China
* Author to whom correspondence should be addressed.
Abstract
The bug algorithm family is the well-known navigation algorithm for robots in unknown environments. However, different types of bug algorithms have their own priorities and weaknesses based on different environmental conditions. According to the characteristics of the bug navigation algorithms, the bug algorithm family is mainly divided into 4 parts. In this paper, four types of bug algorithms (original bug algorithm, M-line Bug, Angel Bug and Range Bug) are presented along with typical samples of each type. Each type of algorithm will be thoroughly explained and exemplified, highlighting its unique characteristics and the suitable environmental conditions for each algorithm. By presenting the basic logic behind each algorithm and examining the environmental conditions they are best suited for, this paper aims to provide researchers with a comprehensive understanding of the bug algorithm family. Ultimately, this knowledge will contribute to the advancement of navigation capabilities in robots operating in unknown and challenging environments.
Keywords
bug algorithm, mobile robot, navigation algorithm, path planning
[1]. Kobayashi Y, Kanai S, Kikumoto C, and Sakoda K 2022 Design and Fabricate of Reconnaissance Robots for Nuclear Power Plants that Underwent Accidents. Journal of Robotics and Mechatronics, 34(3), 523–526.
[2]. Nosrati M S, Karimi R and Hasanvand H A 2012 Investigation of the * (Star) Search Algorithms: Characteristics, Methods and Approaches - TI Journals. World Applied Programming.
[3]. Dijkstra E 1959 A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271.
[4]. Hart P E, Nilsson N J and Raphael B 1968 A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
[5]. Mishra S and Bande P 2008 Maze Solving Algorithms for Micro Mouse. 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems, 86–93.
[6]. Maravall D, de Lope J and Fuentes J P n.d. Visual Bug Algorithm for Simultaneous Robot Homing and Obstacle Avoidance Using Visual Topological Maps in an Unmanned Ground Vehicle. Bioinspired Computation in Artificial Systems, 301–310. https://doi.org/10.1007/978-3-319-18833-1_32
[7]. Shaikh F K, Chowdhry B S, Zeadally S, Hussain D M A, Memon A A and Uqaili M A 2014 IBA: Intelligent Bug Algorithm A Novel Strategy to Navigate Mobile Robots Autonomously. In Communication Technologies, Information Security and Sustainable Development (Vol. 414, pp. 291–299). Switzerland: Springer International Publishing AG.
[8]. McGuire K N, de Croon G C H E and Tuyls K 2019 A comparative study of bug algorithms for robot navigation. Robotics and Autonomous Systems, 121, 103261–.
[9]. Ng J and Bräunl T 2007 Performance comparison of Bug navigation algorithms. Journal of Intelligent & Robotic Systems, 50(1), 73–84.
[10]. Oroko J A and Nyakoe G N 2022 Obstacle avoidance and path planning schemes for autonomous navigation of a mobile robot: a review. In Proceedings of the Sustainable Research and Innovation Conference (pp. 314-318).
[11]. Sankaranarayanan A and Vidyasagar M 1990 A new path planning algorithm for moving a point object amidst unknown obstacles in a plane. Proceedings., IEEE International Conference on Robotics and Automation, 1930–1936 vol.3.
[12]. Lumelsky V and Stepanov A 1986 Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Transactions on Automatic Control, 31(11), 1058–1063.
[13]. Al-Haddad A, Sudirman R, Omar C, Koo Yin Hui and bin Jimin M R 2012 Wheelchair motion control guide using eye gaze and blinks based on bug 2 algorithm. 2012 8th International Conference on Information Science and Digital Content Technology (ICIDT2012), 2, 438–443.
[14]. Menegatti E, Michael N, Berns K and Yamaguchi H 2015 A Minimalistic Quadrotor Navigation Strategy for Indoor Multi-floor Scenarios. In Intelligent Autonomous Systems 13 (Vol. 302, pp. 1561–1570). Springer International Publishing AG.
[15]. Kamon I and Rivlin E 1997 Sensory-based motion planning with global proofs. IEEE Transactions on Robotics and Automation, 13(6), 814–822.
[16]. Lee S, Adams T M and Ryoo B 1997 A fuzzy navigation system for mobile construction robots. Automation in Construction, 6(2), 97–107.
[17]. Al-Haddad A A, Sudirman R and Omar C 2011 Guiding Wheelchair Motion Based on EOG Signals Using Tangent Bug Algorithm. 2011 Third International Conference on Computational Intelligence, Modelling & Simulation, 40–45.
[18]. Tomita M and Yamamoto M 2008 A Navigation Algorithm for Avoidance of Moving and Stationary Obstacles for Mobile Robot. Nihon Kikai Gakkai ronbunshū. C, 74(748), 2976–2984.
[19]. Kamon I, Rimon E and Rivlin E 1998 TangentBug: A Range-Sensor-Based Navigation Algorithm. The International Journal of Robotics Research, 17(9), 934–953.
Cite this article
Liu,K. (2024). A comprehensive review of bug algorithms in path planning . Applied and Computational Engineering,33,259-265.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 2023 International Conference on Machine Learning and Automation
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).