Автоматика и телемеханика, № 4, 2019

Обзоры

(Институт проблем передачи информации им. А.А. Харкевича РАН, Москва,

Институт радиотехники и электроники им. В.А. Котельникова РАН, Москва),

Н.А. КУЗНЕЦОВ, академик РАН (kuznetsov@cplire.ru)

(Институт радиотехники и электроники им. В.А. Котельникова РАН, Москва,

Московский физико-технический институт (ГУ)),

П.Ю. ЧЕБОТАРЕВ, д-р физ.-мат. наук (pavel4e@gmail.com)

(Институт проблем управления им. В.А. Трапезникова РАН, Москва,

Институт радиотехники и электроники им. В.А. Котельникова РАН, Москва,

Московский физико-технический институт (ГУ))

КОНСЕНСУС В АСИНХРОННЫХ МУЛЬТИАГЕНТНЫХ СИСТЕМАХ.

I. АСИНХРОННЫЕ МОДЕЛИ КОНСЕНСУСА¹

Представлен обзор результатов по моделям консенсуса в асинхронных

мультиагентных системах с дискретным и непрерывным временем. Дает-

ся описание математических методов, разработанных в последние годы,

которые используются при анализе проблем устойчивости, стабилизируе-

мости и консенсуса для линейных мультиагентных систем с дискретным

временем. В основе этих методов лежит идея привлечения понятия сов-

местного/обобщенного спектрального радиуса наборов матриц для ана-

лиза скорости сходимости матричных произведений с сомножителями из

множеств матриц со специальными свойствами.

Ключевые слова: асинхронные мультиагентные системы, консенсус,

устойчивость, стабилизируемость, марковские системы, матричные про-

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

DOI: 10.1134/S0005231019040019

1. Введение

В последние годы растущий интерес исследователей привлекают мульти-

агентные системы (МАС) с асинхронным взаимодействием агентов. Следует

отметить, что в современной научной литературе термин “мультиагентные

системы” часто трактуется достаточно неопределенно и широко. В широ-

ком смысле под мультиагентными понимают любые системы, состоящие из

нескольких сравнительно изолированных частей (агентов), которые функ-

ционируют в определенном смысле независимо от других (иногда добавля-

ют “интеллектуально”), обмениваясь тем не менее с остальными агентами

информацией. В более строгом понимании, принятом в теории управления,

теории передачи информации и других “родственных” областях науки, под

мультиагентными системами понимают системы, в которых каждый агент

имеет свою последовательность моментов времени, в которые он обновляет

¹ Работа поддержана грантом Российского научного фонда 16-11-00063, предоставлен-

ным ИРЭ им. В.А. Котельникова РАН.

информацию о своем состоянии и использует обновленную информацию о со-

стояниях других агентов. Дискретность и асинхронность информационного

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

рационально использовать вычислительные и коммуникационные ресурсы.

В то же время изучение свойств асинхронных систем и синтез управления

для них приводят к более сложным задачам и требуют более совершенно-

го математического аппарата, чем аналогичные исследования, проводимые в

предположениях синхронности. В связи с этим первая часть настоящего об-

зора содержит информацию о современных разработках в области анализа и

синтеза асинхронных протоколов консенсуса, составляющих ядро алгоритмов

децентрализованного управления сетевыми мультиагентными системами.

Несмотря на то, что термин “мультиагентные системы” стал широко ис-

пользоваться в научной литературе в последние 20 лет, близкие понятия

под другими названиями использовались уже давно, как минимум с нача-

ла 50-х гг. XX в. При математическом анализе такого рода систем в зави-

симости от исторических традиций и области науки использовались такие

термины, как асинхронные или рассинхронизованные системы, переключаю-

щиеся системы и т.п. А при исследовании линейных мультиагентных систем

с дискретным временем (анализ устойчивости которых часто выражается в

терминах сходимости матричных произведений) зачастую авторы, опуская

содержательную мотивацию, просто ограничивались изучением свойств бес-

конечных матричных произведений. О многообразии систем, которые могут с

полным правом в современной терминологии трактоваться как мультиагент-

ные, говорят следующие примеры, где асинхронный характер взаимодействия

различных частей систем возникает естественно:

• системы, состоящие из живых организмов;

• стаи мобильных роботов, многопроцессорные системы; мультиконтроллер-

ные устройства;

• распределенные информационно-коммуникационные сети;

• вычислительные GRID-алгоритмы;

• модели Хопфилда - Танка [1-3] нейронной активности в живых организ-

мах;

• производственные системы;

• модели рыночной экономики и т.д.

Консенсус в мультиагентной системе есть общее для всех агентов значение

некоторой рассматриваемой характеристики. Как правило, предполагается,

что это общее значение должно оставаться постоянным с момента t^∗ дости-

жения консенсуса. Иногда допускается, однако, что это значение, оставаясь

общим для всех агентов, может меняться во времени. Последний случай сво-

дится к предыдущему: для этого в качестве новой характеристики достаточно

рассмотреть функцию изменения во времени характеристики, рассмотренной

ранее, при t ≥ t^∗. Под асимптотическим консенсусом понимают стремле-

ние значения исследуемой характеристики каждого агента к общему пределу

при t → ∞.

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

или разностными уравнениями второго порядка, как правило, в вектор со-

стояния агента включают как исследуемую переменную, так и скорость ее

изменения. В этом случае речь идет обычно о консенсусе по скорости. Если

консенсусное значение скорости отлично от нуля, то значения самой перемен-

ной ни к какому пределу не сходятся. Для систем, состоящих из интеграторов

первого порядка, скорость изменения исследуемой переменной в вектор со-

стояния не включают и говорят о консенсусе по самой этой переменной.

К понятию консенсуса близко понятие синхронизации процессов, введен-

ное в работах И.И. Блехмана [4]. В широком смысле синхронизация пони-

мается как согласованное поведение агентов [5]. Полная или частичная ко-

ординатная синхронизация означает асимптотическое сближение состояний

агентов ∥x_i(t) - x_j (t)∥ → 0 или их наблюдаемых выходов ∥y_i(t) - y_j(t)∥ → 0

при t → ∞. Для колеблющихся или вращающихся тел и вообще для коле-

бательных процессов часто важна частотная синхронизация, а при равной

частоте также фазовая синхронизация.

В начале 2000-х гг. было осознано, что протоколы поиска консенсуса со-

ставляют ядро алгоритмов управления сетевыми мультиагентными система-

ми. Это связано с тем, что если агенты способны прийти к консенсусу, то

далее мультиагентная система может решать поставленную перед ней задачу

как единое целое. Тем самым специфика децентрализованного управления в

существенной мере сводится к решению задач достижения консенсуса. По-

этому неудивительно, что значительная часть работ по сетевому управлению

посвящена именно этим задачам.

Одной из сравнительно ранних работ, в которых проблема консенсуса для

асинхронных систем была выделена и сформулирована в простой форме, был

оставшийся почти не замеченным отчет [6]. В 2000-е гг. анализ математиче-

ских проблем консенсуса в мультиагентных системах стал одним из важней-

ших направлений в потоке исследований по устойчивости и стабилизируемо-

сти мультиагентных систем.

Уже первые попытки анализа динамики таких подклассов мультиагент-

ных систем, как асинхронные (рассинхронизованные) системы управления [7]

или системы распределенных вычислений [8], показали, что даже в случае

линейных систем классические методы анализа плохо “справляются” с воз-

никающими задачами. Позже ряд проблем устойчивости и стабилизируемо-

сти линейных мультиагентных систем были сведены к задачам о сходимости

произведений матриц, описывающих поведение агентов в последовательные

промежутки времени, и исследованы с использованием различных вариантов

понятия совместного спектрального радиуса набора матриц (см., например,

библиографию [9]).

Тем не менее и сегодня комплекс математических методов анализа муль-

тиагентных систем едва ли можно считать сформированным ввиду большого

разнообразия систем, объединенных термином “мультиагентные”, а также из-

за сложности анализа их функционирования. В следующих частях настояще-

го обзора основное внимание уделено достижениям и подходам, развитым в

последние годы для анализа устойчивости и стабилизируемости лишь одно-

го класса мультиагентных систем - так называемых линейных переключаю-

щихся систем, которые изменяют свои состояния в определенные дискретные

моменты времени.

2. Базовые понятия

Динамика агента с номером i в непрерывном времени t ∈ R⁺ = [0, +∞) в

составе группы из N агентов моделируется обыкновенным дифференциаль-

ным уравнением вида

(1)

x_i(t) = f(x_i(t),u_i

(t)), i ∈ V = {1, . . . , N},

где x_i(t) ∈ Rnx и u_i(t) ∈ Rnu - соответственно вектор состояния и управ-

ляющий вектор агента i в момент t (их порой удобно представлять вектор-

строками); функция f : Rnx × Rnu → Rnx удовлетворяет условию f(0, 0) = 0.

Относительная автономность и пространственная разделенность агентов

делают реалистичной асинхронную парадигму их взаимодействия, при кото-

рой каждый агент имеет свой набор моментов времени, когда он актуализи-

рует доступную другим агентам информацию о своем состоянии и начинает

использовать новейшую предоставленную агентами-“соседями” информацию

об их состояниях.

Информация, представляемая агентом i, имеет вид x_i(s^ik), где {sik},

k ∈ N = {0,1,2,...} - последовательность моментов времени, удовлетворяю-

щая условиям

(2)

0 = si0 < si1 < ··· < s^ik < ··· ∈ R⁺, lim

s^ik

= +∞, i ∈ V.

k→∞

Последовательность (2) определяет, когда производятся измерения состоя-

ния агента i, используемые как им самим, так и его “соседями”. Очевидно,

⋃

∞

[s^ik, sik+1) = R⁺. Пусть T^ik = sik+1 - s^ik - интервал времени между двумя

k=0

последовательными моментами наблюдения для i ∈ V . Величина T^ik называ-

ется k-м асинхронным периодом агента i. Не учитывая задержек на кван-

тование и кодирование данных, результатом данного измерения будем счи-

тать пакет данных (s^ik, xⁱ(s^ik)), где s^ik - временная метка. Этот пакет данных

предоставляется “соседям” агента i. При этом соседство определяется тополо-

гией информационного взаимодействия, моделируемой взвешенным орграфом

влияний Γ.

3. Асинхронные механизмы организации взаимодействия агентов

Влияние асинхронности используемой информации (“выборок”) на точ-

ность результатов исследуется специалистами по управлению, по крайней

мере, с середины 80-х гг. XX в. [10, 11]. Для теории мультиагентных си-

стем эта проблема имеет первостепенное значение. Так, каждый робот при

совместном движении с другими роботами, планируя свой маршрут, обыч-

но использует информацию о положении и скоростях роботов-соседей. При

этом получение информации разными роботами не обязательно синхронизо-

вано: как отмечено выше, асинхронные механизмы сбора информации более

реалистичны. В то же время асинхронная система может быть неустойчива

при устойчивости соответствующей синхронной системы [12]. В техническом

отношении алгоритмы управления асинхронными системами предъявляют

довольно строгие требования к надежности датчиков и контроллеров, к воз-

можным ошибкам и задержкам передачи и обработки информации. Боль-

шинство результатов в этой области было получено для систем одинарных

и двойных интеграторов, но есть и результаты, относящиеся к системам с

общей линейной [13-20] и нелинейной [21-24] динамикой.

В теории децентрализованного управления мультиагентными системами

рассматриваются четыре основные механизма [25, 26] организации измерений

при асинхронном взаимодействии агентов.

1. Асинхронный равномерный механизм (asynchronous uniform sampling,

AUS). Этот механизм из-за относительной простоты имплементации и ана-

лиза использовался в ранних цифровых реализациях МАС. Здесь интер-

вал между измерениями i-го агента есть известная константа Tⁱ [27], т.е.

T^ik ≡ Tⁱ > 0. Тем самым состояния агента i измеряются в эквидистантные мо-

менты времени s^ik = kTⁱ, k ∈ N, i ∈ V . Для анализа таких систем обычно

используют модели МАС с временными задержками.

2. Асинхронный неравномерный механизм (asynchronous nonuniform

sampling, ANS). Этот механизм, предполагающий апериодические измерения

состояния каждого агента, сложнее, но обеспечивает большую гибкость и

позволяет моделировать более широкий класс МАС [28-32]. Здесь интервал

между измерениями агента i может произвольно меняться, оставаясь в за-

данных границах: T^ik ∈ [T^im, T^iM ] ⊆ R⁺, где T^im и T^iM - известные константы;

T^ik не фиксировано, но ограничено.

3. Асинхронный случайный механизм (asynchronous random sampling,

ARS). При этом механизме интервалы между измерениями T^ik представля-

ют собой случайные величины, распределенные на положительной полуоси.

Естественно полагать их распределения финитными, и тогда ARS-механизм

можно трактовать как неравномерный (ANS) механизм, дополненный веро-

ятностной структурой. Случайный механизм весьма полезен при моделирова-

нии определенных систем, например работы некоторых радаров. Он исполь-

зуется также для снижения перегрузок в компьютерных сетях, для демпфи-

рования периодических колебаний и уменьшения влияния иных помех [33].

Специальным случаем ARS механизмов являются стохастические сплет-

невые (gossip) алгоритмы [34, 35]. В таких алгоритмах в каждый дискретный

момент времени коммуницируют лишь два агента, соединенные ребром в гра-

фе взаимодействий. Это ребро для каждого момента выбирается случайно.

Подобные асинхронные алгоритмы реализуются, например, тогда, когда на

всю мультиагентную систему есть единственный канал связи, в каждый мо-

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

популярный инструмент моделирования социальных сетей. Существует их

разновидность, в которой выбор пары взаимодействующих агентов произво-

дится детерминированно, например ребра графа могут чередоваться перио-

дически. Для сплетневых алгоритмов ставятся и решаются задачи консенсу-

са [35], но из-за ярко выраженной специфики этих алгоритмов в настоящем

обзоре не останавливаемся на них подробно.

4. Асинхронный механизм, определяемый событиями (asynchronous event-

triggered sampling, AES). Этот механизм был предложен еще в [36], где ис-

пользование его обосновывалось принципом приоритетной важности получе-

ния данных, нарушающих очевидные прогнозы. С тех пор схема измерений,

инициированных событиями, получила развитие в работах по импульсным

системам управления (см., например, [37, 38]), по управлению стохастиче-

скими системами [39, 40], в работах П. Табуада [41, 42], а также в ряде работ,

напрямую посвященных управлению сетевыми системами, см. [43, 44] и биб-

