Simulation of swarm algorithms for path planning in a two-dimensional non-mapped environment

V. A. Kostyukov   ; I. M. Medvedev   ; M. Yu. Medvedev   ; V. Kh. Pshikhopov

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 16 (2024) no. 2, pp. 26-40

Résumé

This paper examines the effectiveness of swarm path planning algorithms in a two-dimensional unmapped environment. The efficiency criteria are the number of iterations in the path finding process and an assessment of the probability of successfully achieving the goal. During the study, the maximum speed of movement of the swarm and the maximum number of iterations during which it is allowed that the distance to the target does not decrease are changed. It is assumed that each particle can determine the state of the environment in a certain local region. By determining the state we mean determining the presence of an obstacle in a cell of the environment. To solve the problem of local minima, it is proposed to introduce a virtual obstacle at the local minimum point. This approach is generally known. The novelty of this approach lies in the fact that it solves the problem of detecting a local minimum by a swarm of particles. With a single movement, detecting a local minimum is trivial and comes down to checking the movement to previously visited cells. In the group case, a new solution to the problem of detecting a local minimum is required. This article provides a review and analysis of the path planning problem, problem formulation, problem statement, mathematical description of global swarm path planning algorithms with proposed modifications, pseudo-codes of planning algorithms and the results of a numerical study. In the course of numerical studies, the paper presents the criteria for the efficiency of path planning in an environment of 100$\times$100 cells with randomly placed obstacles.

Détail

Keywords: swarm algorithms, two-dimensional environment, local minimum, virtual obstacles, local search, virtual obstacle.

Bibliographie

[1] Kazakov K.A., Semenov V.A., “Reviwes of Modern Path Planing Methods”, Proceedings of ISP RAS, 28:4 (2016), 241–294

[2] S. Chakravorty, S. Kumar, “Generalized Sampling-Based Motion Planners”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 41:3 (2011), 855–866 | DOI | MR

[3] Beloglazov D., Gaiduk A., Kosenko E., Medvedev M., Pshikhopov V., Soloviev V., Titov A., Finaev V., Shapovalov I., Group Control of Vehicles in Uncertain Environments, FIZMATLIT Publ, M., 2015, 305 pp. (in Russ.)

[4] C. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model”, ACM SIGGRAPH Computer Graphics, 21:4, 25–34 | DOI | MR

[5] M. Dorigo, V. Maniezzo, A. Colorni, “Ant System: Optimization by a Colony of Cooperating Agents”, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26:1 (1996), 29–41 | DOI

[6] D. Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005

[7] D.A. Pomerleau, “Pomerleau, D.A. ALVINN: An Autonomous Land Vehicle in a Neural Network”, NeurIPS Proceedings, 1988, 305–313

[8] Gladkov L.A., Kureychik V.V., Kureychik V.M., Genetic Algorithms, Fizmatlit Publ, M., 2010, 365 pp. (in Russ.)

[9] Nagoev Z.V., Sundukov Z.A., Pshenokova I.A., Denisenko V.A., “Architecture of CAD for Distributed Artificial Intelligence Based on Self-Organizing Neuro-Cognitive Architectures”, News of the Kabardino-Balkarian Scientific Center of the RAS, 2020, no. 2(94), 40–47 (in Russ.) | DOI

[10] Nagoev Z.V., Bzhikhatlov K.CH., Pshenokova I.A., Nagoeva O.V., Atalikov B.A., Chechenova N.A., Malyshev D.A., “Autonomous Formation of Spatial Ontologies in the Intelligent Decision-Making System of a Mobile Agricultural Robot Based on the Self-Organization of Multi-Agent Neurocognitive Architectures”, News of the Kabardino-Balkarian Scientific Center of the RAS, 2020, no. 2(98), 68–79 (in Russ.) | DOI

[11] Nagoev Z.V., Shuganov V.M., Zammoev A.U., Bzhikhatlov K.Ch., Ivanov Z.Z., “Development of Intelligent Integrated System for “Smart” Agricultural Production”, Izvestiya SFedU. Engineering Sciences, 2022, no. 1(225), 81–91 (in Russ.) | DOI

[12] Nagoev Z.V., Pshenokova I.A., Anchekov M.I., Bzhikhatlov K.Ch., Atalikov B.A., Kankulov S.A., Enes A.Z., “Classification and Conditions of Application of Algorithms for Automatic Ontologization of the State Space of a General Artificial Intelligence Agent under the Control of Neurocognitive Architecture”, News of the Kabardino-Balkarian Scientific Center of the RAS, 2023, no. 6(116), 210–225 (in Russ.) | DOI

[13] Anchekov M.I., Apshev A.Z., Bzhikhatlov K.Ch., Kankulov S.A., Nagoev Z.V., Nagoeva O.V., Pshenokova I.A., Khamov A.A., Enes A.Z., “Formal Genome Model of a General Artificial Intelligence Agent Based on Multi-Agent Neurocognitive Architectures”, News of the Kabardino-Balkarian Scientific Center of the RAS, 2023, no. 5(115), 11–24 (in Russ.) | DOI

[14] Gaiduk A.R., Martjanov O.V., Medvedev M.Yu., Pshikhopov V.Kh., Hamdan N., Farhood A., “Neural Network Based Control System for Robots Group Operating in 2-d Uncertain Environment”, Mekhatronika, avtomatizatsiya, upravlenie, 21:8 (2020), 470–479 | DOI

[15] M. Bojarski, D.D. Testa, D. Dworakowski et al., End to End Learning for Self-Driving Cars, arXiv: 1604.07316v1

