Мультиагентное управление

Введение

Презентацию к лекции Вы можете скачать здесь.

Совместное управление или управление распределенными динамическими системами на графах относится к ситуации, в которой каждый узел может получать информацию для проектирования управления только от самого себя и от своих соседей. Граф может задавать топологию сети связей, которая ограничивает связи между узлами. Это также называют мультиагентным управлением.

Несмотря на большое количество публикаций по этой тематике, пока удовлетворительные решения получены лишь для ограниченного класса практически важных задач, так как решение таких проблем существенно усложняется, с одной стороны, из-за обмена неполной информацией, которая, кроме того, обычно измеряется с помехами, а, с другой, из-за эффектов квантования (дискретизации), свойственных всем цифровым системам.

Цели управления

Остановимся на различных целях управления, которые решают системы мультиагентного управления (МАУ).

Синхронизация — совпадение или сближение переменных состояния двух или нескольких систем, либо согласованное изменение некоторых количественных характеристик систем.

Задача синхронизации отличается от задачи управления с эталонной моделью, поскольку в ней допускается совпадение различных переменных, взятых в различные моменты времени. Временные сдвиги могут либо быть постоянными, либо стремиться к постоянным. Кроме того, во многих задачах синхронизации связи между системами являются двусторонними (двунаправленными). Это значит, что предельный режим в системе (синхронное решение) заранее не известен. Общей особенностью задач управления синхронизацией является то, что желаемое поведение однозначно не фиксировано, а его характеристики задаются лишь частично. В задачах синхронизации часто основным требованием является совпадение или согласованность колебаний всех подсистем, в то время как характеристики движения каждой подсистемы могут варьироваться в широких пределах 1. В контексте МАУ под синхронизацией понимают согласованное поведение агентов, например, полное или частичное сближение со временем состояний агентов или их наблюдаемых выходов.

В МАУ такая цель управления чаще формулируется как задача достижения консенсуса 2,3 или согласования характеристик 4, в которых каждый агент стремится уменьшить отклонение своей целевой переменной от соответствующих переменных своих соседей. Если речь идет об отклонении от среднего арифметического состояний соседей, то ставится задача достижения усредненного консенсуса.

Задача по переводу группы агентов в некоторое общее состояние называется задачей о рандеву (англ. rendezvous). В ней требуется, чтобы все агенты оказались в заданном месте в заданное время.

Еще одним классом задач МАУ является распределенное управление формациями (англ. formation control) — управление локально взаимодействующими агентами, образующими некоторые геометрические конфигурации. Такие задачи обычно решаются применительно к мобильным роботам, беспилотным летательным аппаратам, подводным автономным устройствам и др. Задачи группового управления (управления формациями) 5 сводятся к задачам частичной координатной синхронизации с помощью метода виртуального лидера.

При большом числе агентов (а в ряде задач число агентов достигает тысяч и миллионов), требование заданного поведения всех без исключения агентов оказывается излишне жестким и трудновыполнимым. В таких случаях выделяется характерная точка в множестве состояний агентов (центр, лидер, центр тяжести), а желательным поведением является заданное поведение центра при условии ограниченности отклонений от него состояний всех агентов. Для такого поведения вводятся понятия, заимствованные из биологии: сбивание в стаи, роение (англ. swarming, flocking), и устанавливаются условия возникновения в системе соответствующих свойств 6,7.

Отдельный класс задач МАУ — распределение ресурсов между разными возможными заданиями, задачи диспетчеризации (англ. scheduling), которые сводятся к задаче достижения консенсуса.

Балансировка загрузки узлов децентрализованной вычислительной сети при неполной информации

Распределенное взаимодействие в сетях динамических управляемых агентов привлекает в последние время внимание все большего числа исследователей. Во многом это объясняется широким применением мультиагентных систем в разных областях, включая автоматическую подстройку параметров нейронных сетей распознавания, управление формациями 1, роение 2, распределенные сенсорные сети 3, управление перегрузкой в сетях связи 4, взаимодействие групп беспилотных летательных аппаратов (БПЛА), относительное выравнивание групп спутников и др. Многие из таких задач легко переформулируются в терминах достижения консенсуса в мультиагентных системах 5-7.