лиографию в [26]. В данном контексте следует упомянуть также исследования

по синхронизации в сетях импульсно-связанных осцилляторов [45, 46].

Децентрализованному управлению МАС с использованием асинхронных

измерений, инициированных событиями, в последнее время посвящено очень

много работ - это направление исследований рассматривается как одно из

самых перспективных. Основная мотивация использования механизма AES

сводится к исключению из информационных обменов рутинной, легко пред-

сказуемой информации и к экономии за счет этого вычислительных и комму-

никационных ресурсов - энергии и пропускной способности сети. В литера-

туре встречается несколько альтернативных терминов для механизмов этого

типа: в частности, межуровневая выборка (level-crossing sampling) и выборка

Лебега. Встречаются также комбинированные AES/ANS механизмы, в кото-

рых моменты измерений и взаимодействия определяются как событиями, так

и не зависящими от событий обстоятельствами [47, 48].

В механизме AES интервалы T^ik входят в число параметров управления

и определяются посредством проверки выбранных условий появления “со-

бытий”. Этот механизм, по сути, является интеллектуальным, поскольку он

позволяет задавать моменты наблюдения продуманным выбором условий по-

добно тому, как это делает человек.

4. Две парадигмы асинхронного взаимодействия агентов

Для асинхронных механизмов взаимодействия агентов существуют две ос-

новных парадигмы формирования управляющих воздействий. Управление,

относящееся к агенту i, в соответствии с этими парадигмами может быть

представлено в общем виде как

⎛

⎞

∑

(3)

u_i(s^ik) = u⎝K,x_i(s^ik),

a_ijx_j(s^ik)⎠

j∈N_i

⎛

⎞

∑

(4)

u_i(s^ik) = u⎝K,x_i(s^ik),

a_ijx_j(sj˜

)^⎠

j∈N_i

соответственно, где N_i - множество агентов, влияющих на i, K - матрица

управления,

{

}

k= k(t,j)=argmin

t-s^jp |t≥s^jp,p∈N

Нижний индекс^k =^k(t, j) момента s^j есть номер позднейшего не превосхо-

дящего t момента “опорного” измерения состояния агента j. Чтобы формулы

не становились слишком громоздкими, аргументы t и j можно опускать, что

не приведет к неоднозначности вследствие присутствия параметров t и j в

близком контексте. Так, j всегда является вторым индексом той же величи-

ны sj˜

Выражения (3) и (4) отличаются тем, что состояния x_j “соседей” агента i

берутся в них в разные моменты времени. В (3) используются актуальные на

момент s^ik измерения агентов-соседей, тогда как в (4), корректируя свое со-

стояние, агент i комбинирует свое последнее измерение с последними доступ-

ными измерениями других агентов. При этом может складываться парадок-

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

данными о чужих состояниях, чем о своем собственном.

В частном случае задачи консенсуса без лидера с фиксированной тополо-

гией и механизмом AES парадигма (3) реализуется протоколом

∑

(

)

(5)

u_i(t) = K

a_ij

x_j(s^ik) - x_i(s^ik)

