Диссертация (Управление группами наблюдателей на основе мультиагентного подхода)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТНа правах рукописиЕрофеева Виктория АлександровнаУПРАВЛЕНИЕ ГРУППАМИНАБЛЮДАТЕЛЕЙ НА ОСНОВЕМУЛЬТИАГЕНТНОГО ПОДХОДА01.01.09 —Дискретная математика и математическая кибернетикаДиссертацияна соискание ученой степеникандидата физико-математических наукНаучный руководитель:доктор физико-математических наук, профессорОлег Николаевич ГраничинСанкт-Петербург2018ОглавлениеВведение . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Оценивание параметров движения объектов на основе мультиагентного подхода151.1 Оценивание параметров движения объектов на основе последовательности наблюдений . . . . . . . . . . . . . . . .171.1.1Калмановская фильтрация . . . . .

. . . . . . . . .201.1.2Стохастическая аппроксимация . . . . . . . . . . . .231.1.3Линейные матричные неравенства . . . . . . . . . .271.2 Мультиагентный подход . . . . . . . . . . . . . . . . . . . .371.3 Управление группами агентов в динамической среде . . . .382 Оптимизация распределения объектов наблюдения между наблюдателями и оценивание параметров движениягруппы объектов на основе мультиагентного подхода412.1 Постановка задачи распределенного отслеживания траекторий движущихся объектов . .

. . . . . . . . . . . . . . .422.1.1Модель наблюдений . . . . . . . . . . . . . . . . . .422.1.2Оптимизация нестационарного функционала среднего риска . . . . . . . . . . . . . . . . . . . . . . . .442.1.3Распределенная оптимизация . . . . . . . . . . . . .472.1.4Доверительные эллипсоиды . . . . . . . . . . . . . .492.2 Оптимизация распределения объектов между наблюдателями на основе решения системы линейных матричныхнеравенств . .

. . . . . . . . . . . . . . . . . . . . . . . . . .532.3 Оценивание состояний движущихся объектов . . . . . . . .5622.3.1Циклический подход . . . . . . . . . . . . . . . . . .562.3.2Верхняя граница среднеквадратической ошибки оценивания по циклическому алгоритму . . . . . . . . .582.4 Мультиагентный алгоритм отслеживания изменений параметров с применением циклического подхода . . . .

. . . .613 Имитационное моделирование653.1 Модели движения объектов . . . . . . . . . . . . . . . . . .653.2 Исследование работы алгоритма оптимизации распределения объектов между наблюдателями на основе решения системы линейных матричных неравенств . . . . . . . . . . .683.3 Оценивание траекторий движущихся объектов с помощьюалгоритма циклической стохастической аппроксимации . .71Заключение . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .75Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .763ВведениеВ соответствии со Стратегией научно-технологического развития Российской Федерации в ближайшие 10-15 лет одним из важнейших приоритетов будет «переход к передовым цифровым, интеллектуальным производственным технологиям, роботизированным системам, новым материалам и способам конструирования, создание систем обработки больших объемов данных, машинного обучения и искусственного интеллекта». Для решения указанных задач, создания соответствующих методов и технологий требуется выполнение опережающих исследований, кчислу которых можно отнести управление группами роботизированныхустройств, функционирующими в динамической среде. На сегодняшнийдень получили широкое распространение роботизированные системы, состоящие из нескольких устройств, способных реагировать на измененияво внешней среде, самостроятельно обрабатывать данные и коммуницировать с другими устройствами.

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

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

Линч (N. A. Lynch) [73],теории принятия оптимальных управленческих решений М. Х. ДеГрута (M. H. DeGroot) [50], коллективного поведения Т. Висека (T. Vicsek)[104, 105], распределенным методам принятия решений Дж. Н. Тситсиклиса (J. N. Tsitsiklis) [102,103] в области теории управления. В работах А.Джадбабаи (A. Jadbabaie), А. С. Морса (A.S. Morse) [63], Р. М. Мюррея(R. M.

Murray) [53, 81], Р. Олфати-Сабера (R. Olfati-Saber) [81], В. Рена(W. Ren) [88,89], Р. В. Берда (R. W. Beard) [88,89], Р. П. Агаева [35], П. Ю.Чеботарева [35], А. Л. Петросяна [24, 25], В. В. Захарова [101], Ф. Булло(F. Bullo) [44], Ф. Л. Льюиса (F. L. Lewis) [74] и других заложены фундаментальные принципы построения распределенных алгоритмов мультиагентной (многоагентной) координации и управления движением, обсуждаются сферы практического применения разработанных подходов корганизации коллективного поведения наблюдателей (роботов, агентов).Организация коллективного поведения групп наблюдателей включает в себя ряд задач, при этом распределение заданий в группе является неотъемлемой частью функционирования роботизированной системы.

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

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

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

Такой подход детальноизучался в работах И. В. Бычкова [6], В. И. Городецкого [14], П. О. Скобелева [14,90], Г. А. Ржевского [90], М. Вулдриджа (M. Wooldridge) [107],И. А. Каляева [23] и др.Несмотря на наличие очевидных преимуществ использования мультиагентного управления для решения сложных, комплексных задач, такой подход несет в себе некоторые трудности. Во-первых, мультиагентные системы в значительной степени опираются на возможность взаимодействия между агентами.

Коммуникации сопряжены с рядом неопределенностей, такими как: ограничения пропускной способности каналов данных, помехи при передачи данных, сетевые задержки, обрывысвязей между агентами и др. Во-вторых, в таких системах зачастуюприменяют «простые» устройства, которые обладают меньшими вычислительными ресурсами и требуют повышенной энергоэффективности.Вследствие этого требуется разработка ресурсо-эффективных алгоритмов управления, что актуализирует направление диссертационного исследования. В работах А. Недич (A. Nedic) [76, 77], Р. Олфати-Сабера(R. Olfati-Saber) [82], А.

В. Проскурникова [54,83,84], А. С. Матвеева [83]представлены результаты исследования алгоритмов распределенной оптимизации и консенсусного управления. Для задачи достижения кон6сенсуса на графах при наличии зашумленных измерений о состоянияхсоседей в работах М. Хуанга (M.

Huang) [62], М. Дж. Вайнрайта (M. J.Wainwright) [91], Д. Вергадоса (Vergados D.J.) с соавторами [106], А. Л.Фрадкова и Н. О. Амелиной [1,39] рассматривалось применение алгоритмов типа стохастической аппроксимации. Этот тип алгоритмов являетсяодним из важнейших классов среди подходов к решению задач оптимизации с неопределенностями. Сегодня стохастическая аппроксимацияимеет широкий спектр приложений в таких областях, как адаптивнаяобработка сигналов, адаптивное размещение ресурсов в коммуникационной сети, идентификация систем, адаптивное управление и других. Вработах Б. Т.

Поляка [26], Дж. С. Спалла (J. C. Spall) [94,95], В. С. Боркара (V. S. Borkar) [40], А. Б. Цыбакова [26], Х. Кушнера (H. Kushner)и Г. Г. Ина (G. G. Yin) [64] стохастическая аппроксимация используетсяс убывающими со временем до нуля размерами шагов. Сейчас возрастает использование алгоритмов стохастической аппроксимации для оптимизации нестационарных функционалов качества (изменяющихся современем).