Автоматика и телемеханика, № 8, 2015
Навигация и управление движущимися
системами
© 2015 г. Р.П. АГАЕВ, д-р физ.-мат. наук (agaraf@rambler.ru), П.Ю. ЧЕБОТАРЕВ, д-р физ.-мат. наук (pavel4e@gmail.com) (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
О МЕТОДЕ ПРОЕКЦИИ ДЛЯ НЕПРЕРЫВНОЙ МОДЕЛИ КОНСЕНСУСА1
Для случая, когда орграф зависимостей не содержит остовного входящего дерева, указана область сходимости дифференциальной модели поиска консенсуса и показано, что консенсус может быть достигнут использованием метода ортогональной проекции, который ранее был предложен для дискретной модели согласования.
1. Введение
В моделях поиска консенсуса в сетевых многоагентных системах условия достижения консенсуса, как правило, формулируются в терминах спектральных свойств лапласовской матрицы орграфа зависимостей. В частности, известно, что консенсус достигается при любых начальных условиях тогда и только тогда, когда нуль - простое собственное значение данной матрицы. Критерием этого является [1] наличие в орграфе зависимостей остовного входящего дерева. При выполнении этого условия консенсус в дифференциальной модели выражается [2-4] скалярным произведением левого собственного вектора, соответствующего нулевому собственному значению лапласовской матрицы, на вектор начального состояния. В [5, 6] установлено, что в случае произвольного орграфа зависимостей предельный вектор состояния в упомянутой модели равен произведению собственного проектора лапласовской матрицы модели на вектор начального состояния. Указанный собственный проектор совпадает со стохастической матрицей максимальных входящих лесов взвешенного орграфа зависимостей (теорема о лесах и консенсусе). Аналогичный результат для дискретной модели Де Гроота в общем случае включает предел по Чезаро.
В [7] для дискретной модели Де Гроота с правильной (но не обязательно регулярной) стохастической матрицей зависимостей предложен новый метод достижения консенсуса - метод ортогональной проекции. В [5] отмечалось, что он может быть применен также к дифференциальной модели поиска консенсуса. Это и составляет содержание настоящей статьи.
1 Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проекты №№ 13-07-00990, 13-01-13105, 13-07-13167).
В разделе 2 вводятся основные понятия, используемые в работе. Определения остальных необходимых понятий даны в [7].
2. Основные понятия и предварительные результаты
2.1. Дифференциальная модель поиска консенсуса
Рассмотрим дифференциальную модель поиска консенсуса в многоагент-ной системе [2, 3]:
(1) ¿¿(*) = и*(*),
п
(2) Мг(£) = - хз (¿)), г = 1,..., п,
3=1
где хД£) - состояние г-го агента, а^ ^ 0 - вес, с которым г-й агент учитывает расхождение в значении характеристики с ^-м агентом. А = (а^) - матрица зависимостей данной модели.
Перепишем модель (1)-(2) в матричной форме:
(3) х(г) = -Ьх(г),
где х(£) = (хх(^),..., хп(£))Т, Ь - лапласовская матрица модели (1)-(2), определяемая равенством
(4) Ь = (А1) - А, 1 = (1,..., 1)Т -
Матрица А = (а^) задает взвешенный орграф зависимостей Г с множеством вершин V(Г) = {1,..., п}: Г содержит дугу (г, с весом wij = а^ всегда, когда а^ > 0 (т.е. когда агент г зависит от агента ] или, иначе говоря, агент ] влияет на агента г). Таким образом, дуги в Г проводятся от зависимых агентов в направлении агентов, влияющих на них; вес Wij дуги (г,^) отражает степень зависимости г от
2.2. Лапласовская матрица и матрица максимальных входящих лесов орграфа
В силу определения лапласовская матрица Ь модели (1)-(2) имеет нулевые строчные суммы, следовательно, она - вырожденная, и вектор 1 = (1,..., 1)Т принадлежит ядру Ь.
Согласно теореме Гершгорина действительные части всех ненулевых собственных значений Ь строго положительны. Таким образом, все ненулевые собственные значения матрицы (-Ь), определяющей систему (3), имеют строго отрицательные действительные части.
Пусть А € Спхп - произвольная квадратная матрица, ^(А) и N (А) - соответственно образ и ядро А. Пусть V = тё А - индекс А, т.е. наименьшее к € {0,1,...}, при котором = I, где I - единичная
матрица порядка п).
Собственным проектором матрицы A, соответствующим собственному ззначению 0 (или просто собственным проектором A), называют такой проектор (т.е. идемпотентную матрицу) Z, что R(Z) = N(Av) и N(Z) = R(Av). Иными словами, Z есть проектор на n(Av) вдоль R(Av).
В [8] показано, что собственный проектор J матрицы L совпадает с нормированной матрицей J = (jks) максимальных входящих лесов орграфа зависимостей, где
fks 1 Jks = k,S = l,...,H,
f - суммарный вес2 всех остовных входящих лесов орграфа Г, fks - суммарный вес тех из них, в которых вершина s является корнем (стоком) некоторого дерева, а к принадлежит этому дереву.
3. Леса и консенсус
Пусть орграф зависимостей многоагентной системы не содержит остов-ного входящего дерева, или, что эквивалентно [1], лапласовская матрица L модели (1)-(2) имеет кратное нулевое собственное значение. Тогда [4, теорема 3.12] не для любого вектора начального состояния процесс (1)-(2) сходится к консенсусу.
Теорема 1 (о лесах и консенсусе) [5, 6]. Пусть x(t) - решение системы (3). Тогда
(5) lim x(t) = Jx(0),
t—y^o
где J - собственный проектор матрицы L, совпадающий с матрицей максимальных входящих лесов J орграфа зависимостей.
Теорема 1 является следствием выражения x(t) = e-Ltx(0) для решения системы уравнений (3) и тождества (см. [6])
(6) J = lim e-Lt.
t—ro
Результат дискретизации модели (3) совпадает (см. [5]) с моделью Де Гроота [9]
(7) y(k)= Pk y(0), к = 1, 2,...,
где y(k) - вектор состояния системы в момент к, P - строчно стохастическая матрица
(8) P := I - tl, где т > 0 - достаточно малый параметр.
2 Под весом орграфа (в том числе входящего леса) понимается произведение весов всех его дуг.
Заметим, что при
(9) 0 < т < I max ^
_, V
г '
матрица (8) - стохастическая.
Сравним асимптотические свойства моделей (3) и (7). Необходимое и достаточное условие сходимости {Pк} - апериодичность матрицы P. В то же время предел по Чезаро
1 к
(10) Р°° := lim — У^ Pi
к^ж k ^
г=1
существует для любой стохастической матрицы P и совпадает с limk^^ Pк, если последний предел существует. Если же P периодична с периодом s, то Pж = s-
-1 (P(1) + ... + PW) , где P(1),...,P(s) - пределы сходящихся подпоследовательностей {Pk}: P(г) = limj^^ Pjs+i, i = 1,... ,s.
Следующий результат - дискретный аналог теоремы 1, который нетрудно доказать [5] с использованием ряда известных результатов.
Теорема 2. Пусть последовательность y(k) удовлетворяет (7), где матрица P определена соотношениями (8)-(9). Тогда
1к
(П) Ит -5>(0 = .7У(0),
г=1
где J - собственный проектор матрицы L, который совпадает с матрицей J максимальных входящих лесов орграфа зависимостей Г, соответствующего матрице L. Более того, если (9) выполняется строго, то
(12) lim y(k) = Jy(0).
k^-ж
Таким образом, главное существенное отличие теорем 1 и 2 - необходимость использования предела по Чезаро в случае, когда параметр т модели Де Гроота принимает свое максимальное значение (9).
4. Область консенсуса
Под областью консенсуса процедуры согласования понимается множество векторов начальных условий, каждый элемент которого данной процедурой асимптотически приводится к вектору с равными компонентами, т.е. к состоянию-консенсусу. Область консенсуса процедуры (3) с матрицей Ь обозначим через Т(Ь).
Теорема 3. Для процедуры (3) с матрицей Ь имеет место Т(Ь) = = ^(Ь) ф 8рап(1), где 8рап(1) - линейная оболочка вектора 1 = (1,..., 1)т.
Доказательства теорем 3-6 приведены в Приложении.
Итак, дифференциальная модель (3) и соответствующая ей модель Де Гроота (7) имеют одну и ту же область консенсуса Т(Ь) = ^.(Ь) ф 8рап(1) за исключением случая, когда матрица Р не является правильной, что может
реализовываться лишь при т = ^шах^ ^^ а , т.е. когда т достигает своей верхней границы (9). В последнем случае реализуется лишь обобщенный «консенсус по Чезаро», как в (11). При таком обобщении область консенсуса остается неизменной, поскольку значение предела по Чезаро совпадает (теорема 2) со значением обычного предела, когда последний существует.
5. Метод ортогональной проекции для непрерывной модели
Из теории стохастических матриц следует, что сходимость к консенсусу в модели Де Гроота (7) гарантирована при любом векторе начальных мнений у(0) тогда и только тогда, когда матрица Р регулярна3. Для более общего случая правильной4 матрицы Р в [7] предложен метод ортогональной проекции, позволяющий получать некоторый квази-консенсус. Этот метод сводится к 1) преобразованию вектора начальных мнений в вектор, принадлежащий области консенсуса Т'(Ь) = ^.(Ь) Ф 8рап(1), с помощью ортогональной проекции и 2) его итеративной коррекции посредством преобразования Р.
Рассмотрим применение метода ортогональной проекции к дифференциальной модели (1)-(2). При этом уравнение (3) остается неизменным, но корректируется вектор начальных условий, а именно
(13) x(0) = Sx(0),
где S - ортогональный проектор на подпространство T(L) = R(L) ф span(1). Поэтому согласно теореме 1
(14) lim x(t) = JSx(0).
Проектор 5 может быть найден с помощью следующего предложения. Предложение 1. Ортогональный проектор Б на подпространство Т(Ь) = ^Ь) Ф 8рап(1) представляется в виде
(15) S = U (UTU )-1UT
где и - любая матрица, полученная из Ь отбрасыванием по одному столбцу, соответствующему какой-либо вершине из каждого финального класса5 орграфа зависимостей, и добавлением столбца 1 в качестве первого.
3 Стохастическая матрица называется 'регулярной [10], если кроме простого собственного значения 1 она не имеет собственных значений, по модулю равных единице.
4 Стохастическую матрицу называют правильной, если у нее нет собственных значений, имеющих единичный модуль, но не равных единице.
5 Финальный класс - множество вершин бикомпоненты, из которой не выходят дуги вовне.
Пример 1. Рассмотрим систему с матрицей зависимостей А, приведенной ниже, и найдем соответствующие матрицы Ь = diag (А1) — А и и:
0 0 \ 0 0 00 00 00 7 —3 —2
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.