t ∈ [s^ik,sik+1

i∈V,

j∈N_i

а протокол поиска консенсуса, использующий (4), имеет вид

∑ (

)

(6)

u_i(t) = K

a_ij x_j(sj˜) - xi(sik) ,

t ∈ [s^ik,sik+1

i∈V.

j∈N_i

Выражение

∑

(

)

(7)

χ_i(t) =

a_ij

x_j(t) - x_i(t)

j∈N_i

назовем термом относительных измерений агента i в момент t. Пользуясь

этим обозначением, перепишем (5) в виде

u_i(t) = Kχ_i(s^ik), t ∈ [s^ik,sik+1), i ∈ V.

Таким образом, для реализации протокола (5) в реальных МАС каждо-

му агенту i необходимо вычислить терм относительных измерений χ_i(t) в

сопоставленные этому агенту моменты наблюдения t ∈ {s^ik}. Один из спосо-

бов достижения этой цели - за пренебрежимо малый промежуток времени

отправить запросы соседям (агентам j ∈ N_i) на получение результатов их

измерений x^j(t) и, комбинируя полученные ответы с собственными измере-

ниями xⁱ(s^ik), реализовать протокол (5) [15]. Однако данный подход, вообще

говоря, неприменим к ориентированным агентным сетям, где информацион-

ные связи несимметричны: те, кому агент i может отправить запрос, и те,

в чьих измерениях он нуждается, - это разные множества агентов. В этом

отношении парадигма (4) более реалистична.

5. Использование переменных запаздываний при описании систем

с дискретными измерениями

Во второй половине ХХ в. был предложен [49] подход, связанный с пред-

ставлением систем с дискретными (в том числе асинхронными и зависящими

от событий) измерениями как систем с непрерывным временем и перемен-

ными запаздываниями пилообразной формы. Этот подход позволяет адапти-

ровать некоторые результаты анализа систем с запаздываниями для иссле-

дования асинхронных МАС. Результаты такого рода могут быть получены

с использованием обобщенных функционалов Ляпунова - Красовского [50],

так называемого дескрипторного метода исследования систем с запаздывани-

ем [51] и численных методов решения линейных матричных неравенств (LMI).

О применении этого подхода для исследования сетевых систем управления

см. [52-54]. При изучении задач консенсуса он был использован, в частности,

в [23, 55-58]. В случае системы с дискретным временем аналогичный прием

применялся в [12].

Далее в обзоре будут рассмотрены исследования, относящиеся к каждому

из перечисленных механизмов измерения, взаимодействия агентов и коррек-

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

6. Реализации асинхронных безусловных механизмов взаимодействия

в детерминированных системах

Равномерный механизм AUS в случае непрерывных моделей второго по-

рядка с переменной топологией изучался, в частности, в [27]. Консенсусный

протокол в этой работе имел вид

∑

(

)

u_i(t) = α

a_ij(s^ik)

x_j(s^ik) - x_i(s^ik)

j∈N_i(s^ik )

∑

(

)

+β

a_ij(s^ik)

v_j(s^ik) - v_i(s^ik)

t ∈ [s^ik,sik+1),

j∈N_i(s^ik)

где v_i(t) = x_i(t); s^ik = t₀ + klⁱT при k ∈ N, lⁱ ∈ N⁺, T > 0; i ∈ V . Далее задача

достижения консенсуса преобразовывалась в задачу асимптотической устой-

чивости системы с дискретным временем.

В большинстве современных работ понятие асинхронности подразумева-

ет непериодичность моментов измерений состояния агентов. Отметим, что

выборочные измерения вносят в систему существенный элемент дискретно-

сти. Распространенным приемом анализа асинхронных систем с непрерыв-

ным временем является преобразование их в системы с дискретным време-

нем, имеющие ту же асимптотику.

Прежде всего рассмотрим асинхронные системы с дискретным временем

и детерминированными моментами внесения выборочной информации в за-

коны управления.

6.1. Асинхронность в дискретных детерминированных

моделях поиска консенсуса

Одна из ранних асинхронных дискретных моделей консенсуса была пред-

ложена в [59, 60], где рассматривалась система точек, сближающихся на плос-

кости. При этом дуги в орграфе влияний агентов определялись текущей гео-

метрической близостью соответствующих им точек, т.е. зависели от событий.

Тем самым изменение топологии системы подчинялось событийному механиз-

му. Однако моменты маневров от этих событий не зависели и определялись

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

здесь неоднозначность типична: следует определиться, условия наступления

каких моментов оцениваются при определении типа механизма - моментов

измерений или же моментов, когда новейшие измерения корректируют управ-

ляющие воздействия. Более естественным представляется второй подход.

В [59] накладывалось специальное условие, обеспечивающее симметрич-

ность орграфа влияний: “соседями” назначались агенты, расстояние между

которыми не превышает константы r. С учетом ряда нюансов, связанных с

дискретностью, схема формирования управляющих воздействий была близ-

ка к (4). При конкретном алгоритме построения графа влияний (соседства)

уравнения коррекции состояний в этой работе, напротив, имели весьма об-

щий, вообще говоря нелинейный, вид. Воздействие на агента i его соседей

определялось как

( (

)

(

)

j_|N

ui,k+1 = u xj1 sj1

- x_i(sⁱ

), . . . , xj|N

- x_i(s^ik) ,

i ∈ V, k ∈ N,

где j₁, . . . , j|Ni| ∈ Ni, u(·) - непрерывная функция из шара с центром 0 и ра-

диусом r в пространстве R|Ni| в круг с центром 0 и меньшим радиусом r_M

на плоскости. Далее на функцию u(·) с переменным количеством аргументов

накладывались естественные ограничения, но вид ее оставался достаточно

общим. Наконец, новые положения агентов определялись равенством

x_i(sik+1) = x_i(s^ik) + ui,k+1, i ∈ V.

Для анализа данной асинхронной системы строилась синхронная система,

имеющая те же асимптотические свойства. Процедура ее построения была

названа аналитической синхронизацией. Отмечалось сходство предложенно-

го подхода с реализованным в главе 7 классической монографии [8], посвя-

щенной асинхронным итерационным алгоритмам.

В этой книге и других работах Джона Цициклиса и его соавторов [11, 61],

опубликованных в 1980-е гг. (см. также [62], где компактно изложены соот-

ветствующие результаты), был разработан подход к анализу асинхронных си-

стем, который был развит далее и отчасти переоткрыт только через 15-20 лет.

Следует отметить, что доказательства в [8, 11, 61] существенно использу-

ют предположение о существовании положительного числа, ограничивающе-

го снизу ненулевые коэффициенты влияния (имеющие тот же смысл, что и

коэффициенты a_ij в (6)), входящие в рассматриваемую модель. В дальней-

ших исследованиях значительные усилия были предприняты для получения

условий консенсуса при ослаблении ограничений, накладываемых в ранних

работах (включая [62]), в частности допущений, что при корректировке со-

стояний каждый агент обязательно учитывает свое предыдущее состояние

и что остальные ненулевые коэффициенты влияния равномерно ограничены

снизу положительным числом.

Процедура аналитической синхронизации, примененная в [59, 60], исполь-

зовалась и в [63], где задача координации движения агентов на плоскости ре-

шалась посредством последовательного нахождения каждым агентом ариф-

метического среднего его собственного курса (heading) и направлений движе-

ния его соседей. При этом скорости всех агентов предполагались равными.

Под соседями агента i в каждый момент понимались те агенты, информа-

ция о направлении движения которых доступна i в данный момент. Бинар-

ные отношения доступности информации предполагались произвольными, в

частности не обязательно симметричными. Изменение такого отношения со

временем можно рассматривать как событие, вместе с тем моменты пере-

счета курса движения от этих событий не зависели и определялись каждым

агентом произвольно. Поэтому моменты коррекции управления подчинялись

механизму ANS. Моменты обновления информации, полученной от соседей,

можно считать подчиняющимися событийному механизму, однако это ничего

не добавляет к утверждению, что система имеет переменную топологию.

Для получения условий консенсуса применялась техника анализа сходи-

мости произведений стохастических матриц (см. часть II настоящего обзора,

работы [64-69], заложившие начало этого направления, и библиографию [9]),

введенная в контекст сетевого консенсуса в [70], одной из наиболее популяр-

ных ранних статей по децентрализованному сетевому управлению (подробнее

см. [71, раздел 3.3]).

Относительно задач дискретной сетевой коррекции курса стоит отметить

следующее. Пусть агенты совместно движутся и каждый из них время от вре-

мени обновляет направление своего движения, причем моменты обновления

определяет самостоятельно, что и приводит к асинхронности. Если в модели

постулируется, что между моментами обновления направление движения не

меняется, то, вообще говоря, это допущение исключает буквальную физиче-

скую реализуемость системы, требуя бесконечно больших ускорений физи-

ческих агентов, имеющих массу. Таким образом, в отношении механических

систем такая модель неизбежно приблизительна. В контексте распределен-

ных вычислений, рассмотренных в [8, 11, 61], этой проблемы не возникает.

Среди сравнительно недавних работ, выполненных в парадигме параллель-

ных вычислений, отметим [72], где агенты вместе решают задачу кластери-

зации, используя алгоритм k-средних и асинхронный протокол консенсуса с

коммуникациями типа “сплетен” (такие алгоритмы упоминались в разделе 3).

В [12] рассматривалась следующая простая асинхронная дискретная мо-

дель консенсуса со взаимодействием типа ANS:

⎧

∑

⎨

p_ij(k)x_j (k - d(i,j,k)) , i ∈ V (k),

(8)

x_i(k + 1) =

⎩j=1

x_i(k),

i ∈ V (k),

где P (k) = (p_ij(k)) - стохастическая матрица, задающая переменную струк-

туру взаимодействия агентов, d(i, j, k) - функция запаздывания последнего

опорного измерения состояния агента j по отношению к текущему дискрет-

ному моменту k, V (k) - множество агентов, чьи состояния обновляются в

момент k.

Особенность функции запаздывания d(i, j, k) - зависимость от i, позво-

ляющая разным агентам i использовать разные измерения их соседей.

Авторы получают следующую теорему, используя при доказательстве ре-

зультаты [73].

Теорема 1. Пусть асинхронный протокол (8) с постоянной матрицей

P (k) = P = (p_ij ) обладает следующими свойствами:

1. p_ii > 0, i ∈ V.

2. Существует агент i ∈ V такой, что ∀k ∈ N d(i, i, k) = 0 и x_i(0) > 0.

3. Орграф влияний, соответствующий P, имеет остовное исходящее де-

рево.

Тогда состояния агентов асимптотически сходятся к консенсусу.

В [12] показано, что данная асинхронная система может быть представ-

лена синхронной системой с переменной топологией. Действительно, можно

считать, в частности, что каждый агент корректирует свое состояние на всех

тактах, но на некоторых тактах никакие другие агенты на него не влияют.

Легко видеть, что этот прием позволяет представить любую асинхронную

систему как синхронную с переменным графом взаимодействий. Разумеется,

тем самым специфика асинхронности, сосредоточенная в основном в механиз-

мах определения моментов измерений, взаимодействия агентов и переключе-

ний управления, не устраняется, а лишь транслируется в графовый язык, что

для некоторых целей может быть весьма удобно. Так, в данном случае это

позволяет, адаптировав результат [74], получить следующую теорему, анало-

гичную результату [75].

Теорема 2. Пусть Γ(k) - взвешенный орграф влияний в момент k с по-

ложительными весами дуг, выбранными из фиксированного конечного мно-

жества. Тогда состояния агентов, подчиняющиеся протоколу (8), асимп-

тотически сходятся к консенсусу, если и только если существуют T > 0 и

неограниченная последовательность временных полуинтервалов [k₀ = 0,k₁),

[k₁, k₂), . . . таких, что

1) для каждого l ∈ N имеет место 0 < k_l - kl-1 < T и

⋃kl-1

Γ_k содержит остовное исходящее дерево.

k=kl-1

Далее в работе обсуждаются проблемы, связанные с нахождением вели-

чины асимптотического консенсуса при асинхронном протоколе согласования

и с построением алгоритмов управления, приводящих агентов к заданному

значению согласуемого параметра.

Отметим, что условие наличия в орграфе влияний остовного исходящего

дерева, т.е. наличия хотя бы одного агента, прямо или косвенно влияющего

на всех остальных, в случае синхронных непрерывных МАС первого поряд-

ка является не только необходимым, но и достаточным условием реализации

асимптотического консенсуса при всевозможных начальных условиях [76].

Это следует из того факта, что данное условие эквивалентно [77-79] одно-

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

зависимостей. Для дискретных систем ситуация чуть сложнее: дополнитель-

но требуется апериодичность стохастической матрицы системы [80, 81]. Усло-

вие наличия остовного исходящего дерева в том или ином виде присутствует

в большинстве критериев консенсуса - для МАС разных порядков, с разными

типами динамики, синхронных и асинхронных, непрерывных и дискретных.

О взаимосвязях между свойствами МАС, с одной стороны, и свойствами их

орграфов влияний/зависимостей и соответствующих лапласовских матриц -

с другой см. [80, 82, 83].

В [84] для исследования асинхронных протоколов консенсуса предлага-

лось использовать технику нахождения общих неподвижных точек множе-

ства нелинейных обобщенно-сжимающих (paracontracting) операторов и были

даны примеры такого использования.

В [85] изучалась задача консенсуса для дискретизированной асинхронной

системы второго порядка с ориентированной переменной топологией:

(9)

x_i(tk+1) - x_i(t_k) = τ_kv_i(t_k

(10)

v_i(tk+1) - v_i(t_k) = τ_ku_i(t_k

i∈V,

где

∑

(

)

u_i(t_k) = -γv_i(t_k) +

a_ij(t_k)

x_j(t^is) - x_i(t_k)

j∈N_i(t_k )

a ≤ a_ij(t_k) ≤ a,

0<a<a,

{t^ik} - моменты, когда агент i получает информацию о состояниях всех своих

соседей², причем интервалы между моментами обновления информации огра-

ничены: T_u ≤ tik+1 - t^ik

T_u, k ∈ N, i ∈ V . Здесь используется объединенная

⋃

последовательность моментов времени {t_k} =_i∈V {t^ik}, и в (9)-(10) имеет

место t^is ≤ t_k < tk+1 ≤ tis+1.

√

Показано, что при

(n - 1)a ≤γ2 <

T_u)-1 система (9)-(10) сходится к

асимптотическому консенсусу, если бесконечная последовательность оргра-

фов Γ(t₁), Γ(t₂), . . . может быть разбита на равномерно ограниченные по

длине интервалы, для каждого из которых объединение орграфов влияний

имеет остовное исходящее дерево.

Авторы отмечают, что этот результат практически совпадает с достаточ-

ным условием консенсуса, полученным в [86] для синхронных систем.

В [87] достаточное условие консенсуса получено для дискретных систем,

для которых в отличие от абсолютного большинства работ по данной теме

предполагается, что состояние каждого агента i всегда остается в индивиду-

альном замкнутом выпуклом множестве X_i. При этом протокол консенсуса

имеет вид

⎡

⎤

∑

⎣

(11)

x_i(tⁱ

k+1

)=PXi

a_ij(t^ik)x_j(t^ik)⎦ ,

j∈N_i(t^ik )

где PXi - оператор ортогональной проекции на X_i. Задача поиска такого огра-

ниченного консенсуса возникает в теории коалиционных игр с трансфера-

бельной полезностью, где распределенный протокол торгов имеет вид (11).

² Отметим отличие этих моментов от моментов {s^ik}, входящих в ряд рассмотренных

выше моделей.

Матрицы A(t^ik) = [a_ij (t^ik)] полагаются стохастическими. Достаточное усло-

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

и ненулевых недиагональных коэффициентов влияния a_ij(t^ik) и представимо-

сти всего упорядоченного по времени набора орграфов влияния в виде после-

довательности равномерно ограниченных интервалов, объединения орграфов

по которым сильно связны.

Следует отметить, что протокол (11) в синхронном варианте впервые был

рассмотрен в [88] как применение и развитие метода последовательных про-

екций Губина - Поляка - Райка [89] для нахождения общей точки нескольких

выпуклых множеств. Цель алгоритма - нахождение точки, лежащей в пере-

сечении множеств (без необходимости обмениваться информацией о самих

множествах). В [88] показано, что алгоритм тесно связан с выпуклой распре-

деленной оптимизацией.

В последние годы расширение класса исследуемых асинхронных систем

привело к рассмотрению гетерогенных систем, т.е. МАС, состоящих из аген-

тов разных типов. В [90] рассматривалась задача вхождения состояний аген-

тов в ограниченную область (containment control) для асинхронных систем

с дискретным временем, переменными временными задержками, постоян-

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

агентами-последователями первого и второго порядков.

В работе получен критерий попадания состояний агентов в выпуклую обо-

лочку состояний лидеров и удерживания в ней. Его доказательство опирается

на свойства произведений регулярных³ стохастических матриц (см. часть II

настоящего обзора). Необходимым условием здесь является наличие в оргра-

фе влияний исходящего леса с корнями в вершинах, соответствующих лиде-

рам.

В [91] исследован еще один класс гетерогенных дискретных систем, со-

стоящих из агентов первого и второго порядка. Здесь топология меняется, и

для разных типов агентов предложены два асинхронных консенсусных про-

токола, определяющих локальное управление. Получено достаточное условие

асимптотического консенсуса, сводящееся к набору неравенств и знакомо-

му по предыдущим работам требованию наличия исходящего дерева в объ-

единениях орграфов влияния по равномерно ограниченным отрезкам после-

довательности таких орграфов, реализующихся во всевозможные моменты

времени.

6.2. Консенсус в непрерывных моделях с неравномерным

асинхронным механизмом

Неравномерный механизм ANS рассматривался в [92], где изучалась про-

блема консенсуса с интеграторами первого порядка и меняющейся ориенти-

рованной топологией. Интервалы между выборками предполагались произ-

вольными, но принадлежащими заданному интервалу. Коэффициенты влия-

³ Стохастическая матрица регулярна, если она не имеет собственных значений с моду-

лем 1, кроме однократного собственного значения 1. Синонимичное понятие в англоязыч-

ной терминологии - SIA (Stochastic, Indecomposable, Aperiodic) matrix.

ния агентов полагались заключенными в интервале с положительными гра-

ницами.

Система преобразовывалась в систему с дискретным временем, для кото-

рой далее анализировалась сходимость состояний. При получении результа-

тов использовалась следующая лемма.

Лемма 1. Пусть A ∈ Rnx×nx - строчно стохастическая матрица. Тогда

A регулярна, если в орграфе влияний есть исходящее дерево, корень которого

имеет петлю.

Далее использовалась теорема Вольфовица [69], согласно которой для лю-

бого конечного множества A₁, . . . , A_m ∈ R^n×n регулярных матриц такого, что

любая конечная последовательность его элементов дает в произведении ре-

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

элементов сходятся к матрицам, строки которых равны.

Показано, что при сделанных предположениях и наличии остовного ис-

ходящего дерева в объединении орграфов влияний для всех временных ин-

тервалов некоторой ширины T ≥ 0 реализуется асимптотический консенсус.

Если же топология не меняется, то наличие такого дерева, кроме того, и

необходимо. Некоторые другие работы такого рода обсуждались в [71].

Этот подход был развит в [93], где рассматривалась система первого по-

рядка с переменной ориентированной топологией и временными задержками

и вводились дополнительные переменные состояния, которые в отличие от

основных переменных претерпевали разрывы.

В [94] был разработан синхронный протокол консенсуса для случая двой-

ных интеграторов, который применим и к механизму ANS с произвольными

интервалами между выборками и фиксированной неориентированной топо-

логией информационных связей.

В [29] рассмотрен механизм ANS второго порядка с фиксированной ориен-

тированной топологией и независимыми моментами выборочных измерений.

Асимптотика анализировалась сведением системы к системе с дискретным

временем и задержками. Для получения достаточного условия асинхронного

консенсуса использовался прямой метод Ляпунова. Среди условий консенсу-

са - наличие остовного исходящего дерева в орграфе влияний, ограничен-

ность задержек наблюдения, отделенность от 0 и ограниченность сверху ин-

тервалов между наблюдениями и, кроме того, набор матричных неравенств,

связывающих параметры модели.

Эта линия исследований была продолжена в [95], где изучалась задача до-

стижения консенсуса с механизмом ANS для интеграторов второго порядка

с меняющейся топологией связей. Интервалы между выборками и задержки

предполагались ограниченными, но верхняя граница при этом не ограничи-

валась. Последнее приводит к несколько более слабым условиям асимпто-

тического консенсуса, чем те, что были получены в [85] для систем с дис-

кретным временем. В предлагаемом протоколе консенсуса каждому агенту

доступна непрерывная информация о его состоянии и выборочная информа-

ция о состояниях его соседей. Используя алгебраическую теорию графов, ав-

торы доказывают, что асимптотический консенсус реализуется при перемен-

ных задержках связи, если объединение орграфов влияний агентов содержит

остовное дерево на любом временном интервале некоторой длины.

Асинхронный консенсус в импульсных системах второго порядка с ори-

ентированной топологией исследовался в [96]. Рассматривался протокол им-

пульсного управления, отличающийся от предложенного в [27, 29]:

⎡

⎤

∑

(

(12)

u_i(t) =

⎣-c1v_i(t) - c₂

a_ij

x_i(t - τ_ij) - x_j(t - τ_ij))⎦δ(t-si),

s=1

j∈N_i

где c₁, c₂ > 0, δ(·) - дельта-функция Дирака. Протокол (12) обобщает алго-

ритм, предложенный в [97], введением задержек τ_ij и моментов измерения s^ik,

вообще говоря, различных для разных агентов. Интервалы между измерения-

ми полагаются ограниченными сверху и снизу:

(13)

0<T_m ≤sik+1 -s^ik ≤T_M

, k ∈ N,

где T_m и T_M - соответственно нижняя и верхняя границы.

Результатом импульсного управления вида (12) является следующее изме-

нение скорости:

(

)

lim

v_i(s^ik + σ) - v_i(s^ik - σ)

σ→0⁺

∑

(

)

= -c₁v_i(s^ik) - c₂

a_ij

x_i(s^ik - τ_ij) - x_j(s^ik - τ_ij)

i ∈ V, s ∈ N.

j∈N_i

Главный результат работы - теорема, согласно которой при выполнении

определенного матричного неравенства система x_i(t) = u_i(t) (i ∈ V ) с управ-

лением u_i(t), задаваемым (12)-(13), и ориентированной топологией, содержа-

щей остовное исходящее дерево, приходит к асимптотическому консенсусу.

В [23] асинхронность трактуется иначе, чем в [27, 28, 85, 92], и в некотором

отношении более радикально, а именно, каждому агенту в его выборочные

моменты (отличные от моментов других агентов) доступна лишь его соб-

ственная актуальная информация. Тем самым результаты, полученные в пе-

речисленных работах, в данном случае неприменимы. Другое отличие в том,

что вместо однородной простой динамики первого или второго порядка рас-

сматривается случай гетерогенной нелинейной динамики высокого порядка.

А именно, динамика N агентов определяется уравнением

x_i(t) = B_ix_i(t) + C_if_i(x_i,t) + u_i(t), i ∈ V,

где x_i(t), u_i(t) ∈ Rnx , B_i, Ci — квадратные матрицы, функции fi : Rnx ×

×[0, +∞) → Rnx, вообще говоря, нелинейны и есть лидер с динамикой

(

)

x₀(t) = Ax₀(t) + Bf₀

x₀(t),t

Асинхронный протокол консенсуса имеет вид

⎡

⎤

∑ (

)

(

)

u_i(t) = -K_i ⎣ a_ij x_i(s^ik) - x_j(s^jk

)

+ a_i x_i(s^ik) - x₀(s0k

)

⎦_,

(t)

0(t)

j=1

s^ik ≤ t < sik+1, i ∈ V.

С использованием подхода Ляпунова - Красовского показано, что ограни-

ченное консенсусное следование за лидером реализуется с экспоненциальной

сходимостью, если матрицы и функции, входящие в модель, удовлетворяют

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

агентов и его траектория ограничена. Кроме того, указана область сходимо-

сти в пространстве состояний и предложен вид матриц K_i, обеспечивающих

указанное следование.

7. Исследования асинхронных протоколов, определяемых событиями

7.1. Условия реализации событий

Механизмы взаимодействия, определяемые событиями, в том числе асин-

хронные механизмы AES, имеют “расписание” [26], определяемое условиями

вида

{

}

(14)

sik+1 = inf

t > s^ik | F_i(e_i) ≥ T_i(X_i,σ_i)

где {s^ik}k∈N - последовательность моментов времени, удовлетворяющая (2),

ei - “дефект” (ошибка) выборки - расхождение между данными последней

выборки и данными в текущий момент t; F_i(e_i) - применяемая трансформа-

ция ошибки e_i; T_i(X_i, σ_i) - пороговая функция, задающая условие реализа-

ции события, выполнение которого влечет немедленное проведение агентом i

очередного измерения; X_i может в разных моделях зависеть как от измере-

ний состояния в текущий момент, так и от данных в предыдущий опорный

момент s^ik; σ_i - параметр пороговой функции. Таким образом, согласно (14)

агент i проводит очередное опорное измерение тогда и только тогда, когда

выполняется условие реализации события F_i(e_i) ≥ T_i(X_i, σ_i). Тщательным

подбором этого условия интервалы между взаимодействиями агентов можно

настроить таким образом, чтобы экономились ограниченные вычислительные

и коммуникационные ресурсы. “Ошибка выборки” и порог являются ключе-

выми параметрами механизмов взаимодействия, определяемых событиями.

Предложен целый ряд подходов к заданию “дефекта выборки” e_i и порого-

вой функции T_i(·) в механизмах взаимодействия, определяемых событиями.

Так, X_i = X_i(t) может представлять состояние агента, его оценку или кос-

венный результат измерения; порог T_i(·) может быть постоянным, а также

зависеть от времени и/или состояния. Следует также отметить, что в слу-

чае непрерывных МАС некоторые протоколы управления по событиям мо-

гут приводить к ситуациям апорий Зенона, что нужно исключить еще на

стадии разработки выборочного механизма. Под поведением Зенона в тео-

рии мультиагентных систем понимают построение бесконечной ограничен-

ной последовательности моментов переключения. Такие последовательности

дефектны в силу своей физической нереализуемости. Для их исключения ча-

сто требуют выполнения более сильного условия, а именно, чтобы разница

по времени между двумя последовательными выборками не стремилась к ну-

лю (sik+1 - s^ik → 0). В действительности имеет смысл использовать еще более

сильное требование: чтобы временные интервалы между последовательными

выборками имели строго положительную нижнюю границу.

Далее рассмотрим некоторые механизмы определения моментов выборки

для моделей консенсуса без лидера, представленные в недавних работах и

систематизированные в [26].

Коррекция по событиям с постоянным порогом. Пусть условие реализа-

ции “события” в (14) имеет вид

(15)

∥e_i(t)∥ ≥ δ_i,

где порог δ_i > 0, вообще говоря, зависит от агента и может варьироваться.

Основанный на этом механизме выборки асинхронный протокол консенсуса

∑

(

)

u_i(k^is) = Kχ_i(k^is) = K

a_ij

y_j(kj˜s) - y_i(k^is)

j∈N_i

где {k^is}i∈Vs∈N - последовательность моментов опорных наблюдений, y_i(k) - ре-

зультат измерения функции y от состояния агента i, для стохастических МАС

с дискретным временем исследовался в [98, 99]. Более конкретно: в текущий

дискретный момент k вычисляется дефект выборки

e_i(k) = χ_i(k^is) - χ_i(k),

и делать ли переключение на основе новых наблюдений определяется про-

веркой неравенства ∥e_i(k)∥ > δ_i (в [98]) либо eTi(k) Ω-1i(k) e_i(k) > 1 (в [99],

где Ω_i(k) > 0 - матрица весов, сопоставленная агенту i). Идея событийного

управления состоит в использовании последнего опорного измерения до тех

пор, пока расхождение текущего состояния с ним не превысит порога. Есте-

ственно предположить, что такой алгоритм работоспособен при робастности

системы управления к погрешностям в измерении состояний. В связи с этим

в [98] задача о поиске консенсуса c событийным механизмом взаимодействия

была заменена задачей устойчивости от входа к состоянию (input-to-state

stability, ISS) [100] в вероятностной постановке и были получены - в фор-

ме матричных неравенств - достаточные условия достижения консенсуса по

вероятности.

В [99] получено - в виде системы рекурсивных линейных матричных нера-

венств - достаточное условие среднеквадратичного консенсуса с выборкой по

событиям в случае сенсорных насыщений. Получен явный вид соответствую-

щих регуляторов. Рассмотрены также две оптимизационные задачи, решение

которых направлено на повышение скорости приближения к консенсусу и

снижение частоты переключений. Насыщение сенсоров - явление, вызван-

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

никационных каналов по мощности, точности и надежности. Учет сенсорных

насыщений приближает теоретическую постановку задачи к реальной.

В [101] исследовалась задача консенсусного управления с выборкой по со-

бытиям для подверженной кибератакам стохастической МАС с неориентиро-

ванной топологией и потерями в измерениях. Условие реализации события

имеет здесь вид, аналогичный (15) при

e_i(k) = x_i(k^is) - x_i(k),

где x_i(k) - оценка состояния агента i. В терминах собственных значений

и собственных векторов лапласовской матрицы графа коммуникаций аген-

тов сформулировано и доказано достаточное условие обеспечения средне-

квадратичного ограниченного консенсуса и указан вид матриц, задающих

регулятор.

Коррекция по событиям с порогом, зависящим от времени. Одним из

факторов, побуждающих обновить данные, на основании которых проводит-

ся коррекция, является существенное время, прошедшее с предыдущего опор-

ного наблюдения. Для реализации этой идеи через механизм AES в правую

часть условия появления события включают слагаемое, убывающее по време-

ни, т.е. со временем делающее условие менее жестким. Так, условие появления

события, используемое в (14), может иметь вид

(16)

∥e_i(t)∥ ≥ c₀ + c₁e-μi(t)t,

где

e_i(t) = x_i(s^ik) - x_i(t),

c₀ ≥ 0, c₁ ≥ 0, c₀ + c₁ > 0 и μ_i(t) > 0. В [102] этот механизм взаимодействия с

постоянным μ_i(t) использовался для обеспечения попадания состояний аген-

тов в шар с центром в среднем значении всех состояний - для интеграторов

первого и второго порядков с задержками связи и без них.

Частный случай условия (16) с c₀ = 0 использовался в [18] при решении

задачи адаптивного консенсуса в МАС с общей линейной динамикой и по-

стоянной неориентированной топологией. В этой работе построен адаптив-

ный протокол управления и доказаны асимптотическая сходимость к сред-

нему консенсусу и существование положительной нижней границы интерва-

лов между событиями. Установлена зависимость динамики системы от спек-

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

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

консенсусу. Планируется распространить данный подход на случай наличия

возмущений и переменной топологии.

В [17] условие реализации события (16) применялось в форме условия с

однородным по агентам “дисконтированием” ∥e_i(t)∥ ≥ c₁e^-μt, причем в выра-

жении e_i(t) использовалась матричная экспонента:

(17)

e_i(t) = eA(t-sk)x_i(s^ik) - x_i

(t),

где A - матрица общей линейной динамики агента x_i(t) = Ax_i(t) + Bu_i(t).

Консенсус группы агентов с ориентированной топологией обеспечивался на-

стройкой (за счет выбора матрицы обратной связи K и коэффициента уси-

ления α > 0) протокола

∑ (

)

u_i(t) = αK

a_ij eA(t-sk)x_i(s^ik) - eA(t-sj)xi(sj˜

)

j∈N_i

основанного на взаимодействии типа AES. Отметим, что проверка выпол-

нения условия появления события с ошибкой (17) требует от агента лишь

непрерывного отслеживания его собственного состояния; в непрерывном об-

мене информацией с агентами-соседями нет необходимости. В этой работе

результаты, полученные ранее для систем одинарных и двойных интегра-

торов, перенесены на случай систем с произвольной линейной динамикой.

Ключевыми условиями достижения асимптотического консенсуса независи-

мо от начального состояния являются наличие остовного исходящего дерева

в орграфе влияний, стабилизируемость пары матриц (A, B) и гурвицевость

матриц A + αλ_iBK, где λ_i - ненулевые собственные значения лапласовской

матрицы орграфа зависимостей. Показано, что поведение Зенона при пред-

ложенном протоколе не реализуется.

Коррекция по событиям с порогом, непрерывно зависящим от состояния.

Пусть условие реализации события в (14) имеет вид

(18)

∥e_i(t)∥ ≥ σ_i∥X_i

(t)∥,

где σ_i∥X_i(t)∥ - порог, непрерывно зависящий от состояния. Так, в [103] про-

токол консенсуса на основе AES

∑ (

)

(

)

u_i(t) =

a_ij x_j

sj˜

- x_i(s^ik)

j∈N_i

рассматривался в комбинации с X_i(t), определенным как терм относительных

измерений агента i, X_i(t) = χ_i(t), и ошибкой e_i(t), равной отличию текущего

состояния x_i(t) от данных последней опорной выборки x_i(s^ik). Показано, что

в синхронном случае для фиксированного связного неориентированного гра-

фа взаимодействий G при σ_i = σ/∥L∥ (где L - лапласовская матрица G) и

0 < σ < 1 асимптотический консенсус реализуется и интервалы между “собы-

тиями” ограничены снизу. Асимптотический консенсус равен при этом сред-

нему арифметическому начальных состояний агентов. Аналоги этих резуль-

татов получены и для асинхронных систем.

В условии реализации события, использованном в [15], X_i(t) имел тот же

вид, что в [103], но дефект выборки задавался как e_i(t) = χ_i(s^ik) - χ_i(t). Рас-

сматривался протокол консенсуса на основе AES

u_i(t) = Kχ_i(s^ik)

для МАС с общей линейной динамикой. В случае стабилизируемости ли-

нейной динамики системы и связности фиксированного неориентированного

графа влияний указан вид матрицы управления K, обеспечивающей асимп-

тотический консенсус. Показано, что при этом последовательность моментов

переключения не обрывается и не реализуется поведение Зенона.

Механизмы взаимодействия, аналогичные [15], изучались также в [104].

Для случая постоянной ориентированной топологии получены достаточные

условия консенсуса, включающие сильную связность орграфа влияний либо

наличие в нем остовного исходящего дерева. Как и в других работах этого

направления, показано, что предлагаемые алгоритмы выбора моментов пере-

ключения позволяют исключить поведение Зенона.

В [105] X_i(t) определялось как среднее отличие состояния агента i от

состояний его соседей X_i(t) = q_i(t) = 1/(n_i + 1)χ_i(t), а дефект выборки зада-

вался формулой e_i(t) = q_i(s^ik)-q_i(t), где n_i = |N_i| - число соседей агента i. На

основе этого механизма взаимодействия, определяемого событиями, исследо-

вался протокол u_i(t) = α_iq_i(s^ik) решения задачи встречи (rendezvous) агентов

первого порядка в евклидовом пространстве. Показано, что при постоянном

связном неориентированном графе влияний встреча асимптотически реали-

зуется при выполнении дополнительного условия, что ни один агент исходно

не находится в центре тяжести положений своих соседей.

Коррекция на основе порога, зависящего от выборочного состояния. В со-

ответствии с этим механизмом условие реализации события (14) задается как

(19)

∥e_i(t)∥ ≥ σ_i∥X_i(s^ik

)∥,

где σ_i∥X_i(s^ik)∥ - выборочный порог, зависящий от состояния, а X_i(s^ik) обо-

значает либо дискретизированные данные, либо терм их относительных из-

мерений. В [106, 107] дефект выборки определялся как e_i(t) = x_i(s^ik) - x_i(t),

а в качестве X_i(s^ik) был использован терм относительных измерений агента i:

∑

X_i(s^ik) =j∈Ni a_ij(x_j(sj˜

) - x_i(s^ik)). Исходя из несколько разных условий

реализации событий, зависящих от выборки, в этих работах решалась задача

консенсуса для МАС первого порядка с использованием протокола на осно-

ве AES u_i(t) = X_i(s^ik). В [106] рассматривался постоянный неориентирован-

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

являлась его связность. Аналогичный приближенный результат был дока-

зан и для квантифицированных данных, т.е. данных, измеренных с конечной

точностью. В [107] граф влияний также неориентированный, но переменный

и условием асимптотического консенсуса является его “объединенная связ-

ность” (ограничение, встречавшееся в целом ряде упомянутых выше работ)

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

предлагаемое условие реализации событий исключает поведение Зенона.

В [16] условие реализации события (19) использовалось с термом относи-_∑

тельных измерений вида X_i(s^ik) = χ_i(s^ik) =i∈Ni a_ij (x_j (s^ik) - x_i(s^ik)) и с де-

фектом выборки e_i(t) = χ_i(s^ik) - χ_i(t). На этой основе посредством протоко-

ла управления с динамической обратной связью по выходу решалась задача

консенсуса для гетерогенных линейных МАС с фиксированной неориенти-

рованной топологией. К стандартным условиям связности графа влияний и

стабилизируемости пар матриц (A_i, B_i), задающих гетерогенную линейную

динамику x_i = A_ix_i +B_iu_i, добавляется условие детектируемости пар матриц

(A_i, C_i), где C_i задает выход y_i = C_ix_i, и условие разрешимости указанных в

статье матричных уравнений. Как и в большинстве работ этого направления,

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

ведение Зенона.

Коррекция с порогом, непрерывно зависящим от состояния, и положи-

тельным сдвигом. В соответствии с (14) переключения происходят тогда, ко-

гда выполняется условие реализации события F_i(e_i) ≥ T_i(χ_i, σ_i). Имеет прак-

тическое значение вопрос: “Как усилить это условие, чтобы коррекция состоя-

ний происходила как можно реже?” Один из вариантов ответа на него - доба-

вить положительную константу или функцию времени в правую часть (18),

что приводит к следующим двум вариантам условия:

(20)

∥e_i(t)∥ ≥ σ_i∥X_i(t)∥ + δ_i

(21)

∥e_i(t)∥ ≥ σ_i∥X_i(t)∥ + c₁e^-μt.

Эти условия сильнее, чем (18) и, следовательно, позволяют уменьшить ко-

личество коррекций. Задача консенсуса с условием реализации события (20)

для линейных МАС с ориентированными взаимодействиями исследовалась

в [13]. Установлено, что достаточное условие реализуемости асимптотическо-

го консенсуса с любой заданной точностью сводится к стабилизируемости па-

ры матриц (A, B), задающих линейную динамику x_i = Ax_i +Bu_i, и наличию в

орграфе влияний остовного исходящего дерева; указан вид соответствующего

регулятора. Показано, что поведение Зенона исключено.

В [108] применялось условие переключения (21) для поиска консенсуса

в общих линейных МАС, характеризующихся насыщениями по входам, при

начальных состояниях из заданной ограниченной области пространства. По-

казано, что при неориентированной связной топологии, стабилизируемости

пары матриц (A, B), задающей линейную динамику агентов, липшицевости

матрицы A и μ, удовлетворяющем предложенному ограничению, указанный

консенсус реализуется, причем поведение Зенона исключено.

Коррекция с порогом, зависящим от выборочного состояния, и положи-

тельным смещением. Аналогично (20) и (21) можно добавить положительное

смещение в правую часть условия реализации событий (19), использующего

данные последней опорной выборки. В частности, рассматривались следую-

щие два условия:

(22)

∥e_i(t)∥ ≥ σ_i∥X_i(s^ik

)∥ + c(t),

где c(t) - убывающая функция с нижней границей c₀ > 0, и

(23)

∥e_i(t)∥ ≥ σ_i∥X_i(s^ik)∥ + δ_iμ^t,

где σ_i, δ_i > 0 и μ ∈ (0, 1). В [109] задача консенсуса для линейных МАС реша-

лась с помощью условия реализации события (22), куда вводилась временная

задержка τ > 0:



(

)

∑

(

)



∥e_i(t)∥ ≥ σ_i

a_ij

x_j s^j

-τ

-x_i

s^ik - τ

 + c(t),

j∈N_i

при e_i(t) = x_i(s^ik - τ) - x_i(t - τ). Показано, что при стабилизируемости пары

матриц, задающих линейную динамику, наличии в орграфе влияний остов-

ного дерева, исходящего из выделенной вершины, и параметрах, удовлетво-

ряющих введенным ограничениям, в рассмотренной модели с задержкой ре-

ализуется (без поведения Зенона) асимптотический консенсус.

Задача консенсуса c условием реализации события (23), где X_i(s^ik) = χ_i(s^ik)

и e_i(t) = χ_i(s^ik) - χ_i(t), для МАС второго порядка с дискретным временем

решалась в [110]. Показано, что консенсус реализуется, если орграф влия-

ний содержит остовное исходящее дерево и квант времени не превосходит

указанной в работе границы.

В [111] рассматривалась модель, в которой каждый агент узнает о внеш-

нем для него событии лишь при очередном своем контакте с информацион-

ным “облаком”. После этого он автономно определяет время следующего кон-

такта. Таким образом, агенты взаимодействуют не напрямую, а через своего

рода доску объявлений. Строится алгоритм координации агентов, направлен-

ный на сведение к минимуму числа контактов и при этом гарантирующий

достижение системой множества желаемых состояний. В качестве времени

следующего контакта каждый агент выбирает самый ранний момент, когда

его прогнозируемый терм относительных измерений, характеризующий рас-

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

Вопрос о робастности алгоритмов управления асинхронными мультиагент-

ными сетями исследовался в [25]. Авторы анализировали одновременную

устойчивость локально взаимодействующих линейных подсистем с симмет-

ричной топологией связей, механизмами взаимодействия ANS и AES, ограни-

ченными временными задержками и ошибками измерения. С использованием

метода Ляпунова было получено условие устойчивости таких систем с де-

централизованным управлением. Для организации выборки данных исполь-

зовались логарифмические квантователи и интервалы между измерениями,

исключающие поведение Зенона при задействовании AES-механизмов. Полу-

ченные результаты позволяют оценить максимально допустимые задержки и

промежутки между выборками в случае асинхронных протоколов консенсуса

с относительными и абсолютными измерениями.

7.2. Достоинства и недостатки основных условий реализации событий

Предложенные в литературе условия реализации событий, основанные на

различных определениях дефекта выборки и его пороговой величины и пред-

назначенные для решения задач консенсуса без лидера, приведены выше в

формулах (15)-(23). Каждый из этих механизмов имеет свои достоинства и

недостатки. Обсуждению их в последние годы уделяется большое внимание,

поскольку выбрать конкретный механизм необходимо в любой практической

работе.

При сравнении этих механизмов будем в основном следовать [26]. Сначала

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

выборки e_i(t) имеет две основные формы.

Форма 1. e_i(t) = x_i(s^ik) - x_i(t): расхождение между последним опорным

измерением состояния и измерением его в текущий момент t.

Форма 2. e_i(t) = χ_i(s^ik) - χ_i(t) : расхождение между значениями терма от-

носительных измерений в последний опорный момент и в текущий момент.

- В отличие от формы 2 форма 1 не требует постоянной связи между сосед-

ними агентами, которая необходима для отслеживания в реальном времени

терма относительных измерений χ_i(t), входящего в форму 2.

- Коррекция с дефектом выборки, определяемым формой 1, по существу,

эффективна лишь для решения задачи консенсуса с устойчивым равновеси-

ем в точке консенсуса. Так, рассмотрим группу агентов, следующих за ли-

дером, чья траектория осциллирует, и пусть траектории всех агентов асимп-

тотически приближаются к траектории лидера. Тогда рассогласование будет

приближаться к нулю, в то время как дефект выборки e_i(t) = x_i(s^ik) - x_i(t)

может далеко отклоняться от нуля. В этом случае коррекция по рассмотрен-

ному протоколу будет выполняться почти непрерывно, что может приводить

к поведению Зенона. Таким образом, механизм коррекции с дефектом вы-

борки, определяемым формой 1, вообще говоря, не исключает поведения Зе-

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

Напротив, дефект выборки e_i(t), определяемый формой 2, подходит как для

моделей консенсуса с устойчивым консенсусным равновесием, так и для мо-

делей с осциллирующей консенсусной траекторией, поскольку эта величина

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

сближаются. Однако если принимается механизм взаимодействия с дефек-

том выборки формы 2, то необходимо обеспечить всем агентам возможность

вычислять термы относительных измерений как в моменты выборки, так и в

текущие моменты.

Теперь сравним функции, задающие пороговые значения в условиях реа-

лизации событий.

- Условия (15) и (16) могут снизить по сравнению с (18)-(23) интенсив-

ность взаимодействий между агентом i и его соседями, поскольку порог в

них не зависит от текущего состояния соседей i, времени и выборочных из-

мерений. Однако в отношении (15) и (16) (особенно при c₀ > 0) следует иметь

ввиду, что 1) из-за использования положительного порога МАС может дости-

гать лишь приблизительного консенсуса, а не точного или асимптотического

консенсуса; 2) коррекция в результате взаимодействия не учитывает измене-

ний, происходящих в системе с обратной связью, поскольку порог не зависит

от измерений состояний агентов.

- Порог в (18) (а также в (20) и (21)) предполагает непрерывную

связь между агентами, поскольку каждый агент использует текущее состоя-

ние X_i(t) для определения своих моментов событий. В отличие от этого усло-

вие реализации события (19) (как и (22), (23)) допускает выборочный зави-

сящий от состояния порог X_i(s^ik), что предполагает меньшую интенсивность

взаимодействий между агентами-соседями.

- По сравнению с (18) и (19) условия реализации событий (20) и (21)

(и, соответственно, (22) и (23)) содержат пороги, предполагающие положи-

тельные смещения, что имеет два преимущества: 1) это может обеспечить

