Агентные модели и динамика сетевых систем

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а): Парсегов С.Э., Проскурников А.В.

1. Краткая характеристика дисциплины

Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области динамики многоагентных моделей и сетевых управляемых систем, связанных с ними вопросов теории графов и линейной алгебры, а также применения указанных тем для решения прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся осваивают язык и понятия теории многоагентных систем, описываемых дифференциальными и разностными уравнениями, и принципы их исследования. В курсе вводятся базовые понятия теории графов - типы связности графов, сильно связные компоненты, циклы, матрицы Кирхгофа-Лапласа, спектры и рассматривается их связь с теорией неотрицательных матриц и марковскими цепями. Рассматриваются группы агентов, описываемых моделями порядка 1 и алгоритмы достижения консенсуса, основанные на методе последовательных усреднений, рассматриваются приложения таких систем в моделировании социальных процессов, задачах управления мобильными агентами, связь с задачами оптимизации и динамикой электрических цепей. Рассматриваются также алгоритмы синхронизации для динамических систем второго и высших порядков.

2. Перечень планируемых результатов обучения

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

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

Общая характеристика результата обучения по дисциплине

Знания: обучающийся получил систематические знания в следующих областях:

Основные свойства графов и ассоциированных с ними матриц;
Типовые модели координированного взаимодействия агентов в дискретном и непрерывном времени (социальная динамика, движение мобильных агентов, распределенное оценивание в сенсорных сетях);
Критерии сходимости алгоритмов последовательного усреднения в дискретном и непрерыв-

ном времени, достижение этими алгоритмами консенсуса;

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

Умения: обучающийся развил умения в следующих направлениях:

Построение матриц смежности, инцидентности и Лапласа произвольного (ориентированного либо неориентированного) графа, вычисление сильно связных компонент графа и исследование их апериодичности;
Ранжирование вершин графа - вычисление различных мер центральности;
Использование алгебраических критериев консенсуса и синхронизации в группах однотипных агентов, исследование скорости сходимости к консенсусу или синхронной траектории;
Применение консенсусных критериев для синтеза алгоритмов усреднения в сенсорных сетях и управления формациями мобильных агентов.

Навыки (владения): обучающийся овладел следующими навыками:

