banner
Home > Open Journal Systems

Efficiency analysis of path-finding algorithms in a 2D grid environment

Ch Nirmal Prabhath, M. Kavitha, Kanak Kalita

Abstract


This paper offers a focused overview of pathfinding algorithms, particularly emphasizing Greedy Best First Search (G-BFS) and Rapidly-Exploring Random Trees (RRT). Their performance is evaluated within a 2D grid setting tailored for Unmanned Aerial Vehicles (UAVs). Divided into two main sections, the study first expounds on the theoretical underpinnings of these algorithms, followed by empirical validation. A series of systematic experiments, involving varied 2D grid dimensions and traversal patterns, facilitates a comparative analysis between G-BFS and RRT. Importantly, the real-world implementation of these algorithms in UAV navigation underscores their practicality, illuminating their respective execution times and resource utilization. While G-BFS thrives in straightforward scenarios, RRT, especially RRT*, displays superior capability in navigating more intricate and expansive terrains, albeit with marginally extended execution durations attributed to its explorative nature.


Keywords


RRT; G-BFS; path-finding problem; 2D grid; UAV

Full Text:

PDF

References


1. Aggarwal S, Kumar N. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges. Computer Communications. 2020, 149: 270-299. doi: 10.1016/j.comcom.2019.10.014

2. Han J. An efficient approach to 3D path planning. Information Sciences. 2019, 478: 318-330. doi: 10.1016/j.ins.2018.11.045

3. Wakabayashi T, Yukimasa Suzuki, Suzuki S. Dynamic obstacle avoidance for Multi-rotor UAV using chance-constraints based on obstacle velocity. Robotics and Autonomous Systems. 2023, 160: 104320. doi: 10.1016/j.robot.2022.104320

4. Patle BK, Babu L G, Pandey A, et al. A review: On path planning strategies for navigation of mobile robot. Defence Technology. 2019, 15(4): 582-606. doi: 10.1016/j.dt.2019.04.011

5. Fu YT, Hsu CM, Lee MC, et al. A Path Planning Algorithm based on Leading Rapidly-exploring Random Trees. In: Proceedings of the 2019 International Automatic Control Conference (CACS); 13-16 November 2019; Keelung, Taiwan. pp. 1-6.

6. Karur K, Sharma N, Dharmatti C, et al. A Survey of Path Planning Algorithms for Mobile Robots. Vehicles. 2021, 3(3): 448-468. doi: 10.3390/vehicles3030027

7. Zhang L, Manocha D. An efficient retraction-based RRT planner. In: Proceedings of the 2008 IEEE International Conference on Robotics and Automation; 19-23 May 2008; Pasadena, CA, USA. pp. 3743-3750.

8. Singh M, Dhillon JS. A Simple Opposition-based Greedy Heuristic Search for Dynamic Economic Thermal Power Dispatch. Electric Power Components and Systems. 2016, 44(6): 589-605. doi: 10.1080/15325008.2015.1122113

9. Ahmed SS, Rao BPC, Jayakumar T. Greedy breadth-first-search based chain classification for nondestructive sizing of subsurface defects. Applied Soft Computing. 2016, 40: 260-273. doi: 10.1016/j.asoc.2015.11.032

10. Tian J, Chao T, Yang M, et al. A path planning algorithm based on improved RRT* for UAVs. In: Proceedings of the 2022 IEEE International Conference on Unmanned Systems (ICUS); 28-30 October 2022; Guangzhou, China. pp. 1-6.

11. Wang Y, Xi M, Weng Y. Intelligent path planning algorithm of Autonomous Underwater Vehicle based on vision under ocean current. Expert Systems. 2023. doi: 10.1111/exsy.13399

12. Liu B, Xiao X, Stone P. A Lifelong Learning Approach to Mobile Robot Navigation. IEEE Robotics and Automation Letters. 2021, 6(2): 1090-1096. doi: 10.1109/lra.2021.3056373

13. Noto M, Sato H. A method for the shortest path search by extended Dijkstra algorithm. In: Proceedings of the 2000 IEEE International Conference on Systems, Man and Cybernetics. “Cybernetics Evolving to Systems, Humans, Organizations, and their Complex Interactions” (Cat No00CH37166); 8-11 October 2000; Nashville, TN, USA. pp. 2316-2320.

14. Duchoň F, Babinec A, Kajan M, et al. Path Planning with Modified a Star Algorithm for a Mobile Robot. Procedia Engineering. 2014, 96: 59-69. doi: 10.1016/j.proeng.2014.12.098