большую экономию затрат ресурсов на адаптивную коррекцию состояний

агентов; 2) при этом исключено поведение Зенона [13, 109]. Однако, как и

в случае (15), (16), эти преимущества реализуются за счет снижения эффек-

тивности достижения консенсуса. Так, посредством (20) может быть достиг-

нут лишь приблизительный консенсус вместо точного или асимптотического

консенсуса. Результаты [13] демонстрируют также, что общая ошибка дости-

жения консенсуса зависит от выбора смещения. А именно, более высокое δ_i

приводит к меньшему объему корректирующих действий, но к более высоко-

му значению ошибки. Таким образом, при разработке протоколов консенсуса

с взаимодействием, зависящим от событий, может быть поставлена и решена

задача поиска оптимального (в смысле выбранного критерия) компромисса

между частотой корректирующих воздействий и эффективностью достиже-

ния консенсуса.

7.3. Особенности рассмотренных моделей

Выше обсуждались типичные механизмы взаимодействия агентов при ре-

шении задач консенсуса без лидера. Эти механизмы имеют две общие особен-

ности.

1. Для каждого агента моменты опорных измерений совпадают с момен-

тами передачи данных.

2. Каждый агент должен постоянно получать сведения о своем состоя-

нии x_i(t) (а в ряде протоколов и о состояниях своих соседей x_j(t) для всех

j ∈ N_i), чтобы определять моменты переключения режимов коррекции. Дей-

