Preview

Доклады БГУИР

Расширенный поиск

Динамическая асимметричная задача о назначении в открытых многоагентных системах

https://doi.org/10.35596/1729-7648-2020-18-5-53-61

Полный текст:

Аннотация

Цель работы – разработка моделей и алгоритмов оптимизации паросочетаний в динамически формируемых графах асимметричных отношений в координируемых открытых системах взаимодействующих агентов с централизованным и коллективным управлением. Динамическая асимметричная задача оптимизации паросочетаний здесь возникает как результат компромиссной аппроксимации отображения метода динамического программирования на поток известных открытых задач о назначении или нескольких странствующих коммивояжёров. Однако представленные таким образом альтернативы ветвления на независимых задачах не учитывают взаимозависимость реальных отношений между агентами и их заданиями, включая их привязку ко времени. Игнорирование зависимости альтернатив ветвления приводит к задержке момента или потере качества назначения заданий координируемым агентам. Основная идея предлагаемой реализации известного для эффективного управления принципа – откладывание момента принятия окончательного решения на наиболее поздний момент, учет восприимчивости системы к локальным изменениям переменных состояния. Взаимозависимость состояний выявляется на основе анализа соответствия графа текущего паросочетания оптимальному решению на подграфе совершенного паросочетания. Переход между состояниями реализуется инкрементальной версией алгоритма реоптимизации решения линейных задач о назначении методом кратчайшего пополняющего пути. Пространство состояний поиска – динамически формируемый двудольный разреженный граф альтернатив сочетания агентов и задач, представленный списком дуг. Для выделения множеств изменившихся дуг предложено дополнить веса дуг границами интервалов устойчивости решения, факультативно формируемых в фоновом режиме. По умолчанию вес измененной дуги совпадает с границей интервала устойчивости. На каждом цикле коррекции списков агентов, задач и их ассоциаций выделяются подмножества элементов, для которых требуется пересмотр паросочетания. Усиленное условие отбора таких элементов – выход за границы интервала устойчивости. При этом асимметрия задачи назначения учитывается выбором структуры смежности для доли графа с минимумом вершин. В результате время реакции процедур решения задачи назначения сокращается на порядок.

Об авторах

М. П. Ревотюк
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

Ревотюк Михаил Павлович, к.т.н., доцент, доцент кафедры информационных технологий автоматизированных систем

220013, г. Минск, ул. П. Бровки, 6

тел. +375-17-293-86-58

 



Н. В. Хаджинова
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

cтарший преподаватель кафедры информационных технологий автоматизированных систем

г. Минск



А. П. Кузнецов
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

д.т.н., профессор, профессор кафедры систем управления

г. Минск



Л. Ю. Шилин
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

д.т.н., профессор, декан факультета информационных технологий и управления

г. Минск



Список литературы

1. Korsah G.A., Stentz A., Dias M.B. A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research. 2013;12(32):1495-1512.

2. Spivey M.Z., Powel W.B. The Dynamic Assignment Problem. Transportation science. 2004;38(4):399-419.

3. Pentico D.W. Assignment problems: A golden anniversary survey. European Journal of Operational Research. 2007;176(2):774-793.

4. Bijsterbosch J., Volgenant A. Solving the Rectangular assignment problem and applications. Annals of Operations Research. 2010;181(1):443-462.

5. Ревотюк М.П., Батура П.М., Полоневич А.М. Реоптимизация решения задач о назначении. Доклады БГУИР. 2011;1(55):55-62.

6. Toroslu I.H., Üçoluk G. Incremental assignment problem. Information Science. 2007;177:1523-1529.

7. Ревотюк М.П., Кароли М.К., Батура П.М. Реализация метода ветвей и границ для решения задач коммивояжера c разреженными матрицами. Доклады БГУИР. 2013;7(77):25-31.

8. Ревотюк М.П., Кароли М.К., Батура П.М. Быстрая оценка интервалов устойчивости решения линейных задач о назначении. Доклады БГУИР. 2013;5(75):30-36.


Для цитирования:


Ревотюк М.П., Хаджинова Н.В., Кузнецов А.П., Шилин Л.Ю. Динамическая асимметричная задача о назначении в открытых многоагентных системах. Доклады БГУИР. 2020;18(5):53-61. https://doi.org/10.35596/1729-7648-2020-18-5-53-61

For citation:


Revotjuk M.P., Khajynova N.V., Kuznetsov A.P., Shilin L.Y. Dynamic asymmetric assignment problem in open multi-agent systems. Doklady BGUIR. 2020;18(5):53-61. (In Russ.) https://doi.org/10.35596/1729-7648-2020-18-5-53-61

Просмотров: 65


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1729-7648 (Print)
ISSN 2708-0382 (Online)