авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 17 |

«Институт проблем управления им. В.А. Трапезникова РАН УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ Специальный выпуск 30.1 ...»

-- [ Страница 10 ] --

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

Первый – «Дефицит продукции» – увеличивает «Цену» на 0,69 руб. Второй – замкнутый цикл «Цена»…«Цена» – характе ризует работу рыночного регулятора, уменьшающего «Цену» на 0,16 руб. Оба процесса получения значения фактора «Цена на продукцию» и структура когнитивной карты правдоподобны.

Метод верификации когнитивной карты на основе объясне ния процессов получения значений факторов в прогнозах может быть использован совместно с методами верификации [11, 1, 2], перечисленными во введении.

Предложенный метод построения объясняющих цепочек, основанный на анализе «волны» приращений факторов в матри це прогноза, позволяет сократить время получения объяснения Управление большими системами Специальный выпуск 30.1. «Сетевые модели в управлении»

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

Литература 1. АБРАМОВА Н.А., КОВРИГА С.В. Некоторые критерии достоверности моделей на основе когнитивных карт // Про блемы управления. – 2008. – №6. – С. 23-33.

2. АБРАМОВА Н.А., КОВРИГА С.В. О рисках, связанных с ошибками экспертов и аналитиков // Проблемы управления. – 2006. – №6. – С. 60-67.

3. ВЕРТГЕЙМЕР М. Продуктивное мышление. – М.: Про гресс, 1987. – 336 с.

4. КОРМЕН Т., ЛЕЙЗЕРСОН Ч., РИВЕСТ Р. Алгоритмы:

построение и анализ. – М.: МЦНМО, 2002. – 960 с.

5. КУЛИНИЧ А.А. Когнитивная система поддержки при нятия решений «Канва» // Программные продукты и системы. – 2002. – №3. – С. 25-28.

6. КУЛИНИЧ А.А. Когнитивные карты и методы их ана лиза. // Одиннадцатая национальная конференция по искусст венному интеллекту КИИ-2008. Труды конференции. – М.: Ле нанд, 2008, – Т. 3. – С. 292-299.

7. ПОСПЕЛОВ Д.А. Десять «горячих точек» в исследова ниях по искусственному интеллекту. // Интеллектуальные сис темы (МГУ). – 1996. – Т. 1, вып.1-4. – C. 47-56.

8. РОБЕРТС Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. – М.: Наука, 1986. – 496 с.

9. СИЛОВ В.Б. Принятие стратегических решений в нечет кой обстановке. – М.: ИНПРО-РЕС, 1995. – 228 с.

10. AXELROD R. The Structure of Decision: Cognitive Maps of Political Elites. – Princeton: University Press, 1976.

11. EDEN C. Cognitive mapping // European Journal of Opera tional Research. – 1988. –№ 36. – P. 1–1 3.

12. TORGERSON W.S. Theory and Methods of scaling. – New York, 1958.

Когнитивные карты 13. WILLIAMS BRIAN C. A theory of interactions: unifying qualitative and quantitative algebraic reasoning / Artificial intelli gence. – 1991. – V. 51. – P. 39-94.

COGNITIVE MAPS VERIFICATION BASED ON PROCESSES EXPLANATION Alexander Kulinich, Institute of Control Sciences of RAS, Moscow, Cand.Sc. Senior scientist (kulinich@ipu.ru).

The cognitive maps verification method based on explanation of fac tors values forecasting processes is considered. The method is sug gested of explanations construction for qualitative cognitive maps.

Keywords: cognitive maps, verification, explanation of forecasts.

Статья представлена к публикации членом редакционной коллегии Д. А. Новиковым Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 519.177+519.217.2+517.977. ББК 22. СХОДИМОСТЬ И УСТОЙЧИВОСТЬ В ЗАДАЧАХ СОГЛАСОВАНИЯ ХАРАКТЕРИСТИК (ОБЗОР БАЗОВЫХ РЕЗУЛЬТАТОВ) Агаев Р. П. 2, Чеботарев П. Ю. (Учреждение Российской академии наук Институт проблем управления им. В. А. Трапезникова РАН, Москва) Статья представляет собой обзор базовых работ по проблеме согласования характеристик (consensus problem) в многоагент ных системах и по устойчивости соответствующих процедур.

Ее первая часть посвящена задаче согласования мнений агентов в дискретном времени. Во второй части рассмотрены более об щие задачи согласования и предполагается, что каждый агент характеризуется 2d параметрами в d-мерном евклидовом про странстве: координатами и проекциями скорости. Изучаются процедуры построения траекторий, согласованных с заданным курсом и выстраивающих (поддерживающих) предписанную кон фигурацию группы объектов. При корректировке скорости каж дый агент в качестве нового ее значения выбирает определен ную функцию от значений характеристик своих «соседей» и соб ственных характеристик. Информационные связи задаются ор графом коммуникаций агентов. Для стабилизации используется линейная обратная связь. Устойчивость движения исследуется в терминах, характеризующих связность орграфа коммуникаций.

Ключевые слова: многоагентные системы, децентрализован ное управление, граф коммуникаций, консенсус, лапласовский спектр, модель Де Гроота, устойчивость, управление.

Работа выполнена при поддержке РФФИ (грант № 09-07-00371a) и Программы Президиума РАН «Математическая теория управления».

Рафиг Пашаевич Агаев, к.т.н., с.н.с., доцент (agaraf@rambler.ru).

Павел Юрьевич Чеботарев, д.ф.-м.н., в.н.с. (pavel4e@gmail.com, Москва, ул. Профсоюзная, д. 65, тел. (495) 334-88-69).

Сетецентрическое управление и многоагентные системы 1. Введение Лишь за последние 7 лет опубликовано несколько тысяч ра бот по теоретико-графовым моделям децентрализованного управ ления в многоагентных системах. Для адекватного обзора всего этого направления подходит только формат книги. Наша задача скромнее: обсудить базовые результаты анализа двух классов мо делей. Первый из них включает модели последовательного усред нения мнений агентов в дискретном времени. Исследования этих моделей базируются на результатах теории однородных и неодно родных цепей Маркова. Второй класс объединяет модели согла сованного движения группы объектов в евклидовом пространстве с поддержанием (выстраиванием) заданной геометрической кон фигурации в непрерывном времени. Эти модели представляют ся системами линейных дифференциальных уравнений. В моде лях каждого из классов структура информационных связей между агентами задается взвешенным ориентированным графом, а свой ства траекторий процессов согласования характеристик опреде ляются спектральными свойствами лапласовской матрицы этого орграфа. Нашим приоритетом в настоящем обзоре является не широта охвата работ, а детальное рассмотрение и прослеживание генезиса базовых результатов.

2. Основные определения Решение многих задач управления многоагентными систе мами связано с исследованием спектров графов (орграфов) ком муникаций и их древесной структуры. В литературе использу ются различные матрицы соответствующих графов (см., напри мер, [13, 22]). Пусть G – взвешенный орграф. Обозначим через wij 0 вес дуги орграфа G, направленной из вершины i в верши ну j. Лапласовская матрица (или строчная лапласовская матри ца) L = L(G) = ( ij ) порядка N N для взвешенного орграфа G определяется следующим образом: ij = wij, если j = i, и ii = k=i ik, i, j = 1,..., N. Нередко вместо лапласовской матрицы строится матрица Кирхгофа, которую обычно также обо Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

значают L = ( ij ). Она определяется соотношениями ij = wji, если j = i, и ii = k=i ik, i, j = 1,..., N. Некоторые авторы [40] именно ее называют ориентированным лапласианом оргра фа. Классы матриц Кирхгофа и лапласовских матриц совпадают.

Если граф коммуникаций – неориентированный, то соответству ющую матрицу всегда называют лапласовской и обозначают че рез L.

Для орграфов коммуникаций, в которых направления дуг соответствуют направлениям информационных потоков, удобно использовать матрицы Кирхгофа. В то же время, в теории це пей Маркова для описания переходов между состояниями удобно пользоваться лапласовскими матрицами.

Неотрицательная матрица P называется примитивной 4, ес ли она неразложима и имеет лишь одно собственное значение с максимальным модулем. Стохастическая матрица – это неот рицательная матрица с единичными строчными суммами. Цепь Маркова называют ациклической, если ее матрица переходов при митивна. Стохастическую матрицу P и соответствующую ей од нородную цепь Маркова называют правильными, если у матрицы P нет собственных значений, отличных от единицы и равных по модулю единице. Если P – правильная и единица является ее однократным собственным значением, то P и соответствующую цепь называют регулярными. 5 Для регулярной цепи при k (k) пределы элементов pij матриц P k существуют и не зависят от i, но, вообще говоря, зависят от 6 j. Регулярность эквивалентна понятию SIA (Stochastic, Indecomposable, Aperiodic) 7, часто ис пользуемому в англоязычной литературе. Говорят, что две мат рицы являются однотипными, если все их ненулевые элементы Далее в терминологии в основном следуем [6].

А. Н. Колмогоров, рассмотрев эргодический принцип, показал [8, условие (22b)], что эргодичность цепи эквивалентна ее регулярности.

В [11] введено понятие положительно регулярной цепи, т.е. цепи, (k) для которой дополнительно пределы pij при k все больше нуля.

Стохастическая матрицы P является SIA, если limm P m = Q и все строки Q одинаковы.

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

Если у стохастической матрицы хотя бы один столбец це ликом положителен, то ее называют матрицей Маркова (см., на пример, [12, 20]). Класс таких матриц обозначим через M. Сто хастическая матрица P регулярна тогда и только тогда, когда для некоторого натурального r P r является матрицей Маркова.

