Консенсусное мультиагентное управление стохастическими системами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

АМЕЛИНА Наталья Олеговна

КОНСЕНСУСНОЕ МУЛЬТИАГЕНТНОЕ УПРАВЛЕНИЕ СТОХАСТИЧЕСКИМИ СИСТЕМАМИ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

О ,чГіг ¿ІІІ*

Санкт-Петербург 2012

005018167

Работа выполнена на кафедре теоретической кибернетики математико-механическ факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор технических наук,

профессор ФРАДКОВ Александр Львович

Официальные оппоненты: доктор технических наук,

профессор ТИМОФЕЕВ Адиль Васильевич (Санкт-Петербургский государственный университет)

доктор физико-математических наук, доцент ХЛЕБНИКОВ Михаил Владимирович (Институт проблем управления им. В. А. Трапезникова РАН)

Ведущая организация: Учреждение Российской академии наук

Институт проблем управления сложными системами РАН (г. Самара)

Защита состоится Ф'Л&Л^ 2012 года в часов на заседании совета

Д 212.232.29 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199034, Университетская наб., д. 7/9, ауд. 133.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан " 2012 г.

Ученый секретарь

диссертационного совета Д 212.232.29, доктор физико-математических наук, профессор

В. М. Нежинскиі

Общая характеристика работы

Актуальность темы. Задачи управления и распределенною взаимодействия в сетях динамических систем привлекают в последнее десятилетие все большее число исследователей. Во многом это объясняется широким применением мультиагент-ных систем в разных областях. В работах Р.П. Агаева, Б.Р. Андриевского, Р.В. Бер-да (R.W. Beard), Ф. Булло (F. Bullo), A.A. Воронова, И.А. Каляева, Д. Кортеса (J. Cortes), A.C. Матвеева, Б.М. Миркина, P.M. Мюррея (R.M. Murray), Р. Олфати-Сабера (R. Olfati-Saber), A.B. Проскурникова, В. Pena (W. Ren), А. Савкина, A.B. Тимофеева, А.Л. Фрадкова, П.Ю. Чеботарева, П.С. Щербакова, М. Эгсрстадта (М. Egcr-stedt), В.А. Якубовича и их учеников заложены основы теоретического описания методов анализа и синтеза децентрализованного адаптивного мультиагентиого управления, и дан широкий круг возможных практических приложений в управлении сложными производственными, энергетическими и техническими системами.

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

Д. Армбрустср (D. Armbrustcr), А. Глашепко, В.И. Городецкий, И. Грачев, С. Иноземцев, К. Капепко, И.А. Каляев, A.C. Михайлов, П.О. Скобелев и др. активно изучали алгоритмы управления в вычислительных, производственных сетях, сетях обслуживания, транспортных и логистических сетях, узлы которых выполняют определенные действия параллельно. Зачастую качество работы достаточно простых адаптивных алгоритмов оказывается удовлетворительным, но остаются открытыми вопросы их теоретического обоснования и достижения оптимальной производительности.

Для исследования динамики стохастической дискретной системы достаточно часто применяется имеющий широкое распространение в современной теории управления, теории динамических систем и нелинейной механики метод усредненных моделей, описанный в работах Д.П. Деревицкого, Г. Кушнера (H.J. Kushner), Л. Лыон-га (L. Ljung), С.М. Мсеркова, А.Л. Фрадкова и др., который позволяет свести тс или иные задачи к изучению соответствующей усредненной (дискретной или неире-

рывной) модели.

Для решения задачи достижения консенсуса группой взаимодействующих агентов, обменивающихся информацией, в работах М. Атапса (М. Äthans), Д.П. Берт-секаса (D.P. Bertsekas), Д. Мантона (J.H. Mantón), P.M. Мюррея (R.M. Murray), Р. Олфати-Сабера (R. Olfati-Saber), В. Репа (W. Ren), M. Хуапга (М. Huang), Д.Н. Цициклиса (J.N. Tsitsiklis) и др. предлагается использовать алгоритмы типа стохастического градиента, которые ранее положительно зарекомендовали себя в адаптивных системах (Я.З. Цыпкин, Б.Т. Поляк, В.Н. Фомин, О.Н. Граиичин, Дж. Спал (J.C. Spall), Г. Кушнер (H.J. Kushner), Г. Ип (G.G. Yin) и др). При динамических внешних изменениях состояний агентов с течением времени (поступлении новых заданий и т. п.) алгоритмы стохастической аппроксимации с уменьшающимся до нуля размером шага неработоспособны.

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

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

1) исследовать поведение состояний агентов с нелинейной динамикой при переменной структуре связей, помехах в наблюдениях и отсутствии задержек в измерениях;