Решение таких задач существенно усложняется при практическом применении, с одной стороны, из-за обмена неполной информацией, которая, кроме того, обычно измеряется с помехами, а, с другой, из-за эффектов квантования (дискретизации), свойственных всем цифровым системам 8-12.

Для группы взаимодействующих агентов, обменивающихся с задержкой неполной информацией в дискретные моменты времени, при изменяющейся топологии связей в 2 предложен и обоснован алгоритм стохастической аппроксимации для решения задачи о достижении консенсуса. Алгоритмы типа стохастического градиента использовали в такого типа задачах и ранее 14-17. Стохастическая аппроксимация с убывающим размером шага позволяет каждому агенту получать информацию о состоянии своих соседей при одновременном снижении воздействия помех. Популярным инструментом для доказательства состоятельности этих алгоритмов являются квадратичные функции Ляпунова, наличие которых гарантировано при фиксированной топологии сети.

В случае сети с переменной топологией квадратичная функция Ляпунова в 6 применяется для случая сбалансированной модели графа связности, матрицы которого стохастические по строкам и столбцам. В 9 для неориентированных графов стохастические по строкам и столбцам весовые матрицы строились на основе весов Метрополиса. Распределенные итеративные алгоритмы для построения на ориентированных графах (орграфах) стохастических матриц по строкам и столбцам были предложены в 18, но они не применимы при отсутствии полной информация о текущей топологии сети.

Практическое значение имеет рассмотрение моделей без свойства стохастичности матриц по строкам и столбцам, как в 12. Кроме того, желательно иметь алгоритмы достижения консенсуса, работоспособные и в нестационарных условиях.

При динамических внешних изменениях состояний агентов (получение новых заданий и т. п.) алгоритмы стохастической аппроксимации с уменьшающимся размером шага не применимы. В 9-22исследуется работоспособность алгоритмов стохастической аппроксимации с постоянным размером шага в условиях нестационарных функционалов качества (среднего риска). Их применимость для балансировки загруженности узлов централизованной вычислительной сети при доступности текущей зашумленной иформации о загруженности и производительности узлов была исследована в 22,23 для разработки специальной программы - брокера загрузки.

В этой лекции будут рассмотрены возможности применения результатов 12 к задачам о балансировке загруженности узлов децентрализованной вычислительной сети при поступлении в каждый узел только зашумленной информации о загруженности и производительности соседей, причем топология связей в сети может меняться со временеи, а информация от соседей доходить с задержкой по времени.

Задача консенсуса на графах