3. Дискретные модели достижения консенсуса 3.1. Модель Де Гроота Одна из первых моделей достижения консенсуса была пред ложена и изучена М. Де Гроотом. В [23] он рассмотрел задачу согласования субъективных оценок неизвестного параметра. Эти оценки сопоставлены членам группы, действующей как единая команда. В основе согласования мнений, т.е. получения единой оценки для всей группы, лежат итерации, последовательно сбли жающие мнения агентов. Если s(0) = (s1,..., sN )T – вектор на 0 чальных мнений членов группы, а s(1) = (s1,..., sN )T – вектор 1 мнений на следующем шаге, то s(1) = P s(0), где P – стоха стическая матрица, элемент которой pij задает степень влияния мнения j-го агента на мнение i-го. На k-ом шаге получаем вектор мнений s(k) = P k s(0). Согласие достижимо, если при некотором s R для всех i имеет место limk si = s. Согласие дости k жимо при любых начальных мнениях в том и только том случае, если существует предельная матрица limk P k и все ее строки совпадают, иными словами, если матрица P регулярна. Таким об разом, в модели Де Гроота достижение консенсуса определяется сходимостью степеней стохастической матрицы влияний.

В [23] приведены некоторые достаточные условия сходимо сти степеней P k : одно из них – наличие положительного столбца в матрице P k при некотором k, т. е. принадлежность P k классу M матриц Маркова (теорема 1 в [23]);

другое – взаимная достижи мость всех состояний цепи Маркова, соответствующей матрице P, и ее апериодичность (в этом случае P примитивна) – теорема в [23].

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Вероятностный вектор 8 называют стационарным для сто хастической матрицы P, если имеет место T P = T. Стацио нарный вектор – левый собственный вектор P, соответствующий собственному значению 1.

Как отмечено в [23], согласие достигается тогда и только тогда, когда существует вектор = (1,..., N )T, такой, что для (k) всех i, j имеет место limk pij = j. Общее мнение в этом случае определяется формулой N i si. i= Если согласие достижимо при любых начальных мнениях и N согласованное мнение равно T s(0) = i i=1 i s0, то (см. тео 9 стационарный вектор рему 3 в [23]) вектор – единственный для P.

Если согласие достижимо и состояние i в цепи Маркова, определяемой P, невозвратно, то, как показано в [23], i = 0 и мнение i-го агента не влияет на согласованное мнение. Например, если матрица P имеет вид 1 1 P = 1 3 0, 4 1 1 3 3 то T = ( 3, 3, 0) и консенсус определяется формулой 3 s1 + 2 s2.

12 0 Поскольку состояние, соответствующее третьему агенту, – невоз вратное, при определении консенсуса его мнение не учитывается.

Для матрицы 1 1 1 1 0 P = 2 2 1 0 0 2 1 Вектор называется вероятностным, если все его компоненты неотрицательны и их сумма равна единице.

В действительности, еще в [6] (§ 7 главы 13) отмечалось, что если P регулярна, то из уравнения = P T вектор определяется однозначно и каждая строка матрицы предельных вероятностей есть результат его транспонирования.

Сетецентрическое управление и многоагентные системы согласие, вообще говоря, не достигается. Но оно достижимо, в частности, при s1 + s2 = s3 + s4. Существенный вопрос о том, 0 0 0 при каких начальных векторах s(0) согласие достижимо в случае нерегулярной матрицы, в [23] не изучается. Мы обсудим его в одной из следующих работ. Отметим, что здесь могут быть ис пользованы, в частности, результаты [4]. Одним из важных при менений модели Де Гроота является информационное управление в социальных сетях [3].

3.2. Обобщения модели Де Гроота Модель Де Гроота была обобщена в работе Чаттерджи и Се неты [20], где матрица коммуникаций меняется на каждом шаге, и итеративный процесс задается произведением матриц:

s(k) = Pk Pk1 · · · P1 s(0).

(1) Решение задачи согласования мнений в такой постановке сводится к исследованию сходимости неоднородных цепей Мар кова. Базовые результаты в этой области принадлежат Дж. Хадж налу [26, 27]. Так, теорема 2 из [20] аналогична приводимой ниже теореме 3, полученной в [27]. Прежде чем перейти к результа там [26, 27], приведем более раннюю теорему [12].

Рассмотрим неоднородную цепь Маркова, характеризующу юся последовательностью стохастических матриц P1, P2,..., и введем обозначение k Hk = Pi, k = 1, 2,...

(2) i= Заметим, что порядок умножения матриц Pi в (2) отличается от порядка умножения в (1).

Отметим также, что как для неоднородных цепей Маркова, так и в задачах достижения согласия не представляет интереса тривиальный случай Pi = 1v T, где v T – вероятностный вектор (см. стр. 91 в [20]). В этом случае для любой стохастической матрицы S верно SPi = Pi, причем произведение Pi S – также матрица с одинаковыми строками. Таким образом, если в моде ли (1) хотя бы один сомножитель имеет одинаковые строки, то Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

согласие уже достигнуто, и матрицы-множители, стоящие слева от матрицы с одинаковыми строками, не играют никакой роли.

Пусть K1 – множество всех примитивных матриц. В [12] отмечается, что это множество не замкнуто относительно умно жения. В K1 выделим подмножество K2 следующим образом:

P K2 тогда и только тогда, когда произведение P на любую матрицу из K1 – примитивная матрица. Нетрудно видеть, что если у примитивной матрицы все элементы главной диагонали положительны, то она принадлежит классу K2. Класс M также входит в K2.

Теорема 1 [12]. 1) Если все матрицы последовательности Hk принадлежат классу K2 и наименьший элемент каждой мат рицы не меньше некоторого фиксированного числа 0, то цепь Маркова, определяемая этой последовательностью, является эр годической.

2) Если выполняется только второе условие, то для эрго дичности цепи необходимо и достаточно, чтобы существова ла бесконечная последовательность марковских стохастических матриц вида Mni, ni1 = Pni1 +1 Pni1 +2 · · · Pni, где i = 1, 2,...

и n0 = 1.

Данная теорема весьма полезна при исследовании эргодич ности неоднородных цепей Маркова.

Рассмотрим теперь результаты Хаджнала [26, 27], также при менимые при решении задач согласования мнений в случае изме няющейся матрицы влияний.

В работе [26] рассматривается неоднородная цепь, матри ца переходных вероятностей которой на каждом шаге регулярна.

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

Пусть Ui = limk Pik, i = 1, 2,...

(k) Цепь Маркова с матрицами Hk = his (см. (2)) называется слабо эргодической, если для всех i, j, s = 1,..., N имеет место (k) (k) his hjs 0. Слабая эргодичность предполагает стремление к нулю разности между строками, но не предполагает существо вания предела матриц Hk. Цепь с матрицами Hk называют сильно Сетецентрическое управление и многоагентные системы эргодической, если для некоторого вероятностного вектора lim Hk = 1 T, (3) k где 1 – вектор из единиц. Из результатов [26] вытекает Следствие 1. Если для неоднородной цепи 1) последовательность U1, U2,... имеет предел U, 2) ряд (Uj Pj+1 Uj ) абсолютно сходится и (j) (j) 3) limk k (1 pmin ) = 0, где pmin – наименьший эле j= мент матрицы Pj, то цепь с матрицами Hk сильно эргодична.

Если выполняется только условие 3) следствия 1, то цепь – слабо эргодическая (теорема 2 в [26]).

Еще одно условие сильной эргодичности дает теорема 2.

Теорема 2 (теорема 3 в [26]). Если в неоднородной цепи Маркова все матрицы переходных вероятностей образуют ко нечное коммутативное семейство регулярных матриц, то такая цепь – сильно эргодическая.

Для неоднородной цепи Маркова, заданной последовательно стью стохастических матриц P1, P2,..., слабая эргодичность не влечет сильную. Но в модели согласования мнений Чаттерджи и Сенеты стохастические матрицы умножаются в обратном поряд ке, и можно показать, что аналоги слабой и сильной эргодичности эквивалентны. Несколько иначе обстоит дело, когда вместо по следовательности P1, P2,... используется Pr, Pr+1,..., где для данной цепи r может принимать любое натуральное значение. В этом случае для «обратного» порядка умножения стохастических матриц, как и для «прямого», сильная эргодичность не вытекает из слабой.

(r,k) Пусть Hr,k = (hij ) – стохастические матрицы, определяе мые следующим образом [27]:

k Hr,k = Pr+i, (4) i= где Pi – исходные стохастические матрицы.

В [27] изучается сходимость последовательностей Hr,k при k. Как и ранее, для цепи, характеризующейся матрицами Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Hr,k, могут быть введены понятия слабой эргодичности, когда для (r,k) (r,k) всех i, j, s = 1,..., N и r 0 имеет место (his hjs ) 0, и сильной эргодичности, когда для всех r 0 верно T lim Hr,k = 1r, (5) k где r – некоторый вероятностный вектор, зависящий от r. При сильной эргодичности (из которой следует слабая эргодичность) мнения агентов не только сближаются, но и стабилизируются.

Даже если разности между строками матрицы Hr,k не стре мятся к нулю при k, такое стремление при определенных условиях может быть обеспечено умножением Hr,k слева на одну или несколько матриц, не являющихся эргодическими.

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

1) если две матрицы принадлежат данному классу, то их про изведение также ему принадлежит;

2) наличие у цепи, удовлетворяющей определенному есте ственному условию, бесконечного числа матриц из этого класса обеспечивает ее эргодичность.

