OPTIMIZATION OF SWARM ROBOTICS ALGORITHMS
DOI:
https://doi.org/10.15588/1607-3274-2022-3-7Keywords:
swarm robotics, ant colony optimization algorithm, salesman problem.Abstract
Context. Among the variety of tasks solved by robotics, one can single out a number of those for the solution of which small dimensions of work are desirable and sometimes necessary. To solve such problems, micro-robots with small dimensions are needed, the mass of which allows them to move freely in tight passages, in difficult weather conditions, and remain unnoticed. At the same time, the small dimensions of the microrobot also impose some indirect restrictions; therefore, it is better to use groups of microrobots for the solution of these problems. The efficiency of using groups of microrobots depends on the chosen control strategy and stochastic search algorithms for optimizing the control of a group (swarm) of microrobots.
Objective. The purpose of this work is to consider a group of swarm algorithms (methods) belonging to the class of metaheuristics. The group of these algorithms includes, in particular, the ant colony algorithm, the possibilities of which were investigated to solve the traveling salesman problem, which often arises when developing an algorithm for the behavior of a group of microrobots.
Method. At the first stage of the study, the main groups of parameters were identified that determine the flow and characterize the state at any time of the ant colony algorithm: input, control, disturbance parameters, output parameters. After identifying the main groups of parameters, an algorithm was developed, the advantage of which lies in scalability, as well as guaranteed convergence, which makes it possible to obtain an optimal solution regardless of the dimension of the graph. At the second stage, an algorithm was developed, the code of which was implemented in the Matlab language. Computer experiments were carried out to determine the influence of input, control, output, and disturbance parameters on the convergence of the algorithm. Attention was paid to the main groups of indicators that determine the direction of the method and characterize the state of the swarm of microrobots at a given time. In the computational experiment, the number of ants placed in the nodes of the network, the amount of pheromone, the number of graph nodes were varied, the number of iterations to find the shortest path, and the execution time of the method were determined. The final test of modeling and performance of the method was carried out.
Results. Research has been carried out on the application of the ant algorithm for solving the traveling salesman problem for test graphs with a random arrangement of vertices; for a constant number of vertices and a change in the number of ants, for a constant number of vertices at different values of the coefficient Q; to solve the traveling salesman problem for a constant number of vertices at different values of the pheromone evaporation coefficient p; for a different number of graph vertices. The results showed that ant methods find good traveling salesman routes much faster than clear-cut combinatorial optimization methods. The dependence of the search time and the found optimal route on the values of control parameters are established using the example of test networks for a different number of graph vertices and iterations.
Conclusions. The studies were carried out to make it possible to give recommendations on the application of the ant colony algorithm to control a group (swarm) of microrobots.
References
Beni, G. From Swarm Intelligence to Swarm Robotics, International Workshop on Swarm Robotics. Springer, Berlin, Heidelberg, 2004, pp. 1–9. DOI: 10.1007/978-3-540-30552-1_1
Colorni A., Dorigo M., & Maniezzo, V. Distributed optimization by ant colonies, Proceedings of the first European conference on artificial life, 1991, Vol. 142, pp. 134–142. https://faculty.washington.edu/paymana/swarm/colorni92ecal.pdf
Deshpande A., Kumar M., & Ramakrishnan S. Robot swarm for efficient area coverage inspired by ant foraging: the case of adaptive switching between brownian motion and lévy flight, Dynamic Systems and Control Conference, American Society of Mechanical Engineers, 2017, October, Vol. 58288, pp. 1–8. DOI: 10.1115/DSCC2017-5229
Dimidov C., Oriolo G., & Trianni V. Random walks in swarm robotics: an experiment with kilobots, International Conference on Swarm Intelligence. Springer, Cham, 2016, pp. 185–196. DOI: 10.1007/978-3-319-44427-7_16
Dorigo M., Floreano D., Gambardella L. M., Mondada F., Nolfi S., Baaboura T., ... & Vaussard F. Swarmanoid: a novel concept for the study of heterogeneous robotic swarms, IEEE Robotics & Automation Magazine, 2013, Vol. 20(4), pp. 60–71. DOI: 10.1109/MRA.2013.2252996
Efremov M. A., & Kholod I. I. Swarm Robotics Foraging Approaches, IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 2020, January, pp. 299–304. IEEE. DOI: 10.1109/EIConRus49466.2020.9039340
Fricke G. M., Hecker J. P., Cannon J. L., & Moses M. E. Immune-inspired search strategies for robot swarms. Robotica, 2016, No. 34(8), pp. 1791–1810. DOI: 10.1017/S0263574716000382
Fujisawa R., & Dobata S. Lévy walk enhances efficiency of group foraging in pheromone-communicating swarm robots. In Proceedings of the 2013 IEEE/SICE International Symposium on System Integration, IEEE, 2013, pp. 808–813. DOI: 10.1109/SII.2013.6776760
Grosan C., Abraham A., & Chis M. Swarm intelligence in data mining, Swarm Intelligence in Data Mining. Springer, Berlin, Heidelberg, 2006, pp. 1–20. DOI: 10.1007/978-3-540-349563_1
Karaboga D. An idea based on honey bee swarm for numerical optimization, Technical ReportTR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005, Vol. 200, pp. 1–10. https://abc.erciyes.edu.tr/pub/tr06_2005.pdf
Lima D. A., Tinoco C. R., & Oliveira G. M. A cellular automata model with repulsive pheromone for swarm robotics in surveillance, International Conference on Cellular Automata. Springer, Cham, 2016, pp. 312–322. DOI: 10.1007/978-3-31944365-2_31
O’Gra R., Grob R., Christensen & Dorigo M. Performance Benefits of SelfAssembly in a Swarm-Bot, IEEE Computer Society Press, 2007, pp. 2381–2387. DOI: 10.1109/IROS.2007.4399424
Olfati-Saber R. Flocking for multi-agent dynamic systems: Algorithms and theory, IEEE Transactions on automatic control, 2006, Vol. 51(3), pp. 401–420. DOI: 10.1109/TAC.2005.864190
Payton D., Estkowski R., & Howard M. Pheromone robotics and the logic of virtual pheromones, International Workshop on Swarm Robotics. Springer, Berlin, Heidelberg, 2004, July, pp. 45–57. DOI: 10.1007/978-3-540-30552-1_5
Şahin E. Swarm robotics: From sources of inspiration to domains of application, International workshop on swarm robotics, Springer, Berlin, Heidelberg, 2004, pp. 10–20. DOI: 10.1007/978-3-540-30552-1_2
Schroeder A., Ramakrishnan S., Kumar M., & Trease B. Efficient spatial coverage by a robot swarm based on an ant foraging model and the Lévy distribution, Swarm Intelligence, 2017, Vol. 11(1), pp. 39–69. DOI: 10.1007/s11721-017-0132-y
Seyfried J., Szymanski M., Bender N., Estana R., Thiel M., & Wörn H. The I-SWARM project: Intelligent small world autonomous robots for micro-manipulation, International Workshop on Swarm Robotics. Springer, Berlin, Heidelberg, 2004, pp. 70–83. DOI: 10.1007/978-3-540-30552-1_7
Shtovba, S. D. Ant algorithms: theory and applications, Programming and Computer Software, 2005, Vol. 31(4), pp. 167–178. DOI: 10.1007/s11086-005-0029-1
Timmis J., Andrews P., & Hart E. (). On artificial immune systems and swarm intelligence, Swarm Intelligence, 2010, Vol. 4(4), pp. 247–273. DOI: 10.1007/s11721-010-0045-5
Tinoco C. R., Lima D. A., & Oliveira G. M. (). An improved model for swarm robotics in surveillance based on cellular automata and repulsive pheromone with discrete diffusion, International Journal of Parallel, Emergent and Distributed Systems, 2019, Vol. 34(1), pp. 53–77. DOI: 10.1080/17445760.2017.1334886
Valentini G., Brambilla D., Hamann H. & Dorigo M. Collective Perception of Environmental Features in a Robot Swarm, International Conference on Swarm Intelligence. Springer, 2016, pp. 65–76. DOI: 10.1007/978-3-319-44427-7_6
Wilson S., Pavlic T. P., Kumar G. P., Buffin A., Pratt S. C., & Berman S. Design of ant-inspired stochastic control policies for collective transport by robotic swarms, Swarm Intelligence, 2014, Vol. 8(4), pp. 303–327. DOI: 10.1007/s11721-014-0100-8
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 T. A. Vakaliuk, R. P. Kukharchuk, O. V. Zaika, A. V. Riabko
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
