Optimization of swarm robotics algorithms

Abstract

EN: 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. UK: Актуальність. Серед різноманіття завдань, які вирішуються робототехнікою, можна виділити цілий ряд таких, для вирішення яких невеликі габарити робота бажані, а часом і необхідні. Для вирішення подібних завдань необхідні мікророботи з малими габаритами, маса яких дозволяє безперешкодно переміщатися у тісних проходах, складних погодних умовах, залишатися непоміченими. Водночас, малі габарити мікроробота накладають також і ряд непрямих обмежень, що зумовлює застовування для означених завдань групи мікророботів. Ефективність застосування груп мікророботів залежить від обраної стратегії управління і стохастичних пошукових алгоритмів оптимізації управління групою (роєм) мікророботів. Мета. Метою данної роботи є розгляд групи ройових алгоритмів (методів), які відносяться до класу метаеврістік. До групи означених алгоритмів відноситься, зокрема, алгоритм мурашиної колонії, можливості якого досліджувалися для розв’язування задачі комівояжера, яка часто постає при розробці алгоритму поведінки групи мікророботів. Метод. На першому етапі дослідження було виділено основні групи параметрів, які визначають перебіг і характеризують стан в будь-який момент часу алгоритму мурашиної колонії: вхідні, керуючи, параметри збурення, вихідні. Після виділення основних груп параметрів було розроблено алгоритм, перевага якого полягає в масштабованості, а також гарантованій збіжності, що дозволяє отримати оптимальний розв’язок незалежно від розмірності графа. На другому етапі ророблений алгоритм ACO (ant colony optimization algorithm) було реалізовано на мові Matlab. Були проведені комп’ютерні експерименти з метою визначення впливу вхідних, керуючих, вихідних і параметрів збурення на збіжність алгоритму. Було приділено увагу основним групам показників, які визначають напрямок способу і характеризують стан рою мікророботів у даний момент часу. В обчислювальному експерименті варіювалася кількість мурах, що розміщуються у вузлах мережі, місткість феромона, чисельність вузлів графа, визначалася чисельність ітерацій для розшуку найменшого шляху та час виконання методу. Проведено тест підсумків моделювання та продуктивності методу. Результати. Проведено дослідження застосування мурашиного алгоритму для розв’язування задачі комівояжера для тестових графів з випадковим розташуванням вершин; для постійної кількості вершин і зміні кількості мурах, для постійної кількості вершин при різних значеннях коефіцієнта Q; для розв’язування задачі комівояжера для постійної кількості вершин при різних значеннях коефіцієнта випаровування феромону p; для різної кількості вершин графа. Результати показали, що мурашині способи знаходять хороші маршрути комівояжера значно швидше, ніж чіткі методи комбінаторної оптимізації. Встановлено залежності часу пошуку і знайденого оптимального маршруту від значень керуючих параметрів на прикладі тестових мереж для різної кількості вершин графа та ітерацій. Висновки. Проведені дослідження дозволяють дати рекомендації щодо застосування алгоритму мурашиної колонії ACO (ant colony optimization algorithm) для управління групою (роєм) мікророботів.