Как следует из достаточных условий сходимости степеней k [23], в качестве такого класса может быть рассмотрено мно P жество матриц, содержащих хотя бы один столбец из ненулевых элементов.

Матрицу P называют матрицей сцеплений, или скрембли рующей матрицей (scrambling matrix), если для любых двух ее строк i и j существует хотя бы один столбец k такой, что pik и pjk 0.

В [27] введена мера эргодичности (P ) для стохастической матрицы:

(P ) = min min(pik, pjk ).

(6) i, j k Легко убедиться, что P – скремблирующая матрица тогда и только тогда, когда (P ) 0.

Сетецентрическое управление и многоагентные системы Размахом m(P ) матрицы P называется величина m(P ) = max max |pik pjk |.

(7) i,j k Дж. Хаджнал показал, что размах матрицы Hk = k Pii= связан с мерами эргодичности (Pi ) следующим неравенством (теореме 2 в [27]):

k (1 (Pi )).

m(Hk ) (8) j= Следует отметить, что m(Hk ) = 0 тогда и только тогда, когда все строки Hk равны. Это утверждение вместе с неравенством (8) позволяет доказать следующее необходимое и достаточное условие эргодичности неоднородной цепи Маркова.

Теорема 3 [27]. Неоднородная цепь Маркова эргодична то гда и только тогда, когда существует разбиение последова тельности шагов (испытаний) на блоки, начинающиеся с ша гов i1 = 0, i2, i3,... и такие, что (1 (Hij,kj )) = 0, где j= kj = ij+1 ij, j N.

Из теории рядов известно, что если (Hij kj ) = 1, i = 1, 2,..., то (1 (Hij kj )) = 0 тогда и только тогда, когда j= j=1 (Hij kj ) расходится. С использованием этого факта дока зывается Следствие 2 (из теоремы 3). Если j=1 (Pj ) расходится, то цепь Маркова – эргодическая.

Кроме того, в [27] доказана следующая Лемма 1 [27]. Неоднородная цепь Маркова является эргодической, если все переходные матрицы регулярны и однотипны.

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

Теорема 4 [43]. Пусть P1,..., Pk – стохастические матри цы одного порядка. Словом длины t назовем произведение t мат риц (не обязательно различных) из этого набора. Пусть все слова – регулярные матрицы. Тогда для любого 0 существует та кое натуральное (), что для любого слова H длины t () выполняется m(H).

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Таким образом, если каждая матрица Pi, i = 1,..., k, явля ется регулярной, то при росте w разница между строками матриц Hw сходит на нет. В [43] отмечается, что одного лишь условия регулярности (SIA) матриц Pi для получения этого вывода недо статочно. Так, в следующем примере (где обозначает ненулевые элементы):

0 1 0 0 0 0 1 = 0 1 0, 010 приведенном в [12], произведение двух регулярных матриц не является примитивной матрицей.

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

3.3. Дискретная модель согласованного движения по плоскости В [41] была предложена следующая модель движения N ав тономных агентов по плоскости в разных направлениях. Направ ление движения (курс) каждого агента в дискретные моменты времени t усредняется им с направлениями движения ni (t) его соседей, находящихся на расстоянии не более r от него и состав ляющих множество Ni (t). В момент t = 0 положения агентов на плоскости произвольны;

агенты имеют одинаковые по модулю и случайные по направлению скорости. Закон движения агентов имеет вид xi (t + 1) = xi (t) + vi (t)t.

(9) Скорость агента vi (t) имеет абсолютное значение v и на правление, задаваемое углом s(t). Закон изменения направлений движения сводится к усреднению:

si (t + 1) = si (t) + sj (t), (10) 1 + ni (t) jNi (t) где ni (t) = |Ni (t)|.

В [28] были получены условия сходимости для различных конфигураций группы агентов.