Выбор наиболее эффективного и удобного критерия исследования достижимости консенсуса (алгебраического или графового),
Нахождение значения консенсуса для систем с небольшим числом агентов.
Aнализ структуры (графа) многоагентной системы, исходя из ее математической модели
Исследование поведения однородной марковской цепи, исходя из свойств ее графа
Выбор наиболее эффективного и удобного критерия исследования многоагентной или сетевой системы в непрерывном и дискретном времени Вычисление консенсусного значения (либо синхронной траектории) для группы агентов, описываемых заданной линейной моделью.
Синтез алгоритмов синхронизации для группы однотипных агентов с моделью произвольного порядка.

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Многоагентные системы и динамические сети	Понятие агента и многоагентной системы в различных областях знания Математические модели в естественных науках: модели Висека, модели биологических формаций (модель BOIDS Рейнольдса, модель стаи Какера-Смейла), сети осцилляторов (Курамото, нейроны), модели популяций, экологические системы Многоагентные системы в инженерных науках, сети сенсоров, связанные электрические цепи и генераторы.
2.	Основные понятия теории графов, связь с матричным анализом.	Граф связей многоагентной системы Ориентированные и неориентированные графы. Основные понятия. Ориентированные и неориентированные графы. Пути, маршруты и циклы. Связность, компоненты связности, остовные деревья и леса в графе. Матрицы, ассоциированные с графом: инцидентности, смежности и Кирхгофа-Лапласа. Нагруженные графы. Ядро матрицы Лапласа и лесная размерность, теорема Гершгорина и расположение спектра. Неотрицательные матрицы и их графы. Теорема Перрона-Фробениуса. Степень матрицы и маршруты заданной длины. Неприводимость, примитивность, апериодичность матрицы в терминах графа. Масштабируемые графы и их свойства
3.	Меры центральности, марковские цепи и случайные блуждания по графу	Марковская цепь как случайное блуждание на графе. Свойства цепи в терминах графа. Стационарное распределение марковской цепи (собственный вектор Перрона-Фробениуса) как мера центральности, идея ранжирования (высший ранг имеют те, на кого ссы- лаются высокоранговые вершины). Другие меры центральности (примеры). Задача PageRank: интерпретация в терминах блуждания по графу гиперссылок, регуляризация уравнения ранжирования
4.	Консенсусные алгоритмы и сетевые модели социального влияния	Модель Френча-Харари-ДеГроота и модель Абельсона. Критерии консенсуса и сходимости. Вычисление консенсусного значения. Влиятельность социального агента по Френчу: другая интерпретация меры центральности, задаваемой собственным вектором. Модели Фридкина-Джонсена и Тейлора. Связь с PageRank, центральность Фридкина • Дальнейшее развитие: нелинейные модели с ограниченным доверием, отрицательные взаимодействия между агентами.
5.	Приложения к сенсорным сетям и мобильным роботам	Вычисление среднего значения сетью сенсоров, задача о выборе весов. Задача циклического преследования. Задача равноудаленного расположения на отрезке, удерживающее управление (containment control). Задача о создании пространственной формации мобильных агентов. Локализация спектра для специальных графов (иерархические формации)
6.	Синхронизация в сетях агентов с динамикой второго и высших порядков	Критерии устойчивости и синхронизации сети однотипных агентов в пространстве состояний. Примеры: агенты второго порядка в непрерывном и дискретном времени. Алгоритмы синхронизации с измерением абсолютной и относительной скорости. Критерий Поляка-Цыпкина: условие устойчивости и синхронизации в частотном времени. Сравнение с критерием Найквиста. Области устойчивости и синхронизации, обобщенная частотная переменная. Синтез алгоритмов синхронизации - различные подходы (линейные матричные неравенства, линейно-квадратичная оптимизация)

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Многоагентные системы и динамические сети	Для системы (1, консенсус) в дискретном времени проведите моделирование, убедитесь, что достигается среднее значение начальных условий для различных начальных условий. Для системы (2, отрезок/ RC-цепочки) покажите, что добавление новых агентов в систему сохраняет основное свойство: разность предельных состояний соседних по номерам агентов остается постоянной. Промоделируйте сеть идентичных связанных осцилляторов Курамото. Убедитесь, что если рассогласование между начальными фазами не превосходит π, то достигается синхронизация
2.	Основные понятия теории графов, связь с матричным анализом	Для пяти ориентированных и пяти неориентированных графов (число вершин 3, 4, 5, 7, 10) Исследуйте связность графа, найдите сильно связные компоненты, исследуйте их периодичность. Постройте матрицы смежности, инцидентности и Лапласа (Кирхгофа). Найдите собственные вектора и собственные числа матриц Лапласа. Подтвердите выводы о связности графов на основе анализа спектральных свойств их матриц Лапласа
3.	Меры центральности, марковские цепи и случайные блуждания по графу	Для заданной цепи Маркова постройте нагруженный граф переходов. Сопоставьте свойства цепи (возвратные и невозвратные состояния, классы связанных возвратных состояний, неразложимость, регулярность) и свойства графа. Вычислите стационарное распределение цепи. Для графа социальной сети Zachary Karate Club вершинами посчитайте различные меры центральности: степени вершин, PageRank, eigenvector (с единичной матрицей весов).
4.	Консенсусные алгоритмы и сетевые модели социального влияния	Для графов из предыдущего раздела постройте динамические модели Абельсона и Тейлора. Для произвольных начальных условий постройте траектории систем, решив соответствующие системы уравнений, и исследуйте предельное состояние (если существует). Найдите наиболее влиятельного агента в каждой из моделей. Промоделируйте модель Хегсельманна-Краузе с идентичными агентами. Покажите, что при близких начальных мнениях достигается консенсус, а на произвольных начальных данных возможен как консенсус, так и кластеризация
5.	Приложения к сенсорным сетям и мобильным роботам	Для заданного графа найдите набор весов, обеспечивающий схождение к среднему консенсусу. Найдите скорость сходимости. Промоделируйте алгоритм размещения на отрезке в 3-мерном пространстве для агентов с динамикой первого порядка в дискретном времени и в непрерывном времени. Найдите скорость сходимости алгоритмов. Промоделируйте алгоритм удерживающего управления (containment control) c 3 фиксированными лидерами в вершинах треугольника на плоскости
6.	Синхронизация в сетях агентов с динамикой второго и высших порядков	Для задачи циклического преследования на плоскости с агентами типа "двойной интегратор"а с измеряемой абсолютной скоростью введите матрицу поворота и найдите критический угол, при котором нарушается сходимость при заданном значении коэффициента усиления по скорости Для 5 агентов заданного вида в пространстве состояний и заданного неориентированного графа синтезируйте алгоритм синхронизации. Постройте на комплексной плоскости множества устойчивости и синхронизации для агентов с передаточной функцией второго порядка

