Особливості використання алгоритмів ройового інтелекту для оптимізації маршрутів дронів
Анотація
Досліджено особливості використання алгоритмів ройового інтелекту для оптимізації маршрутів доставки безпілотними апаратами корисного навантаження. Класичні алгоритми планування маршрутів, такі як алгоритм Дейкстри, А* або APF, мають недоліки під час використання в умовах реального світу, через можливість впадання у локальні мінімуми та підвищену обчислювальну складність за багатьох перешкод. Щоб обійти ці недоліки, запропоновано використання алгоритмів ройового інтелекту для планування маршрутів, багато з яких натхненні біологічною поведінкою тварин. Розглянуто особливості роботи та придатність використання у динамічних умовах таких алгоритмів, як Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Cuckoo Search Algorithm (CSA) and Sparrow Search Algorithm (SSA). За результатами дослідження з'ясовано, що не існує єдиного універсального алгоритму для всіх типів середовищ. Усі алгоритми показують високу ефективність у разі використання у найкращих для них умовах. Встановлено, що PSO має швидку збіжність навіть у разі використання великої кількості агентів, що робить його придатним для планування маршруту у ройових системах. Натомість розширювальна здатність алгоритму ABC та його легкість в обчислювальній складності дає змогу виконувати ефективний розподіл завдань між агентами у великих ройових системах. Алгоритм СSA дає можливість досягти найкращого локального планування, що у комбінації з іншими алгоритмом сприяє досягненню найкращих результатів у балансі між глобальним і локальним плануванням маршруту. Алгоритм SSA досягає швидкої збіжності в разі використання більших обчислювальних ресурсів, водночас забезпечуючи виконання планування у динамічному середовищі. За результатами дослідження визначено роль алгоритмів ройового інтелекту у покращенні продуктивності БПЛА, водночас забезпечуючи надійні, ефективні та масштабовані маршрути доставки. Майбутні дослідження можна спрямувати на вивчення нових гібридних алгоритмічних моделей, що будуть поєднувати алгоритми ройового інтелекту з технологіями машинного навчання для покращення їхньої ефективності в динамічних середовищах. Для покращення роботи алгоритмів та тестування їх обмежень важливе тестування алгоритмів в умовах комплексних середовищ з багатьма перешкодами.
Завантаження
Посилання
Abdulsattar, K., Harrath, Y., & Kaabi, J. (2023). Ant colony algorithm to solve a drone routing problem for hazardous waste collection. Arab Journal of Basic and Applied Sciences, 30(1), 636–649. https://doi.org/10.1080/25765299.2023.2275505
Anastasiou, A., Kolios, P., Panayiotou, C., & Papadaki, K. (2020). Swarm Path Planning for the Deployment of Drones in Emergency Response Missions. In: IEEE Proceedings of the 2020 International Conference on Unmanned Aircraft Systems (pp. 456–465). https://doi.org/10.1109/ICUAS48674.2020.9213876
Athira, K. A., Yalavarthi, R., Saisandeep, T., Harshitha, K. S. S., Sha, A., & Ja, D. U. (2024). ACO-DTSP Algorithm: Optimizing UAV swarm routes with workload constraints. Procedia Computer Science, 235, 163–172. https://doi.org/10.1016/j.procs.2024.04.019
Cosar, M. (2023). Path Planning via Swarm Intelligence Algorithms in Unmanned Aerial Vehicle Population. The Eurasia Proceedings of Science, Technology, Engineering & Mathematics (EPSTEM), 26, 439–450. https://doi.org/10.55549/epstem.1411059
El Gmili, N., Mjahed, M., El Kari, A., & Ayad, H. (2019). Particle Swarm Optimization and Cuckoo Search-Based Approaches for Quadrotor Control and Trajectory Tracking. Applied Sciences, 9(8), article ID 1719. https://doi.org/10.3390/app9081719
Gandomi, A. H., Yang, X. S., & Alavi, A. H. (2013). Cuckoo Search Algorithm: A Metaheuristic Approach to Solve Structural Optimization Problems. Engineering with Computers, 29(4), 17–29. https://doi.org/10.1007/s00366-012-0308-4
Guo, S., Chen, M., & Pang, W. (2023). Path Planning for Autonomous Underwater Vehicles Based on an Improved Artificial Jellyfish Search Algorithm in Multi-Obstacle Ocean Current Environment. IEEE Access, vol. 11, 31010–31023. https://doi.org/10.1109/ACCESS.2023.3257025
He, Y., & Wang, M. (2024). An Improved Chaos Sparrow Search Algorithm for UAV Path Planning. Scientific Reports, 14(366), 1–16. https://doi.org/10.1038/s41598-023-50484-8
Karaboga, D., & Basturk, B. (2007). Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems. In: P. Melin, et al. (Eds.), IFSA 2007, LNAI 4529 (pp. 789–798). Springer-Verlag. https://doi.org/10.1007/978-3-540-72950-1_77
Liu, G., Shu, C., Liang, Z., Peng, B., & Cheng, L. (2021). A Modified Sparrow Search Algorithm with Application in 3D Route Planning for UAV. Sensors, 21(4), article ID 1224. https://doi.org/10.3390/s21041224
Meng, Q., Chen, K., & Qu, Q. (2024). PPSwarm: Multi-UAV Path Planning Based on Hybrid PSO in Complex Scenarios. Drones, 8(5), article ID 192. https://doi.org/10.3390/drones8050192
Meng, Z., Li, D., Zhang, Y., & Yan, H. (2024). Intelligent Scheduling Technology of Swarm Intelligence Algorithm for Drone Path Planning. Drones, 8(4), 120 p. https://doi.org/10.3390/drones8040120
Ming, Y., Li, Y., Zhang, Z., & Yan, W. (2021). A Survey of Path Planning Algorithms for Autonomous Vehicles. Commercial Vehicles, 14(1), 97–109. https://doi.org/10.4271/02-14-01-0007
Puente-Castro, A., Rivero, D., Pazos, A., & Fernandez-Blanco, E. (2022). A Review of Artificial Intelligence Applied to Path Planning in UAV Swarms. Journal of Intelligent & Robotic Systems, 103(1), 65–83. https://doi.org/10.1007/s00521-021-06569-4
Rabichuk, I. O., & Fechan, A. V. (2024). The main challenges of adaptability of swarm intelligence algorithms. Scientific Bulletin of UNFU, 34(5), 97–103. https://doi.org/10.36930/40340513
Sabet, S., Shokouhifar, M., & Farokhi, F. (2016). A Comparison Between Swarm Intelligence Algorithms for Routing Problems. Electrical & Computer Engineering: An International Journal (ECIJ), 5(1), 17–32. https://doi.org/10.5281/zenodo.3630059
Saied, M., Slim, M., Mazeh, H., Francis, C., & Shraim, H. (2019). Unmanned Aerial Vehicles Fleet Control via Artificial Bee Colony Algorithm. In: IEEE Proceedings of the 4th Conference on Control and Fault Tolerant Systems (SysTol) (pp. 80–85). https://doi.org/10.1109/SYSTOL.2019.8864752
Sharma, A., Shoval, S., Sharma, A., & Pandey, J. K. (2021). Path Planning for Multiple Targets Interception by the Swarm of UAVs based on Swarm Intelligence Algorithms: A Review. IETE Technical Review, 39(3), 675–697. https://doi.org/10.1080/02564602.2021.1894250
Sharma, K., Singh, S., & Doriya, R. (2021). Optimized Cuckoo Search Algorithm Using Tournament Selection Function for Robot Path Planning. International Journal of Advanced Robotic Systems, 18(3), 1–11. https://doi.org/10.1177/1729881421996136
Taha Houda, Jinan Charafeddine, Hani Hamdan, Sylvain Chevallier. On Path Planning and Optimization Strategies: Toward Embedded Road Applications. IEEE International Conference on Smart Systems and Power Management 2022, Nov 2022, Beirut, Lebanon, pp. 197–202. https://doi.org/10.1109/IC2SPM56638.2022.9988830
Wang, W., Tao, Q., Cao, Y., Wang, X., & Zhang, X. (2020). Robot Time-Optimal Trajectory Planning Based on Improved Cuckoo Search Algorithm. IEEE Access, 8, 86923–86933. https://doi.org/10.1109/ACCESS.2020.2992640
Xu, Y., Sang, B., & Zhang, Y. (2024). Application of Improved Sparrow Search Algorithm to Path Planning of Mobile Robots. Biomimetics, 9(6), 351 p. https://doi.org/10.3390/biomimetics9060351
Xue, J., & Shen, B. (2020). A Novel Swarm Intelligence Optimization Approach: Sparrow Search Algorithm. Systems Science & Control Engineering: An Open Access Journal, 8(1), 22–34. https://doi.org/10.1080/21642583.2019.1708830
Zhang, Y., Wang, S., & Ji, G. (2015). A Comprehensive Survey on Particle Swarm Optimization Algorithm and Its Applications. Mathematical Proble1ms in Engineering, 2015, article ID 931256. https://doi.org/10.1155/2015/931256
Zhao, H., Fu, W., Li, X., & Liu, Z. (2024). Leveraging swarm intelligence to drive autonomously: A particle swarm optimization based approach to motion planning. arXiv Preprint. https://doi.org/10.48550/arXiv.2404.02644
Zheng, L., Yu, W., Li, G., Qin, G., & Luo, Y. (2023). Particle Swarm Algorithm Path-Planning Method for Mobile Robots Based on Artificial Potential Fields. Sensors, 23(6082), 1–15. https://doi.org/10.3390/s23136082
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