Сетецентрическое управление и многоагентные системы Занумеруем все простые графы (неориентированные, без пе тель, невзвешенные) на N вершинах. Пусть P – множество их индексов. Эти графы будем обозначать Gp, p P. Обозначим через Ap и Dp матрицу смежности и диагональную матрицу ва лентностей (степеней вершин) графа Gp, где p P. Тогда модель (10) в матричной форме имеет вид s(t + 1) = F(t) s(t), (11) 1,..., sN ] – вектор направлений движения агентов, где s(t) = [st t F(t) = (I + D(t) )1 (I + A(t) ) (12) и (t) : N P – функция, моменту t сопоставляющая ин декс неориентированного графа коммуникаций в этот момент.

В [28] функция (t) названа переключающим сигналом. Сходи мость каждого состояния si (t) к s равносильна сходимости s(t) к s 1. Однако процесс может и не сходиться, если, например, для некоторого агента i при любом t N множество Ni (t) пусто.

В другом крайнем случае, если каждый агент взаимодействует со всеми остальными при всех t, то граф G(t) полон, и при любом начальном состоянии процесс сходится. Представляет ин терес промежуточный случай, когда не для всех t графы G(t) полны. Исследованию этого случая и посвящена работа [28].

Пусть Q P – множество индексов всех связных графов.

Из определения (12) матрицы Fp следует, что она стохастическая и ее диагональные элементы отличны от нуля.

Теорема 5 [28]. Если для всех t N (t) Q, то при любом s(0) верно lim s(t) = s 1, t где число s зависит только от s(0) и (t).

Поскольку в [28] рассматриваются простые (т. е. неориен тированные, невзвешенные, без петель) графы, в силу условия теоремы 5 каждая матрица Fp является примитивной, более то го, принадлежит классу K2, и ее минимальный положительный элемент не меньше N 1. Поэтому теорема 5 есть частный случай + пункта 1 теоремы 1, из которой следует, что аналог теоремы верен также и для ориентированного графа.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Условие теоремы 5 может быть ослаблено. Для этого вводит ся понятие совместной связности совокупности графов. Графы (G1,..., Gm ) совместно связны, если их объединение – связный граф. О связности группы N агентов на временном отрезке [t, ] говорят, если графы (G(t), G(t+1),..., G( ) ) совместно связ ны.

Теорема 6 [28]. Пусть начальное состояние s(0) фиксиро вано и для функции (t) имеется бесконечная совокупность по следовательных непустых ограниченных интервалов [ti, ti+1 ), i 0, такая, что на каждом из этих интервалов группа N агентов связна. Тогда lim s(t) = s 1, t где число s зависит только от s(0) и (t).

Доказательство этой теоремы основано на теореме Вольфо вица (теорема 4 выше) и на результате (см. лемму 1 в [28]), соглас но которому для любого множества индексов {p1,..., pm } P, если Gp1,..., Gpm – совместно связные графы, то произведение соответствующих стохастических матриц есть примитивная мат рица.

Пусть P есть (N 1)N матрица ранга N 1 с ядром, натяну тым на вектор 1. Нетрудно доказать 10, что матричное уравнение P Fp = Fp P, p P (13) имеет единственное решение Fp с таким спектром Sp(Fp ), что Sp(Fp ) {1} = Sp(Fp ), из чего следует P Fpi Fpi1 · · · Fp0 = Fpi Fpi1 · · · Fp0 P, p P.

(14) Сходимость произведения Fpi Fpi1 · · · Fp0 к 1cT равносильна сходимости Fpi Fpi1 · · · Fp0 к нулевой матрице. Например, если Для этого, например, в соотношении (13) матрицу P можно заме нить на квадратную, добавив к ней строку [1... 1], а Fp – на блочно диагональную матрицу из двух блоков, один из которых равен Fp, а другой – единичный.

Сетецентрическое управление и многоагентные системы p0, p1,... – бесконечная последовательность индексов, принадле жащих Q, то 11 в силу теоремы 4 выполняется lim Fpi Fpi1... Fp0 = 0.

(15) i Отметим, что (15) имеет место, если существует единствен ная положительно определенная матрица M (общая матрица Ля T пунова), для которой все матрицы Fp M Fp M, p Q являются отрицательно определенными (см., например, лемму П.19 в [10] для случая симметричных матриц).

Однако, как отмечается в [28, с. 992], все матрицы Fp, p Q могут быть стабильными (т. е. иметь спектральный радиус, мень ший единицы), но при этом может не существовать общей матри цы Ляпунова M. Поэтому подход авторов статьи, основанный на использовании метода Ляпунова для сходящейся последователь ности, не является универсальным.

Преобразуем формулу (12):

(16) F(t) = (I + D(t) )1 (I + A(t) ) = = (I + D(t) )1 (I + D(t) (D(t) A(t) )) = = I (I + D(t) )1 (D(t) A(t) ) = = I (I + D(t) )1 L(t).

Согласно (16) модель (11) представима в виде s(t + 1) = s(t) (I + D(t) )1 L(t) s(t) = s(t) + u(t).

(17) В [28] величина u(t) = (I + D(t) )1 L(t) s(t) трактуется как децентрализованное управление.

Таким образом, здесь используется общая идея децентрали зованного управления: для достижения выбранной цели (в дан ном случае – согласия) состояние каждого агента на каждом шаге корректируется с использованием «невязок» – разностей между характеристиками данного агента и его «соседей». Тем самым, управляющие воздействия формируются не централизованно, а каждым агентом отдельно – на основании его текущего состоя ния и информации, полученной от «соседей».

В силу конечности N некоторые матрицы Fp повторяются.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Теорема 6 остается верна, если в (11)–(12) заменить матрицу I + D(t) на диагональную матрицу gI, где g N. Очевидно, что и в этом случае симметричная матрица (см. (16)) Fp = I g Lp, p P остается стохастической.

Лидером называют агента i, для которого Ni =. Сле дуя [28], рассмотрим группу агентов {0, 1,..., N } с одним лиде ром;

пусть, без ограничения общности, это агент 0. Предположим, как и ранее, что все агенты движутся с одинаковыми и постоян ными по модулю скоростями, причем, в отличие от курсов других агентов, курс s лидера остается постоянным. Граф коммуникаций агентов обозначим через Gp (и множество индексов таких графов – через P), а граф, полученный из Gp удалением вершины 0 и всех инцидентных ей ребер, обозначим Gp. Для каждого агента i {1,..., N } закон изменения курса имеет вид (18) si (t + 1) = si (t) + sj (t) + bi (t), s 1 + ni (t) + bi (t) jNi (t) где bi (t) = 1, если агент i связан ребром с лидером;

в противном случае bi (t) = 0.

Пусть Bp – диагональная матрица порядка N, у которой i-ый диагональный элемент равен 1, если в графе Gp вершины i и связаны ребром. В противном случае i-ый диагональный элемент равен 0. Как и ранее, Ap – матрица смежности графа Gp.

Перепишем (18) в матричной форме:

(19) s(t+1)=(I+D(t)+B(t) )1((I+A(t) )s(t)+B(t) 1), t N{0}.

s Теорема об условиях сходимости курсов движения всех N агентов к курсу s лидера (теорема 4 в [28]) аналогична теореме 6.

При этом если графы G(t), G(t+1),..., G( ), относящиеся к интервалу [t, ], совместно связны, то говорят, что на этом интер вале все N агентов связаны с лидером.

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

(chattering) положения агентов. Чтобы ее избежать, предполага ют, что агенты обмениваются информацией и корректируют свои параметры не постоянно, а через фиксированные интервалы вре мени d 0. Тем самым задача сводится к дискретной, и для нее Сетецентрическое управление и многоагентные системы имеет место следующий результат: пусть d, s(0) и s фиксирова ны, : [0, ) P p – кусочно-постоянная функция с моментами «переключений» ti, отстоящими не менее, чем на d, и существу ет бесконечная последовательность ограниченных непересекаю щихся интервалов [ti, ti+1 ], в пределах каждого из которых все N агентов связаны с лидером. Тогда lim s(t) = s 1.

t Следует отметить, что некоторые из перечисленных выше ре зультатов [28] являются частными случаями теорем, полученных другими авторами задолго до этой работы. Так, модель, обобщаю щая (10), была изучена в работах Тситсиклиса и Бертсекаса (см., например, [39, 17]), что отмечено в их заметке [18].

Замечание 1. Теорема 6 доказана в [28] довольно рутин ным методом. Но в этом доказательстве нет необходимости, так как в силу симметричности матриц Fp требуемое утверждение может быть выведено из пункта 1 теоремы 1. Действительно, нетрудно доказать, что если F(ti ), F(ti +1),..., F(ti+1 ) – сим метричные матрицы, соответствующие совместно связным гра ti+ фам G(ti ), G(ti +1),..., G(ti+1 ), то Ti = k=ti F(k) – неразло жимая матрица с положительными диагональными элементами и Ti K. Поэтому согласно пункту 1 теоремы 1 соответствующая неоднородная цепь регулярна.

Модель, рассмотренная в данном подразделе, является связу ющим звеном между первой и второй частями настоящего обзо ра. Это «еще» дискретная модель, но «уже» модель физического движения. Во второй части обзора будут рассмотрены модели, в которых агенты, совершая групповое движение в евклидовом про странстве, динамически корректируют свои координаты и скоро сти в непрерывном времени с целью поддержания определенной геометрической конфигурации.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

4. Непрерывные модели согласования характеристик 4.1. Модель с коррекцией скоростей В этом разделе мы обсудим основные результаты из [40, 30, 29, 19, 42], касающиеся процедур построения траекторий, согла сованных с заданным курсом и выстраивающих (поддерживаю щих) предписанную конфигурацию группы объектов.

Предположим теперь, что каждый агент (объект) i из группы N объектов движется в d-мерном пространстве Rd и характери зуется 2d-мерным вектором координат и проекций скорости. В реальных приложениях d равно 2 или 3.

Пусть X = {1,..., N } R2d. Каждый элемент z X харак теризуется 2dN действительными координатами. При этом пер вые 2d компонент задают положение и скорость первого агента, следующие 2d компонент – положение и скорость второго аген та и т.д. Каждой нечетной компоненте соответствует координата агента, а четной – проекция его скорости на ту же ось. С помощью кронекерова произведения каждый элемент z X представляется в виде N ei zi, z= (20) i= где ei – N -мерный вектор с единицей в i-ой позиции и нулями в остальных позициях;

zi – вектор координат и проекций скоро сти i-го агента, имеющий 2d компонент. Если si = (si,..., si )T 1 d – положение, а v i = (v1,..., vd )T – скорость i-го агента, то z i i можно записать в виде N 1 ei si + vi z=.

(21) 0 i= Каждому i-му агенту в группе ставится в соответствие свое предписанное положение (место) в группе, задаваемое в виде hi = (hi,..., hi ) Rd.

1 d Пусть z = (z 1,..., z N )T, z i = (si, v1,..., si, vd )T, hs = (h1,..., hN )T, i i 1 d Сетецентрическое управление и многоагентные системы где верхний индекс задает номер агента.

1. Вектором конфигурации группы Определение 1.

агентов называют вектор h X, определяемый следующим образом [40, 30]:

N ei hi h=.

(22) i= 2. Орбита : R X группы поддерживает конфигурацию (formation), если для некоторого dp 1 =p +q, где q =, 0 1 dt она представляется в виде N ei = h + 1N.

(t) = h + i= 3. Группа сходится к заданной конфигурации, если существу ют вектор-функции q(·), w(·) : R Rd, для которых имеет ме сто si (t) hi q(t) 0 и v i (t) w(t) 0 при t для всех i = 1,..., N.

Каждый агент следит за характеристиками своих «соседей»;

отношение соседства не меняется. Он непрерывно усредняет (с весами) значения координат соседей, сравнивает результаты усреднения с собственными координатами и полученные разно сти сравнивает с предписанными значениями. Например, если соседями агента i являются агенты j и k, и веса, с которыми учи тываются координаты j и k, равны, то агент i вычисляет d-мерный вектор (si hi ) 1/2((sj hj ) + (sk hk )) и d-мерный вектор v i 1/2(v j + v k ). На основании полученных результатов произ водится коррекция движения агента посредством «тяги», усилия (thrust).

В общем случае для i-го агента с множеством соседей Ni Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

закон движения имеет вид si = v i (si hi )(sj hj ) +g j i v = av i+f i v1 v 1 1 1 1 1 jNi jNi....................................

(23) s = vi i d d (si hi )(sj hj ) + g j i v = av i +f i vd vd d d d d d d jNi jNi или в матричной форме z = (IN A)z + (IN K)(LN I2d )(z h), (24) где LN – матрица Кирхгофа орграфа коммуникаций на N верши нах. Элемент ij 0 тогда и только тогда, когда i-ый агент полу чает информацию непосредственно от j-го агента, т. е. последний является его соседом. В этом случае орграф коммуникаций, со ответствующий данной матрице, содержит дугу (j, i). Поскольку для квадратных матриц A и B соответственно порядка m и n име ет место тождество (Im B)(A In ) = A B, (24) определяет более компактное выражение z = (IN A)z + (LN K)(z h).

(25) В работе [42] разности между параметрами i-го агента и его соседей задаются матрицей (LN I2d )(z h), а матрица IN K рассматривается как линейный фильтр, с помощью которого может быть обеспечена сходимость к заданной конфигурации.

В данной модели матрица A имеет вид 01 A = diag,...,, (26) 0a 0a а в более общем случае 0 1 0 A = diag,..., d (27) a1 a1 a21 ad 21 22 и 00 K = diag,...,.

(28) f1 g1 fd gd В случае f1 =... = fd и g1 =... = gd эти величины обозначаем f и g.

Сетецентрическое управление и многоагентные системы Определение 2. Достижимым множеством R(v) для верши ны v орграфа называют множество, полученное объединением v со всеми вершинами, достижимыми из v. Охват 12 R – макси мальное достижимое множество.

Очевидно, если орграф сильно связен, то он имеет лишь один охват R.

Далее будем использовать следующую декомпозицию мат риц A и K порядка 2d:

4 Ai Ji, Ki Ji, A= K= (29) i=1 i= 10 01 где J1 =, J2 =, J3 =, J4 = 00 00, причем компоненты A1 и K1 задают связи позицион ных элементов с позиционными, A2 и K2 – связи позиционных элементов с компонентами скорости и т.д. При этом из физиче ских соображений можно заключить, что A1 = 0 и A2 = Id.

Введем новую переменную y:

1 y = z h 1N p +q.

(30) 0 Пусть N 1 ei i + i h=, 0 i= т. е., в отличие от (22), задаются не только положения, но и ско рости.

Предложение 1 (предложение 4.2 в [40]). Пусть орграф коммуникаций группы из N агентов фиксирован. Тогда:

1) система, описываемая уравнением (25), поддерживает за данную конфигурацию тогда и только тогда, когда в (29) A3 = 0;

при этом можно положить k = 0 для всех k;

2) при заданных конфигурации и скоростях группы имеет место p = q и q = A4 q.

Не путать с обхватом в теории графов.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

4.2. Задача устойчивости Следующее определение основано на классической связи между устойчивостью системы (сходимостью ее траекторий) и отрицательностью действительных частей собственных значений матрицы, соответствующей закону ее движения.

Определение 3 [42]. Система, заданная уравнением (25), называется устойчивой, если при некоторой матрице K для каждого ненулевого из спектра LN все собственные значе ния матрицы A + K имеют отрицательные действительные части.

