Авторефераты по всем темам  >>  Авторефераты по разным специальностям САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

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

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

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

АВТОРЕФЕРАТ

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

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

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

Научный консультант: доктор технических наук, профессор ФРАДКОВ Александр Львович

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

Ведущая организация: Учреждение Российской академии наук Институт проблем управления сложными системами РАН (г. Самара)

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

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

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

Ученый секретарь диссертационного совета Д 212.232.29, доктор физико-математических наук, профессор В. М. Нежинский

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

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

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

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

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

Для решения задачи достижения консенсуса группой взаимодействующих агентов, обменивающихся информацией, в работах М. Атанса (M. Athans), Д.П. Бертсекаса (D.P. Bertsekas), Д. Мантона (J.H. Manton), Р.М. Мюррея (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; пос. Ярополец, Московская обл., Россия, 12-19 июня, 2011), 3-й Мультиконференции по проблемам управления (Санкт-Петербург, 12-14 октября 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-а и ФЦП УКадрыФ (госконтракт № 16.740.11.0042). Результаты диссертации использованы при выполнении работ по проекту УМультиагентная система для управления группой легких беспилотных летательных аппаратовФ в рамках программы УСТАРТ-10Ф Фонда содействия развитию малых форм предприятий в научно-технической сфере. По материалам работы было получено свидетельство об официальной регистрации программы для ЭВМ № 2010612684 УSmartFly TogetherФ от 19 апреля 2010 г..

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

Работы [6, 8, 10, 13] написаны в соавторстве. В [6] Н.О. Амелиной принадлежит методика формализации математической модели, а соавторам Ч общая постановка задачи, детализация алгоритмов управления и результаты имитационного моделирования. В работах [8, 10, 13] А.Л. Фрадкову принадлежат общие постановки задач, а Н.О. Амелиной Ч реализация описываемых методов, формулировки и доказательства теорем, разработка демонстрационных примеров и программных средств.

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

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

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

Рассмотрим динамическую сеть из набора агентов (узлов) N = {1, 2,..., n}.

Граф (N, E) определяется N и набором (множеством) ребер или дуг E. Множеством соседей узла i называется Ni = {j : (j, i) E}, т. е. множество узлов с ребрами, входящими в i. Сопоставив каждому ребру (j, i) E вес ai,j > 0, определяем матрицу смежности (или связности) A = [ai,j] графа, обозначаемого далее GA (здесь и далее верхние индексы у переменных показывают соответствующие номера узлов). Определим взвешенную полустепень захода вершины i как сумму i-й n строки матрицы A: di(A) = ai,j.

j=Каждому агенту i N в момент времени t = 0, 1, 2..., T сопоставляется изменяющееся во времени состояние xi R, динамики которых описываются разностными t уравнениями xi = xi + fi(xi, ui) (1) t+1 t t t с некоторыми функциями fi(, ) : R R R, зависящими от состояний в предшествующий момент времени xi и управляющих воздействий ui R, которые в t t момент времени t воздействуют на узел i.

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

t t Узлы i и j называются согласованными в сети в момент времени t тогда и только тогда, когда xi = xj.

t t Задача о достижении консенсуса Ч это согласование всех узлов между собой, т. е. требуется найти такой протокол управления, который переводит все состояния в одно и то же постоянное значение x = xi, i N.

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

Будем считать, что структура связей динамической сети моделируется с помощью последовательности ориентированных графов {(N, Et)}t0, где Et E меняются во времени. Если (j, i) Et, то говорим, что узел i в момент времени t получает информацию от узла j для целей управления с обратной связью. Обозначим At Ч соответствующие Et матрицы смежности; Emax = {(j, i) : supt0 ai,j > 0} t Ч максимальное множество каналов связи.

Для формирования стратегии управления каждый узел i N имеет информацию о своем собственном состоянии (может быть и зашумленную) i,i i,i yt = xi + wt (2) t и, если Nti = , зашумленные наблюдения о состояниях соседей i,j i,j yt = xj + wt, j Nti, (3) t-di,j t i,i i,j где wt, wt Ч помехи, а 0 di,j d Ч целочисленная задержка, d Ч максимально t возможная задержка. Так как система начинает работу при t = 0, неявное треi,j бование к множеству соседей: j Nti t - di,j 0. Положив wt = 0 для всех t остальных пар i, j, определим wt Rn Ч вектор (матрица n n, расписанная по i,j строкам в виде вектора), составленный из элементов wt, i, j N.

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

i,j i,i ui = t bi,j(yt - yt ), (4) t t i jNt где t > 0 Ч размеры шагов протокола управления, bi,j > 0, j Nti. Положив t bi,j = 0 для всех остальных пар i, j, определим Bt = [bi,j] Ч матрицу протокола t t управления.

Пусть (, F, P) Ч основное вероятностное пространство. Будем обозначать: E Ч математическое ожидание и Ex Ч условное математическое ожидание при условии x. Во второй главе изложены основные теоретические результаты работы, при формулировке которых используются следующие условия.

A1. i N функции fi(x, u) Ч липшицевы по x и u: |fi(x, u)-fi(x, u)| L1(Lx|xx|+|u-u|); скорость роста ограничена: |fi(x, u)|2 L2(Lc+Lx|x|2+|u|2) и при любом фиксированном x функции fi(x, ) такие, что Exfi(x, u) = fi(x, Ex u);

i,j A2. а) i N, j Ni {i} помехи наблюдений wt Ч центрированные, независимые, одинаково распределенные случайные величины с ограниченными i,j дисперсиями: E(wt )2 w.

