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