Теорема 7 [42]. Пусть система (25) устойчива при неко торой матрице управления K. Тогда каждая орбита асимп тотически сходится к некоторой орбите в h + V, где V – подпространство, порождаемое линейными комбинациями век торов {i j } при всех i {1,..., k} и j {1,..., 2d}, i – векторы, образующие базис ядра LN, j – независимые решения уравнения i = Ai.

Определение 4. Непустое подмножество вершин K V (G) орграфа G называют его базовой бикомпонентой, если все вершины, принадлежащие K, взаимно достижимы и нет дуг (wj, wi ), где wi K, wj V (G)\K.

В качестве примера рассмотрим группу из 5 агентов, ор граф коммуникаций G которой имеет множество дуг E(G) = {(1, 2), (1, 3), (3, 4), (4, 3), (5, 4)}. В G две базовых бикомпо ненты: {1} и {5}. Предположим, что A4 = aI4 и h = (0, 1, 2, 3, 4)T. В качестве базиса ядра матрицы LN возьмем 1 = (1, 1, 3, 1, 0) и 2 = (0, 0, 3, 2, 1).

2 3 Поскольку A =, общее решение уравнения = A 0a при a = 0 имеет вид 1 at 1 ae c =.

eat 0 c Сетецентрическое управление и многоагентные системы При начальных условиях (0) = (p0, q0 ) подпространство V порождается кронекеровыми произведениями указанных выше векторов 1 и 2 на систему независимых частных решений из полного множества решений q0 q0 1 at p0 + e (31) 0 aa a уравнения = A.

Поскольку порядок матрицы A равен двум, число линейно независимых решений вида (31) равно двум. Поэтому размер ность пространства устойчивых решений задачи равна четырем.

4.3. Условия устойчивости Согласно предложению 1, приведенному выше, для управле ния движением группы агентов может быть использована подхо дящая матрица A в (25). Покажем, как с помощью матриц K3 и K система может быть стабилизирована (т. е. сделана устойчивой) при заданной матрице A.

Пусть = min Re() 0.

Sp(L)\{0} Предположим, что A не меняется со временем. Диагональные элементы матриц A4, K3 и K4 обозначим соответственно через am, fm и gm, где 1 m d.

Предложение 2 (предложение 5.1 в [40]). Для заданной матрицы A4 система всегда может быть стабилизирова на;

для этого достаточно выбрать (gk, fk ) такими, чтобы выполнялось fk 0, gk 0, fk gk (gk + ak ) для всех k {1,..., d} эквивалентное условие: fk 0, gk 0 и max (fk + ak gk )/gk, 0.

Критерий устойчивости системы (25) имеет более сложный вид [30];

см. подраздел 4.5.

В силу приведенных выше результатов для коррекции скоро стей агентов может быть использована матрица A4. Так, средние скорости системы q0 и q1 в моменты t = 0 и t = 1 связаны соот ношением q1 = eA4 q0. Отметим, что для диагональной матрицы Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

A4 отдельные проекции скорости не могут при данном подхо де менять знак. Кроме того, использование (31) ограничивается тем фактом, что физические характеристики лишь краткосрочно могут расти экспоненциально.

В заключение этого подраздела приведем пример, в котором система с заданной конфигурацией может менять направление движения. Предположим, что d = 2, K3 = f Id, K4 = gId, и система движется по окружности на плоскости.

Теорема 8 (теорема 5.2 в [40]). Пусть a0 0 фиксировано, 0 m fk 0, gk 0 и fk gk (gk + a0 ). Если A4 = m 2 |f + 2 gk | = 0, то группа устойчиво движется и |m| по окружности кривизны = m/v0 с постоянной скоростью v0 = 0.

4.4. Оценивание скорости сходимости к заданной конфигурации Согласно определению 3 система, заданная уравнением (25), может не быть устойчивой даже при чисто действительном спек тре матрицы LN. Это происходит, если собственные значения некоторых диагональных (2 2)-блоков матрицы A + i K при действительных i, принадлежащих спектру LN, имеют неотри цательные действительные части.

Среди собственных значений матрицы системы (25) могут быть комплексные. Характеристический многочлен системы ра вен произведению квадратных трехчленов x2 (a22 + g)x f, (32) где f, g – элементы матрицы управления K. Дискриминант урав нения x2 (a22 + g)x f = 0 есть D = (a22 + g)2 + 4f.

(33) Чтобы не допустить приближения 13 к 0 действительной части собственного значения соответствующего диагонального блока, f Это приближение привело бы к замедлению (за счет корня (32), в запись которого дискриминант входит со знаком +) сходимости к заданной конфигурации.

Сетецентрическое управление и многоагентные системы при фиксированном g подбирают так, чтобы дискриминант (33) был отрицателен и соотношение (a22 + g) f (34) выполнялось для всех из спектра LN.

Таким образом (см. утверждение 6.1 в [30]) действительные части корней (32) равны (a22 + g)/2, и показателем качества сходимости может служить величина (a22 + 1 g)/2, где 1 – наи меньшее собственное значение матрицы LN с действительным спектром.

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

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

В [29] показано, что если при некоторой матрице управления K для любой заданной конфигурации h каждое решение системы уравнений (25) сходится к h, то для матрицы A верно ai = 0, i = 1,..., d.

Как было отмечено в [30] (замечание 4.3), если нуль – соб ственное значение LN с алгебраической кратностью 1, то агенты поддерживают заданную конфигурацию h тогда и только тогда, когда (LN I2d )(x h) = 0. Действительно, ядро матрицы LN натянуто на вектор 1 RN, а ядро LN I2d – на векторы 1 ei, где {ei } – стандартный базис в R2d.

Если нуль – простое собственное значение матрицы LN ор графа коммуникаций (или, эквивалентно, если орграф коммуни каций содержит входящее корневое дерево для случая, когда дуги проводятся от лидеров и строится лапласовская матрица или же Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

содержит исходящее корневое дерево, если дуги проводятся к ли деру и строится матрица Кирхгофа [1, 22, 13]), то, как показано в [30] (теорема 4.4), устойчивость матрицы A+K для всех ненуле вых эквивалентна 14 сходимости процесса, описываемого (25), к вектору заданной конфигурации h.

Матрица A + K блочно-диагональна и каждый ее блок, по вторяющийся d раз, имеет размерность 2. Заметим, что опре делитель каждого такого блока выражается трехчленом (x) = x2 (a22 + g)x f, коэффициенты которого в общем случае комплексны. Если u = u1 + u2 i – корень (x), то u = u1 u2 i – корень многочлена (x) = x2 (a22 + g)x f. Многочлен (x) устойчив тогда и только тогда, когда устойчив многочлен (x)(x). Последний многочлен имеет четвертую степень и дей ствительные коэффициенты. Для проверки его устойчивости в [30] используется критерий Рауса–Гурвица. Напомним, что со гласно этому критерию для того, чтобы действительные части всех корней многочлена были отрицательны, необходимо и до статочно, чтобы все последовательные главные миноры матрицы Гурвица, составленной из коэффициентов многочлена, были по ложительны. Для нахождения значений f и g (элементов матрицы K), гарантирующих устойчивость многочлена (x)(x), соглас но утверждению 4.5 из [30] нужно решить следующую систему из четырех неравенств 15 относительно f и g (все остальные па постоянны и = + i):

раметры a22 g 2f + (a22 + g)2 + 2 g 2.

(35) 2 a22 f + ( + )f g f (a22 + g)2 2 f g(a22 + g) 2 f 2 В [42] показано, что если в системе уравнений движения Эта теорема в одну сторону доказана в [29] (предложение 4.3), где установлено, что если нуль – простое собственное значение матрицы LN орграфа коммуникаций, то из устойчивости матрицы A + K для всех ненулевых следует L(x h) 0. Однократность нуля как собственного значения LN в формулировку предложения 4.3 не входит, но, судя по доказательству, неявно предполагается.

Левые части этих неравенств есть определители Гурвица.

Сетецентрическое управление и многоагентные системы группы на плоскости матрица A задается как 0 a22 0 m A= 0 0 0 1, (36) 0 m 0 a то при действительном спектре матрицы коммуникаций устойчи вость матрицы A + K (т. е. отрицательность всех действитель ных частей спектра) не зависит от m, и для нее достаточно, чтобы числа f и g были отрицательными.

Для сходимости системы при не полностью действительном спектре LN кроме отрицательности f и g требуется выполне ние следующих дополнительных условий (см. утверждение 4. в [42]):

f 2 (2 + 2 );

g f || g(2 + 2 ) |m| || g для всех не действительных собственных значений = + i матрицы коммуникаций.

4.6. Группа с независимыми лидерами В этом подразделе рассмотрим поведение группы, члены ко торой следят за лидерами (т. е. агентами l, для которых Nl = ), чьи орбиты – заданные функции времени. Такие лидеры называ ются независимыми. Лидер, не являющийся независимым, назы вается зависимым. Движение зависимого лидера l, положение и скорость которого обозначим через xl и vl, определяется уравне ниями xl = vl, vl = A4 vl.

(37) По определению, каждое максимальное исходящее дерево орграфа коммуникаций может содержать не более одного лидера.

В этом случае группа объектов движется по окружности с кри визной m/v0, где v0 – скорость группы.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Предположим, что хотя бы один из лидеров является независи мым, т. е. имеет заданную априори орбиту 1 zl (t) l (t) + l (t).