б) i N, j Ni появление переменных ребер (j, i) в графе GA Ч незаt висимые, случайные события, вероятность которых pi,j (т. е. матрицы At Ч a независимые, одинаково распределенные случайные матрицы).

в) i N, j Ni веса bi,j в протоколе управления Ч ограниченные, слуt чайные величины: b bi,j b с вероятностью 1, и существуют пределы t bi,j = limt Ebi,j.

t г) Cуществует конечная величина d N: i N, j Ni di,j d с вероятноt стью 1 и целочисленные задержки di,j Ч независимые, одинаково распредеt ленные случайные величины, принимающие значения k = 0,..., d с вероятностями pi,j.

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

Обозначим n = n(d + 1) и определим матрицу Amax размерности n n по правилу: ai,j = pi,j mod d pi,j mod d bi,j mod d, i N, j = 1, 2,..., n, ai,j = 0, i = max a max j div d n + 1, n + 2,..., n, j = 1, 2,..., n. Здесь операция mod Ч остаток от деления, а div Ч деление нацело.

Заметим, что при d = 0 это определение структуры связей сети (матрицы Amax размерности n n) имеет вид ai,j = pi,jbi,j, i N, j N.

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

A3. Граф (N, Emax) имеет остовное дерево, и для любого ребра (j, i) Emax среди элементов ai,j, ai,j+n,..., ai,j+dn матрицы Amax найдется хотя бы один ненуmax max max левой.

Рассмотрим случай, когда отсутствуют задержки в измерениях, т. е. d = 0.

Обозначив xt = [x1;... ; xn] Ч соответствующий вектор-столбец, полученный верти t t кальным соединением n чисел, можно переписать уравнение динамики состояний сети в векторно-матричном виде:

xt+1 = xt + F (t, xt, wt), (5) где F (t, xt, wt) Ч вектор размерности n:

i,j i,i fi(xi, t bi,j((xj - xi) + (wt - wt ))) t t t t F (t, xt, wt) =. (6) i jNt Применение метода усредненных моделей состоит в приближенной замене исходного стохастического разностного уравнения (5), описывающего динамику сети, dx обыкновенным дифференциальным уравнением: = R(, x), в котором d x ,. .

R(, x) = R =, (7) fi(xi, si(x)) .

xn n si(x) = ai,j (xj - xi) = -di(Amax)xi + ai,j xj, i N.

max max j=jNi Теорема 2.1. Если выполнены условия A1ЦA2аЦв, i N функции fi(x, u) гладкие по u и при любом x верно fi(x, 0) = 0, тогда существует такое, что при 0 < t < справедлива следующая оценка:

E max ||xt - x(t)||2 C1eC max, (8) 0tmax где C1 > 0, C2 > 0 Ч некоторые константы, t = 0 + 1 +... + t.

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

Будем говорить, что n узлов достигают среднеквадратичного -консенсуса в момент времени t, если E||xi||2 < , i N и существует случайная переменная x t такая, что E||xi - x||2 для всех i N.

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

Теорема 2.2. Пусть выполнены условия A1, A2аЦв; i N функции fi(x, u) гладкие по u; при любом x верно fi(x, 0) = 0; 0 < t ; для непрерывной мо дели достигается -консенсус за время T/4; параметры протокола консенсуса {t} T выбраны таким образом, что max = t > T/4 и для констант C1, C2 из Теореt= мы 2.1 выполнено неравенство C1eC max max :tmax t , тогда в стохастической t дискретной системе (5)-(6) в моменты времени t : T/4 t max достигается среднеквадратичный -консенсус.

Для важного частного случая: fi(x, u) = u, i N, в Теореме 2.3 установлено, что при выполнении условий A2аЦв, A3 в непрерывной модели достигается консенсус, а в стохастической дискретной Ч среднеквадратичный -консенсус, и получена оценка для времени его достижения.

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

В п. 2.3 рассматривается случай, когда в наблюдениях может быть задержка (d 0). Положим xt 0 для -d t < 0, и определим Xt Rnd Ч расширенный вектор состояний Xt = [xt, xt-1,..., xt-d], где xt-k Ч вектор, состоящий из таких xi, что j Ni k k : pi,j > 0, т. е. это значение с положительной вероятt-k k ностью участвует в формировании хотя бы одного из управляющих воздействий.