2) найти условия достижения среднеквадратичного приближенного консенсуса в мультиагентной системе с помехами и переключающейся структурой связей в сети при отсутствии и при наличии задержек в измерениях;

3) исследовать поведение траекторий состояний агентов дискретной стохастической системы при переменной структуре связей, помехах и задержках в наблюдениях;

4) исследовать возможности применения в управлении загрузкой узлов децен-

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

Методы исследования. В диссертации применяются методы теорий управления, вероятностей и математической статистики, оценивания и оптимизации, теории графов, а также имитационное моделирование.

Основные результаты. В работе получены следующие основные научные результаты в условиях применения в контурах управления агентов протокола локального голосования:

1) построены оценки среднеквадратичной близости траекторий дискретной стохастической системы, описывающей поведение состояний агентов с нелинейной динамикой при консенсусном управлении, переменной структуре связей и помехах в наблюдениях, к траекториям ее непрерывной детерминированной модели при отсутствии задержек в измерениях;

2) сформулированы условия достижения среднеквадратичного приближенного консенсуса в мультиагентпой системе с помехами и переменной структурой связей в сети при отсутствии и при наличии задержек в измерениях;

3) получены оценки среднеквадратичной близости траекторий дискретной стохастической системы, описывающей поведение состояний агентов с нелинейной динамикой при консенсусном управлении, переменной структуре связей, помехах и задержках в наблюдениях, к траекториям ее дискретной усредненной модели;

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

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

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

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

Апробация работы. Результаты диссертации докладывались на семинарах кафедр теоретической кибернетики и системного программирования математико-ме-ханичсского факультета СПбГУ, на российских и международных конференциях но оптимизации и теории управления: Второй и Третьей традиционных всероссийских молодежных летних школах "Управление, информация и оптимизация" (Переславль-Залесский, Россия, 20-27 июня, 2010; rioc. Ярополец, Московская обл., Россия, 12-19 июня, 2011), 3-й Мультикопфсреиции но проблемам управления (Санкт-Петербург, 12-И октября 2010), научно-техническом семинаре "Управление в распределенных сетецентрических и мультиагентных системах" (Санкт-Петербург, 12-14 октября, 2010), 2-й Межвузовской научной конференции по проблемам информатики СПИСОК-2011 (Санкт-Петербург, 27-29 апреля, 2011), 5th

>

International Conference on Physics and Control (5-8 September, 2011, Leon, Spain), Международной научно-практической мультикопферепции "Управление большими системами" (Институт проблем управления им. В.А. Трапезникова РАН, Москва, 14-16 ноября 2011 года), Международной студенческой конференции "Science and Progress" (Санкт-Петербург, 14-18 ноября, 2011). Проект "Разработка алгоритма для балансировки загрузки узлов децентрализованной вычислительной сети", основанный па материалах диссертации, был представлен па Международной суперком-пьютерпой конференции "Научит,їй сервис в сети Интернет: экзафлопеное будущее" (Новороссийск, Россия, 19-24 сентября, 2011), проект "Мулътиагептпая система для управления распределенными вычислительными блоками" на конкурсе проектов Лаборатории СПРИНТ-Intel 2010 был отмечен дипломом "За лучший проект". Вы-

полненный в ходе работы над диссертацией проект "Балансировка загрузки сети при неполной информации и задержках в измерениях" был отмечен дипломом победителя конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2011 г.

Результаты диссертации были частично использованы в работе но гранту РФФИ 11-08-01218-а и ФЦП "Кадры" (госконтракт №10.740.11.0042). Результаты диссертации использованы при выполнении работ по проекту "Мультиагептмая система для управления группой легких беспилотных летательных аппаратов" в рамках программы "СТАРТ-10" Фонда содействия развитию малых форм предприятий в научно-технической сфере. По материалам работы было получено свидетельство об официальной регистрации программы для ЭВМ № 2010G12G84 "SmartFly Together" от 19 апреля 2010 г..

Публикация результатов. Основные результаты исследований отражены в работах [1-13]. Статьи [1, 5, 6] опубликованы в ведущих рецензируемых научных журналах.

Работы [6, 8, 10, 13] написаны в соавторстве. В [б] И.О. Амелиной принадлежит методика формализации математической модели, а соавторам — общая постановка задачи, детализация алгоритмов управлении и результаты имитационного моделирования. В работах [8, 10, 13] A.JI. Фрадкову принадлежат общие постановки задач, а Н.О. Амелиной — реализация описываемых методов, формулировки и доказательства теорем, разработка демонстрационных примеров и программных средств. Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 133 источника. Текст занимает 87 страниц и содержит 6 рисунков.

Содержание работы

Во введении обосновывается актуальность тематики диссертационной работы, ставятся задачи исследования и кратко излагаются ее основные результаты.

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