0 Пусть имеется N + k агентов, из которых k – независимые лидеры. Множество вершин, соответствующих независимым ли дерам, обозначим через L. Для каждого l L положим hl = 0, т. е. положения лидеров без ограничения общности предполага ются равными нулю (вообще говоря, hl определяется из (22)).

Из соответствующей матрицы LN +k размерности N + k удалим все строки, которые соответствуют независимым лидерам. Через Li обозначим i-й столбец матрицы порядка N (N + k). Нако нец, пусть P = PN – матрица, полученная из матрицы порядка N (N + k) удалением столбцов, соответствующих независимым лидерам. Как и ранее, z – вектор положения-скорости для агентов 1,..., N. Установлена следующая Лемма 2 (лемма 6.2 в [40]). Движение группы с множе ством L независимых лидеров описывается уравнением (38) z = (IN A)z + (PN K)(z h) + Ll (Kzl (t)).

lL Проведя замену переменных y = z h, получаем y = (IN A + PN K)y + g(t) = M y + g(t).


(39) Пусть G = k Ri – представление графа в виде объеди i= нения всех охватов Ri. Проиндексируем множество охватов и определим множество I следующим образом: i I (Ri не содержит независимого лидера).

Предположим, что {i }iI – множество линейно независи мых собственных векторов, соответствующих нулевым собствен ным значениям матрицы LN.

Теорема 9 (теорема 6.4 в [40]). Пусть матрица управления K обеспечивает устойчивость системы. Предположим, что yp (t) – произвольное частное решение системы (39). Тогда каж дая орбита асимптотически сходится к орбите вида h + yp (t) + V, где V – линейная оболочка векторов {i j }iI, j{1,...,2d}, i Сетецентрическое управление и многоагентные системы принадлежит ядру LN +k, а 1,..., 2d есть 2d линейно незави симых решений системы уравнений j = Aj.

Общий вид t eM s g(s)ds y(t) = eM t y(0) + eM t решения системы уравнений (39) есть сумма любого частного решения и общего решения однородной системы линейных диф ференциальных уравнений y = (IN A + PN K)y = M y.

Тем самым, теорема 9 может быть доказана тем же способом, что и теорема 7.

Устойчивость при децентрализованном управлении группой объектов, движение которых описывается уравнением z = (IN A)z + (LN K)(z h), (40) обеспечивается [40, 30] выбором матрицы управления K. После замены переменных и приведения матрицы IN A + (LN K) к блочно-диагональному виду [30] необходимое и достаточное условие устойчивости может быть получено применением крите рия Рауса–Гурвица к диагональным блокам вида 0, (41) i f1 a22 + i f где i – ненулевые собственные значения (не обязательно дей ствительные) матрицы Кирхгофа орграфа коммуникаций. Как следует из предложения 4.5 в [30], действительность собствен ных значений i существенно упрощает условие устойчивости и оставляет б льшую свободу выбора элементов матрицы управле о ния K, действующей однородно по отношению ко всем агентам.

Необходимое и достаточное условия действительности спектра для одного специального класса орграфов (а именно, для оргра фов с кольцевой структурой) получены в [16]. Ряд характери стик переходных процессов системы, таких как затухание, сте пень устойчивости, колебательность (см., например, [14, с. 211]), Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

в децентрализованном управлении также связаны с спектром мат рицы LN орграфа коммуникаций. Как следует из [30], для отсут ствия колебаний необходима действительность спектра орграфа коммуникаций. При этом условии скорость сходимости группы к заданной конфигурации зависит как от элементов матрицы K, так и от минимального ненулевого собственного значения матрицы LN (см. предложение 6.1 в [30]). Достаточное условие устойчи вости, выполнение которого зависит от величины минимальной действительной части собственного значения LN, дано в предло жении 6.1 в [40].

5. Заключение В настоящем обзоре основное внимание было уделено двум направлениям в литературе по децентрализованному управлению многоагентными системами. Это, во-первых, работы, где анализ дискретных моделей согласования характеристик опирается на классические результаты теории цепей Маркова и стохастиче ских матриц, и, во-вторых, работы по управлению совместным движением объектов в евклидовом пространстве с выстраивани ем (поддержанием) заданной конфигурации.

Никоим образом не претендуя на полноту (как уже отме чалось во введении, в середине 2000-х годов поток работ по теоретико-графовым моделям децентрализованного управления приобрел лавинообразный характер, и в нем можно выделить це лый ряд «подпотоков»), в заключение упомянем некоторые другие существенные исследования (см. также обзор в [13]).

В начале 2000-х годов проблема децентрализованного управ ления группой движущихся объектов со структурой информаци онных связей, задаваемой графом, изучалась в [24, 25]. В [33] исследовалась проблема достижения согласия при фиксирован ной и меняющейся (посредством переключений) топологии ком муникаций. Рассмотрены протоколы согласования без временной задержки и с временной задержкой, и для обоих случаев полу чены условия сходимости. При этом специальное внимание уде лено случаю, когда орграф коммуникаций сбалансирован. Отме Сетецентрическое управление и многоагентные системы тим, что в указанной работе авторы «переоткрывают» некоторые результаты по алгебраической теории ориентированных графов, полученные в [1, 2] и известные им по переписке с авторами настоящего обзора (подробнее см. в [21]).

Исследуя алгебраическую связность в сетях «малого мира»

(small-world networks) Р. Олфати-Сабер [31] рассматривает спо собы существенного увеличения этого показателя, что, в свою очередь, значительно ускоряет процесс достижения консенсуса.

В работе также изучено соотношение между связностью сети и ее устойчивостью по отношению к неисправностям узлов и ли ний связей. Упомянем также работу [32], где приведен обзор ис следований по проблемам достижения согласия и кооперации в сетевых многоагентных системах.

Еще в одном обзоре [37], посвященном информационному согласию в многоагентном кооперативном управлении, рассмат риваются задачи сходимости процедур согласования характери стик при фиксированной и меняющейся структуре связей, а также асинхронные процедуры с временной задержкой обмена данны ми. Последний раздел этой работы посвящен синтезу алгоритмов согласования. Проблема консенсуса для дискретных и непрерыв ных моделей с меняющейся структурой связей исследовалась так же в [35]. Результаты этой работы пересекаются с результатами [28], которые частично обсуждались выше. В частности, речь идет о теореме, согласно которой для достижения согласия в системе с меняющейся структурой связей достаточно, чтобы в определен ных временных интервалах объединение графов коммуникаций содержало остовное дерево на множестве всех вершин, соответ ствующих агентам.

В недавней работе [34] был предложен вычислительный ал горитм для согласования траекторий при ограничениях, наложен ных на управление. Этот алгоритм обеспечивает согласование траекторий в случае, когда лидеры группы и структура связей меняются. Алгоритм был применен для согласования траекторий движения роботов. Реализации протоколов согласования траекто рий агентов посвящена и работа [38]. Отметим, наконец, моно Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

графию [36], которая подытоживает результаты работ по децен трализованному управлению, проведенных до 2008 г. активной группой исследователей из государственного университета штата Юта в США.

Среди русскоязычных работ по различным аспектам управ ления групповым движением упомянем здесь [5, 7, 9, 15]. Ра зумеется, отечественные исследования по данной проблематике, практически неизвестные на Западе, требуют отдельного рассмот рения и изложения в ведущих международных изданиях. В про тивном случае не подозревающим об их существовании западным авторам ничего не останется, как постепенно переоткрывать все полученные в них результаты.

Литература АГАЕВ Р. П., ЧEБОТАРЕВ П. Ю. Матрица максимальных 1.

исходящих лесов орграфа и ее применения // Автоматика и телемеханика. – 2000. – №9. – С. 15–43.

АГАЕВ Р. П., ЧEБОТАРЕВ П. Ю. Остовные леса орграфа 2.

и их применение // Автоматика и телемеханика. – 2001. – №3. – С. 108–133.

3. БАРАБАНОВ И. Н., КОРГИН Н. А., НОВИКОВ Д. А., ЧХАРТИШВИЛИ А. Г. Динамические модели информаци онного управления в социальных сетях // Автоматика и телемеханика. – 2010 (в печати).

БЛЮМИН С. Л. Мультиагентные системы: проблемы и 4.

протоколы согласия, псевдообращение лапласианов гра фов // Системы управления и информационные техноло гии. – 2007. – №2(28). – С. 4–9.

ГАБАСОВ Р., ДМИТРУК Н. М., КИРИЛЛОВА Ф. М. Оп 5.

тимальное децентрализованное управление группой дина мических объектов // Журнал вычислительной математики и математической физики. – 2008. – Vol. 48, №4. – С. 593– 609.

ГАНТМАХЕР Ф. Р. Теория матриц. – 3-е изд. – М.: Наука, 6.

1988. – 576 с.

Сетецентрическое управление и многоагентные системы ЗОЛОТУХИН Ю. Н., КОТОВ К. Ю., НЕСТЕРОВ А. А. Де 7.

централизованное управление подвижными объектами в составе маневрирующей группы // Автометрия. – 2007. – Vol. 43, №3. – C. 31–39.

КОЛМОГОРОВ А. Н. Об аналитических методах в тео 8.

рии вероятностей // Успехи математических наук. – 1938. – №5. – С. 5–41.

КУРЖАНСКИЙ А. Б. Задача управления групповым дви 9.

жением. Общие соотношения // Доклады РАН. – 2009. – Vol. 426, №1. – C. 20–25.

ПОЛЯК Б. Т., ЩЕРБАКОВ П. С. Робастная устойчивость 10.

и управление. – М.: Наука, 2002. – 303 с.

РОМАНОВСКИЙ В. И. Дискретные цепи Маркова. – М.– 11.

