Uncrewed Vehicle Pathfinding Approach Based on Artificial Bee Colony Method

1
Львівський національний університет імені Івана Франка
2
Ivan Franko National University of Lviv
3
Львівський національний університет імені Івана Франка
4
Ivan Franko National University of Lviv
5
Ivan Franko National University of Lviv
6
Ivan Franko National University of Lviv

The presented study is dedicated to the dynamic pathfinding problem for UV. Since the automation of UV movement is an important area in many applied domains like robotics, the development of drones, autopilots, and self-learnable platforms, we propose and study a promising approach based on the algorithm of swarm AI. Given the 2D environment with multiple obstacles of rectangular shape, the task is to dynamically calculate a suboptimal path from the starting point to the target. The agent has been represented as UV in 2D space and should find the next optimal movement point from the current position only within a small neighborhood area. This area has been defined as a square region around the current agent’s position. The size of the region has been determined by the attainability of the agent's scanning sensors. If the obstacle is detected by the agent, the latter should be taken into consideration while calculating the next trajectory point. To perform these calculations, the ABC metaheuristic, one of the best representatives of swarm AI, has been used. The validation of the proposed approach has been performed on several 2D maps with different complexity and number of obstacles. Also, to obtain the proper configuration, an inverse problem of identification of guided function weights has been formulated and solved. The outlined results show the perspective of the proposed approach and can complement the existing solutions to the pathfinding problem.

  1. Yanmaz, E., Yahyanejad, S., Rinner, B., Hellwagner, H.,& Bettstetter, C. (2018). Drone networks: Communica- tions, coordination, and sensing. Ad Hoc Networks, 68, 1- 15. DOI: https://doi.org/10.1016/j.adhoc.2017.09.001.
  2. Gad, A. G. (2022). Particle swarm optimization algorithm and  its  applications:  a  systematic  review.  Archives  of computational  methods  in  engineering,  29(5),  2531-2561. DOI: https://doi.org/10.1007/s11831-021-09694-4.
  3. Abu-Mouti, F. S., & El-Hawary, M. E. (2012, March).Overview of Artificial Bee Colony (ABC) algorithm and its  applications.  In 2012  IEEE  International  Systems Conference  SysCon  2012 (pp.    1-6). IEEE. DOI: https://doi.org/10.1109/syscon.2012.6189539.
  4. Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical computer science, 344(2- 3),     243-278.DOI: https://doi.org/10.1016/j.tcs.2005.05.020.
  5. Fister, I., Fister Jr, I., Yang, X. S., & Brest, J. (2013). A comprehensive review of firefly algorithms. Swarm and evolutionary computation, 13, 34-46.DOI: https://doi.org/10.1016/j.swevo.2013.06.001.
  6. Bhattacharjee, P., Rakshit, P., Goswami, I., Konar, A., & Nagar, A. K. (2011, October). Multi-robot path-planning using  artificial   bee   colony   optimization   algorithm. In 2011 Third World Congress on Nature and Biologi- cally   Inspired   Computing (pp.    219-224).    IEEE. DOI: https://doi.org/10.1109/nabic.2011.6089601.
  7. Contreras-Cruz, M. A., Ayala-Ramirez, V., & Hernan- dez-Belmonte, U. H. (2015). Mobile robot path planning using artificial bee colony and evolutionary program- ming. Applied Soft Computing, 30, 319-328.DOI: https://doi.org/10.1016/j.asoc.2015.01.067.
  8. Contreras-Cruz, M. A., Lopez-Perez, J. J., & Ayala- Ramirez, V. (2017, June). Distributed path planning for multi-robot teams based on artificial bee colony. In 2017 IEEE congress on evolutionary computation (CEC) (pp. 541-548).   IEEE.DOI: https://doi.org/10.1109/cec.2017.7969358.
  9. Liang, J. H., & Lee, C. H. (2015). Efficient collision-free path-planning of multiple mobile robots system using ef- ficient artificial bee colony algorithm. Advances in Engi- neering Software, 79, 47-56.DOI: https://doi.org/10.1016/j.advengsoft.2014.09.006.
  10. Nayyar, A., Nguyen, N. G., Kumari, R., & Kumar, S.(2020). Robot path planning using modified artificial bee colony algorithm. In Frontiers in Intelligent Computing: Theory and Applications: Proceedings of the 7th Interna- tional Conference on FICTA (2018), Volume 2 (pp. 25-36). Springer Singapore. DOI: https://doi.org/10.1007/978-981-13-9920-6_3.
  11. Kumar, S., & Sikander, A. (2022). Optimum  mobile robot path planning using improved artificial bee colony algorithm and evolutionary programming. Arabian Jour- nal for Science and Engineering, 47(3), 3519-3539. DOI: https://doi.org/10.1007/s13369-021-06326-8.
  12. Kumar, S., & Sikander, A. (2024). A novel hybrid framework for single and multi-robot path planning in a complex industrial environment. Journal of Intelligent Manufacturing35(2), 587-612.DOI: https://doi.org/10.1007/s10845-022-02056-2.
  13. Faridi, A. Q., Sharma, S., Shukla, A., Tiwari, R., & Dhar,J. (2018). Multi-robot multi-target dynamic path planning using artificial bee colony and evolutionary programming in  unknown  environment. Intelligent  Service  Robot- ics, 11, 171-186. DOI: https://doi.org/10.1007/s11370- 017-0244-7.
  14. Karaboga, D., & Akay, B. (2011). A modified artificial bee colony (ABC) algorithm for constrained optimization problems. Applied soft computing, 11(3), 3021-3031. DOI: https://doi.org/10.1016/j.asoc.2010.12.001.