постановке.

Рассмотрим динамическую сеть из набора агентов (узлов) N = {1,2,... ,п}. Граф (Лг, Е) определяется N и набором (множеством) ребер или дуг Е. Множеством соседей узла г называется N' = {у : (}, г) 6 Е}, т. е. множество узлов с ребрами, входящими в í. Сопоставив каждому ребру г) 6 Е вес а'^ > 0, определяем матрицу смежности (или связности) А — [а1'3] графа, обозначаемого далее Я а (здесь и далее верхние индексы у переменных показывают соответствующие номера узлов). Определим взвешенную полустепень захода вершины г как сумму г-й строки матрицы А: <Р(А) = а''3 ■

Каждому агенту г е N в момент времени I = 0,1, 2 ... ,Т сопоставляется изменяющееся во времени состояние х\ € К, динамики которых описываются разностными уравнениями

= + /'(*{, и!) (1)

с некоторыми функциями /'(-, ■:) : Е х 1 -> К, зависящими от состояний в предшествующий момент времени х\ и управляющих воздействий и\ 6 К, которые в момент времени t воздействуют на узел г.

Будем рассматривать сетевую (мультиагептиую) систему, состоящую из динамических агентов с входами и\, выходами у\'г и состояниями х).

Узлы г и ] называются согласованными в сети в момент времени Ь тогда и только тогда, когда х) = х] . >

Задача о достижении консенсуса — это согласование всех узлов между собой, т. с. требуется найти такой протокол управления, который переводит все состояния в одно и то же постоянное значение х* = х', \/г 6 N.

Под консенсусиым управлением будем понимать управление, обеспечивающее достижение консенсуса.

Будем считать, что структура связей динамической сети моделируется с помощью последовательности ориентированных графов {(./V,£0}/>о, где Et С Е меняются во времени. Если г) е Е1, то говорим, что узел г в момент времени í получает информацию от узла ] для целей управления с обратной связью. Обозначим Аг — соответствующие Е1 матрицы смежности; ¿?тах = {0, г) : зир4>0 а)'3 > 0} — максимальное множество каналов спязи.

Для формирования стратегии управления каждый узел г & N имеет информа-

цига о своем собственном состоянии (может быть и зашумлонную)

^ = (2) и, если N¡ ф 0, зашумленные наблюдения о состояниях соседей

У? = :>1 + J е N¡, (3)

где ги]'', w)'3 — помехи, а 0 < dJ'J < d целочисленная задержка, d — максимально возможная задержка. Так как система начинает работу при t = 0, неявное требование к множеству соседей: j 6 N¡ => t — dlt'J > 0. Положив w\J = 0 для всех остальных пар i,j, определим wt 6 R"2 — вектор (матрица п х п, расписанная по строкам в виде вектора), составленный из элементов tul'3, hj £ N.

Алгоритм управления, называемый "протоколом локального голосования", задается формулами:

= (4)

где ctt > 0 — размеры шагов протокола управления, blt'3 > 0, Vj 6 N¡. Положив bJJ = 0 для всех остальных пар i,j, определим В, = [Ь]'3] — матрицу протокола управления.

Пусть (Г2, Т, Р) — основное вероятностное пространство. Будем обозначать: Е — математическое ожидание и Ех — условное математическое ожидание при условии х. Во второй главе изложены основные теоретические результаты работы, при формулировке которых используются следующие условия.

Al. Vi е N функции Р{х, и) — лишпицевы по х и и: \f'(x,u)—f(x',u')\ < L\{Lx\x — х'\ + \и — и'\)\ скорость роста ограничена: |/'(х, u)|2 < L2{LC +Lx\x\2+ \и\2) и при любом фиксированном х функции f'(x, •) такие, что ЕXf'(x,u) = f'(x,Exu);

А2. a) Vi е TV, j G N* U {i} помехи наблюдений w\'3 — центрированные, независимые, одинаково распределенные случайные величины с ограниченными дисперсиями: E(w't'3)2 <

б) Vi е N,j е N' появление переменных ребер (j, i) в графе 5л, — независимые, случайные события, вероятность которых p'¿3 (т. е. матрицы At — независимые, одинаково распределенные случайные матрицы).

в) Vi 6 N,j 6 N' веса b*('3' в протоколе управления — ограниченные, случайные величины: b < b< b с вероятностью 1, и существуют пределы b^ = lim,^ ЕЬ?.

г) Существует конечная величина de № Vi £ N,j € N' <ftJ < d с вероятностью 1 и целочисленные задержки d^'1 — независимые, одинаково распределенные случайные величины, принимающие значения к = 0,..., d с вероятностями p'jf.

Кроме того, все эти случайные величины и матрицы независимы между собой, и их элементы имеют ограниченные дисперсии.