Л.: Гостехиздат, 1949. – 436 с.

САРЫМСАКОВ T. A. Об эргодическом принципе для неод 12.

нородных цепей Маркова // Доклады Академии наук СССР. – 1953. – Т. 90, №1. – С. 25–28.

ЧЕБОТАРЕВ П. Ю., АГАЕВ Р. П. Согласование характе 13.

ристик в многоагентных системах и спектры лапласов ских матриц орграфов // Автоматика и телемеханика. – 2009. – №3. – С. 136–151.

ФЕЛЬДБАУМ А. А., БУТКОВСКИЙ А. Г. Методы теории 14.

автоматического управления. – М.: Наука, 1971. – 744 с.

15. ФУНАСИ Р., АРАКОВА М., ТСУДА Ю., КАВАГУЧИ ДЖ.

Децентрализованное управление группой спутников с уче том информационного обмена // Труды МАИ (электрон ный журнал). – 2009. – №9.

AGAEV R. P., CHEBOTAREV P. YU. Which digraphs with 16.

ring structure are essentially cyclic? // Advances in Applied Mathematics. – 2010. – Vol. 45. – P. 232-251.

BERTSEKAS D. P., TSITSIKLIS J. N. Parallel and 17.

Distributed Computation: Numerical Methods // Englewood Cliffs, NJ: Prentice-Hall, 1989. – URL:

http://hdl.handle.net/1721.1/3719.

BERTSEKAS D. P., TSITSIKLIS J. N. Comments on 18.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»


“Coordination of groups of mobile autonomous agents using nearest neighbor rules” // IEEE Transactions Automatic Control. – 2007. – Vol. 52, No. 5. – P. 968–969.

CAUGHMAN J. S., VEERMAN J. J. P. Kernels of 19.

directed graph Laplacians // The Electronic Journal of Combinatorics. – 2006. – Vol. 13. No. 1. R39.

CHATTERJEE S., SENETA E. Towards consensus: Some 20.

convergence theorems on repeated averaging // J. Appl.

Probab. – 1977. – Vol. 14. – P. 89–97.

CHEBOTAREV P. Comments on “Consensus and cooperation 21.

in networked multi-agent systems” // Proc. IEEE. – 2010. – Vol. 98, No. 7. – P. 1353–1354.

CHEBOTAREV P., AGAEV R. Forest matrices around the 22.

Laplacian matrix // Linear Algebra Appl. – 2002. – Vol. 356. – P. 253–274.

DeGROOT M. H. Reaching a consensus // J. Amer. Statist.

23.

Assoc. – 1974. – Vol. 69, No. 345. – P. 118–121.

FAX J. A., MURRAY R. M. Graph Laplacians and 24.

Stabilization of Vehicle Formations // Proc. 15th IFAC World Congress on Automatic Control, Barcelona, Spain. – 2002.

FAX J. A., MURRAY R. M. Information flow and cooperative 25.

control of vehicle formations // IEEE Transactions Automatic Control. – 2003. – Vol. 49, No. 9. – P. 1465–1476.

HAJNAL J. The ergodic properties of non-homogeneous finite 26.

Markov chains // Proc. Cambridge Philos. Soc. – 1956. – Vol. 52. – P. 67–77.

HAJNAL J. Weak ergodicity in non-homogeneous Markov 27.

chains // Proc. Cambridge Philos. Soc. – 1958. – Vol. 54. – P. 233–246.

JADBABAIE A., LIN J., MORSE A. S. Coordination of 28.

groups of mobile autonomous agents using nearest neighbor rules // IEEE Transactions Automatic Control. – 2003. – Vol. 48, No. 6. – P. 988–1001.

29. LAFFERRIERE G., CAUGHMAN J. S., WILLIAMS A.

Graph theoretic methods in the stability of vehicle formations Сетецентрическое управление и многоагентные системы // Proc. American Control Conference ACC2004, July 2004. – P. 3729–3734.

30. LAFFERRIERE G., WILLIAMS A., CAUGHMAN J. S., VEERMAN J. J. P. Decentralized control of vehicle formations // Sys. Control Lett. – 2005. – Vol. 54, No. 9. – P. 899–910.

OLFATI-SABER R. M. Ultrafast consensus in small-world 31.

networks // Proc. American Control Conference. – 2005. – P. 2371–2378.

32. OLFATI-SABER R. M., FAX J. A., MURRAY R. M.

Consensus and cooperation in networked multi-agent systems // Proc. IEEE. – 2007. – Vol. 95, No. 1. – P. 215–233.

OLFATI-SABER R. M., MURRAY R. M. Consensus problems 33.

in networks of agents with switching topology and time-delays // IEEE Transactions Automatic Control. – 2004. – Vol. 49, No. 9. – P. 1520–1533.

REN W. Consensus tracking under directed interaction 34.

topologies: Algorithms and experiments // Transactions Control Systems Technology. – 2010. – Vol. 18, No. 1. – P. 230–237.

REN W., BEARD R. W. Consensus seeking in multiagent 35.

systems under dynamically changing interaction topologies // IEEE Transactions Automatic Control. – 2005. – Vol. 50, No. 5. – P. 655–661.

REN W., BEARD R. W. Distributed Consensus in Multi 36.

Vehicle Cooperative Control. – London: Springer-Verlag. – 2008.

REN W., BEARD R. W., ATKINS E. M. Information 37.

consensus in multivehicle cooperative control // IEEE Control Syst. Magazin. – 2007. – Vol. 27, No. 2. – P. 71–82.

38. REN W., CHAO H., BOURGEOUS W., SORENSEN N., CHEN Y.Q. Experimental validation of consensus algorithms for multivehicle cooperative control // Transactions Control Systems Technology. – 2010. – Vol. 16, No. 4. – P. 745–752.

39. TSITSIKLIS J. N., BERTSEKAS D. P., ATHANS M.

Distributed asynchronous deterministic and stochastic Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

gradient optimization algorithms // IEEE Transactions Automatic Control. – 1986. – Vol. AC-31, No. 9. – P. 803–812.

40. VEERMAN J. J. P., LAFFERRIERE G., CAUGHMAN J. S., WILLIAMS A. Flocks and formations // J. Statistical Physics. – 2005. – Vol. 121, No. 5-6. – P. 901–936.

41. VICSEK T., CZIROK A., BEN JACOB E., COHEN I., SCHOCHET O. Novel type of phase transitions in a system of self-driven particles // Phys. Rev. Lett. – 1995. – Vol. 75. – P. 1226–1229.

42. WILLIAMS A., LAFFERRIERE G., VEERMAN J. J. P.

Stable motions of vehicle formations // Proc. 44th IEEE Conference on Decision and Control, December 2005. – P. 72– 77.

WOLFOWITZ J. Products of indecomposable, aperiodic, 43.

stochastic matrices // Proc. Amer. Math. Soc. – 1963. – Vol. 15. – P. 733–736.

CONVERGENCE AND STABILITY IN CONSENSUS AND COORDINATION PROBLEMS (A SURVEY OF BASIC RESULTS) Rafig Agaev, Institute of Control Sciences of RAS, Moscow, Candidate of Science, senior researcher, senior lecturer (agaraf@rambler.ru).

Pavel Chebotarev, Institute of Control Sciences of RAS, Moscow, Doctor of Science, leading researcher (pavel4e@gmail.com, Moscow, Profsoyuznaya str., 65, (495)334-88-69).

Сетецентрическое управление и многоагентные системы Abstract: This paper is a survey of the basic results on coordination and consensus seeking in multiagent systems and on the stability of the corresponding algorithms. The first part of the paper is devoted to the consensus problem in the discrete time. The second part deals with more general problems of coordination in which every agent is characterized by 2d parameters in the Euclidean space of dimension d.

These parameters are the coordinates and velocity components of the agents. We discuss procedures of determining the trajectories converging to a given course and obeying a prescribed geometric configuration of the agents (the agents are moving in formation).

The dynamically adjusted speed of each agent is a function of the current parameters of this agent and its ”neighbors.” The information links between agents are determined by a communication digraph.

To stabilize the system, linear feedback is used. The stability of motion is studied in terms that characterize the connectivity of the communication digraph.

Keywords: multi-agent systems, decentralized control, communication digraph, consensus, coordination, Laplacian spectrum, DeGroot model, stability, control.

Статья представлена к публикации членом редакционной коллегии А. Г. Чхартишвили Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 021.8 + 025. ББК 78. СЕТЕЦЕНТРИЧЕСКОЕ УПРАВЛЕНИЕ НА СЕТЯХ ПЕТРИ В СТРУКТУРИРОВАННОЙ ДИСКРЕТНО СОБЫТИЙНОЙ СИСТЕМЕ Амбарцумян А. А. (Учреждение Российской академии наук Институт проблем управления РАН, Москва) На основе концептов сетецентрического управления разрабо тана методика синтеза управляющей cети Петри для систем автоматизации, работающих в реальном времени. Методика использует для анализа функциональности и согласованности модель СДСС – структурированная дискретно-событийная система. Определен состав модели, предложена техника анализа управляемости и моделирования объекта сетью Пет ри процесса. Разработана техника анализа сети Петри про цесса и метод синтеза супервизора – управляющей сети Пет ри, обеспечивающей совместно с сетью процесса выполнение спецификации СДСС 2.

Ключевые слова: системы управления, сетецентрические системы, логическое управление, дискретно-событийные системы, событийные модели, сети Петри.

1. Введение Определяющей тенденцией современного развития систем информатизации сложных технологических комплексов являет Александр Артемович Амбарцумян, доктор технических наук, про фессор (ambar@ipu.ru).