ствительно, дефект выборки, входящий в условия (форм 1 и 2) реализации со-

бытий зависит от состояния x_i(t) либо терма относительных измерений χ_i(t)

как функций непрерывного времени t.

Отметим, что это требование может быть трудновыполнимым, поскольку

постоянное отслеживание состояний агентов предполагает задействование ап-

паратных средств, требующих затрат, существенно превышающих расходы на

реализацию механических и других функций МАС. Альтернатива, позволяю-

щая отказаться от этих затрат, состоит в том, чтобы определять дефект вы-

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

кооперативного управления МАС на основе дискретизированных данных.

При этом измерения и их передача, вообще говоря, разделены и проис-

ходят в разные моменты времени. Измерения могут выполняться синхронно

или асинхронно, периодически, апериодически или в случайные моменты,

тогда как передача их обуславливается реализацией событий определенного

вида. Такие механизмы передачи информации использовались для решения

задач управления сетевыми системами, в частности, в [54, 112, 113].

Работа [112] посвящена построению H_∞-регулятора для сетевых МАС. Ха-

рактер управления кусочно-постоянный с задержками. Исследуется влияние

задержек и строятся (в виде линейных матричных неравенств и в терминах

H_∞-нормы) критерии устойчивости и совместного выбора характеристик об-

ратной связи и переключений.

В [113] моделировалась возможность потери данных. Предложена схема

переключения на основании информации о собственном состоянии агента с

учетом потерь данных и задержек связи. Асимптотическая устойчивость оце-

нивалась по H_∞-норме. В [114] для нелинейных сетевых систем H_∞-управле-

ния с дискретным временем потеря данных исследовалась посредством про-

цесса Бернулли и полиномиальной нечеткой модели.

При подобных выборочных схемах следующий момент выборки определя-

ется не столько проверкой в реальном времени условия реализации события,

зависящего от состояния, сколько коммуникационными характеристиками,

такими как задержки связи и число последовательных потерь данных при

передаче пакетов, а также характеристиками управления. При этом интер-

вал между выборками может адаптивно регулироваться в целях снижения

коммуникационной нагрузки и улучшения энергоэффективности при сохра-

нении границы H_∞-нормы.

В [54] рассматривалось “событийное” H_∞-управление для класса нелиней-

ных сетевых систем. Авторами предложена схема выбора “необходимых” па-

кетов данных для передачи, обеспечивающая значительную экономию ре-

сурсов связи. Эта схема строится посредством исследования модели с пере-

менными временными задержками, для которой в работе получены новые

эффективные оценки производной функционала Ляпунова - Красовского и

новое достаточное условие существования H_∞-регуляторов с переключения-

ми по событиям. Полученные регуляторы не требуют настройки внутренних

параметров. Разработанный метод применяется для робастной стабилизации

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

Более подробные сведения об управлении и фильтрации в линейных сете-

вых системах с взаимодействиями, определяемыми событиями, могут быть

получены из аналитических обзоров [53, 115, 116].

7.4. Некоторые асинхронные модели следования за лидером

В задачах о консенсусе без лидера для моделей первого порядка агентам

требуется прийти к общему значению определенной характеристики, которое

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

тов. Однако во многих приложениях имеется лидер (физический или вир-

туальный, статический или динамический), указывающий цель группе аген-

тов. Например, перед командой беспилотных подводных или летательных ап-

паратов может быть поставлена задача синхронно отслеживать траекторию

движущейся цели или ведущего аппарата. Такие содержательные постанов-

ки приводят к задачам о консенсусе при следовании за лидером. При этом

движение лидера не зависит от последователей и лишь часть последователей

имеет доступ к информации, непосредственно исходящей от лидера. В дан-

ном подразделе обсуждаются некоторые недавние результаты по распреде-

ленному консенсусу в задачах следования за лидером в случае протоколов с

выборочными данными.

Рассмотрим несколько механизмов взаимодействия, определяемых собы-

тиями (см. [26]).

- Коррекция с порогом, непрерывно зависящим от состояния. В этом слу-

чае условие реализации события имеет вид

(24)

∥e_i(t)∥ ≥ σ_i∥χ_i

(t)∥,

где e_i(t) = χ_i(s^ik) - χ_i(t),

∑

(

)

(

)

χ_i(t) =

a_ij

x_j(t) - x_i(t)

+λ_i

x^∗(t) - x_i(t)

j∈N_i

λ_i - усиление, соответствующее агенту i, x^∗(t) - состояние лидера. В [20] в

условие реализации события (24) включается дополнительная весовая мат-

рица Φ:

∥e_i(t)Φ∥ ≥ σ_i∥χ_i(t)Φ∥,

где e_i(t) = x_i(t) - x_i(t), x_i(t) = eA(t-sk )x_i(s^ik).

В данной работе проблема консенсуса при следовании за лидером изуча-

ется для МАС с общей линейной динамикой. Схемы взаимодействия агентов,

определяемые событиями, классифицируются на распределенные, централи-

зованные и кластерные и исследуются на различных топологиях. В распреде-

ленных схемах агенты детектируют события независимо. В централизован-

ных схемах события являются общими для всех агентов и последние пере-

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

схемах все последователи лидера разбиваются на несколько кластеров и схе-

ма взаимодействия строится как распределенная в отношении кластеров и

централизованная внутри каждого из них. Показано, что рассмотренные схе-

мы взаимодействия можно выстроить эффективно в смысле минимизации

частоты взаимодействий и переключений управления при сохранении воз-

можности следования за лидером. Кроме того, для схем этих типов можно

исключить поведение Зенона. Соответствующие алгоритмы обнаружения со-

бытий выстраиваются таким образом, чтобы избежать непрерывной связи

между агентами.

- Коррекция с порогом, непрерывно зависящим от состояния, и поло-

жительным смещением. При использовании смещения условие реализации

события (24) может быть заменено на

∥e_i(t)∥ ≥ σ_i∥χ_i(t)∥ + δ_i

или

(25)

∥e_i(t)∥ ≥ σ_i∥χ_i(t)∥ + c₁e^-μt + δ_i,

где e_i(t) = χ_i(s^ik) - χ_i(t); σ_i, δ_i, c₁ и μ - положительные константы.

В [117] с применением условия (25) был разработан AES-протокол поиска

консенсуса вида u_i(t) = -K χ_i(s^ik) для линейных МАС с неориентированными

и ориентированными графами влияния агентов. Для него получены доста-

точные условия того, что ошибки следования за лидером не превысят задан-

ной границы. Граница ошибок может быть снижена за счет настройки пара-

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

ду агентами на начальном этапе отслеживания. Показано, что предлагаемая

схема взаимодействия не приводит к поведению Зенона даже при парамет-

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

Высокие требования к точности слабо влияют на интервалы между события-

ми начиная с достаточно большого времени. Алгоритм генерации состояний

агентов сконструирован так, что не возникает необходимости в непрерывном

отслеживании состояний соседей.

- Коррекция с порогом, зависящим от выборочного состояния, и положи-

тельным смещением. Здесь условие реализации события может иметь вид

(26)

∥e_i(t)∥ ≥ σ_i∥χ_i(s^ik)∥ + c₁e-μ(t-t0 ),