Обозначим n = n(d + 1) и определим матрицу Лшах размерности n х п по

nnniiMMV- n*'j — „'Jm°dini,j'modJl)i,jmod<ï с M 1 = 12 П a''J =0 г =

правилу. amax — p.divj Ра 0 > ' с ' ' J > > • ■ • > > "max ui '

n + 1, n + 2,..., n, j = 1,2,..., п. Здесь операция rriod — остаток от деления, а div — делеиие нацело.

Заметим, что при d = 0 это определение структуры связей сети (матрицы Лтах размерности n х га) имеет вид = Pajb'û, г е N, j е iV.

Будем считать, что для матрицы структуры связей сети AmiX выполняется следующее условие:

A3. Граф (TV, i?max) имеет остовное дерево, и для любого ребра (j,i) 6 £max среди элементов а'^, а^",..., матрицы Лшах найдется хотя бы один непу-

левой.

Рассмотрим случай, когда отсутствуют задержки в измерениях, т. е. d = 0. Обозначив xt = [х\ \... ;х"] — соответствующий вектор-столбец, полученный вертикальным соединением п чисел, можно переписать уравнение динамики состояний сети в векторно-матричном виде:

xt+i = xt + F(at, xt, wt), (5)

где F{at,xt,wt) — вектор размерности n: t

F(at,xt,wt) =

j€NÎ

\

(6)

Применение метода усредненных моделей состоит в приближенной замене исходного стохастического разностного уравнения (5), описывающего динамику сети,

Лт

обыкновенным дифференциальным уравнением: Ф- = R(a,x), в котором

х1 \ /

R(a,x) = R \ а, \

х" J \

У'(х\а^(х)) , (7)

¿(х) = J2 - х<) = -¿(Атах)х< + * € N.

j€N' j=1

Теорема 2.1. Если выполнены условия А1-А2а—в, Vi G TV функции f'(x,u) гладкие по и и при любом г верно fl{x, 0) = 0, тогда существует а такое, что при 0 < о( < а < а справедлива следующая оценка:

Е шах ||ж4-ж(п)||2 < CieC27V""a, (8)

О <Tt<TmaT.

где > 0, Сг > 0 — некоторые, константы, Tt = a0 + a.i + ... + at.

Здесь и далее нормы векторов или матриц вычисляются как корень квадратный из суммы квадратов элементов.

Будем говорить, что п узлов достигают среднеквадрати^шого е-консенсуса в момент времени i, если E||a;J||2 < оо, i Е N и существует случайная переменная х* такая, что E||xJ - г*||2 < е для всех i е N.

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

Теорема 2.2. Пусть выполнены условия А1, А2а—в; Vi G TV функции fl(x,u) гладкие по и; ири любом х верно f'(x, 0) = 0; 0 < at < й; для непрерывной модели достих-ается ^-консенсус за время параметры протокола консенсуса {at} выбраны таким образом, что rmilI = X!t=o Qt > 7^/4 и для констант С\, Сг из Теоремы 2.1 выполнено неравенство Схес%Ттлх П1ах„1:Т1<Тт,„ at < j, тогда в стохастической дискретной системе (5)-(6) в моменты времени t : Тсц < t < rmax достигается среднеквадратичный е-консенсус.

Для важного частного случая: f{x,u) = и,Mi е N, в Теореме 2.3 установлено, что при выполнении условий А2а-в, A3 в непрерывной модели достигается

консенсус, а в стохастической дискретной — среднеквадратичный е-копсеисус, и получена оценка для времени его достижения.

Далее в п. 2.2 при выполнении условий Теоремы 2.1 в Теореме 2.4 доказано достижение асимптотического среднеквадратичного е-консенсуса в стохастической дискретной системе при экспоненциальной устойчивости непрерывной модели, а в Теореме 2.5 — при достижении асимптотического консенсуса в непрерывной модели и существовании предельного многообразия для траекторий.