Текущий контроль успеваемости обучающихся по дисциплине:

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1.	Многоагентные системы и динамические сети	Тестирование (письменное или компьютерное); Устный опрос	Что такое многоагентная система и каки компоненты ее образуют? Какие основные принципы работы многоагентной системы? Приведите примеры моделей многоагентных систем в естественных науках (принципы моделирования биологических формаций, модели популяций) и принципы их функционирования Какие способы моделирования динамики многоагентных систем вам известны и в чем их особенности? Что такое консенсус и синхронизация, приведите примеры моделей
2.	Основные понятия теории графов, связь с матричным анализом	Тестирование (письменное или компьютерное); Устный опрос	Что такое граф связей и какою роль он играет в описании многоагентной системы? Дайте определения и опишите основные признаки и свойства ориентированных и неориентированных графов. Как по графу оценить его связность (например, понять, содержит он ориентированное остовное дерево или нет)? Матрица Кирхгофа-Лапласа: дайте определение расскажите о свойствах Что такое число Фидлера и каково его значение в теории сетей и теории многоагентных систем? Сформулируйте теорему Перрона-Фробениуса и расскажите о ее применениях в теории многоагентных систем Какое следствие теоремы Агаева-Чеботарева важно при изучении задач многоагентой динамики? Перечислите известные базовые масштабируемые неориентированные графы и укажите, у какой из топологий число Фидлера не зависит от числа вершин в графе
3.	Меры центральности, марковские цепи и случайные блуждания по графу	Тестирование (письменное или компьютерное); Устный опрос	Какие меры центральности вам известны? Дайте соответсвующие определения и расскажите о свойствах той или иной меры Расскажите о взгляде на динамику марковской цепи как на случайное блуждание на графе, перечислите свойства матрицы переходных вероятностей Как структура графа связана с регулярностью (эргодичностью) марковской цепи? Как интерпретируется вектор PageRank в задаче о случайном блуждании по графу гиперссылок? Как записать линейную систему уравнений для нахождения этого вектора?
4.	Консенсусные алгоритмы и сетевые модели социального влияния	Тестирование (письменное или компьютерное); Устный опрос	Какую роль играют модели динамики мнений в теории многоагентных систем? В чем отличие консенсуса и кластеризации? Приведите примеры известных вам моделей. В чем заключается связь моделей Абельсона и Френча-Харари-ДеГроота? Покажите на примере системы из трех агентов В чем заключается связь моделей Тейлора и Фридкина-Джонсена? Покажите на примере системы из трех агентов (при наличии/остуствии одного упрямого агента) В чем суть обобщенной модели Фридкина-Джонсена с многомерными мнениями агентов? Какие нелинейные модели социального взаимодействия вам известны и в чем их особенности?
5.	Приложения к сенсорным сетям и мобильным роботам	Тестирование (письменное или компьютерное); Устный опрос	Как решается распределенным образом задача вычисления среднего значения? Как производится выбор весов? В чем специфика графа задачи циклического преследования и каковы спектральные свойства матрицы Лапласа? Приведите примеры задач удерживающего управления Для каких известных вам задач такого типа можно точно локализовать спектр матрицы Лапласа?
6.	Синхронизация в сетях агентов с динамикой второго и высших порядков	Тестирование (письменное или компьютерное); Устный опрос	В чем особенность динамики многоагентных систем с моделями агентов второго и более высоких порядков? Какого свойства матрицы Лапласа недостаточно для достижения консенсуса? Что такое область консенсуса в частотной области? Сформулируйте критерии консенсуса во временной и частотной области

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Многоагентные системы и динамические сети.	Агент и многоагентная система Модели Висека Модель Рейнольдса Модель стаи Какера-Смейла Модель Курамото Модель Лотки-Вольтерра Модель сети сенсоров Модель каскадно соединенных RC-фильтров
2.	Основные понятия теории графов, связь с матричным анализом.	Ориентированные и неориентированные графы Пути, маршруты и циклы Связность, компоненты связности Остовные деревья и леса Матрицы инцидентности, смежности и Кирхгофа-Лапласа Нагруженные (взвешенные) графы Ядро матрицы Лапласа и теорема Агаева-Чеботарева Теорема Перрона-Фробениуса Граф-звезда, граф-цикл и граф-колесо
3.	Меры центральности, марковские цепи и случайные блуждания по графу.	Марковская цепь и случайное блуждание на графе Стационарное распределение марковской цепи как мера центральности Меры центральности и их применение Задача PageRank и связь с блужданием по графу
4.	Консенсусные алгоритмы и сетевые модели социального влияния.	Модель Френча-Харари-ДеГроота Mодель Абельсона Критерии консенсуса и сходимости Модель Фридкина-Джонсена Модель Тейлора Модель Хегсельманна-Краузе Модель Деффуанта-Вейсбуха Модель Альтафини
5.	Приложения к сенсорным сетям и мобильным роботам.	Модель сети сенсоров, вычисляющих среднее значение Модели циклического преследования на прямой и плоскости, матрица поворота Модель равноудаленного расположения на отрезке Удерживающее управление Пространственная формация мобильных агентов Локализация спектра матриц Лапласа
6.	Синхронизация в сетях агентов с динамикой второго и высших порядков.	Устойчивость и синхронизация сети однотипных агентов в пространстве состояний Критерий Поляка-Цыпкина как условие устойчивости и синхронизации в частотной области

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. Что такое агент в многоагентной системе в широком смысле и какими признаками он обладает?
2. Назовите известные вам модели биологических формаций и перечислите их особенности.
3. Как устроено положение равновесия элетрической цепи из каскадно соединенных RC-фильтров, на входе и выходе которой напряжения V1 и V2, соответственно?
4. В чем отличие матриц Лапласа ориентированных и неориентированных графов? Что у них общего?
5. Какие виды связности неориентированных и ориентированных графов вам известны, дайте соответствующие определения.
6. В чем связь матриц, ассоциированных с графом, между собой?
7. Сформулируйте теорему Перрона-Фробениуса для неотрицательных матриц.
8. Связь динамики марковской цепи с моделью Френча-Харари-ДеГроота.
9. SIA-матрицы и соответствующие графы.
10. Назовите известные вам меры центральности, дайте соответствующие определения.
11. Задача PageRank и ее интерпретации.
12. Модель Френча-Харари-ДеГроота и модель Абельсона: запишите уравнения динамики, укажите, как модели взаимосвязаны.
13. Критерии консенсуса для модели Френча-Харари-ДеГроота в терминах графа взаимодействия и в терминах матрицы.
14. Модель Фридкина-Джонсена, критерии сходимости и устойчивости.
15. Многомерное обобщение модели Фридкина-Джонсена и его особенности.
16. Gossip-версия модели Фридкина-Джонсена и ее особенности.
17. Модель Тейлора, связь с моделью Фридкина-Джонсена.
18. Модель Хегсельманна-Краузе и модель Деффуанта-Вейсбуха: что общего и какие отличия.
19. Модель Альтафини и ее свойства.
20. Консенсусные усредняющие алгоритмы, применение в сетях сенсоров, выбор весов.
21. Задача циклического преследования первого порядка на прямой: особенности матрицы Лапласа и ее спектра.
22. Циклическое преследование на плоскости с матрицей поворота. Критический угол.
23. Равноудаленное расположение на отрезке как задача удерживающего управления.
24. Устройство многоагентной системы с точки зрения “пространства сложности.” Общий вид модели многоагентной системы.
25. Типовые неориентированные графы, лапласовские матрицы и спектр.
26. Локализация спектра ориентированных графов для задачи иерархического циклического преследования.
27. Однотипные системы, построенные из SISO-агентов. Виды описания, вывод характеристической функции.
28. Частотный критерий устойчивости и консенсуса Поляка-Цыпкина для однотипных систем, область консенсуса (устойчивости). Связь с критерием Найквиста.
29. Критерий консенсуса в пространстве состояний. Область консенсуса.
30. Что такое обобщенная частотная переменная?
31. Одиночная и кооперативная стабилизация, примеры.
32. Циклическое преследование второго порядка с измерением абсолютной и относительной скоростей. Явление неустойчивости для произвольного числа агентов.
33. Синтез алгоритмов сихронизации.

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