где e_i(t) = χ_i(s^ik) - χ_i(t). Условие (26) использовалось, в частности, в [14, 118]

для решения задачи консенсуса в МАС с входными задержками.

В [14] рассматривались системы МАС с общей линейной динамикой, ори-

ентированной топологией и временными задержками. Для случая кусочно-

постоянного управления с переключениями по событиям получены необхо-

димое и два достаточных условия достижения консенсуса в задаче следова-

ния за лидером. Условия включают стабилизируемость пары матриц (A, B),

задающей линейную динамику, и наличие остовного дерева, исходящего

из вершины-лидера, в орграфе влияний. Схема взаимодействия не требует

непрерывной коммуникации агентов-соседей и исключает поведение Зенона.

Работа [118] посвящена консенсусу при следовании за лидером в МАС

второго порядка с задержками передачи данных. Рассматриваемый прото-

кол, основанный на измерениях состояний агентов-соседей в дискретные мо-

менты времени, рассчитан на агентов с ограниченными коммуникационны-

ми и вычислительными ресурсами. Представлено необходимое и достаточное

условие достижения глобального консенсуса в случае ориентированной топо-

логии. Основной результат сформулирован не совсем аккуратно, но основа

полученного условия - наличие остовного дерева, исходящего их вершины,

соответствующей лидеру, в орграфе влияний.

- Коррекция на основе адаптивного порога. В [24] условие реализации со-

бытия имело общий вид

(27)

eTi(t)Φ_ie_i(t) ≥ σ_i(t)yTi(t)Φ_iy_i

(t),

(28)

σ_i(t) = -ρ_iσ2i(t)eTi(t)Φ_ie_i

(t),

где Φi - положительно определенные матрицы весов; ei(t) = yi(t) - yi(t);

y_i(t) = x_i(t) - x^∗(t) и y_i(t) = x_i(s^ik) - x^∗(t), если агент i получает прямую ин-

формацию от лидера (его состояние, как и ранее, обозначено через x^∗(t));

в противном случае y_i(t) = x_i(t) - x_j (sj˜) и yi(t) = xi(sik) - xj(sj˜). В (27) по-

роговый параметр σ_i(t) не фиксирован, а меняется в соответствии с (28) в

зависимости от дефекта выборки и начального условия σ_i(0).

При условии (27)-(28) в [24] рассматривалась задача консенсуса для нели-

нейных МАС с условием Липшица и ориентированной топологией в предпо-

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

Задачу авторы, как и в случае многих других работ по асинхронному управ-

лению, видят в снижении нагрузки на коммуникационные ресурсы мультиа-

гентной сети. Рассмотрены два типа адаптивных схем управления с переклю-

чениями, определяемыми событиями. Один из них основан на непрерывном

взаимодействии агентов, другой - на обмене выборочными данными. С ис-

пользованием модели секторной нелинейности [119] для описания насыщений

по входу и метода Ляпунова получены достаточные условия локального кон-

сенсуса, имеющие форму линейных матричных неравенств.

7.5. Дискретизация непрерывных моделей следования за лидером

Условие реализации события (27)-(28), вообще говоря, требует постоян-

ного мониторинга состояний агентов. В [24] был предложен его аналог, яв-

ляющийся периодическим выборочным условием коррекции, не требующим

непрерывных измерений и постоянной коммуникации агентов. А именно,

условие (27)-(28) было заменено на

(

)

(

)

(

)

(

)

(

)

eTi

(t^ik + ω_i)T

Φ_ie_i

(t^ik + ω_i)T

≥σ_i

(t^ik + ω_i)T

yTi

(t^ik + ω_i)T

Φ_iy_i

(t^ik + ω_i)T

(

)

(

)

(

)

(29)

σ_i

(t^ik + ω_i)T

=σ_i

(t^ik + ω_i - 1)T

-ρ_iTσ_i

(t^ik + ω_i)T

(

)

(

)

(

)

×σ_i

(t^ik + ω_i - 1)T

eTi

(t^ik + ω_i)T

Φ_ie_i

(t^ik + ω_i)T

где e_i((t^ik + ω_i)T ) = x_i((t^ik + ω_i)T ) - x_i(t^ikT ); y_i((t^ik + ω_i)T ) = x_i((t^ik + ω_i)T ) -

-x^∗((t^ik +ω_i)T), если агент i получает прямую информацию от лидера (x^∗(t) -

его состояние); в противном случае y_i((t^ik + ω_i)T ) = x_i((t^ik + ω_i)T ) - x_j(t^j T )._˜

Условие реализации события (29) проверяется в дискретные моменты выбор-

ки (t^ik + ω_i)T . Другим похожим способом избежать постоянного мониторинга

и проверки условия реализации событий является решение задачи консенсуса

в дискретном времени, как предложено в [19]. Содержательно последнее абсо-

лютно реалистично, поскольку управление большинством реальных мульти-

агентных систем осуществляется посредством цифровых регуляторов. Кроме

того, поведение Зенона, исключение которого в непрерывных моделях порой

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

однако, является вопрос о шаге дискретности, поскольку очевидно, что при

малом шаге частота требуемых измерений и сеансов связи легко может пре-

высить возможности оборудования. Проблеме выбора шага дискретизации

посвящена работа [120].

В [19] применялось условие реализации события

eTi(k)Φ_ie_i(k) ≥ σ_i(k)yTi(k)Φ_iy_i(k),

где e_i(k) = y_i(k) - y_i(t^ik); σ_i(k) ∈ [0, 1) может меняться в зависимости от k;

yi(k) представляет собой зависящий от дискретного времени выходной сиг-

нал.

В этой работе предложен распределенный протокол консенсуса при следо-

вании за лидером для систем с ориентированной топологией, меняющейся в

дискретном времени, общей линейной динамикой, “неизвестным, но ограни-

ченным” (unknown-but-bounded, UBB) шумом, ошибками измерения и огра-

ниченными коммуникационными ресурсами. Показано, что в результате при-

менения разработанного протокола состояния агентов, следующих за лиде-

ром, попадают в границы заданного эллипсоидального множества, “окру-

жающего” состояние лидера. Для описания этого результата введено поня-

тие множественного консенсуса при следовании за лидером (set-membership

leader-following consensus). Оценивание параметров протокола и механизма

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

рекурсивно вычисляющего эллипсоиды, содержащие состояния лидера и его

последователей.

8. Консенсус в системах со случайными интервалами

между переключениями

Асинхронный случайный механизм ARS применялся в [121] в контексте

управления системами с общей линейной инвариантной по времени (LTI:

linear time-invariant) динамикой

x_i(t) = Ax_i(t) + Bu_i(t), t ∈ [s_k,sk+1), i ∈ V,

где s_k = kT, A и B - постоянные действительные матрицы.

Связь этой модели с консенсусом в МАС состоит в следующем. В соответ-

ствии с асинхронным случайным механизмом ARS каждый агент имеет свою

последовательность моментов наблюдения {s^ik}k∈N, удовлетворяющую (2).

Пусть промежутки между наблюдениями для каждого агента могут ме-

няться, принимая значения из конечного множества S = {T₁, T₂, . . . , T_S } (где

0 < T₁ < T₂ < ··· < T_S), каждое - со своей вероятностью P{T^ik = T_m} = p^im

(m = 1, . . . , S), зависящей также от агента i, при выполнении условия

∑_S

p^im = 1 для каждого i ∈ V . Введем кусочно-линейную функцию за-

m=1

держки dⁱ(t) = t - s^ik, t ∈ [s^ik, sik+1). Тогда вероятности принадлежности dⁱ(t)

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

T₁

P{0 ≤ dⁱ(t) < T₁} = pi1 + pⁱ

+···+pⁱ

=qi1,

²T₂

T_S

T₂ - T₁

P{T₁ ≤ dⁱ(t) < T₂} = pⁱ

+···+pⁱ

=qi2,

T₂

T_S

T_S - TS-1

P{TS-1 ≤ dⁱ(t) < T_S } = pⁱ

=q^iS.

T_S

∑_S

При этом, как и требуется,

q^im = 1 для всех i ∈ V . Используя функции-

m=1

индикаторы