15. Heusner M, Keller T, Helmert M. Best-Case and Worst-Case Behavior of Greedy Best-First Search. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence; 13-19 July 2018; Stockholm, Sweden. pp. 1463-1470.

16. Tripathy HK, Mishra S, Thakkar HK, et al. CARE: A Collision-Aware Mobile Robot Navigation in Grid Environment using Improved Breadth First Search. Computers & Electrical Engineering. 2021, 94: 107327. doi: 10.1016/j.compeleceng.2021.107327

17. Gao P, Liu Z, Wu Z, et al. A Global Path Planning Algorithm for Robots Using Reinforcement Learning. In: Proceedings of the 2019 IEEE International Conference on Robotics and Biomimetics (ROBIO); 6-8 December 2019; Dali, China. pp. 1693-1698.

18. Navya P, Ranjith R. Analysis of Path Planning Algorithms For Service Robots in Hospital Environment. In: Proceedings of the 2021 12th International Conference on Computing Communication and Networking Technologies (ICCCNT); 6-8 July 2021; Kharagpur, India. pp. 1-6.

19. Li Q, Xie F, Zhao J, et al. FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search. Remote Sensing. 2022, 14(15): 3720. doi: 10.3390/rs14153720

20. Yuanhao H, Shi H, Hao W, et al. Application of 3-D Path Planning and Obstacle Avoidance Algorithms on Obstacle-Overcoming Robots. In: Proceedings of the 2023 IEEE 5th Eurasia Conference on Biomedical Engineering, Healthcare and Sustainability (ECBIOS); 2-4 June 2023; Tainan, Taiwan. pp. 207-212.

21. Paces P, Udatny V. Comparison of Flight-Planning Algorithms in View of Certification Requirements. In: Proceedings of the 2019 IEEE/AIAA 38th Digital Avionics Systems Conference (DASC); 8-12 September 2019; San Diego, CA, USA. pp. 1-8.

22. Gnanaraj AAM, Abbas Ali F, Arumugam AC, et al. Hierarchical IoT network management and cloud computing to make healthcare green. AIP Conference Proceedings. 2023, 2581(1): 070001. doi: 10.1063/5.0126165

23. Kumar SV, Mary GAA, Mahdal M. Integrated Edge Deployable Fault Diagnostic Algorithm for the Internet of Things (IoT): A Methane Sensing Application. Sensors. 2023, 23(14): 6266. doi: 10.3390/s23146266

24. Vásconez JP, Basoalto F, Briceño IC, et al. Comparison of path planning methods for robot navigation in simulated agricultural environments. Procedia Computer Science. 2023, 220: 898-903. doi: 10.1016/j.procs.2023.03.122

25. Cao S, Fan P, Yan T, et al. Inland Waterway Ship Path Planning Based on Improved RRT Algorithm. Journal of Marine Science and Engineering. 2022, 10(10): 1460. doi: 10.3390/jmse10101460

26. Karaman S, Walter MR, Perez A, et al. Anytime Motion Planning using the RRT*. In: Proceedings of the 2011 IEEE International Conference on Robotics and Automation; 9-13 May 2011; Shanghai, China. pp. 1478-1483.

27. Melchior NA, Simmons R. Particle RRT for Path Planning with Uncertainty. In: Proceedings 2007 IEEE International Conference on Robotics and Automation; 10-14 April 2007; Rome, Italy. pp. 1617-1624.

28. Kang JG, Lim DW, Choi YS, et al. Improved RRT-Connect Algorithm Based on Triangular Inequality for Robot Path Planning. Sensors. 2021, 21(2): 333. doi: 10.3390/s21020333

29. Ma H, Meng F, Ye C, et al. Bi-Risk-RRT Based Efficient Motion Planning for Autonomous Ground Vehicles. IEEE Transactions on Intelligent Vehicles. 2022, 7(3): 722-733. doi: 10.1109/tiv.2022.3152740

30. Mao S, Yang P, Gao D, et al. A Motion Planning Method for Unmanned Surface Vehicle Based on Improved RRT Algorithm. Journal of Marine Science and Engineering. 2023, 11(4): 687. doi: 10.3390/jmse11040687




DOI: https://doi.org/10.32629/jai.v7i2.1284

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 Ch Nirmal Prabhath, M. Kavitha, Kanak Kalita

License URL: https://creativecommons.org/licenses/by-nc/4.0/