[16] Y. LeCun, U. Muller, J. Ben et al., “Off-Road Obstacle Avoidance through End-to-End Learning”, Part of Advances in Neural Information Processing Systems 18, NIPS 2005, 2005, 739–746

[17] J. Hawke, R. Shen, C. Gurau et al., “Urban Driving with Conditional Imitation Learning”, 2020 IEEE International Conference on Robotics and Automation (ICRA) (Paris, France, 2020), 2020, 251–257 | DOI

[18] Pankratov I., “Genetic Algorithm for Optimizing Energy Costs for Reorienting the Orbital Plane of a Spacecraft”, Mekhatronika avtomatizatsiya upravlenie, 23:5 (2022), 256–262 | DOI

[19] A. Elshamli, H.A. Abdullah, S. Areibi, “Elshamli, A. Genetic Algorithm for Dynamic Path Planning”, Canadian Conference on Electrical and Computer Engineering 2004 (Niagara Falls, ON, Canada, 2024), v. 2, 2004, 677–680 | DOI

[20] Filimonov A.B., Filimonov N.B., Nguyen T.K., Pham Q.P., “Planning of UAV Flight Routes in the Problems of Group Patrolling of the Extended Territories”, Mekhatronika avtomatizatsiya upravlenie, 24:7 (2023), 374–381 | DOI

[21] Rodzin S., “Current State of Bio Heuristics: Classification, Benchmarking, Application Areas”, Izvestiya SFedU. Engineering sciences, 2023, no. 2, 280–298 | DOI

[22] E. Masehian, D. Sedighizadeh, “A Multi-Objective PSO-based Algorithm for Robot Path Planning”, 2010 IEEE International Conference on Industrial Technology (Via del Mar, Chile, 2010), 2010, 465–470 | DOI

[23] Kostyukov V., Medvedev M., Pshikhopov V., “An Algorithm for Path Planning in a Two-Dimensional Environment With Polygonal Obstacles on a Class of Piecewise Polyline Trajectories”, Izvestiya SFedU. Engineering sciences, no. 5:235 (2023), 34–48 | DOI

[24] Pshikhopov V., Medvedev M., Kostyukov V., Hussein F., Kadim A., “Trajectory Planning Algorithms in Two-Dimensional Environment with Obstacles”, Informatics and Automation, 2022, no. 3(21), 459–492 | DOI

[25] M. Nandanwar, A. Nandanwar, “Implementation and Comparison between PSO and BAT Algorithms for Path Planning with Unknown Environment”, International Journal of Latest Technology in Engineering, Management Applied Science (IJLTEMAS), 6:8 (2017), 67–72

[26] P.I. Adamu, J.T. Jegede, H.I. Okagbue, P.E. Oguntunde, “Shortest Path Planning Algorithm - A Particle Swarm Optimization (PSO) Approach”, Proceedings of the World Congress on Engineering, WCE 2018 (July 4-6, 2018), v. I, 2018, 19-24

[27] M.K. Nandanwar, A.S. Zadagaonkar, D.A. Shukla, “Nandanwar, M.K. Path Planning through BAT Algorithm in Complex Environments”, International Journal of Computer Science Trends and Technology (IJCST), 4:1 (2016), 79–86

[28] X. Cheng, J. Li, C. Zheng et al., “An Improved PSO-GWO Algorithm With Chaos and Adaptive Inertial Weight for Robot Path Planning”, Front. Neurorobot, 15 (2021), 770361 | DOI

[29] Y. Qu, Y. Zhang, Y. Zhang, “A Global Path Planning Algorithm for Fixed-wing UAVs”, J. Intell. Robot. Syst., 91 (2018), 691–707 | DOI

[30] Pshihopov V.H., Sukonkin S.Ya., Naguchev D.Sh., Strakovich V.V., Medvedev M.Ju., Gurenko B.V., Kostukov V.A., Voloshchenko Yu.P., “Autonomous Underwater Vehicle “Skat” for Search and Detection Silty Object Tasks”, Izvestiya SfedU, 2010, no. 3(104), 153–163 (in Russ.)

[31] V.Kh. Pshikhopov, M.Yu. Medvedev, A.R Gaiduk. et al., “Position-Trajectory Control System for Unmanned Robotic Airship”, IFAC Proceedings Volumes, 47:3 (2014), 8953–8958 | DOI

[32] Z. Yan, J. Li, Y. Wu, G. Zhang, “A Real-Time Path Planning Algorithm for AUV in Unknown Underwater Environment Based on Combining PSO and Waypoint Guidance”, Sensors, 19:1 (2018), 20 | DOI

[33] J.J. Shin, H. Bang, “UAV Path Planning under Dynamic Threats Using an Improved PSO Algorithm”, International Journal of Aerospace Engineering, 2020, 8820284, 17 pp. | DOI

[34] A. Mirshamsi, S. Godio, A. Nobakhti, “A 3D Path Planning Algorithm Based on PSO for Autonomous UAVs Navigation”, Bioinspired Optimization Methods and Their Applications, BIOMA 2020, Lecture Notes in Computer Science, 12438, Springer, Cham, 2020 | DOI

[35] M.D. Phung, Q.P. Ha, “Phung, M.D. Safety-Enhanced UAV Path Planning with Spherical Vector-Based Particle Swarm Optimization”, Applied Soft Computing, 107 (2021), 107376 | DOI

[36] Skobcov Yu., Speransky D., Evolutionary Calculations, National Open University, M., 2016

[37] Kostjukov V.A., Medvedev M.Y., Pshikhopov V.Kh., “Algorithms for Planning Smoothed Individual Trajectories of Ground Robots”, Mekhatronika avtomatizatsiya upravlenie, 23:11 (2022), 585–595 | DOI