ISSN 2658–5782
DOI 10.21662
Electronic Scientific Journal


© Институт механики
им. Р.Р. Мавлютова
УФИЦ РАН

Яндекс.Метрика web site traffic statistics

Darintsev O.V., Migranov A.B. Using an ant algorithm to find a strategy for the behavior of a group of mobile robots on a work field with obstacles. Multiphase Systems. 17 (2022) 3–4. 177–186 (in Russian).
2022. Vol. 17. Issue 3–4, Pp. 177–186
URL: http://mfs.uimech.org/mfs2022.3.016
DOI: 10.21662/mfs2022.3.016
Using an ant algorithm to find a strategy for the behavior of a group of mobile robots on a work field with obstacles
Darintsev O.V., Migranov A.B.
Mavlyutov Institute of Mechanics of UFRC RAS, Ufa, Russia

Abstract

A more complex solution to the problem of the distribution of tasks in a group of mobile robots, in the presence of obstacles in the workspace, is considered. The work is a continuation of a cycle of research in which the basic algorithm for solving the tasks was one of the types of ant algorithm — the multicolonial ant system method in combination with the trajectory planning algorithm implemented using the principle of dynamic programming. The task statement, the workspace model, the goals of the robots functioning and the parameters characterizing their work have been adjusted. The choice of free parameters of the ant algorithm for performing multi-criteria optimization and tuning of the solution is carried out: the number of iterations, the number of intercolonial groups of ants, the weight of the concentration of the pheromone of arcs, the weight of the heuristic attractiveness of arcs and the pheromone evaporation coefficient. The results of computational experiments conducted in the presence of static (known in advance) and dynamic (other robots) obstacles in the workspace are presented. The proposed algorithm was tested using the example of a group consisting of three robots performing 10 tasks. As shown in the results of computational experiments, robot trajectories are built on a subset of free cells of the workspace and do not intersect cells with obstacles. At the same time, the configuration of the work field affects not only the actual routes of robots, but also the redistribution of tasks between them, and the number of robots involved. Additionally, a series of computational experiments with different combinations of values of free parameters was carried out to determine the optimal ratios and implement a more efficient ant algorithm. Optimization was carried out by a single adjustment method, which allowed us to find the required values of free parameters. It is shown that the adjustment of the parameters made it possible to reduce the relative error in the synthesis of the optimal route of movement of a group of robots by 3–6 %.

Keywords

group of robots,
ant algorithm,
distribution of tasks,
trajectory planning

Article outline

The solution of the problem of distribution of tasks in a group of mobile robots in the presence of various obstacles on the working field is considered. When switching to managing a group of robots, the task arises of optimally allocating the resources of the entire group, taking into account the actual list of tasks and the situation on the field of action. This task can be classified as optimizing the search for a strategy for the behavior of a group of mobile robots. The purpose of this work is to find new solutions to the problem of the distribution of tasks in a group of mobile robots, taking into account the characteristics of objects and the presence of obstacles on the working field – both static and dynamic in the form of other robots of the group. As a solution method, it is proposed to use an ant algorithm – the method of a multicolonial ant system (Ant Multi-Colony Optimization, AMCO) in combination with a trajectory planning algorithm based on the principle of dynamic programming. In earlier works of the authors, the possibility of using AMCO was already shown, but the solution of the problem was given on an empty working field, without taking into account natural obstacles. In addition, one set of parameters was selected for AMSO without analyzing its optimality.

Within the framework of the initial data, the problem statement, the workspace model, the goals of the robots' functioning and the parameters characterizing their work are formulated. The objective function is determined from the components of its main parameters:

  • Efficiency of robot operation;
  • specific energy required for the functioning of the support group during the entire duration of the operation;
  • the energy spent on placing one robot on the field.

The parameters of the ant algorithm for multi-criteria optimization and tuning are selected:

  • number of iterations and intercolonial groups of ants;
  • the weight of the concentration of the pheromone of the arcs and the heuristic attractiveness of the arcs;
  • pheromone evaporation coefficient.

To implement the functionality of constructing motion trajectories taking into account static (obstacles on the field) and dynamic (other robots) obstacles, the trajectory planning module based on the principle of dynamic programming was used in AMSO. The simulation of the algorithm is considered on the example of a group consisting of three robots and 10 tasks. As shown in the results, the robot trajectories pass through free cells and do not cross obstacles. At the same time, the configuration of the work field affects not only the actual routes of robots, but also the redistribution of tasks between them and the number of robots involved.

