Classification of Algorithms for Constructing a Path Working with Obstacles
DOI:
https://doi.org/10.36910/4293-52779-2025-17-02-02Keywords:
algorithm, robot path, obstacle avoidance, simulation, data analysisAbstract
The paper provides an overview and classification of eleven algorithms for constructing a robot path with obstacles, divided into six categories: classical graph-based approaches (A*, Dijkstra), heuristic approaches for dynamic environments (D* Lite, Theta*), metaheuristic strategies (genetic algorithm, RRT), bio-inspired methods (ACO, GWO), probabilistic algorithms (PRM, RRT*), and hybrid algorithms (A* with potential fields). It has been determined that each of the algorithms considered has distinct properties that are important for different classes of planning problems. The main characteristics and advantages of each type of algorithm are described, which is important for their software implementation and comparative analysis of effectiveness.
References
[1] Obstacle Avoidance and Path Planning Methods for Autonomous Navigation of Mobile Robot. URL: https://pmc.ncbi.nlm.nih.gov/ articles/PMC11175283/ (дата звернення: 15.07.2025).
[2] Path planning diagram. URL: https://www.researchgate.net/figure/Path-planning-diagram_fig1_366333455 (дата звернення: 15.07.2025).
[3] How can i use particle swarm optimisation algorithm for to find optimal path interms of shortest distance between start and goal point to be followed by mobile robot? URL: https://www.mathworks.com/matlabcentral/answers/263094-how-can-i-use-particle-swarm-optimisation-algorithm-for-to-find-optimal-path-interms-of-shortest-dis (дата звернення: 15.07.2025).
[4] Obstacle-Free Path Planning for Autonomous Drones Using Floyd’s Algorithm. URL: https://www.arxiv.org/pdf/2409.13149v1 (дата звернення: 15.07.2025).
[5] Theta* algorithm path planning schematic. URL: https://surl.lu/nayurk (дата звернення: 15.07.2025).
[6] Modified A* algorithm for path smoothing and obstacle avoidance. URL: https://www.ewadirect.com/proceedings/ace/article/view/9971/pdf (дата звернення: 15.07.2025).
[7] Genetic Algorithm-based Robot Path Planning. URL: https://repo.pens.ac.id/188/1/c3d14cd2e419cde877993555eeef.pdf (дата звернення: 15.07.2025).
[8] The Path Planning of Mobile Robots Based on an Improved Genetic Algorithm. URL: https://surl.lu/mxhour (дата звернення: 15.07.2025).
[9] HPS-RRT*: An Improved Path Planning Algorithm for a Nonholonomic Orchard Robot in Unstructured Environments. URL: https://www.mdpi.com/2073-4395/15/3/712 (дата звернення: 15.07.2025).
[10] Path-Planning Strategy: Adaptive Ant Colony Optimization Combined with an Enhanced Dynamic Window Approach. URL: https://www.mdpi.com/2079-9292/13/5/825 (дата звернення: 15.07.2025).
[11] Optimizing Robot Path Planning with the Particle Swarm Optimization Algorithm. URL: https://surl.li/ohjkdm (дата звернення: 15.07.2025).
[12] Artificial bee colony algorithm. URL: https://surli.cc/bnzjrg (дата звернення: 15.07.2025).
[13] Multi-objective path planning for mobile robot with an improved artificial bee colony algorithm. URL: https://pubmed.ncbi.nlm.nih.gov/36899544/ (дата звернення: 15.07.2025).
[14] Path Planning and Obstacle Avoidance of a Mobile Robot based on GWO Algorithm. URL: https://surl.li/zmmmpg (дата звернення: 15.07.2025).
[15] Robot Motion Control using Dual Avoidance Scheme. URL: https://www.espublisher.com/journals/articlehtml/engineered-science/10.30919-es1261 (дата звернення: 15.07.2025).
[16] Cuckoo Search Algorithm using Lèvy Flight: A Review. URL: https://www.researchgate.net/publication/269651786_Cuckoo_Search_Algorithm_using_Levy_Flight_A_Review (дата звернення: 15.07.2025).
[17] Wang, H.; Wang, S.; Yu, T. Path Planning of Inspection Robot Based on Improved Ant Colony Algorithm. Appl. Sci. 2024, 14, 9511. URL: https://doi.org/10.3390/app14209511 (дата звернення: 15.07.2025).
[18] Hybrid potential field based control of differential drive mobile robots. URL: https://chaoslab.unm.edu/MaterialDownload/Hybrid%20potential%20Field%20based%20control%20of%20differential%20drive%20mobile%20robots.pdf (дата звернення: 15.07.2025).
[19] Optimal Path Planning using RRT for Dynamic Obstacles. URL: https://nopr.niscpr.res.in/bitstream/123456789/54909/1/JSIR%2079(6)%20513-516.pdf (дата звернення: 15.07.2025).
[20] Path Tracking Hybrid A* For Autonomous Agricultural Vehicles. URL: https://arxiv.org/html/2411.14086v1 (дата звернення: 15.07.2025).
[21] Byari M., Bernoussi A., Jellouli O., Ouardouz M., Amharref M. Multi-scale 3D cellular automata modeling: Application to wildland fire spread. Chaos Solitons Fractals, 2022, V. 164, pр. 112-153.
[22] A Mathematical Model for Predicting Fire Spread in Wildland Fuels by Richard C. Rothermel. URL: https://www.fs.usda.gov/rm/pubs_int/int_rp115.pdf (дата звернення: 15.07.2025).
Published
Issue
Section
License
Copyright (c) 2025 Свирид Ю. В., Гуменюк Л. О., Гуменюк П. О.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
