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

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

Направление подготовки: 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.	Введение в реконструкцию 3D-сцен	Проверка выполнения домашних заданий	Практическое задание: Создание панорамы
3.	Атаки на методы оценки визуального качества изображений/видео	Проверка выполнения домашних заданий	Практическое задание: Реализация нескольких методов атак на методы оценки визуального качества изображений/видео FGSM UAP
4.	Методы защиты от атак на методы оценки визуального качества изображений/видео	Проверка выполнения домашних заданий	Практическое задание: Необходимо реализовать методы защиты метрики Linearity на свое усмотрение.
5.	Карты внимания (салиентность)	Проверка выполнения домашних заданий	Практическое задание: Реализация и обучение нейронной сети для задачи предсказания карт внимания
6.	Архитектура трансформера в задачах компьютерного зрения. ViT и DETR	Проверка выполнения домашних заданий	Практическое задание: Разработка алгоритма детекции продуктов на полках магазина

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

Промежуточная аттестация проводится на основе рейтинга, сформированного по результатам текущей аттестации в течение семестра.

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

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

Computer Vision: Algorithms and Applications, 2nd ed. Richard Szeliski, The University of Washington.
Gonzalez and. Richard E. Woods' Digital Image Processing, Fourth Edition
Carion, Nicolas, et al. "End-to-end object detection with transformers." European conference on computer vision. Cham: Springer International Publishing, 2020.
Dosovitskiy, Alexey, et al. "An image is worth 16x16 words: Transformers for image recognition at scale." arXiv preprint arXiv:2010.11929 (2020).

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

An Introduction to 3D Computer Vision Techniques and Algorithms Boguslaw Cyganek and J. Paul Siebert
Computational Photography Mastering New Techniques for Lenses, Lighting, and Sensors Jack Tumblin
Ватолин, Д. С. Методы сжатия изображений : учебное пособие / Д. С. Ватолин. — 2-е изд. — Москва : ИНТУИТ, 2016. — 196 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100646

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

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

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

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

BSc: NetworkDynamicModelsAnalysisAndManagement

Contents