Класифікація алгоритмів побудови шляху робота з перешкодами
DOI:
https://doi.org/10.36910/4293-52779-2025-17-02-02Ключові слова:
алгоритм, рух з перешкодами, моделювання, аналіз данихАнотація
У роботі складено огляд та класифікацію одинадцяти алгоритмів побудови шляху робота з перешкодами, поділених на шість категорій: класичні підходи на графах (A*, Дейкстри), евристичні підходи для динамічних середовищ (D* Lite, Theta*), метаевристичні стратегії (Генетичний алгоритм, RRT), біонатхненні методи (ACO, GWO), імовірнісні алгоритми (PRM, RRT*) та гібридні алгоритми (A* з потенційними полями). Визначено, що кожен із розглянутих алгоритмів має окремі властивості, які важливі для різних класів задач планування. Описано основні характеристики та переваги кожного типу алгоритмів, що є важливим для їх програмної реалізації та порівняльного аналізу ефективності.
Посилання
[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).
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2025 Свирид Ю. В., Гуменюк Л. О., Гуменюк П. О.
TЦя робота ліцензується відповідно до ліцензії Creative Commons Attribution-ShareAlike 4.0 International License.
