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

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

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.