В п. 2.3 рассматривается случай, когда в наблюдениях может быть задержка {3 > 0). Положим х( = 0 для —й < < < 0, и определим X, 6 К'"' — расширенный вектор состояний Х[ = [Ж(,£(_1,.. . где хг-к — вектор, состоящий из таких

чт0 Зк' > к ■. р1^ > 0, т. е. это значение с положительной вероят-

ностью участвует в формировании хотя бы одного из управляющих воздействий. В дальнейшем для простоты будем считать, что так введенный расширенный вектор состояний равен = [х1,х(~1, ■ ■ ■ , 5(-,г], т. е. в пего входят все компоненты со всевозможными задержками, не превосходящими й.

Динамику обобщенных состояний сети в векторно-матричном виде можно записать следующим образом:

Хм = иХ1 + Р{а1,Хищ), (9)

где II — матрица размерности пхп, состоящая из нулей и единиц в первых п строках главной диагонали и по п + 1-й диагонали, а F(at,Xi,гDí) : М х К" х К"2 —> К" — вектор-функция соответствующих аргументов:

Г{х[,а1 Е Г - -А) + № - О))

¿¡ЕЛ7 '

(10)

/ ••• \

^("(> Х1г -ш4) =

V <и /

содержащая ненулевые компоненты только на первых п местах.

Рассмотрим соответствующую (9) усредненную дискретную модель

г1+1 = и21 + ¿о = х0, (и)

где

G(a,Z) = G

\ г /

\

0„j

(12)

/

n(d+l)

¿(2) = £ ~ *') = -¿(А™*)*4 + £ * е

jSNi к.=0 1 = 1

Условие близости в среднеквадратичном смысле траекторий исходной системы {X,} из (9) в момент времени Ь к траекториям усредненной дискретной системы (11) установлено в следующей теореме.

Теорема 2.6. Если выполнены условия А1, А2, тогда существует а такое, что при 0 < а( < б < а справедлива следующая оценка:

Е шах \\Х, - Z,||2 < С1тгеП2Тта, a<t<r

где тт = + fti + ... + rtT_i), Ci, с2 > 0 — некоторые константы:

,пЬ2Ьс + а2 с

(13)

С\ = 8n ( с 4- с(

Сз

|^о||2)еГ1п(сз+1)^ f g = f £ = 2Ь2п{п _ 1)-Ь2<

с2 = 2i-SL]{^ + 2й2||£(Лтах)|Ц), а = min а,, с3 = d+ Lx(21+rf/2Li + L2) + ас', а 1 <t<T

с1 = 21+""/2^||£(/1тях)||2 -I- а(Ь2\\С(АтлЖ + с),

d = 0, если d = 0, или d = 1, если d > 0.

В Теореме 2.7 установлены условия, при выполнении которых в стохастической дискретной системе достигается среднеквадратичный е-копсепсус, и далее в Теореме 2.8 — для важного частного случая: fl(x,u) = u,Vi е N.

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

В п 3.1 определяется модель децентрализованной системы распределения заданий между п агентами (узлами), выполняющими параллельно однотипные задания, в которой допускается перераспределение заданий между агентами па основе об-

ратных связей. Каждый агент г е N = {1,..., п} выполняет поступающие задания по принципу очереди. Задания поступают в систему в различные дискретные моменты времени Ь = 1, 2,..., Т на разные узлы. Связь между узлами определяется, как и ранее, структурой связи динамической сети.

В момент времени Ь поведение каждого агента г Е N описывается двумя характеристиками:

• <Й — загруженность или длина очереди из атомарных элементарных заданий узла г в момент времени £;

• г] — производительность узла г в момент времени

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

Ч\+1 = Я] ~ г\ + я\ + и{; I е /V, £ = 0,1,... ,Т, (14)

где г\ — размер нового задания, поступившего на узел г в момент времени £.

Если N1 ф 0, то будем считать, что в момент времени Ь узел г получает данные о производительности соседей и зашумленные наблюдения об их загруженности: у\'3 = ^ ^ и]\3, з € N1- Кроме того, в каждый момент времени £ узел i имеет зашумленные данные о своей загруженности у\'г = + и

Требуется поддерживать равномерную загрузку всех узлов сети.

В Лемме 3.1 (об оптимальной стратегии управления) установлено, что из всех возможных вариантов распределения общего количества заданий, необработанных к моменту времени наименьшее время работы системы соответствует тому, при котором

= еЛГ. (15)

Следовательно, если взять х\ = в качестве состояния узла г, то цель управления — достижение консенсуса — будет соответствовать приведенным выше соображениям об оптимальном распределении заданий между узлами.

Предположим, что г\ ф О, V г. Рассмотрим протокол управления (4), в котором V г 6 Ы, V £ определим Ы* = N1 и = г{/г\, ] е Щ.

Динамика замкнутой системы (14) для протокола (4) в рассматриваемом случае

имеет вид:

*;+! =х\-1 + + - у|-7г{). (16)

зек;

Для задачи со случайными неопределенностями в измерениях, структуре связей в сети и в протоколе управления в Теореме 3.1 даны условия достижения среднеквадратичной е-оптималыюй загрузки узлов сети с помощью управлений по протоколу локального голосования.

Далее в п. 3.2 в качестве примера рассматриваются примеры имитационного моделирования для системы, состоящей из шести вычислительных узлов, выполняющей поступающие задания, в п. 3.3 описывается модель системы распределения заказов в системе управления автотранспортом.

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

Публикации автора по теме диссертации

[1] Граничина (Амелина) Н.О. Мультиагентная система для распределения заказов // Управление большими системами. Вып. 30.1 "Сетевые модели в управлении". — 2010. — С. 549-566.

[2] Амелина Н.О. Мультиагентная система для организации транспортных перевозок // В сб. материалов каучно-технич. семннара "Управление в распределенных сетецентрических и мультиагентных системах" 3-й Мультиконферен-цни по проблемам управления. — 2010. — С. 96-98.

[3] Амелина Н.О. Достижение консенсуса автономной группой беспилотных самолетов // В сб. стохастическая оптимизация в информатике. Т. 6. — СПб: Изд-во СПбГУ, - 2010. - С. 127-132.

[4| Амелина Н. О. Построение модели мультиагентной системы для маршрутизации автотранспорта //В сб. трудов Второй традиционной всероссийской молодежной летней школе "Управление, информация и оптимизация". Переславль-Залесский. — 2010. — С. 18-31.

[5] Амелина Н.О. Балансировка загрузки узлов децентрализованной вычислительной сети при неполной информации // Нейрокомпьютеры: разработка, применение. — 2011. — № 6. — С. 56—63.

1-5

[6] Амелина H.О., Лада А.H., Майоров И.В., Скобелев П.О., Царев А.В. Исследование моделей организации грузовых перевозок с применением мультиагентной системы для адаптивного планирования мобильных ресурсов в реальном времени // Проблемы управления. — 2011. — № 6. — С. 31-37.

[7] Амелина Н. О. Нестационарный случай в задаче достижения консенсуса в сети при неполной информации //' В сб. материалов второй межвузовской научной конф. по проблемам информатики СПИСОК-2011. — 2011. — С. 135— 138.

[8] Амелина Н. О., Фрадков А. Л. Мультиагентная система для задачи балансировки загрузки сети при неполной информации // В сб. трудов межд. научно-практич. конф. "Управление большими системами-2011". — Т. 3. — 2011. — С. 201-209.

[9] Амелина Н.О. Мультиагентные технологии, адаптация, самоорганизация, достижение консенсуса //В сб. стохастическая оптимизация в информатике. Т. 7. Вып. 1. - СПб: Изд-во СПбГУ, - 2011. С. 149-185.

[10] Amelina N.O., Fradkov A.L. Nonstationary consensus problem in networks with iinperfect information and delay // In Proc. of the 5-h Int. Scientific Conf. on Physics and Control (PhysCon 2011). Léon. Spain. — 2011. - P. 62.

[11] Amelina N. 0. Consensus problem in multi-agent load balancing system //In Proc. of the Int. Student Conf. "Science and Progress". St. Petersburg. Russia. — 2011. - P. 67.

[12] Амелина Н.О. Балансировка загрузки сети при неполной информации и задержках в измерениях // В сб. трудов 16-ой Санкт-Петербургской ассамблеи молодых ученых и специалистов. — 2011. — С. 32.

[13] Амелина Н.О., Фрадков А.Л. Метод усредненных моделей в задаче достижения консенсуса // В сб. стохастическая оптимизация в информатике. Т. 8. — СПб: Изд-во СПбГУ, - 2012. С. 3-39.

Подписано к печати 29.02.12. Формат60x84 'А . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. Тираж 100 экз. Заказ 5391.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург. Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043. 428-6919

61 12-1/1015

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

На правах рукописи

Амелина Наталья Олеговна

КОНСЕНСУСНОЕ МУЛЬТИАГЕНТНОЕ УПРАВЛЕНИЕ СТОХАСТИЧЕСКИМИ

СИСТЕМАМИ

01.01.09 — дискретная математика и математическая кибернетика

Диссертация

на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д. т. н., проф. А. Л. Фрадков

Санкт-Петербург 2012

Оглавление

Введение ....................................3

1 Предварительные сведения 8

1.1 Основные понятия мультиагентных технологий..............8

1.1.1 Мультиагентные системы..............................8

1.1.2 Мультиагентное управление............................18

1.2 Основные сведения из теории графов........................20

1.3 Задача о достижении консенсуса..............................23

1.4 Метод усредненных моделей ..................................30

2 Условия достижения консенсуса в стохастической дискретной мультиагентной системе 38

2.1 Основные предположения......................................38

2.2 Применение метода усредненных моделей при отсутствии задержек ........................................................41

2.3 Условия достижения консенсуса при

задержках в наблюдениях......................................50

3 Примеры практических приложений 61

3.1 Балансировка загрузки узлов

децентрализованной сети......................................62

3.2 Пример имитационного моделирования......................67

3.3 Распределение заказов в системах управления автотранспортом ............................................................72

Заключение............................................................74

Литература............................................................75

Введение

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

На современном этапе развития теория управления фокусируется на исследовании стохастических динамических систем, состоящих из объектов с нелинейностями в математических моделях, неопределенностями характеристик объектов управления и внешних воздействий, наличием задержек в измерениях состояний объектов сети, переменной структурой сетевых связей, полной или частичной децентрализованностью регуляторов. В работах Р.П. Агаева, Б.Р. Андриевского, Р.В. Берда (R.W. Beard), Ф. Булло (F. Bullo), A.A. Воронова, И.А. Каляева, Д. Кортеса (J. Cortes), A.C. Матвеева, Б.М. Миркина, P.M. Мюррея (R.M. Murray), Р. Олфати-Сабера (R. Olfati-Saber), A.B. Проскурникова, В. Рена (W. Ren), А. Сав-кина, A.B. Тимофеева, A.JI. Фрадкова, П.Ю. Чеботарева, П.С. Щербакова, М. Эгерстадта (М. Egerstedt), В.А. Якубовича и их учеников [1,15,24,36,40,41,49,64,85,87,114,116,120,123,129,133] заложены основы теоретического описания методов анализа и синтеза децентрализованного адаптивного мультиагентного управления, и дан широкий круг возможных практических приложений в управлении сложными производственными, энергетическими и техническими системами.

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

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

Д. Армбрустер (D. Armbruster), А. Глашенко, В.И. Городецкий, И. Грачев, С. Иноземцев, К. Капенко, И.А. Каляев, A.C. Михайлов, И.О. Скобелев и др. [12,28,40,41,52,53,70,93] активно изучали алгоритмы управления в вычислительных, производственных сетях, сетях обслуживания, транспортных и логистических сетях, узлы которых выполняют определенные действия параллельно. Зачастую качество работы достаточно простых адаптивных алгоритмов оказывается удовлетворительным, но остаются открытыми вопросы их теоретического обоснования и достижения оптимальной производительности.

Для исследования динамики стохастической дискретной системы достаточно часто применяется имеющий широкое распространение в современной теории управления, теории динамических систем и нелинейной механики метод усредненных моделей, описанный в работах Д.П. Дере-вицкого, Г. Кушнера (H.J. Kushner), JL Льюнга (L. Ljung), С.М. Меерко-ва, A.JI. Фрадкова и др. [32,35,48,101,110], который позволяет свести те или иные задачи к изучению соответствующей усредненной (дискретной или непрерывной) модели.

Для решения задачи достижения консенсуса группой взаимодействующих агентов, обменивающихся информацией, в работах М. Атанса (М. Äthans), Д.П. Бертсекаса (D.P. Bertsekas), Д. Мантона (J.H. Mantón), P.M. Мюррея (R.M. Murray), Р. Олфати-Сабера (R. Olfati-Saber), В. Pe-на (W. Ren), M. Хуанга (М. Huang), Д.Н. Цициклиса (J.N. Tsitsiklis) и др. [96,97,107,120,122,130] предлагается использовать алгоритмы типа стохастического градиента, которые ранее положительно зарекомендовали себя в адаптивных системах (Я.З. Цыпкин, Б.Т. Поляк, В.Н. Фомин, О.Н. Граничин, Дж. Спал (J.C. Spall), Г. Кушнер (H.J. Kushner), Г. Ин (G.G. Yin) и др. [29,50,57,62,105,126]).

При динамических внешних изменениях состояний агентов с течением времени (поступлении новых заданий и т. п.) алгоритмы стохастичес-

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

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

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

1) исследовать поведение состояний агентов с нелинейной динамикой при переменной структуре связей, помехах в наблюдениях и отсутствии задержек в измерениях;

2) найти условия достижения среднеквадратичного приближенного консенсуса в мультиагентной системе с помехами и переключающейся структурой связей в сети при отсутствии и при наличии задержек в измерениях;

3) исследовать поведение траекторий состояний агентов дискретной стохастической системы при переменной структуре связей, помехах и задержках в наблюдениях;

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

Методы исследования. В диссертации применяются методы теорий управления, вероятностей и математической статистики, оценивания и

оптимизации, теории графов, а также имитационное моделирование.

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

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

Структура и объем диссертации Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 133 источника. Текст занимает 87 страниц и содержит 6 рисунков.

Во введении обосновывается актуальность тематики диссертационной работы, ставятся задачи исследования и кратко излагаются ее основные результаты.

В первой главе дан краткий обзор литературы по теме исследования, вводятся основные понятия мультиагентных технологий, сведения из теории графов, постановки задач о консенсусном мультиагент-

ном управлении, описываются методы сведения задач об исследовании свойств траекторий дискретных стохастических систем к усредненным задачам в детерминированной дискретной или непрерывной постановке.

Во второй главе сформулированы условия и изложены основные теоретические результаты работы.

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

Далее в п. 3.2 качестве примера рассматриваются примеры имитационного моделирования для системы, состоящей из шести вычислительных узлов, выполняющей поступающие задания.

В п. 3.3 описаны приложения для систем распределения заказов при управлении автотранспортом.

В заключении диссертации приводятся итоги диссертационного исследования и формулируются основные результаты работы.

Глава 1

Предварительные сведения

1.1 Основные понятия мультиагентных технологий

Под мультиагентными технологиями сейчас часто понимают как технологии разработки и использования мультиагентных систем (MAC), так и мультиагентное управление (МАУ).

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

1.1.1 Мультиагентные системы

В начале XXI в. группа ведущих мировых ученых [118], проработав несколько лет, составила список приоритетных задач кибернетики на ближайшие 50 лет. Среди них:

• динамически реконфигурируемое интеллектуальное управление,

• асинхронная теория управления,

• управление через Интернет,

• перепрограммирование системы управления бактериями,

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

MAC кардинально отличаются от традиционных "жестко" организованных систем, и в перспективе способны помочь в решении этих задач.

Применение мультиагентных систем (MAC) на практике было положено в 1960-70-х годах. В качестве основы были взяты достижения таких областей деятельности человека, как системы искусственного интеллекта (Artificial Intelligence), параллельные вычисления (Parallel Computing), распределенное решение задач (Distributed Problem Solving). Мно-гоагентные системы имеют реальную возможность интегрировать в себе самые передовые достижения перечисленных областей, демонстрируя принципиально новые качества [28]. Сейчас MAC —- одно из наиболее динамично развивающихся и перспективных направлений в области искусственного интеллекта [28].

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

примерами событий, вызывающих необходимость заново идентифицировать потребности и возможности, являются: появление нового выгодного заказа, для исполнения которого недостаточно собственных ресурсов предприятия, выход из строя части имеющихся ресурсов, а также изменение критериев принятия решений. Чем выше неопределенность, чем более распределенный характер имеют процессы принятия решения и, чем чаще случаются незапланированные события, тем ниже эффективность существующих систем, не способных самостоятельно принимать решения и автоматически перестраиваться под изменения в среде [52]. Кроме того, необходимость модификации схемы принятия решений в традиционных системах оказывается сложной и трудоемкой задачей, которая требует высокой квалификации исполнителей. Это делает разработку и эксплуатацию таких систем крайне дорогостоящими. Соответственно, еще одной актуальной проблемой современности становится рост объемов информации и степени сложности описания систем.

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

Агенты

Словари дают следующее толкование слова "агент": "некто или нечто, прикладывающее усилия для достижения эффекта". Такое определение указывает на первый признак "агента" — агенты совершают действия. Часто утверждается, что агенты не просто совершают действия, но они действуют автономно и рационально. Под автономностью обычно понимают, что агент действует без прямого вмешательства человека или другой управляющей сущности. Под рациональностью понимают стремление агента оптимизировать значение некоторой оценочной функции.

Мера рациональности неявно указывает на то, что агент имеет цели (желания англ. desires), которых агент "хочет" достичь, и представления о внешнем мире (убеждения, англ. beliefs), на которые агент опирается при выборе действия (реализации намерений, англ. intentions —- множество избранных, совместимых и достижимых желаний). Еще одним важным свойством агента является то, что он помещен во внешнюю среду, с которой он способен взаимодействовать. Обычно, среда не контролируется агентом, он лишь способен влиять на нее. Разделение намерений и желаний необходимо, так как агент может иметь несовместимые желания или желания могут быть недостижимы. Поскольку агент ограничен в ресурсах и не может достичь всех желаний одновременно, естественно выбирать наиболее значимые цели — намерения. Итак, агент — разумная сущность, помещенная во внешнюю среду, способная взаимодействовать с ней, совершая автономные рациональные действия для достижения целей, т. е. интеллектуальный агент — это агент, обладающая следующими свойствами:

• реактивность (англ. reactivity) — агент ощущает внешнюю среду и реагирует на изменения в ней, совершая действия, направленные на достижение целей;

• проактивность (англ. pro-activeness) — агент показывает управляемое целями поведение, проявляя инициативу, совершая действия направленные на достижение целей;

• социальность (англ. social ability) — агент взаимодействует с другими сущностями внешней среды (другими агентами, людьми и т. д.) для достижения целей.

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

• адаптивность — способность автоматически приспосабливаться к неопределенным и изменяющимся условиям в динамической среде.

Области применения

На сегодняшний день мультиагентные системы используются для разработки широкого спектра информационных и промышленных систем. В промышленности MAC наиболее распространены применительно к решению задач а