Francesco Bullo, Lectures on Network Systems, https://fbullo.github.io/lns/
Проблемы сетевого управления / Под редакцией д.т.н., проф. А. Л. Фрадкова. М., Ижевск: Институт компьютерных исследований, 2015. 392 с.
Чеботарев П.Ю., Агаев Р.П. Матричная теорема о лесах и лапласовские матрицы орграфов. - Saarbrucken: Lambert Academic Publishing GmbH, 2011. http://www.mtas.ru/search/

search_results.php?publication_id=19178

Новиков Д.А.Ак (Ред.). ТЕОРИЯ УПРАВЛЕНИЯ. ДОПОЛНИТЕЛЬНЫЕ ГЛАВЫ: Неопределенность, оптимизация, распределенность и сети, искусственный интеллект, стратегическое поведение, URSS. 2019. 552 с.

Список дополнительной литературы:

David Easley and Jon Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World, https://www.cs.cornell.edu/home/kleinber/networks-book/
Mark Newman, The structure and function of complex networks, https://arxiv.org/abs/cond-mat/0303516
Z. Li and Z. Duan, Cooperative Control of Multi-Agent Systems: A Consensus Region Approach, Boca Raton, FL, USA::CRC, 2017
W. Ren and Y. C. Cao, Distributed Coordination of Multi-Agent Networks, London, U.K.::Springer, 2011.
Ф.Р.Гантмахер. ТЕОРИЯ МАТРИЦ, 1966, 576с.

Необходимое программное обеспечение:
Matlab, Python

Методические указания для обучающихся по освоению дисциплины

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Устный/письменный опрос	Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Практические (лабораторные) занятия	ОПрактические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Разработка отдельных частей кода	Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
Выполнение домашних заданий и групповых проектов	Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.

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

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

BSc: NetworkDynamicModelsAnalysisAndManagement

Contents