Введение к работе
Актуальность темы. Решение многих задач управления много-агентными системами сводится к анализу лапласовской матрицы ориентированного графа коммуникаций агентов и матриц, связанных с ней. Как для дискретных, так и для непрерывных моделей согласования мнений, управления группой движущихся объектов и др. знание спектра, миноров, собственных проекторов и других функций лапласовской матрицы орграфа коммуникаций позволяет ответить на основные вопросы о поведении моделируемой многоагентной системы.
В начале 2000-х годов проблема децентрализованного управления группой движущихся объектов со структурой информационных связей, задаваемой графом, изучалась в работах Факса и Мюррея. В их работах структурные свойства и собственные значения лапласовских матриц орграфа коммуникаций использовались для анализа сходимости и устойчивости группы движущихся объектов.
Позже Олфати-Сабер и Мюррей исследовали проблему достижения согласия при фиксированной и меняющейся (посредством переключений) топологии коммуникаций. Ими рассмотрены протоколы согласования без временной задержки и с временной задержкой, обеспечивающие сходимость в задаче о консенсусе. При анализе задачи о консенсусе с помощью лапласовских матриц особое внимание уделялось алгебраической связности и сбалансированности сети коммуникаций. В предложенных протоколах было установлено соотношение между связностью сети и се устойчивостью по отношению к неисправностям узлов и линий связей.
Проблема консенсуса для дискретных и непрерывных моделей с меняющейся структурой связей изучалась также в работах Джадбабаи, Лина и Морзе, где главные результаты по достижению согласия в многоагентной системе с меняющейся структурой связей получены с использованием стохастических и лапласовских матриц, связанных с орграфом коммуникаций.
Рен предложил вычислительный алгоритм для согласования траекторий при ограничениях, наложенных на управление. Этот алгоритм обеспечивает согласование траекторий в случае, когда лидеры группы и струк-
тура связей не постоянны. Алгоритм был применен для согласования траекторий движения роботов.
В более общих моделях совместного движения, рассмотренных в работах Веермана, Лаффери, Кауфмана и Вильяме, предполагается, что каждый агент характеризуется 2d параметрами (координаты и проекции скорости) в (і-мерном пространстве. Задача состоит в построении траекторий, согласованных с заданным курсом и поддерживающих предписанную конфигурацию группы объектов. Для исследования устойчивости таких систем необходимо нахождение спектра лапласовской матрицы орграфа коммуникаций. Необходимое и достаточное условие устойчивости задается системой неравенств, зависящей от элементов матрицы управления и ненулевого собственного значения лапласовской матрицы.
Следует заметить, что целый ряд кажущихся на первый взгляд никак не связанными задач о поведении динамических систем и управлении ими имеет тесную связь с проблемой консенсуса для многоагентных систем. Например, решения задач синхронизации связанных осцилляторов, перемещения мобильных агентов в группе (nocking theory), быстрого согласования в "малом мире" (fast consensus in small world networks), "рандеву" в пространстве и т.д. также связаны со спектром лапласовских матриц и другими функциями от лапласовских матриц сети коммуникаций.
Тем не менее, свойства лапласовских матриц орграфов и матриц, связанных с ними, все еще мало изучены. Указанный пробел отчасти объясняется трудностью соответствующих математических задач: исследовать действительный спектр симметричных лапласовских матриц неориентированных графов существенно легче, чем комплексный спектр лапласовских матриц орграфов. Именно этим обусловлена актуальность настоящей диссертационной работы.
Целью диссертации является разработка основ лапласовской теории орграфов для задач управления многоагентными системами, а именно:
анализ базовых моделей управления многоагентными системами, в которых главным объектом анализа являются лапласовские матрицы;
исследование собственного проектора квадратной (в частности, лапла-
совской) матрицы, играющего важную роль при решении задач согласования характеристик в управлении многоагентными системами;
исследование матриц исходящих лесов орграфов с помощью лапласов-ских матриц и их применение в децентрализованном управлении;
анализ, с использованием спектра лапласовской матрицы, структурных свойств орграфов коммуникаций, определяющих сходимость и устойчивость в децентрализованном управлении;
локализация собственных значений лапласовских матриц орграфов коммуникаций, определяющих условия устойчивости в управлении
многоагентными системами;
решение задачи действительности спектра лапласовских матриц орграфов кольцевой структуры, моделирующих распространенный тип коммуникационных сетей;
синтез процедур согласования мнений в многоагентных системах при несвязном орграфе коммуникаций.
Методы исследования. В диссертационной работе анализ структурных свойств и разработка процедур сходимости и устойчивости в управлении многоагентными системами основаны на методологии системного анализа. В качестве математического инструмента используются алгебраическая теория графов, теория матриц, теория цепей Маркова и многочлены Чебышева.
Научная новизна. В диссертации разработаны новые методы лапласовской теории орграфов, применяемые в управлении многоагентными системами.
К основным новым результатам диссертации относятся следующие:
получены явные формулы для вычисления собственного проектора произвольной матрицы, играющего важную роль при вычислении обобщенно-обратных матриц и разработке процедур управления многоагентными системами;
исследованы свойства максимальных исходящих лесов орграфа, с помощью которых описана и интерпретирована процедура ортогональ-
ной проекции при произвольной правильной матрице влияний в дискретной модели многоагентной системы управления;
получен результат, лежащий в основе критерия достижения согласия в децентрализованном управлении многоагентной системой, а именно, установлено, что нуль является простым лапласовским собственным значением орграфа коммуникаций тогда и только тогда, когда лесная размерность орграфа равна единице, т.е. когда он имеет остовное исходящее дерево;
доказана теорема, играющая существенную роль при анализе много-агентных систем, согласно которой все матрицы исходящих лесов являются матричными коэффициентами присоединенной матрицы для лапласовской матрицы. Установлено, что эти матрицы могут быть охарактеризованы как "промежуточные" матрицы влияний в управлении многоагентными системами;
для оценки процесса сходимости и условий устойчивости в децентрализованном управлении установлена взаимосвязь между кратностями нулевого и единичного собственных значений нормированной лапласовской матрицы и лапласовской матрицы дополнительного орграфа;
для оценки устойчивости в децентрализованном управлении исследована область локализации собственных значений лапласовских матриц орграфов коммуникаций;
для класса орграфов кольцевой структуры, которые моделируют распространенный тип коммуникационных сетей, решена задача существенной цикличности, т.е. получено необходимое и достаточное условие наличия собственных значений с ненулевой мнимой частью в ла-пласовском спектре орграфа коммуникаций;
предложен метод ортогональной проекции для задачи согласования мнений при нерегулярной правильной матрице влияний. Введено понятие регуляризованного предела степеней стохастической матрицы;
доказано, что матрица, через которую выражается предел решения системы дифференциальных уравнений, удовлетворяющего начальным
условиям, как и в случае дискретной модели согласования мнений, является собственным проектором лапласовской матрицы.
Практическая ценность работы. Результаты работы могут быть использованы при решении ряда задач управления многоагентными системами в рамках как дискретных, так и непрерывных моделей, а также в приложениях линейной алгебры, теории графов и сетей (в том числе — при исследовании топологии Интернета). Полученные результаты могут быть также полезными в химической информатике, кластерном анализе, построении топологических структурных индексов графов.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, в Институте вычислительной математики РАН (2004 г.), на кафедре алгебры механико-математического факультета МГУ им. М.В. Ломоносова (2011 г.), в Вычислительном центре им. А.А. Дородницына РАН (2011 г.), на общемосковском семинаре "Математические методы в экспертных оценках и анализ данных", на 34-й Международной конференции "Моделирование и имитация систем", MOSIS-2000 (Остра-ва, 2000 г.), XIV Международном симпозиуме "Управление большими системами", CONTROL-2000 (Тбилиси, 2000 г.), Международной конференции по анализу порядковых и символьных данных (Брюссель, 2000 г.), 7-й Конференции Международной федерации обществ классификации (На-мюр, 2000 г.), Международной конференции по линейной алгебре (Хайфа, 2001 г.), Международной конференции по матричному анализу и его применениям (Форт Лодердейл, 2003 г.), Международной конференции обществ GAMM и SIAM по прикладной линейной алгебре (Дюссельдорф, 2006 г.), 3-й Международной конференции по проблемам управления (Москва, 2006 г.), 2-й Международной конференции по матричным методам и операторным уравнениям (Москва, 2007г.), 16-й Международной конференции "Проблемы управления безопасностью сложных систем" (Москва, 2008 г.), Международной научной конференции "Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей" (Минск, 2009 г.), 4-й Международной конференции по проблемам
управления (Москва, 2009 г.), Международной конференции "Управление в технических системах" (С.Петербург, 2010 г.), Международных научных конференциях "Проблемы регионального и муниципального управления" (Москва, 2008, 2010, 2011 гг.), 16-й Конференции Международного общества по линейной алгебре (Пиза, 2010 г.), 17-й Конференции Международного общества по линейной алгебре (Брауншвейг, 2011 г.), 54-й Научной конференции МФТИ "Проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществе" (Москва-Долгопрудный, 2011 г.).
Публикации. Материал диссертации опубликован в 38 работах, среди которых 15 статей в ведущих рецензируемых журналах и одна монография.
Объем и структура работы. Диссертация состоит из введения, семи глав, заключения и списка литературы, число наименований в котором — 239. Содержание работы изложено на 256 страницах. В текст включено 17 рисунков.