In order to establish the influence of free parameters on the effectiveness of the multicolonial ant algorithm, a series of computational experiments with different combinations of their values was carried out. The influence of the following parameters is considered:

  • number of robots;
  • number of tasks;
  • size of the working field;
  • the proportion of obstacles on the work field.

Optimization by the method of one-time parameter adjustment made it possible to identify the following values of free AMCO parameters:

  • the number of iterations is determined from the condition of the maximum calculation time of 10 seconds;
  • number of intercolonial groups of ants m = 30;
  • the weight of the concentration of the pheromone arcs α = 0.5;
  • the weight of the heuristic attractiveness of arcs β = 9;
  • pheromone evaporation coefficient p = 0.5.

Conclusion: This article shows one of their solutions to the problems of finding the optimal management strategy for an arbitrary group of mobile robots, the complexity of which directly depends on the presence of static obstacles, dynamic obstacles in the form of other robots present in the workspace. An arbitrary number of assigned tasks, as well as a comprehensive assessment of optimality (several efficiency criteria) required the use of specific techniques and methods for modifying the previously obtained solution using an ant algorithm. The procedure for making changes to the algorithm was implemented in two stages.

At the first stage, when synthesizing the trajectories of a group of robots by introducing a new module into the AMCO algorithm that calculates the mutual movement of robots using the principle of dynamic programming, stationary (obstacles, walls) and dynamic (other robots of the group) obstacles were adequately taken into account.

The second stage consists in solving the meta-optimization problem of selecting free AMCO parameters by a single parameter adjustment method, which eventually allowed to reduce the relative error in the synthesis of optimal routes for a group of robots, and reduce total energy costs.