Поясним обозначения, использующиеся далее. Верхний индекс $$у$$ переменных будем используется в качестве индекса, а не показателя степени. Для матрицы $$A$$ элемент, находящийся на ее $$i$$-й строке и в $$j$$-м столбце называется $$(i,j)$$-м элементом и обозначается как $$a^{i,j}$$ . Для вектора или матрицы $$M$$определим норму Фробениуса $$\lvert M \rvert=[Tr(M^TM]^{1/2}$$. Будем использовать $$1_k \in P^k$$, чтобы определить вектор-столбец из $$k$$ единиц. Для вектор-столбцов $$Z_1,...,Z_l,[Z_1;...;Z_l]$$ определяет вектор-стоблец, полученный вертикальным соединением $$l$$векторов.

Для описания топологии сети будем использовать понятия теории графов. Ориентированный граф (орграф) $$G=(N,E)$$ состоит из множества узлов $$N={1,…,n}$$ и множества ребер $$E$$. Ребро определяется упорядоченной парой $$(i,j) \in N \times N$$, где $$i \neq j$$. Направленный путь (из узла $$i_1$$ в узел $$i_l$$) состоит из последовательности узлов $$i_1,…,i_l, l \geqslant 2$$ таких, что $$(i_k,i_{k+1}) \in E$$. Орграф $$G$$ называется сильно связным , если из любого узла в любой другой узел существует направленный путь. Направленное дерево – это орграф, в котором каждый узел $$i$$, кроме корня, имеет ровно одного родителя $$j$$, такого, что $$(j,i) \in E$$. Будем называть $$\overline G= (\overline N, \overline E) $$ подграфом $$G$$, если $$\overline N \subset N$$ и $$\overline E \subset E \cap \overline N \times \overline N$$. Будем говорить, что орграф содержит остовное дерево , если существует направленное дерево $$G_{tr}=(N,E_{tr})$$ как подграф $$G$$. Матрицей связности графа $$G$$ называется матрица размером $$ \times \n>$$ такая, что $$A_G=(a^{i,j})_{1 \leqslant i, j \leqslant n}$$, где $$a^{i,j}=1$$, если $$(i,j) \in E$$ и $$ a^{i,j}=0$$ в остальных случаях. Если $$G$$ – неориентированный граф, то каждое ребро определяется как неупорядоченная пара $$(i,j)$$, где $$i \neq j$$.

Топология динамической сети, показывающая принимаемые сигналы моделируется с помощью последовательности орграфов $${G_t=(N,E_t)}_{t \geqslant0}$$, где , а каждое $$E_t \subset E$$ и случайно меняется во времени. Матрица связности $$A_{G_t}$$ – матрица, которая полностью определяет $$E_t$$. Если $$(j,i) \in E_t$$, то говорим, что узел $$i$$ получает информацию от узла $$j$$, который называется соседом узла $$i$$. Обозначим $$N^i_t=\lbrace j \lvert (j,i) \in E_t \rbrace$$ – множеством соседей узла $$i$$. Множество соседей подмножества $$ N_{\overline N}$$ определяется следующим образом:

$$N_{\overline N}:= \bigcap\limits_{i \in \overline N}N^i_t=\lbrace j \in N: i \in\overline N,(i,j) \in E \rbrace$$

Пусть $$x^i_t \in R$$ определяет состояние узла $$i$$ в момент времени $$t \in \lbrace 0,1,2,…\rbrace$$. Определим информационный поток в сети как $$G_x=(G_t,X_t)$$, где $$X_t=[x^1_t,…,x^n_t],t \geqslant 0$$ набор значений состояний узлов сети, $$X_t \in P^n$$, а $$G_t$$ – топология . Состояниями узла могут быть, например, физические характеристики (положение, температура, напряжение и др.). В динамической сети с переменной топологией информационный поток $$G_x$$ – это дискретное состояние системы, меняющееся во времени. Будем говорить, что узлы $$i$$ и $$j$$ согласованы в сети тогда и только тогда, когда $$x^i_t=x^j_t$$, и узлы достигли консенсуса тогда и только тогда, когда $$x^i_t=x^j_t$$для любых $$i,j \in N, i \neq j$$. Когда все узлы сети согласованы, общее значение узлов называется групповым решением .

Если узлы графа – динамические агенты , описываемые уравнениями:

$$\dot{x}^i_t=f^i(x^i_t,u^i_t), i \in N,$$

то динамический граф(или динамическая сеть) – это динамическая система с состояниями $$(G_t,X_t)$$, в которой $$X_t$$ меняется в соответствии с динамикой сети

$$\dot{X}_t=F(X_t,U)=[f^1(x^1_t,u^1_t,...,f^n(x^n_t,u^n_t)]$$, где $$U=[u^1_t,...,u^n_t]$$

Будем считать, что в момент времени $$t$$, если $$N^i_t \neq \varnothing$$ узел $$i$$ получает, возможно, устаревшую информацию от своих соседей, моделируемую следующим образом:

$$y^{ik}_t=x^k_{t-d^{ik}_t}+w^{ik}_t, k \in N^i_t$$

где $$ w^{ik}_t $$ – помехи, а $$d^{ik}_t \geqslant$$ – целочисленная случайная задержка. Так как система начинает работу при $$t=0$$, неявным требованием к множеству соседей будет:

$$k \in N^i_t \rightarrow t-d^{ik}_t \geqslant 0$$

Каждый узел использует информацию о своем собственном состоянии (может быть и зашумленную), а также свои зашумленные измерения для $$u^i_t$$. Будем называть обратную связь по наблюдениям состояний

$$U_t=k_t(X_t),u^i_t=k^i_t(y^{j_1}_t,...,y^{j_{m_i}}_t})$$

протоколом с топологией $$ G_t, \lbrace j_1,…,j_{m_i} \rbrace \in \overline N^{i,t} \subseteq \lbrace i \rbrace \cup N^i_t $$, для любого $$i$$ из узлов $$j_1,…,j_{m_i} \in N$$ удовлетворяет свойству:$$\overline N^i \subseteq \lbrace i \rbrace \cup N^i_t $$. Если $$\lvert \overline N_i \rvert $$ < $$n$$ для любого $$i \in N$$, то (5) называется распределенным протоколом .

Пусть $$\chi : P^n \rightarrow P$$ – некоторая функция $$n$$переменных. Задача $$\chi$$-консенсуса в динамическом графе заключается в распределенном вычислении $$\chi (X_0)$$, применяя входы $$u^i_t$$.

Определение 1: Протокол (5) асимптотически решает задачу $$\chi$$-консенсуса тогда и только тогда, когда существует асимптотически устойчивое равновесие $$X^*$$ для $$\dot {X}_t=F(X_t,k_t(X_t))$$, удовлетворяющее $$x^{*,i}=\chi (X_0)$$для любого $$i \in N$$.

Отметим особые случаи, когда $$\chi (X)=Ave(X)=1/n(\sum \limits^n_{i=1} x^i)$$, $$\chi (X)=max_i x^i$$ и $$\chi (X)=min_i \lvert x^i \rvert$$, называемые консенсус усреднения , -консенсус и -конснсус соответственно 6. Эти случаи широко применяются в распределенных системах принятия решений для мультиагентных систем.

Решение задачи консенсуса усреднения является примером распределенного вычисления линейной функции $$\chi (X)=Ave(X)$$, используя сеть динамических систем (или интеграторов).

Пусть $$(\Omega,F,P)$$ – основное вероятностное пространство и будем считать, что часть или все определенные выше переменные, вектора и матрицы – случайные величины.

Обозначим максимальное множество каналов связи $$E_{max}=\lbrace (k,i) \lvert sup_{t \geqslant 0} ((k,i) \in E_t) > 0 \rbrace$$.

Для удобства статистического моделирования предположим следующее: $$w^{ik}_t$$ и $$d^{ik}_t$$ определены для всех $$(k,i) \in E_{max}$$. Если $$(k,i)$$ не появляется в $$E_t$$, тогда (3) физически не работает и $$w^{ik}_t$$ и $$d^{ik}_t$$ можно считать нулями. Если $$(k,i) \notin E_t$$, положим $$d^{ik}_t=0$$. Пусть $$w^{ik}_t \lvert (k,i) \in E_{max}$$ перечислены в определенном порядке $$(k,i)$$, тогда получаем вектор помех $$W_t$$ размерности $$n_1$$.

Определение 2: $$n$$ узлов достигают среднеквадратичного консенсуса , если $$ E \lvert x^i_t \rvert ^2 < \propto , t \geqslant 0, 1 \leqslant i \leqslant n $$ и существует случайная переменная $$x^*$$ такая что $$lim_{t \rightarrow \propto} E \lvert x^i_t – x^* \rvert ^2=0$$ для $$1 \leqslant i \leqslant n $$.

Далее будет рассмотрен пример мультиагентной системы с описанными выше параметрами.

Задача балансировки загруженности сети

В последнее время все чаще при вычислениях используются распределенные системы параллельных вычислений, для которых актуальна задача разделения пакета заданий между несколькими вычислительными устройствами.

Рассмотрим модель системы разделения однотипных заданий между разными узлами для параллельных вычислений с обратной связью. Обозначим $$N= \lbrace 1,…,n \rbrace$$ набор интеллектуальных агентов (вычислительных узлов), каждый из которых обслуживает поступающие заявки на вычисления по принципу очереди, то есть первый вошел - первый вышел. Будем считать, что всем агентам присылают однотипные задания, которые можно раздробить на одинакове по сложности атомарные единицы. Задания поступают в различные моменты времени и на разные узлы. Считается известным размер каждой задачи (или задания), то есть его трудоемкость, в секундах или циклах процессора.

В каждый момент времени $$t$$ состояние агента $$i$$, $$i=1,…,n$$, описывается двумя характеристиками:

Обозначим $$x^i_t=q^i_t / p^i_t$$

Задача для сети агентов – выполнять поступающие последовательно задания. Будем рассматривать две постановки задачи: стационарную и нестационарную.

В каждый момент времени $$t$$ узел $$t$$ может получить от своих "видимых" соседей $$j \in N^i_t$$ следующую информацию:

Задача состоит в том, чтобы составить протокол общения между агентами, при котором все узлы будут загружены равномерно, т. е. $$q^i_t/p^i_t \rightarrow c^*_t$$, независящей от $$i$$, т. е. если в систему не будут поступать новые заказы, то все узлы закончат работать одновременно.

На рис. 9.1 приведен пример вычислительной сети из шести агентов с указанием возможных каналов связи, часть из которых может "закрываться" и "открываться" с течением времени.

Протоколы консенсуса

В 6 показано, что консенсус асимптотически достижим в двух типичных случаях.

В случае неориентированных графов для интуитивного обоснования протокола (7) можно воспользоваться следующими соображениями. Определим потенциал Лапласа , связанный с неориентированным графом $$G=(N,E,A)$$ следующим образом: $$\Phi_G(X_t)=1/2 \sum \limits^n_{i,j=1}a^{i,j}(x^j_t-x^i_t)^2,$$ и отметим, что обратная связь, основанная на методе скоростного градиента 25 $$u_t=-1/2 \bigtriangledown \Phi_G(X_t)$$ совпадает с протоколом (7). В результате динамика сети для агентов с применением протокола (7) выглядит следующим образом: $$\dot {X}_t=-1/2\bigtriangledown \Phi_G(X_t)$$, которая является градиентной системой порожденной графом .

Для ориентированных сетей вопрос об обосновании протокола консенсуса является более сложным.

Обычно рассматривают два типа протоколов консенсуса, которые решают задачу согласования в сети с непрерывным временем для агентов с динамикой: $$\dot {x}^i_t=u^i_t $$или для модели агентов в дискретном времени: $$x^i_{t+1}=x^i_t+\alpha u^i_t$$, с некоторым размером шага $$\alpha$$ > 0 . Мы далее будем рассматривать только дискретный случай.

Для решения сформулированной в разделе 2 общей постановки задачи о построениии протокола консенсуса в 12 предлагается следующий метод стохастической аппроксимации.

Определим матрицу $$B_t=(b^{i,k}_t)_{1 \leqslant i , k \leqslant n }$$ следующим образом: если $$N^i_t= \varnothing$$, то $$b^{i,k}_t=0$$ для любого $$k \in N$$. Если $$ N^i_t \neq \varnothing $$, то $$\begin{cases} b^{i,k} \in [ \underline {b}, \overline {b}], k \in N^i_t\\ b^{i,k}=0, k \notin N^i_t \cup \lbrace i \rbrace\\ b^{i,i}_t=-\sum \limits_{k \in N^i_t} b^{i,k}_t \end{cases}$$ где $$0 < \underline {b} \leqslant \overline {b} < \propto$$ – две детерминированных константы. Пока последовательность $$\lbrace G_t \rbrace _{t \geqslant 0$$ меняется случайно, $$\lbrace B_t \rbrace _{t \geqslant 0$$ – матричный случайный процесс.

В момент времени $$t \geqslant 0$$, если $$N^i_t = \varnothing$$, множество $$x^i_{t+1}=x^i_t$$.

Если $$N^i_t \neq \varnothing$$, узел $$i$$ меняет свое состояние по правилу: $$x^i_{t+1}=[1+\alpha_t b^{i,j}_t]x^i_t+\alpha \sum \limits_{k \in N^i_t} b^{i,k}_t y^{ik}_t, t \geqslant 0,$$где $$\lbrace \alpha_t \rbrace _{t \geqslant 0$$ – последовательность положительных размеров шагов. Будем называть $$I+ \alpha_t B_t$$ – весовой матрицей. Поскольку все узлы обновляют свои состояния одновременно, (15) является синхронным алгоритмом.

Вернемся к задаче о балансировке загрузки узлов вычислительной сети. В качестве ненулевых $$b^{i,j}_t$$ берем $$p^i_t/p^j_t$$. В этом случае $$\underline {b}=min_t p^i_t/p^j_t, \overline {b}= max_t p^i_t/p^j_t < \propto $$.

Алгоритм (15) в задаче о балансировке загрузки узлов вычислительной сети принимает вид $$q^i_{t+1}=[1+ \alpha_t b^{i,i}]q^i_t+ \alpha_t \sum \limits_{j \in N^i_t} b^{i,j}y^{-ij}_t, t \geqslant 0,$$

Задачи балансировки загрузки встречаются не только в вычислительных сетях, но также в производственных, логистических, транспортных и других сетях 33-37.