Batsamut, V. M.Hodlevsky, S. O.Бацамут, В. М.Годлевський, С. О.2026-01-212026-01-212023https://eir.zp.edu.ua/handle/123456789/26477Batsamut V. M. Method of routing a group of mobile robots in a fixed network for searching the missing objects in a technological disaster zone / V. M. Batsamut, S. O. Hodlevsky // Радіоелектроніка, інформатика, управління. – 2023. – № 1 (64). – C. 141-154.EN: Context. The relevance of the article is determined by the need for further development of models of collective behavior of systems with multi-agent structure construction endowed with intelligence that ensures synchronization of the joint efforts of various agents while achieving the goals set for the system. The method proposed in the article solves the problem of competition between different agents of a multi-agent system, which is important while performing search, rescue, and monitoring tasks in crisis areas of various origins. Objective is to develop a method for determining the sufficient population of a multi-agent system and the optimal routes of movement of its individual elements in a stationary network for the most complete examination of a technological disaster zone (any given zone based on a certain transport network). Method. We implemented the concept of a dynamic programming to search for all possible edge-simple longest paths connecting the directed subsets of vertices-sources and vertices-sinks in the structure of the model weighted directed graph. To this end, the modified Dijkstra method was applied. The modification comprises representing the weights of the arcs of the modeling directed graph with the negative values, which are further used in calculations according to the Dijkstra method. After finding the next edge-simple longest path, the arcs that make up it are fixed in the memory of the computer system (in the route plan) and removed from the graph structure, and the process is iteratively repeated. The search for paths takes place as long as the transitive closure between the vertices that are part of the specified subsets of source vertices and sink vertices is preserved. The developed method makes it possible to find such a set of traffic routes for the elements of the multi-agent system, which maximizes the area examined by them in a technological disaster zone (or the number of checked objects on the traffic routes) in one “wave” of the search and distributes the elements of a multi-agent system by routes that do not have common areas. A derivative of the application of the developed method is the determination of a sufficient population of a multi-agent system for effective search activities within the defined zone. Results. 1) A method of routing a group of mobile robots in a stationary network for searching the missing objects in a technological disaster zone has been developed. 2) The working expression of the Dijkstra method for searching in the structure of a network object (in the structure of a model graph) for the longest paths has been formalized. 3) We have suggested a set of indicators for a comprehensive evaluation of route plans of a multi-agent system. 4) The method has been verified on test problems. Conclusions. Theoretical studies and several experiments confirm the efficiency of the developed method. The solutions made using the developed method are accurate, which allows recommending it for practical use in determining in an automated mode route plans for multi-agent systems, as well as the required number of agents in such systems to perform the required amount of search tasks in a particular crisis area. UK: Актуальність. Актуальність статті обумовлюється потребою у подальшому розвитку моделей колективної поведінки систем із мультиагентною побудовою структури, у наділенні таких систем інтелектом, який забезпечує синхронізацію спільних зусиль різних агентів у ході досягнення поставлених перед системою цілей. Запропонований у статті метод усуває проблему конкуренції між різними агентами мультиагентної системи, що є важливим у ході виконання пошукових, рятувальних, моніторингових завдань у кризових районах різного характеру походження. Мета роботи полягає у розробленні методу визначення достатньої чисельності мультиагентної системи та оптимальних маршрутів руху її окремих елементів на стаціонарній мережі для максимально повного обстеження зони техногенної аварії (будь-якої заданої зони, в основі якої лежить певна транспортна мережа). Метод. Застосовано ідею динамічного програмування для пошуку в структурі модельного зваженого орієнтованого графа всіх можливих реберно-простих найдовших шляхів, що з’єднують директивно визначені підмножини вершин-істоків та вершин-стоків. З цією метою застосовано модифікований метод Дейкстри. Модифікація полягає у представленні ваг дуг моделюючого орієнтованого графа значеннями з від’ємної області з подальшою роботою метода Дейкстри з цими значеннями. Після відшукування чергового реберно-простого найдовшого шляху, дуги, що його складають, фіксуються у пам’яті обчислювальної системи (у маршрутному плані) та видаляються зі структури графа і процес ітераційно повторюється. Пошук шляхів відбувається доти, поки зберігається транзитивне замкнення між вершинами, що входять до складу визначених підмножин вершин-істоків та вершин-стоків. Розроблений метод дозволяє знайти таку сукупність маршрутів руху для елементів мультиагентної системи, яка максимізує обстежену ними площу в зоні техногенної аварії (або кількість перевірених об’єктів на маршрутах руху) за одну “хвилю” пошуку, та розподіляє елементи мультиагентної системи маршрутами, що не мають спільних ділянок. Похідною застосування розробленого методу є визначення достатньої чисельності мультиагентної системи для ефективного проведення пошукових заходів у межах визначеної зони. Результати. 1) Розроблено метод маршрутизації групи мобільних роботів на стаціонарній мережі для виконання завдань пошуку зниклих об’єктів в зоні техногенної аварії; 2) Формалізовано робочий вираз методу Дейкстри для пошуку в структурі мережевого об’єкту (в структурі модельного графа) шляхів найбільшої довжини; 3) Запропонована сукупність показників для комплексного оцінювання маршрутних планів мультиагентної системи; 4) Виконано верифікацію методу на тестових задачах. Висновки. Проведені теоретичні дослідження та низка експериментів підтверджують працездатність розробленого методу. Рішення, що виробляються із використанням розробленого методу, є точними, що дозволяє рекомендувати його до практичного використання при визначенні в автоматизованому режимі маршрутних планів для мультиагентних систем, а також потрібної кількості агентів в таких системах для виконання необхідного обсягу пошукових завдань у певному кризовому районі.enmulti-agent systemgroup of mobile robotsroutingnetwork objectweighted undirected (directed) graphextreme pathsoptimization criterionmethodмультиагентна системагрупа мобільних роботівмаршрутизаціямережевий об’єктзважений неорієнтований (орієнтований) графекстремальні шляхикритерій оптимізаціїметодArticle