Работа выполнена при частичной поддержке РФФИ (проект 09-08-00559-a).

Сетецентрическое управление и многоагентные системы ся интегрирование различных задач жизнеобеспечения техноло гических процессов с их системами автоматизации, работаю щими в реальном времени (САРВ), в комплексную систему путем охвата автономных компонент сетевой структурой.

Функциональность современных САРВ интегрирует задачи контроля и управления: технологическими процессами, безо пасностью производства, защитой оборудования, технологиче ской транспортной системой, обслуживанием и ремонтами, экологическим состоянием среды и т. д. [2, 15]. Проблемы управления, обусловленные запросами обеспечения эффектив ного совместного взаимодействия разнородных систем, харак терны для многих сложных технологических комплексов энер гетики, добывающих отраслей и транспортных систем.

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

Характерная особенность сетецентрических («network centric») систем выражается в способности каждой территори ально-распределенной компоненты (узла) действовать в направ лении достижения общей цели и иметь равные возможности к доступу информации, необходимой для осуществления функций и достижения цели, вне зависимости от расположения этой информации в системе [7]. Создание сетецентрических систем стало реальностью с развитием современных IT-инструментов.

Однако наиболее известные успехи сетецентрических техноло гий в управлении военными действиями армии США стали возможны благодаря подготовленной уже ранее доктрине сете центрического стратегического управления (ССУ) военными действиями, известной как «The Strategic Theory of John Boyd (Boyd`s OODA loop)» [9]. Важнейшая черта ССУ: подготовка в сети данных для потребителей в соответствии с их задачами по принципам цикла OODA (сбор данных под задачи, оценка ситуации, принятие решения и его реализация).

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Вместе с тем в проектировании интегрированных САРВ системные решения всегда являются творческим озарением проектантов, а не результатом каких либо аналитических по строений, и, как правило, эти решения основаны на интуитив ных методах и искусстве системотехника [2, 15, 16]. Вследствие этого структура сетевых решений в основном формируется на основе естественной топологии расположения автономных компонент и выполняет функциональность, обусловленную только потребностями транспортирования данных. Поэтому, по мнению автора, концепты (методы) управления, ориентирован ные на вовлечение в процесс достижения цели (выполнения миссии) всех компонент системы, и доступность любой инфор мации, требуемой для принятия управленческого решения, для систем промышленной автоматизации нуждаются в развитии.

Подходом к проектированию управления оборудованием с дискретным поведением, наиболее близко соответствующим концепции ССУ, на наш взгляд, является дискретно-событийное моделирование, включая парадигму супервизорного управления [18, 20].

Отличительной особенностью теории супервизорного управления в рамках дискретно-событийной системы (ДСС) является моделирование управляемого объекта тройкой компо нент:

· G – собственно объект управления, рассматриваемый как генератора языка L(G);

· спецификация К – это ограничения и востребованная функциональность G, задаваемая тоже как язык K L(G);

· супервизор S – управляющая компонента в ДСС обеспе чивающая поведение G, в соответствии с ограничениями (спе цификацией) K.

При этом S должен быть неблокирующим – не содержать тупиков и «живых циклов» (ловушек).

В рамках определенного триплета G, K, S в теории суперви зорного управления поставлена и решена задача формального синтеза неблокирующего S по L(G) и K. Постановка и решение Сетецентрическое управление и многоагентные системы задачи синтеза создает теоретический базис для гарантирован ного проектирования событийного (часто – автоматного) управ ления, принципиально отличающийся от традиционного подхо да к проектированию логического управления как расшифровки двух черных ящиков – объекта управления и алгоритма управ ления, интуитивно соответствующих друг другу. Справедливо сти ради нужно заметить, что очень близкая постановка была известна в русскоязычной литературе по теории конечных автоматов еще в 70-е годы (см., например, работы ученых шко лы члена-корреспондента М.А. Гаврилова [4, 5] и наиболее близко – исследования в коллективе профессора А.А. Таля [8, 11, 13]). В работе [11] для пары «черный ящик – объект управления» и «черный ящик – система управления» введена конструкция «взаимодействующие автоматы»;

определены понятия управляемости и наблюдаемости, сформулированы и исследованы условия их выполнения и синтез управляющего автомата по заданному поведению автомата – объекта. Обобще ние этих и многих других результатов приведено в монографии [8]. Однако концентрация исследования на уже вполне опреде ленном поведении управляемого объекта методологически значительно сложнее, чем определение поведения пары: ничем не ограниченного объекта и требований (ограничений) к его поведению. Возможно, по этой причине практического прило жения за этими исследованиями не последовало.

Поток публикаций по ДСС в зарубежной литературе огро мен. Укажем пионерскую работу [24] и обобщающую моногра фию [18]. Две основные трудности в практическом использова нии ДСС-моделирования: первая заключается в размерности модели объекта управления – G (для реальных задач число состояний конечного автомата порядка несколько тысяч);

вто рая – в мультипликативной зависимости сложности супервизо ра, от сложности объекта G и сложности спецификации K. Для преодоления этих затруднений разработаны методы модульного синтеза супервизора по G. При этом предложены различные схемы управления: дизъюнктивная, конъюнктивная, иерархиче Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

ская, обобщенная (см. первую известную работу [26], развитие и обобщение в работе [28]). Разработаны методы синтеза по модульному описанию G = G1, G2, …, Gn и модульному заданию спецификации K = K1, K2, …, Kn модульного супер визора S [19, 14, 21]. Однако сложность модульного синтеза и слабое соответствие структуры исходных спецификаций резуль тату делают предложенные методы малопривлекательными для практического применения. Сохранение исходной модульности для отдельных классов ДСС достаточно эффективно обеспечи вается использованием сетей Петри (СП) как аппарата описания и синтеза супервизорного управления в ДСС (работы [20, 23, 27] и многие другие).

Использование сетей Петри как аппарата анализ и синтеза управления для систем промышленной автоматизации известно и раннее. В работах 70-х годов – М. Хэка и многих других авторов (обзор можно найти в [25]) – исследовались методы анализа поведения сложных производственных систем на сетях Петри (СП). В русскоязычной литературе известны исследова ния С.А. Юдицкого [12] по иерархическим СП для задачи опи сания и анализа производственных систем.

Характерна следующая постановка исследований 70-80 гг.

прошлого века по СП для управления промышленными систе мами: задана СП S, предполагается, что она определяет алго ритм управления. Задача синтеза – отвечает ли S определенным требованиям (безопасность, живучесть и т. п.) и если да, то, как преобразовать алгоритм, заданный S, в иной вид (конечный автомат, программу или устройство).

В ДСС постановка задачи управления кардинально отлича ется: дана СП S1, моделирующая ничем не ограниченное пове дение объекта управления G. Определены ограничения на пове дение G – спецификация K. Задача: существует ли СП S2, дополняющая S1 (говорят: встроенная в контур обратной связи по определенным правилам) такая, что совместно (S1 и S2) удов летворяют K. Если S2c существует, то как эту сеть синтезировать.

Сетецентрическое управление и многоагентные системы Использование СП как аппарата моделирования ДСС и синтеза супервизора (работы [20, 23] и многие другие) ориенти рованы, прежде всего, на модульный синтез для отдельных классов ДСС. Метод, предложенный в работе [23], основан на использовании анализа запрещенных состояний и, в общем случае, синтез сети супервизора (как дополнение сети процесса) решается методами целочисленного программирования. Мето ды в работах [20, 27] основываются на матричном представле нии СП и используют технику инвариантов позиций. Эти мето ды дают хорошие решения для управления ресурсным взаимодействием компонент ДСС (выполнение ограничений на количество одновременно активных компонент или задейство ванных ресурсов), но эта техника неэффективна при задании спецификации в виде порядка срабатывания всех переходов.

Однако для САРВ характерно задание спецификации именно в виде требуемой последовательности операций актуаторов.

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

Имеется несколько резонов в такой постановке:

Во-первых, легко реализуется развитие системы. К измене ниям отдельных компонент предъявляется лишь требование сохранения операций (команд) взаимодействия. Добавление новых компонент затрагивает только модуль координации – супервизор.

Во-вторых, повышается живучесть системы.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

В-третьих, смена стратегии (общей цели) затрагивает толь ко супервизор, что может быть реализовано сменой «матрицы»

взаимодействия.

В работах [1, 3] предложена модель структурированной дискретно-событийной системы СДСС, в рамках которой моде лирование проводится на двух уровнях. Первый – это компо ненты СДСС – актуаторы G = (G1, G2, …, Gn). Поведение каж дой компоненты Gi определяется конечным автоматом – генератором языка L(Gi). Второй уровень – это спецификация требуемого поведения СДСС в языке команд и условий K (яв ляющегося проекцией L(G)). Получены условия управляемости и предложен метод синтеза супервизора, которые выполняются с линейной сложностью от сложности спецификации. При этом, несмотря на модульность задания СДСС, супервизор конструи руется как единый модуль второго уровня управления.

В настоящей работе (в развитие работ [1, 3]) ставится сле дующая задача: в рамках ДСС разработать методику анализа и проектирования супервизора, ориентированную на сохранение структурного подобия результатов проектирования и исходных описаний поведения объекта управления. Сохранение структур ного подобия предлагается обеспечить использованием для управления операциями АК их моделей, а на уровень суперви зора перенести только передачу управления между модулями, представляющими АК. В методике предлагается данные о ДСС последовательно формировать в моделях: набор конечных автоматов (этап описания данных о структуре объекта), строки команд (событий) на исполнение операций оборудованием (этап формирование требований технологов на последовательности операций);

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

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



Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 17 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.