References

  1. Bulgakov A.G., Torsten B., Gorchakov V.V., Kasatkin A.V. Razrabotka mobil’nogo robota dlya tekhnologicheskih processov v stroitel’stve // Izvestiya vuzov. Severo-Kavkazskij region. Seriya: Tekhnicheskie nauki. 2011. № 6(164). Pp. 20–25 (In Russian).
    eLIBRARY ID: 17280557
  2. Grechushkin I.V., Savin V.I. Primenenie nazemnyh robototekhnicheskih kompleksov dlya provedeniya pogruzochno-razgruzochnyh i transportno-skladskih rabot // Nauchnye problemy material’no-tekhnicheskogo obespecheniya Vooruzhennyh Sil Rossijskoj Federacii. 2019. № 3(13). Pp. 103–116 (In Russian).
    eLIBRARY ID: 41149529
  3. Ivanov D.YA. Raspredelenie rolej v koaliciyah robotov pri ogranichennyh kommunikaciyah na osnove roevogo vzaimodejstviya // Upravlenie bol’shimi sistemami: sbornik trudov. 2019. № 78. Pp. 23–45 (In Russian).
    eLIBRARY ID: 37652243
  4. Politov E.N., Berezina L.V., SHCHerbakova M.P. Robototekhnicheskie kompleksy voennogo naznacheniya: sovremennoe sostoyanie i perspektivy razvitiya v Rossijskoj Federacii // Molodezh’ i nauka: shag k uspekhu: sbornik nauchnyh statej 3-j Vserossijskoj nauchnoj konferencii perspektivnyh razrabotok molodyh uchenyh: v 5 t., Kursk, 21–22 marta 2019 goda. Tom 5. Kursk: Zakrytoe akcionernoe obshchestvo «Universitetskaya kniga». 2019. Pp. 102–104 (In Russian).
    eLIBRARY ID: 37265522[5] Batanov A.F., Mingaleev S.G., Ochkin I.V. Robototekhnicheskie kompleksy v aeromobil’nyh gruppirovkah MCHS Rossii // Tekhnologii grazhdanskoj bezopasnosti. 2019. T. 16, № 2(60). Pp. 60–69 (In Russian).
    eLIBRARY ID: 38504570
  5. Marino A., Parker L.E., Antonelli G., Caccavale F. A decentralized architecture for multi-robot systems based on the null-space-behavioral control with application to multi-robot border patrolling // J. Intell. Robot. Syst. 2013. V. 71. Pp. 423–444.
    DOI: 10.1007/s10846-012-9783-5
  6. Appel’ganc A.V., Pyatakova O.I., Solov’ev A.A. Gruppovoe upravlenie robotami voennogo naznacheniya // Povyshenie kachestva obrazovaniya, sovremennye innovacii v nauke i proizvodstve. 2019. Pp. 562–568 (In Russian).
  7. Darintsev O.V. Migranov A.B. Using the Hopfield Neural Network to Select a Behaviour Strategy for the Group of Mobile Robots // J. Phys.: Conf. Ser. 2021. V. 2096. 012086.
    DOI: 10.1088/1742-6596/2096/1/012086
  8. Darintsev O., Migranov A. Task Distribution Module for a Team of Robots Based on Genetic Algorithms: Synthesis Methodology and Testing // 2019 XXI International Conference Complex Systems: Control and Modeling Problems (CSCMP), Samara, Russia. 2019.
  9. Darintsev O.V., Migranov A.B. Multi-criteria Optimization of the Mobile Robot Group Strategy Using the Ant Algorithm. In: Ronzhin A., Shishlakov V. (eds) Electromechanics and Robotics. Smart Innovation, Systems and Technologies. V. 232. Springer, Singapore. 2022.
    DOI: 10.1007/978-981-16-2814-6_9
  10. Li X., Liu Z., Tan F. Multi-Robot Task Allocation Based on Cloud Ant Colony Algorithm // ICONIP 2017. Lecture Notes in Computer Science. 2017. Vol 10637. Pp. 3–10.
    DOI: 10.1007/978-3-319-70093-9_1
  11. Kubil V.N. Issledovanie i razrabotka metodov resheniya mnogokriterial’nyh zadach marshrutizacii transporta na osnove murav’inogo algoritma: Dis. . . . kand. tekhn. nauk: 05.13.01 / V.N. Kubil. Novocherkassk. 2019. 184 p. (In Russian).
  12. Karpuhin V.B. Matematicheskaya model’ upravleniya processom poiska optimal’nogo marshruta v transportnoj seti // Innovacionnye tekhnologii v nauke, transporte i obrazovanii: Cbornik statej mezhdunarodnoj nauchno-metodicheskoj internet-konferencii, Moskva, 19–20 iyunya 2018 goda. Moskva: Rossijskij universitet transporta (MIIT). 2018. Pp. 296–308 (In Russian).
    eLIBRARY ID: 36962584
  13. Chencov A.A., Chencov A.G. O realizacii metoda dinamicheskogo programmirovaniya v obobshchennoj zadache kur’era // Trudy Instituta matematiki i mekhaniki UrO RAN. 2007. T. 13, № 3. Pp. 136–160 (In Russian).
    eLIBRARY ID: 12040792
  14. Bellman R. Dinamicheskoe programmirovanie. M.: IL. 1960 (In Russian).
  15. Zajcev A.A., Kurejchik V.V., Polupanov A.A. Obzor evolyucionnyh metodov optimizacii na osnove roevogo intellekta // Izvestiya YUFU. Tekhnicheskie nauki. 2010. № 12(113). Pp. 7–12 (In Russian).
    eLIBRARY ID: 15553703
  16. Karpenko A.P., Svianadze Z.O. Metod meta-optimizacii poiskovyh algoritmov optimizacii // Nauka i obrazovanie: nauchnoe izdanie MGTU im. N.E. Baumana. 2011. № 1. P. 3 (In Russian).
    eLIBRARY ID: 15575356
  17. Karpenko A.P. Metody povysheniya effektivnosti populyacionnyh algoritmov global’noj optimizacii // Perspektivnye napravleniya razvitiya otechestvennyh informacionnyh tekhnologij. materialy V mezhregional’noj nauchno-prakticheskoj konferencii. Sevastopol’skij gosudarstvennyj universitet; Sankt-Peterburgskij institut informatiki i avtomatizacii RAN. Sevastopol’. 2019. Pp. 87–88 (In Russian).
    eLIBRARY ID: 42944531
  18. Agasiev T.A., Karpenko A.P. Meta-optimizaciya algoritmov global’noj parametricheskoj optimizacii // Sistemy komp’yuternoj matematiki i ih prilozheniya. 2019. № 20–1.Pp. 8–16 (In Russian).
    eLIBRARY ID: 39103145
  19. Bremermann H.J. Optimization through evolution and recombination // Yovits M.C., Jacobi G.T. and Goldstein G.D. (Eds.), Self-Organizing Systems. 1962. Pp. 93–106.