{

1, dⁱ(t) ∈ [Tm-1, T_m),

ψ^im = ψidi(t)∈[Tm-1,Tm)⁼

0, dⁱ(t) ∈ [Tm-1, T_m),

где T₀ = 0, имеем

E{ψ^im} = P{dⁱ(t) ∈ [Tm-1, T_m)} = q^im, m = 1, . . . , S.

Поэтому протокол консенсуса типа ARS вида u_i(s^ik) = Kχi (s^ik) (см. (7)) до-

пускает [121, формула (15)] представление

∑

u_i(s^ik) = Kχ_i(t - dⁱ(t)) = K

ψ^imχ_i(t - τ^im(t)), где τ^im(t) ∈ [Tm-1,T_m).

m=1

В свою очередь, это представление позволяет рассмотреть исходную систему

с обратной связью, вероятностной выборкой и асинхронным случайным меха-

низмом как стохастическую систему со случайными переменными ψ^im и про-

извольными задержками τ^im(t) и использовать результаты, полученные для

стохастических систем и систем с задержками [122, 123] при решении задач

о консенсусе (и, более широко, для задач о децентрализованном управлении

мультиагентными системами). В [121] получены достаточные условия робаст-

ной среднеквадратичной экспоненциальной устойчивости систем, характери-

зующихся меняющейся во времени, но ограниченной по норме вероятностной

неопределенностью параметров - как состояний, так и входных матриц. В па-

радигме робастного H_∞-управления разработана процедура проектирования

стабилизирующих регуляторов для таких систем, описываемая посредством

линейных матричных неравенств.

В [21] рассмотрена задача консенсуса в мультиагентной стохастической

системе с нелинейной динамикой, переключающейся ориентированной топо-

логией, помехами и задержками в измерениях. Для ее решения предложен ал-

горитм стохастической аппроксимации с отделенным от нуля размером шага.

Для исследования системы применен метод усредненных непрерывных моде-

лей (называемый также Derevitskii-Fradkov-Ljung (DFL)-схемой). Основным

результатом работы являются условия достижения приближенного средне-

квадратичного консенсуса при использовании протокола локального голо-

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

траекторий исходной динамической сети и ее усредненной модели. В каче-

стве практического примера исследована модель децентрализованной балан-

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

информации о состояниях узлов и переменной топологии. В такой сети ин-

формация о длине очереди и производительности соседей, поступающая в

каждый узел, подвержена действию шума и может поступать с задержками.

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

ствия агентов относится к типу ARS.

Данный подход развит в [22]. В частности, допущение об ограниченности

весов, входящих в протокол управления, заменено на более слабое предпо-

ложение об ограниченности их дисперсий. Кроме того, добавлен численный

эксперимент большого объема.

В [124] рассматривается задача консенсуса для стохастической мультиа-

гентной системы с нелинейной динамикой, симметричной топологией и асин-

хронными переключениями режима работы. Каждый агент переключает ре-

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

деленного контроллера с асинхронной коммутацией, обеспечивающего дости-

жение экспоненциального консенсуса. Критерии ограничивают сверху долю

времени, когда система управляется рассогласованно. Для стохастических си-

стем разработан “принцип сравнения”, обобщающий принцип, предложенный

в [125] для детерминированных систем с задержками и импульсным управ-

лением.

9. Заключение

В представленном обзоре отмечено, что мультиагентная система с асин-

хронным взаимодействием агентов может быть представлена синхронной си-

стемой с переменным графом взаимодействий. В каждый момент в граф

включаются те и только те дуги, которые соответствуют парам взаимодей-

ствующих в этот момент агентов. Тем самым внутренние и внешние по отно-

шению к агентам механизмы, продуцирующие асинхронность, “упаковывают-

ся” в алгоритм генерации графа взаимодействий. Как показывают многочис-

ленные рассмотренные модели, механизмы эти могут быть сложны и разно-

образны: моменты взаимодействий могут определяться “по расписанию”, слу-

чайно либо в зависимости от значений определенных функционалов (по “со-

бытиям”). События, в свою очередь, могут состоять в существенном расхож-

дении результатов наблюдений с предыдущими наблюдениями или прогноз-

ными значениями, в достижении заданных пороговых значений расстояния

или иных характеристик, в нарушениях нормального сценария взаимодей-

ствия агентов (таких, как потеря данных) и т.д.

Английский термин “sampling”, используемый при описании асинхронных

систем, часто переводят как “дискретизация данных”. Рассмотрение конкрет-

ных моделей убеждает, что это понятие имеет сложную структуру. Действи-

тельно, необходимо различать дискретные моменты наблюдений/измерений,

передачи данных другим агентам, отправки запросов “соседям” на получение

данных, получения данных от них, а также моменты переключений управле-

ния. Для каждого агента моменты этих типов, вообще говоря, не совпадают,

причем наступление их может регулироваться специфической комбинацией

внешних и внутренних условий. Легко представить, какое разнообразие мо-

делей порождается такими комбинациями. Вся эта сложность на текущем

этапе развития теории мультиагентных систем связана с переходом от умо-

зрительных моделей к разработке систем, решающих практические задачи

при необходимости экономии энергетических, информационных и временных

ресурсов: экономия почти всегда приводит к усложнению алгоритмов реше-

ния задач.

Критерии достижимости консенсуса для рассмотренных моделей включа-

ют наличие исходящего дерева в орграфе влияний агентов (в случае ори-

ентированной топологии) или связность графа коммуникаций (при неори-

ентированной топологии). В случае переменной топологии эти условия ча-

сто применяются к объединениям соответствующих графов на ограничен-

ных временных отрезках. Как правило, за исключением простейших моделей

первого порядка достаточные условия консенсуса включают также и допол-

нительные требования, определяемые спецификой моделей. Само же дости-

жение консенсуса необходимо для того, чтобы мультиагентная система могла

решать поставленные перед ней задачи как единое целое. Именно по этой

причине протоколы консенсуса составляют ядро алгоритмов децентрализо-

ванного управления сетевыми мультиагентными системами.

В следующей части обзора будут рассмотрены интересные математические

задачи, решение которых необходимо при анализе и синтезе мультиагентных

систем с нестационарной динамикой.

СПИСОК ЛИТЕРАТУРЫ

1. Bhaya A., Kaszkurewicz E., Kozyakin V.S. Existence and Stability of a Unique

Equilibrium in Continuous-Valued Discrete-Time Asynchronous Hopfield Neural

Networks // Proc. 1995 IEEE Int. Sympos. Circuits Syst. ISCAS’95. 1995. V. 2.

P. 1140-1143.

2. Kozyakin V.S., Bhaya A., Kaszkurewicz E. A Global Asymptotic Stability Result

for a Class of Totally Asynchronous Discrete Nonlinear Systems // Math. Control

Signals Syst. 1999. V. 12. No. 2. P. 143-166.

3. MacKay D.J.C. Information Theory, Inference and Learning Algorithms. New York:

Cambridge University Press, 2003. P. xii+628.

4. Блехман И.И. Синхронизация динамических системю М.: Наука, 1971.

5. Проскурников А.В., Фрадков А.Л. Задачи и методы сетевого управления //

АиТ. 2016. № 10. C. 3-39.

Proskurnikov A.V., Fradkov A.L. Problems and Methods of Network Control //

Autom. Remote Control. 2016. V. 77. No. 10. P. 1711-1740.

Szyld D.B. The Mistery of Asynchronous Iterations Convergence when the

Spectral Radius is One: Report 98-102. Temple University: College of Science and

Technology, 1998. URL: https://math.temple.edu/ szyld/reports/mystery.pdf

Асарин Е.А., Козякин В.С., Красносельский М.А., Кузнецов Н.А. Анализ

устойчивости рассинхронизированных дискретных систем. М.: Наука, 1992.

Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical

Methods. Englewood Cliffs. N.J.: Prentice Hall, 1989.

Kozyakin V. An Annotated Bibliography on Convergence of Matrix Products

and the Theory of Joint/Generalized Spectral Radius: Preprint. Moscow:

Institute for Information Transmission Problems,

2013. URL: https://

drive.google.com/uc?export=download&id=0Bxw63g5l4P7pLXgwcWxVZ3RoTVk

10.

Sridharan G., Srisailam M.C., Rao V.S. A Note on the Effect of Asynchronous

Sampling on Estimation Accuracy // Automatica. 1985. V. 21. No. 4. P. 491-493.

11.

Tsitsiklis J.N., Bertsekas D.P., Athans M. Distributed Asynchronous Deterministic

and Stochastic Gradient Optimization Algorithms // IEEE Trans. Automat.

Control. 1986. V. 31. No. 9. P. 803-812.

12.

Fang L., Antsaklis P.J. Information Consensus of Asynchronous Discrete-Time

Multi-Agent Systems / Proc. 2005 Amer. Control Conf. (ACC). IEEE, 2005.

P. 1883-1888.

13.

Zhu W., Jiang Z.P., Feng G. Event-Based Consensus of Multi-Agent Systems with

General Linear Models // Automatica. 2014. V. 50. No. 2. P. 552-558.

14.

Zhu W., Jiang Z.P. Event-Based Leader-Following Consensus of Multi-Agent

Systems with Input Time Delay // IEEE Trans. Automat. Control. 2015. V. 60.

No. 5. P. 1362-1367.

15.

Hu W., Liu L., Feng G. Consensus of Linear Multi-Agent Systems by Distributed

Event-Triggered Strategy // IEEE Trans. Cybernet. 2016. V. 46. No. 1. P. 148-157.

16.

Hu W., Liu L., Feng G. Output Consensus of Heterogeneous Linear Multi-Agent

Systems by Distributed Event-Triggered/Self-Triggered Strategy // IEEE Trans.

Cybernet. 2017. V. 47. No. 8. P. 1914-1924.

17.

Yang D., Ren W., Liu X., Chen W. Decentralized Event-Triggered Consensus for

Linear Multi-Agent Systems under General Directed Graphs // Automatica. 2016.

V. 69. P. 242-249.

18.

Guinaldo M., Sánchez J., Dormido S. Distributed Adaptive Control of Linear Multi-

Agent Systems with Event-Triggered Communications // App. Math. Comput.

2016. V. 274. P. 195-207.

19.

Ge X., Han Q.L., Yang F. Event-Based Set-Membership Leader-Following

Consensus of Networked Multi-Agent Systems Subject to Limited Communication

Resources and Unknown-but-Bounded Noise

// IEEE Trans. Industrial Electron.

2017. V. 64. No. 6. P. 5045-5054.

20.

Xu W., Ho D.W., Li L., Cao J. Event-Triggered Schemes on Leader-Following

Consensus of General Linear Multiagent Systems under Different Topologies //

IEEE Trans. Cybernet. 2017. V. 47. No. 1. P. 212-223.

21.

Амелина Н.О., Фрадков А.Л. Приближенный консенсус в стохастической ди-

намической сети с неполной информацией и задержками в измерениях // 2012.

№ 11. C. 6-29.

Amelina N.O., Fradkov A.L. Approximate Consensus in the Dynamic Stochastic

Network with Incomplete Information and Measurement Delays // Autom. Remote

Control. 2012. V. 73. No. 11. P. 1765-1783.

22.

Amelina N., Fradkov A., Jiang Y., Vergados D.J. Approximate Consensus in

Stochastic Networks with Application to Load Balancing // IEEE Trans. Inform.

Theory. 2015. V. 61. No. 4. P. 1739-1752.

23.

Ding L., Zheng W.X. Consensus Tracking in Heterogeneous Nonlinear Multi-Agent

Networks with Asynchronous Sampled-Data Communication // Syst. Control Lett.

2016. V. 96. P. 151-157.

24.

Yin X., Yue D., Hu S. Adaptive Periodic Event-Triggered Consensus for Multi-

Agent Systems Subject to Input Saturation // Int. J. Control. 2016. V. 89. No. 4.

P. 653-667.

25.

Xiao F., Shi Y., Ren W. Robustness Analysis of Asynchronous Sampled-Data

Multiagent Networks with Time-Varying Delays // IEEE Trans. Automat. Control.

2018. V. 63. No. 7.

26.

Ge X., Han Q.L., Ding D., Zhang X.M., Ning B. A Survey on Recent Advances

in Distributed Sampled-Data Cooperative Control of Multi-Agent Systems //

Neurocomput. 2018. V. 275. P. 1684-1701.

27.

Gao Y., Wang L. Sampled-Data Based Consensus of Continuous-Time Multi-Agent

Systems with Time-Varying Topology // IEEE Trans. Automat. Control. 2011.

V. 56. No. 5. P. 1226-1231.

28.

Cao M., Morse A.S., Anderson B.D.O. Agreeing Asynchronously // IEEE Trans.

Autom. Control. V. 53. No. 8. P. 1826-1838.

29.

Gao Y., Wang L. Asynchronous Consensus of Continuous-Time Multi-Agent

Systems with Intermittent Measurements // Int. J. Control. 2010. V. 83. No. 3.

P. 552-562.

30.

Meng X., Chen T. Optimal Sampling and Performance Comparison of Periodic

and Event Based Impulse Control // IEEE Trans. Automat. Control. 2012. V. 57.

No. 12. P. 3252-3259.

31.

Ge X., Han Q.L., Jiang X. Sampled-Data H_∞ Filtering of Takagi-Sugeno Fuzzy

Systems with Interval Time-Varying Delays // J. Franklin Inst. 2014. V. 351. No. 5.

P. 2515-2542.

32.

Ge X., Han Q.L. Distributed Sampled-Data Asynchronous H_∞ Filtering of

Markovian Jump Linear Systems over Sensor Networks // Signal Proc. 2016. V. 127.

P. 86-99.

33.

Marvasti F. Nonuniform Sampling: Theory and Practice. Berlin: Springer-Verlag,

2001.

34.

Boyd S., Ghosh A., Prabhakar B., Shah D. Randomized Gossip Algorithms // IEEE

Trans. Inform. Theory. 2006. V. 52. No. 6. P. 2508-2530.

35.

Proskurnikov A.V., Tempo R. A Tutorial on Modeling and Analysis of Dynamic

Social Networks. Part II // Annual Rev. Control. 2018. V. 45. P. 166-190.

36.

Ellis P. Extension of Phase Plane Analysis to Quantized Systems // IRE Trans.

Automat. Control. 1959. V. 4. No. 2. P. 43-54.

37.

Pavlidis T., Jury E. Analysis of a New Class of Pulse-Frequency Modulated

Feedback Systems // IEEE Trans. Automat. Control. 1965. V. 10. No. 1. P. 35-43.

38.

Гелиг А.Х., Чурилов А.Н. Колебания и устойчивость нелинейных импульсных

систем. СПб.: Изд-во СПб ун-ва, 1993.

39.

Åström K.J., Bernhardsson B. Comparison of Periodic and Event Based Sampling

for First-Order Stochastic Systems // IFAC Proc. Vol. 1999. V. 32. No. 2. P. 5006-

5011.

40.

Åström K.J., Bernhardsson B.M. Comparison of Riemann and Lebesgue Sampling

for First Order Stochastic Systems // Proc. 41st IEEE Conf. Decision Control

(CDC), 2002. IEEE, 2002. V. 2. P. 2011-2016.

41.

Tabuada P. Event-Triggered Real-Time Scheduling of Stabilizing Control Tasks //

IEEE Trans. Autom. Control. 2007. V. 52. No. 9. P. 1680-1685.

42.

Anta A., Tabuada P. To Sample or not to Sample: Self-Triggered Control for

Nonlinear Systems // IEEE Trans. Automat. Control. 2010. V. 55. No. 9. P. 2030-

2042.

43.

Zhang D., Han Q.-L., Jia X. Network-Based Output Tracking Control for TCS

Fuzzy Systems Using an Event-Triggered Communication Scheme // Fuzzy Sets

Syst. 2015. V. 273. P. 26-48.

44.

Zhang X.M., Han Q.L. A Decentralized Event-Triggered Dissipative Control

Scheme for Systems with Multiple Sensors to Sample the System Outputs // IEEE

Trans. Cybernet. 2016. V. 46. No. 12. P. 2745-2757.

45.

Mirollo R.E., Strogatz S.H. Synchronization of Pulse-Coupled Biological

Oscillators // SIAM J. Appl. Math. 1990. V. 50. No. 6. P. 1645-1662.

46.

Proskurnikov A.V., Cao M. Synchronization of Pulse-Coupled Oscillators and

Clocks Under Minimal Connectivity Assumptions // IEEE Trans. Automat.

Control. 2017. V. 62. No. 11. P. 5873-5879.

47.

Heemels W.P.M.H., Donkers M.C.F., Teel A.R. Periodic Event-Triggered Control

for Linear Systems // IEEE Trans. Automat. Control. 2013. V. 58. No.

P. 847-861.

48.

Xiao F., Chen T. Sampled-Data Consensus in Multi-Agent Systems with

Asynchronous Hybrid Event-Time Driven Interactions // Syst. Control Lett. 2016.

V. 89. P. 24-34.

49.

Михеев Ю.В., Соболев В.А., Фридман Э.М. Асимптотический анализ цифро-

вых систем управления // АиТ. 1988. № 9. C. 83-88.

50.

Fridman E. New Lyapunov-Krasovskii Functionals for Stability of Linear Retarded

and Neutral Type Systems // Syst. Control Lett. 2001. V. 43. No. 4. P. 309-319.

51.

Fridman E., Shaked U. Delay-Dependent Stability and H_∞ Control: Constant and

Time-Varying Delays // Int. J. Control. 2003. V. 76. No. 1. P. 48-60.

52.

Liu K., Fridman E. Stability Analysis of Networked Control Systems: A

Discontiuous Lyapunov Functional Approach / Proc. 48th IEEE Conf. Decision

Control held jointly with the 28th Chinese Control Conf. CDC/CCC 2009. IEEE,

2009. P. 1330-1335.

53.

Hetel L., Fiter C., Omran H., Seuret A., Fridman E., Richard J.P., Niculescu S.I.

Recent Developments on the Stability of Systems with Aperiodic Sampling: An

Overview // Automatica. 2017. V. 76. P. 309-335.

54.

Zhang X.M., Han Q.L. Event-Triggered H_∞ Control for a Class of Nonlinear

Networked Control Systems Using Novel Integral Inequalities // Int. J. Robust

Nonlin. Control. 2017. V. 27. No. 4. P. 679-700.

55.

Ugrinovskii V., Fridman E. A Round-Robin Type Protocol for Distributed

Estimation with H_∞ Consensus // Syst. Control Lett. 2014. V. 69. P. 103-110.

56.

Zareh M., Dimarogonas D.V., Franceschelli M., Johansson K.H., Seatzu C.

Consensus in Multi-Agent Systems with Non-Periodic Sampled-Data Exchange and

Uncertain Network Topology / Int. Conf. Control, Decision and Inform. Technol.

(CoDIT-2014). IEEE, 2014. P. 411-416.

57.

Song Q., Liu F., Wen G., Cao J., Yang X. Distributed Position-Based Consensus of

Second-Order Multiagent Systems with Continuous/Intermittent Communication//

IEEE Trans. Cybernet. 2017. V. 47. No. 8. P. 1860-1871.

58.

Wang X., Wang H., Li C., Huang T., Kurths J. Consensus Seeking in Multiagent

Systems with Markovian Switching Topology under Aperiodic Sampled Data //

IEEE Trans. Syst., Man, Cybernet.: Syst. 2018 (Early Access).

59.

Lin J., Morse A.S., Anderson B.D.O. The Multi-Agent Rendezvous Problem - the

Asynchronous Case // 43rd IEEE Conf. Decision Control (CDC), 2004. IEEE, 2004.

V. 2. P. 1926-1931.

60.

Lin J., Morse A.S., Anderson B.D.O. The Multi-Agent Rendezvous Problem.

Part 2: The Asynchronous Case // SIAM J. Control Optim. 2007. V. 46. No. 6.

P. 2120-2147.

61.

Tsitsiklis J.N. Problems in Decentralized Decision Making and Computation, Ph.D.

dissertation, MIT, Cambridge, MA, 1984.

62.

Blondel V.D., Hendrickx J.M., Olshevsky A., Tsitsiklis J.N. Convergence in

Multiagent Coordination, Consensus, and Flocking // 44th IEEE Conf. Decision

Control (CDC-ECC’05). IEEE, 2005. P. 2996-3000.

63.

Cao M., Morse A.S., Anderson B.D.O. Coordination of an Asynchronous Multi-

Agent System via Averaging // IFAC Proc. Vol. 2005. V. 38. No. 1. P. 17-22.

64.

Сарымсаков Т.А. Об эргодическом принципе для неоднородных цепей Марко-

ва // Докл. АН СССР. 1953. Т. 90. № 1. C. 25-28.

65.

Сарымсаков Т.А. О неоднородных цепях Маркова // Докл. АН СССР 1958.

Т. 120. № 3. C. 465-467.

66.

Сарымсаков Т.А. Неоднородные цепи Маркова // Теория вероятностей и ее

применения. 1961. Т. 6. № 2. C. 194-201.

67.

Hajnal J., Bartlett M.S. The Ergodic Properties of Non-Homogeneous Finite

Markov Chains // Math. Proc. Cambridge Philosoph. Soc. 1956. V. 52. No. 1.

P. 67-77.

68.

Hajnal J., Bartlett M.S. Weak Ergodicity in Non-Homogeneous Markov Chains //

Math. Proc. Cambridge Philosoph. Soc. 1958. V. 54. No. 2. P. 233-246.

69.

Wolfowitz J. Products of Indecomposable, Aperiodic, Stochastic Matrices // Proc.

Amer. Math. Soc. 1963. V. 15. P. 733-736.

70.

Jadbabaie A., Lin J., Morse A.S. Coordination of Groups of Mobile Autonomous

Agents Using Nearest Neighbor Rules // IEEE Trans. Automat. Control. 2003.

V. 48. No. 6. P. 988-1001.

71.

Агаев Р.П., Чеботарев П.Ю. Сходимость и устойчивость в задачах согласо-

вания характеристик (обзор базовых результатов) // Управление большими

системами. 2010. Т. 30. № 1. C. 470-505.

72.

Di Fatta G., Blasa F., Cafiero S., Fortino G. Fault Tolerant Decentralised k-Means

Clustering for Asynchronous Large-Scale Networks // J. Parallel Distributed

Comput. 2013. V. 73. No. 3. P. 317-329.

73.

Lubachevsky B., Mitra D. A Chaotic Asynchronous Algorithm for Computing the

Fixed Point of a Nonnegative Matrix of Unit Spectral Radius // J. ACM (JACM).

1986. V. 33. No. 1. P. 130-150.

74.

Moreau L. Leaderless Coordination via Bidirectional and Unidirectional Time-

Dependent Communication // Proc. 42nd IEEE Conf. Decision Control (CDC),

2003. IEEE, 2003. V. 3. P. 3070-3075.

75.

Ren W., Beard R.W. Consensus of Information under Dynamically Changing

Interaction Topologies // Proc. 2004 ACC, Boston, MA, 2004. P. 4939-4944.

76.

Olfati-Saber R., Murray R.M. Consensus Problems in Networks of Agents with

Switching Topology and Time-Delays // IEEE Trans. Automat. Control. 2004.

V. 49. No. 9. P. 1520-1533.

77.

Агаев Р.П., Чеботарев П.Ю. Матрица максимальных исходящих лесов оргра-

фа и ее применения // АиТ. 2000. № 9. C. 15-43.

Agaev R.P., Chebotarev P.Yu. The Matrix of Maximum Out Forests of a Digraph

and Its Applications // Autom. Remote Control. 2000. V. 61. No. 9. P. 1424-1450.

78.

Агаев Р.П., Чеботарев П.Ю. Остовные леса орграфа и их применение // АиТ.

2001. № 3. C. 108-133.

Agaev R.P., Chebotarev P.Yu. Spanning Forests of a Digraph and Their

Applications // Autom. Remote Control. 2001. V. 62. No. 3. P. 443-466.

79.

Chebotarev P., Agaev R. Forest Matrices around the Laplacian Matrix // Linear

Algebra Appl. 2002. V. 356. P. 253-274.

80.

Chebotarev P., Agaev R. The Forest Consensus Theorem // IEEE Trans. Automat.

Control. 2014. V. 59. No. 9. P. 2475-2479.

81.

Агаев Р.П., Чеботарев П.Ю. Об асимптотике в моделях консенсуса // Управ-

ление большими системами. 2013. Т. 43. С. 55-77.

82.

Агаев Р.П., Чеботарев П.Ю. Согласование характеристик в многоагентных си-

стемах и спектры лапласовских матриц орграфов // АиТ. 2009. № 3. C. 136-151.

Chebotarev P.Yu., Agaev R.P. Coordination in Multiagent Systems and Laplacian

Spectra of Digraphs // Autom. Remote Control. 2009. V. 70. No. 3. P. 469-483.

83.

Chebotarev P. Comments on “Consensus and Cooperation in Networked Multi-

Agent Systems” // Proc. IEEE. 2010. V. 98. No. 7. P. 1353-1354.

84.

Fang L., Antsaklis P.J. Asynchronous Consensus Protocols Using Nonlinear

Paracontractions Theory // IEEE Trans. Automat. Control. 2008. V. 53. No. 10.

P. 2351-2355.

85.

Qin J., Yu C., Hirche S. Stationary Consensus of Asynchronous Discrete-Time

Second-Order Multi-Agent Systems under Switching Topology // IEEE Trans.

Industr. Inform. 2012. V. 8. No. 4. P. 986-994.

86.

Qin J., Gao H., Zheng W.X. Consensus Strategy for a Class of Multi-Agents with

Discrete Second-Order Dynamics // Int. J. Robust Nonlin. Control. 2012. V. 22.

No. 4. P. 437-452.

87.

Zhou B., Liao X., Huang T., Wang H., Chen G. Constrained Consensus of

Asynchronous Discrete-Time Multi-Agent Systems with Time-Varying Topology //

Inform. Sci. 2015. V. 320. P. 223-234.

88.

Nedic A., Ozdaglar A., Parrilo P.A. Constrained Consensus and Optimization

in Multi-Agent Networks // IEEE Trans. Automat. Control. 2010. V. 55. No. 4.

P. 922-938.

89.

Губин Л.Г., Поляк Б.Т., Райк Е.В. Метод проекций для нахождения общих

точек выпуклых множеств // Журн. вычисл. матем. и мат. физики. 1967. № 7.

C. 1-24.

90.

Shao J., Shi L., Zheng W.X., Huang T.Z. Containment Control for Heterogeneous

Multi-Agent Systems with Asynchronous Updates // Inform. Sci. 2018. V. 436.

P. 74-88.

91.

Shi L., Shao J., Cao M., Xia H. Asynchronous Group Consensus for Discrete-

Time Heterogeneous Multi-Agent Systems under Dynamically Changing Interaction

Topologies // Inform. Sci. 2018. V. 463-464. P. 282-293.

92.

Xiao F., Wang L. Asynchronous Consensus in Continuous-Time Multi-Agent

Systems with Switching Topology and Time-Varying Delays // IEEE Trans. Autom.

Control. 2008. V. 53. No. 8. P. 1804-1816.

93.

Almeida J., Silvestre C., Pascoal A.M. Continuous-Time Consensus with Discrete-

Time Communications // Syst. Control Lett. 2012. V. 61. No. 7. P. 788-796.

94.

Xiao F., Chen T. Sampled-Data Consensus for Multiple Double Integrators with

Arbitrary Sampling // IEEE Trans. Autom. Control. 2012. V. 57. No. 12. P. 3230-

3235.

95.

Zhan J., Li X. Asynchronous Consensus of Multiple Double-Integrator Agents with

Arbitrary Sampling Intervals and Communication Delays // IEEE Trans. Circuits

Syst. I: Regular Papers. 2015. V. 62. No. 9. P. 2301-2311.

96.

Jiang F., Liu B., Wu Y., Zhu Y. Asynchronous Consensus of Second-Order

Multi-Agent Systems with Impulsive Control and Measurement Time-Delays

Neurocomput. 2018. V. 275. P. 932-939.

97.

Liu Z.W., Guan Z.H., Shen X., Feng G. Consensus of Multi-Agent Networks with

Aperiodic Sampled Communication via Impulsive Algorithms Using Position-Only

Measurements // IEEE Trans. Automat. Control. 2012. V. 57. No. 10. P. 2639-2643.

98.

Ding D., Wang Z., Shen B., Wei G. Event-Triggered Consensus Control for

Discrete-Time Stochastic Multi-Agent Systems: The Input-to-State Stability in

Probability // Automatica. 2015. V. 62. P. 284-291.

99.

Ma L., Wang Z., Lam H.K. Event-Triggered Mean-Square Consensus Control for

Time-Varying Stochastic Multi-Agent System with Sensor Saturations // IEEE

Trans. Automat. Control. 2017. V. 62. No. 7. P. 3524-3531.

100.

Дашковский С.Н., Ефимов Д.В., Сонтаг Э.Д. Устойчивость от входа к состоя-

нию и смежные свойства систем // АиТ. 2011. № 8. С. 3-40.

Dashkovskiy S.N., Efimov D.V., Sontag E.D. Input to State Stability and Allied

System Properties // Autom. Remote Control. 2011. V. 72. No. 8. P. 1579-1614.

101.

Ding D., Wang Z., Ho D.W., Wei G. Observer-Based Event-Triggering Consensus

Control for Multiagent Systems with Lossy Sensors and Cyber-Attacks

// IEEE

Trans. Cybernet. 2017. V. 47. No. 8. P. 1936-1947.

102.

Seyboth G.S., Dimarogonas D.V., Johansson K.H. Event-Based Broadcasting for

Multi-Agent Average Consensus // Automatica. 2013. V. 49. No. 1. P. 245-252.

103.

Dimarogonas D.V., Frazzoli E., Johansson K.H. Distributed Event-Triggered

Control for Multi-Agent Systems // IEEE Trans. Automat. Control. 2012. V. 57.

No. 5. P. 1291-1297.

104.

Yi X., Lu W., Chen T. Pull-Based Distributed Event-Triggered Consensus for

Multiagent Systems with Directed Topologies // IEEE Trans. Neural Netw.

Learning Syst. 2017. V. 28. No. 1. P. 71-79.

105.

Fan Y., Feng G., Wang Y., Song C. Distributed Event-Triggered Control of Multi-

Agent Systems with Combinational Measurements // Automatica. 2013. V. 49.

No. 2. P. 671-675.

106.

Garcia E., Cao Y., Yu H., Antsaklis P., Casbeer D. Decentralised Event-Triggered

Cooperative Control with Limited Communication // Int. J. Control. 2013. V. 86.

No. 9. P. 1479-1488.

107.

Chen X., Hao F., Shao M. Event-Triggered Consensus of Multi-Agent Systems

under Jointly Connected Topology // IMA J. Math. Control Inform. 2015. V. 32.

No. 3. P. 537-556.

108.

Wang X., Su H., Wang X., Chen G. Fully Distributed Event-Triggered Semiglobal

Consensus of Multi-Agent Systems with Input Saturation // IEEE Trans. Ind.

Electron. 2017. V. 64. No 6. P. 5055-5064.

109.

Mu N., Liao X., Huang T. Event-Based Consensus Control for a Linear Directed

Multiagent System with Time Delay // IEEE Trans. Circuits Syst. II: Express

Briefs. 2015. V. 62. No. 3. P. 281-285.

110.

Zhu W., Pu H., Wang D., Li H. Event-Based Consensus of Second-Order Multi-

Agent Systems with Discrete Time // Automatica. 2017. V. 79. P. 78-83.

111.

Nowzari C., Pappas G.J. Multi-Agent Coordination with Asynchronous Cloud

Access // Amer. Control Conf. (ACC), 2016. IEEE, 2016. P. 4649-4654.

112.

Yue D., Tian E., Han Q.L. A Delay System Method for Designing Event-Triggered

Controllers of Networked Control Systems // IEEE Trans. Automat. Control. 2013.

V. 58. No. 2. P. 475-481.

113.

Peng C., Han Q.-L. On Designing a Novel Self-Triggered Sampling Scheme for

Networked Control Systems with Data Losses and Communication Delays // IEEE

Trans. Industrial Electron. 2016. V. 63. No. 2. P. 1239-1248.

114.

Li H., Chen Z., Wu L., Lam H.K. Event-Triggered Control for Nonlinear Systems

under Unreliable Communication Links // IEEE Trans. Fuzzy Syst. 2017. V. 25.

No. 4. P. 813-824.

115.

Zhang X.M., Han Q.L., Yu X. Survey on Recent Advances in Networked Control

Systems // IEEE Trans. Industr. Inform. 2016. V. 12. No. 5. P. 1740-1752.

116.

Zhang X.M., Han Q.L., Zhang B.L. An Overview and Deep Investigation

on Sampled-Data-Based Event-Triggered Control and Filtering for Networked

Systems // IEEE Trans. Industr. Inform. 2017. V. 13. No. 1. P. 4-16.

117.

Cheng Y., Ugrinovskii V. Event-Triggered Leader-Following Tracking Control for

Multivariable Multi-Agent Systems // Automatica. 2016. V. 70. P. 204-210.

118.

Xie T., Liao X., Li H. Leader-Following Consensus in Second-Order Multi-Agent

Systems with Input Time Delay: An Event-Triggered Sampling Approach

Neurocomput. 2016. V. 177. P. 130-135.

119.

Cook P.A. Describing Function for a Sector Nonlinearity // Proc. Institut. Electrical

Engineers. 1973. V. 120. No. 1. P. 143-144.

120.

Фрадков А.Л., Сейфуллаев Р.Э. Дискретизация систем управления // Ана-

литическая механика, устойчивость и управление: тр. XI Междунар. Четаев-

ской конф.: пленарные доклады. Казань, 13-17 июня 2017 г. Казань: Изд-во

КНИТУ-КАИ, 2017. С. 186-193.

121.

Gao H., Wu J., Shi P. Robust Sampled-Data H_∞ Control with Stochastic

Sampling // Automatica. 2009. V. 45. No. 7. P. 1729-1736.

122.

Zhang X.M., Han Q.L. New Lyapunov-Krasovskii Functionals for Global

Asymptotic Stability of Delayed Neural Networks // IEEE Trans. Neural networks.

2009. V. 20. No. 3. P. 533-539.

123.

Zhang X.M., Han Q.L. Global Asymptotic Stability Analysis for Delayed Neural

Networks Using a Matrix-Based Quadratic Convex Approach // Neural networks.

2014. V. 54. P. 57-69.

124.

Wu X., Tang Y., Cao J., Zhang W. Distributed Consensus of Stochastic Delayed

Multi-Agent Systems under Asynchronous Switching // IEEE Trans. Cybernet.

2016. V. 46. No. 8. P. 1817-1827.

125.

Yang Z., Xu D. Stability Analysis and Design of Impulsive Control Systems with

Time Delay // IEEE Trans. Automat. Control. 2007. V. 52. No. 8. P. 1448-1454.

Статья представлена к публикации членом редколлегии А.Л. Фрадковым.

Поступила в редакцию 17.09.2018

После доработки 22.10.2018

Принята к публикации 08.11.2018