В дальнейшем для простоты будем считать, что так введенный расширенный век тор состояний равен Xt = [xt, xt-1,..., xt-d], т. е. в него входят все компоненты со всевозможными задержками, не превосходящими d.

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

Xt+1 = UXt + F (t, Xt, wt), (9) где U Ч матрица размерности n состоящая из нулей и единиц в первых n строках n, главной диагонали и по n + 1-й диагонали, а F (t, Xt, wt) : R Rn Rn Rn Ч вектор-функция соответствующих аргументов:

i,j i,i t bi,j((xj - xi) + (wt - wt ))) fi(xi, t t t-di,j t t i jNt F (t, Xt, wt) =, (10) 0nd содержащая ненулевые компоненты только на первых n местах.

Рассмотрим соответствующую (9) усредненную дискретную модель Zt+1 = UZt + G(t, Zt), Z0 = X0, (11) где z fi(zi, si(Z)) ,. .

G(, Z) = G =, (12).

zn(d+1) 0nd n(d+1) d si(Z) = pi,jbi,j(( pi,jzj+kn) - zi) = -di(Amax)zi + ai,j zj, i N.

a k max k=0 j=jNi Условие близости в среднеквадратичном смысле траекторий исходной системы {Xt} из (9) в момент времени t к траекториям усредненной дискретной системы (11) установлено в следующей теореме.

Теорема 2.6. Если выполнены условия A1, A2, тогда существует такое, что при 0 < t < справедлива следующая оценка:

E max ||Xt - Zt||2 c1T ec T , (13) 0tT где T = 2d(0 + 1 +... + T -1), c1, c2 > 0 Ч некоторые константы:

( ) nL2Lc + 2c c1 = 8n c + ( + ||X0||2)eT ln(c3+1), c = n2L22w, = 2L2n(n - 1)2, b b 1 cLx + c2 = 21-dL2( + 22||L(Amax)||2), = min t, c3 = d Lx(21+d/2L1 + L2) + c, 1 1tT c = 21+d/2L1||L(Amax)||2 + (L2||L(Amax)||2 + ), d = 0, если d = 0, или d = 1, если d > 0.

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

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

В п 3.1 определяется модель децентрализованной системы распределения заданий между n агентами (узлами), выполняющими параллельно однотипные задания, в которой допускается перераспределение заданий между агентами на основе обратных связей. Каждый агент i N = {1,..., n} выполняет поступающие задания по принципу очереди. Задания поступают в систему в различные дискретные моменты времени t = 1, 2,..., T на разные узлы. Связь между узлами определяется, как и ранее, структурой связи динамической сети.

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

i Х qt Ч загруженность или длина очереди из атомарных элементарных заданий узла i в момент времени t;

i Х rt Ч производительность узла i в момент времени t.

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

i i i i qt+1 = qt - rt + zt + ui; i N, t = 0, 1,..., T, (14) t i где zt Ч размер нового задания, поступившего на узел i в момент времени t.

Если Nti = , то будем считать, что в момент времени t узел i получает данные о производительности соседей и зашумленные наблюдения об их загруженности:

i,j j i,j yt = qt-d + wt, j Nti. Кроме того, в каждый момент времени t узел i имеет i,j t i,i i,i i зашумленные данные о своей загруженности yt = qt + wt.

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

В Лемме 3.1 (об оптимальной стратегии управления) установлено, что из всех возможных вариантов распределения общего количества заданий, необработанных к моменту времени t, наименьшее время работы системы соответствует тому, при котором j j i i qt/rt = qt /rt, i, j N. (15) i i Следовательно, если взять xi = qt/rt в качестве состояния узла i, то цель управt ления Ч достижение консенсуса Ч будет соответствовать приведенным выше соображениям об оптимальном распределении заданий между узлами.

i Предположим, что rt = 0, i. Рассмотрим протокол управления (4), в котором j i i N, t определим Nti = Nti и bi,j = rt /rt, j Nti.

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

i,j j i,i i i i xi = xi - 1 + zt/rt + t bi,j(yt /rt - yt /rt). (16) t+1 t t i jNt Для задачи со случайными неопределенностями в измерениях, структуре связей в сети и в протоколе управления в Теореме 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. Ч C. 56Ц63.

[6] Амелина Н.О., Лада А.Н., Майоров И.В., Скобелев П.О., Царев А.В.

Исследование моделей организации грузовых перевозок с применением мультиагентной системы для адаптивного планирования мобильных ресурсов в реальном времени // Проблемы управления. Ч 2011. Ч № 6. Ч C. 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 imperfect information and delay // In Proc. of the 5-h Int. Scientific Conf. on Physics and Control (PhysCon 2011). Leon. Spain. Ч 2011. Ч P. 62.

[11] Amelina N. O. 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.

Авторефераты по всем темам  >>  Авторефераты по разным специальностям