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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В. А. ТРАПЕЗНИКОВА РОССИЙСКОЙ АКАДЕМИИ НАУК

УДК 519.71 ББК 32.965

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

005052151

ПАРСЕГОВ Сергей Эрнестович

АЛГОРИТМЫ УПРАВЛЕНИЯ ФОРМАЦИЕЙ В ЗАДАЧЕ РАВНОМЕРНОГО РАСПОЛОЖЕНИЯ АГЕНТОВ

05.13.01 Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

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

18 АПР 2013

Москва 2013

005052151

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт проблем управления им. В. А. Трапезникова Российской акаг демии наук

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

ЩЕРБАКОВ Павел Сергеевич (Институт проблем управления им. В. А. Трапезникова РАН)

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

профессор РАПОПОРТ Лев Борисович (Институт проблем управления им. В. А. Трапезникова РАН)

кандидат физико-математических наук ПРОСКУРНИКОВ Антон Викторович (Институт проблем машиноведения РАН)

Ведущая организация: Федеральное государственное бюджетное

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

Защита состоится "_"_2013 года в_часов на заседании диссертационного совета Д002.226.02 при Институте проблем управления им. В. А. Трапезникова РАН по адресу: 117997, г. Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке ИПУ РАН.

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

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

диссертационного совета Д002.226.02, кандидат технических наук

В. Н. Лебедев

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

Актуальность темы. Многие постановки задач современной теории автоматического управления связаны с управлением большими группами объектов. Такими объектами могут быть мобильные роботы, узлы компьютерных сетей, датчики, сенсоры и др. Ранее задачи такого рода решались с использованием только централизованного подхода к управлению. Этот подход подразумевает синтез одного регулятора, управляющего всей совокупностью объектов, и является развитием классической теории управления. Помимо важных достоинств (обеспечение высокого быстродействия системы, наличие детально разработанных методов синтеза), централизованный подход обладает рядом недостатков, к которым можно отнести сложность, а иногда и невозможность построения единого регулятора, а также низкую надежность системы — неполадки в управляющем устройстве могут приводить к нарушению функционирования всей системы.

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

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

з

ботов и многих других.

В работах Р. П. Агаева, П. Ю. Чеботарева, А. Л. Фрадкова, О. Н. Гра-ничина, А. В. Проскурникова, Ш. Хара (S. Нага), Э. Фраццоли (Е. Frazzoli), А. Уильяме (A. Williams), Р. В. Берда (R. W. Beard), Ф, Булло (F. Bullo), X. Кортеса (J. Cortes), Р. М. Мюррея (R. М. Murray), Р. Олфати-Сабера (R. Olfati-Saber), В. Рена (W. Ren) и их учеников заложены теоретические основы методов анализа и синтеза децентрализованного управления мульти-агентными системами, описан широкий круг возможных практических приложений.

Одним из наиболее перспективных и бурно развивающихся направлений в области управления мультиагентиыми системами является распределенное управление формациями. Под формацией в данной работе понимается группа локально взаимодействующих агентов, способная передвигаться в пространстве. Управление формациями включает в себя задачи формирования группой агентов в пространстве некоторых геометрических образов (формообразования), задачи слежения формации за лидером (виртуальным или реальным) с сохранением геометрической конфи1урации и многих других. Часто решение таких задач усложняется ограниченными возможностями агентов получать информацию от соседей, наличием запаздываний в каналах связи, необходимостью обхода препятствий агентами, подавления внешних возмущений и др. Существуют разные подходы к решению перечисленных задач: использование методов линейной алгебры (М. Pavone, Е. Frazzoli, W. Ren, J. J. P. Veerman, П. С. Щербаков), метода функций Ляпунова (H. Tanner, A. Jadbabaie, G. J. Pappas, C. H. Васильев, P. И. Козлов, H. H. Максимкин, С. A. Ульянов), потенциальных функций (R. Olfati-Saber, X. Wang, Z. Lin, Ю. В. Морозов) и др.

В литературе рассматривается много разных геометрических конфигураций, которые могут образовывать группы агентов. В одной из типовых постановок задач требуется выстроить агенты на прямой линии, расположив их определенным образом на некотором фиксированном отрезке, например, равномерно. Задача, равноудаленного расположения агентов на отрезке имеет долгую историю, разные варианты задачи в непрерывном и дискретном времени рассматривались в работах И. А. Вагнера (I. A. Wagner) и А. М. Брук-штейна (А. М. Bruckstein), Я. И. Петрикевич, П. С. Щербакова. Похожий

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

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

Целью работы является синтез новых законов управления для задачи равноудаленного расположения агентов па отрезке. Развитие и обобщение существующих законов управления включают в себя решение следующих задач:

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

2. синтез законов управления формацией с введением сцепления пространственных координат для агентов первого и второго порядков;

3. синтез двухуровневого иерархического закона управления группами агентов;

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

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

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

1. закон управления формацией с моделями агентов второго порядка;

2. закон управления формацией с моделями агентов первого и второго порядков со сцеплением пространственных координат;

3. двухуровневый иерархический закон управления группами агентов;

4. сверхфинитный закон управления мультиагентной системой. Апробация результатов работы. Результаты диссертационной работы докладывались на семинарах лаборатории 7 ИПУ РАН, III и IV Всероссийских традиционных молодежных летних школах "Управление, информация и оптимизация" (ИПУ им. В. А. Трапезникова РАН, п. Ярополец, 2011, г. Звенигород, 2012); на VIII и IX Всероссийских школах-конференциях молодых ученых "Управление большими системами" (г. Магнитогорск, 2011, г. Липецк, 2012), на XVIII международной конференции "Автоматика-2011", г. Львов, 2011, на 14-й Международной студенческой олимпиаде по теории автоматического управления, г. Санкт-Петербург, 2011, на 5-й Российской мульти-конференции "УТЭОСС-2012", г. Санкт-Петербург, 2012, семинарах ИПМаш РАН и математико-механического факультета СПбГУ, г. Санкт-Петербург, семинаре ИДСТУ СО РАН, г. Иркутск.

Публикации. Основные результаты опубликованы в 10 научных работах, в том числе 3 статьи — в рецензируемых журналах из списка, рекомендованного ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Работа изложена на 120 страницах, содержит 35 иллюстраций. Библиография включает 113 наименований.

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

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

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

Мультиагентные системы состоят из агентов — подсистем, связанных друг с другом и образующих некоторую структуру. Сложность задач управления такими системами можно условно определять тремя факторами: 1) сложностью математической модели агента; 2) сложностью сетевой структуры, связывающей агентов; 3) сложностью типов связей между агентами. Можно считать, что каждый из этих факторов характеризует некоторое измерение в пространстве сложности задач по мультиагентным системам. С помощью этого понятия удобно классифицировать задачи управления мультиагентны-ми системами и оценивать их сложность. В работе проводится обобщение одной из задач управления формациями по каждому из измерений в пространстве сложности.

Рассматриваются линейные мультиагентные системы, состоящие из скалярных агентов. Частотный критерий Поляка-Цыпкина, используемый в работе, позволяет исследовать устойчивость таких систем. Критерий устойчивости использует важное понятие области устойчивости на комплексной плоскости, которая строится по принципу Л-разбиения и ограничивается годографом ф(]ш), где </>(й) = 1//((5), а — передаточная функция агента. Критерий упрощает анализ устойчивости линейных стационарных мультиагентных систем, избавляя от необходимости нахождения характеристического полинома системы и применения общих критериев устойчивости.

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

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

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

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

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

xi = Ui, г = 1, ...,п, (1)

где XI 6 К и щ £ К. состояние и управляющий сигнал г-го агента, соответственно.

Линейный закон управления имеет вид:

Х£+1 +

щ =----х{, г = 1 ,...,п, (2)

где Хд и хп+х — координаты начала и конца отрезка (неподвижные агенты).

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

Пусть х = [хх,х2,-- - ,а;п]Т — вектор состояния мультиагентной системы, тогда се динамика может быть записана в компактной форме

х = Ах + Ь,

(3)

где матрица А и вектор Ь имеют вид

А —

-1 0.5 0 ... 0 0.5 -1 0.5 ... 0

Є Ж'

(4)

0 О ... 0.5 -1

Ь= [0.5їо,0,...,0.5хп+1]1 Є К".

|Т

(5)

Матрица А является трехдиагональной, ее собственные значения имеют вид

А)ь = —2 эт.2 . , к = 1,...,п. (6)

2 (п +1)

Для решения системы (3) справедлива оценка ||х(4) — х*|| < еА||а;(0) — ж*||, где ж(0) вектор начального положения агентов. Величина А характеризует скорость сходимости траекторий системы и равна

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

Рассматриваются модели агентов следующего вида

(7)

хі = щ, г = 1,... ,п,

(8)

и предлагается закон управления

Xi+I + Xi-I . . ,

u¡ =----Xi-aXi, г = 1 ,...,n, (9)

где а — некоторый настраиваемый параметр.

Из формул (8)-(9) можно получить выражение, описывающее динамику системы из п агентов

х = Ах — ах + Ь, (10)

где А и b определяются выражениями (4), (5).

Система (10) является системой линейных дифференциальных уравнений второго порядка. Для анализа ее устойчивости используется критерий Поляка-Цыпкина. Справедлива теорема.

Теорема 1. Система (10) является устойчивой для всех а > 0, а нули характеристической функции

G{s) = det (А - (s2 + as)In)

имеют вид I 7

At = -0.5а ± Л(0.5а)2 - 2 sin2 (11)

Для сравнения скоростей сходимости алгоритмов (3), (10) формулируется Теорема 2.

Теорема 2. Алгоритм второго порядка имеет более высокую скорость сходимости при a G (4sin2 ¿p^jy, 1 + 2sin2 j^iy), алгоритм первого

порядка - при а € (о, 4sin25^) (J (l + 2 sin2 ^jj, +oo)7 n > 1. Скорость сходимости двух алгоритмов одинакова при а = 4кт2 а = 1 + 2 sin2 2(n+i)i п> 1. Алгоритм второго порядка имеет наибольшую скорость сходимости при а = € ^4sm2 jp^jy, 1 + 2sin2 n> 1.

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

Далее рассматриваются стратегии равноудаленного расположения на отрезке на плоскости. Пусть положение г-го агента в момент времени t > 0

определяется вектором £¿(4) = £ К2, г = 1, • • • Со = [^о.УоГ

и С„+1 = [хп+1, Уп.+1]Х — координаты начала и конца отрезка, соответственно. С учетом введенных обозначений, выражение, описывающее динамику всей системы, может быть представлено в виде

С = (Л®/2)С + Ь, (12)

где 12 — единичная матрица размера 2x2,® — символ произведения Кро-некера, С = [СпС^-чСТ] е ~ сборный вектор координат агентов системы, Ь = [0.5£о\ 0,.. -,0.5С,Т+1]Т € Ж2".

Для начала рассматривается стратегия равноудаленного расположения на отрезке со сцеплением координат, когда модели агентов описываются уравнением (1). Сцепление координат можно получить введением в выражение (12) матрицы более общего вида, чем единичная. Рассмотрим частный случай, когда вектор скорости каждого агента смещен на одинаковый для всех агентов угол а € [—тг, тг], тогда соответствующая матрица сцепления имеет вид матрицы поворота.

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

Пусть управление на входе г-го агента определяется следующей формулой

щ = Д(а) г = 1,..., п, (13)

где Я(а) — матрица поворота

Я(а) =

соз а sin а

(14)

• sin а cos а

Система уравнений, описывающая динамику^ всей системы из п агентов

имеетвпд é = (A®R(am + b*, (15)

Ь* = (/„ ® Д(а))Ь Є R2n. (16)

Справедлива следующая теорема. Теорема 3. Система (15) устойчива тогда и только тогда, когда |а| < §. При этом & £о + ;¿i(£n+i - £о), £ оо, k = 1,... ,п, т.е. все агенты из любого начального положения асимптотически выстраиваются на отрезке с фиксированными концами Со и £„+і на равном расстоянии друг от друга. При п —* оо оценка скорости сходимости (15) определяется А «

^ 2n2~' Д"* значений угла | < |а| < тт це.аь управления не достигается.

Замечай и el .В общем случае в законе управления (13) может фигурировать не матрица поворота R(a), а матрица более общего вида. Введение в уравнение движения матрицы R(a) имеет определенный физический смысл — тем самым мы отклоняем вектор скорости. Кроме того, для А ® R(a) известна аналитическая запись спектра, что облегчаъгп анализ задачи и ее обобщение. Если для сцепления координат применяется матрица общего вида, то вопросы трактовки ее физического смысла и вычисления спектра остаются открытыми.

Усложним модели агентов, учитывая при этом сцепление координат при помощи матрицы поворота R(a). Пусть модель агента описывается уравнением (8)

Закон управления выбирается в следующем виде

Ui = R(a) _ 6 _ об) , i = 1,..., п, (17)

где о — некоторый настраиваемый параметр.

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

£ = (Л ® R(a))£ - aR(a)¿ + b", (18)

где матрицы А и R(a) имеют вид (4) и (14) соответственно,

Ь* = (In ® R(a)) [0.5Й", 0,..., 0.5С+1]Т б R2". Справедлив следующий критерий устойчивости.

Теорема 4. Система (18) устойчива тогда и только тогда, когда

1 _ . п 7171 . 0

a cosa > 2snr —--sin2 a, а > 0.

2 (n +1)

При этом & —> t —» оо, к = 1,..., п, т.е. все агенты из

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

Замечание 2. Следует отметить, что законы управления (9) и (17) отличаются от (13) необходимостью знания скорости i-го агента. По сути, слагаемые —ащ а > 0 имеют смысл отрицательных обратных связей, стабилизирующих систему.

В рамках усложнения структуры мультиагентной системы предлагается применение концепции иерархичности для алгоритма равноудаленного расположения групп агентов на отрезке. Рассматривается следующая задача: имеется пд групп мобильных агентов, по п агентов в каждой (общее число агентов N = п х пд)\ необходимо получить такой закон управления, чтобы центроиды — центры масс каждой из групп — стремились равномерно расположиться на заданном отрезке [.х'о, х„9], а агенты каждой группы стягивались к ее центроиду.

Для решения поставленной задачи предлагается закон управления в виде двухуровневой иерархической схемы. На втором (высоком) уровне иерархии рассматривается движение пД групп агентов по закону равноудаленного расположения на отрезке, на первом (низком) — движение агентов внутри каждой из групп по алгоритму циклического преследования.

Алгоритм циклического преследования, в соответствии с которым каждый агент преследует следующего по модулю п агента со смещением, описывается следующим уравнением:

где х — координата центроида группы агептов (19).

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

Вводятся следующие обозначения для агентов: хРД, где р = 1,... ,пд является индексом группы, а. q = 1,...,п индексом агента в группе. Тогда двухуровневая иерархическая схема может быть записана в следующем виде

= (£¿+1 + с,-) - х,-, г = 1,..., п. где с,-, г = 1,..., п — смещения. Справедливо следующее равенство

(19)

(20)

х = Ах

где X = [т,1,2^2, ...,Х11П1 ...,х„дг1,...,

всех агентов, а матрица системы определяется выражением

А = 1Пд ® С + £> ® I,

(22)

где матрицы С Є Епхп и О є I іПдХТІд

-11 0 ... 0 "

0 -1 1 ... 0

С =

1 0 ... 0 -1

а ИМЄЮТ ВИД

-1 0.5 0 0.5 -1 0.5

О О

... О ... О

0.5 -1

Матрица О используется для описания движения центроидов групп. Вектор Ъ = Ь ® 1, где 1 = [1,1,..., 1]т Є К", и Ь Є К"» определяется аналогично (5). Матрицы 1п, 1Пз — единичные матрицы соответствующих размерностей.

Учитывая тот факт, что матрица А Є ЕЛГхЛ является кронекеровой суммой матриц С и О: А — С ф Д формулируется следующая теорема.

Теорема 5. Система (21) устойчива и множество собственных значений матрицы А является прямой суммой множеств собственных значений матриц С и Б. При этом хрл —> хо + — ^о), £ —► оо,р = 1 ,...,Пд, т.е. для любого начального положения каждый агент сходится к центроиду своей группы, а центроиды групп, в свою очередь, асимптотически, располагаются равномерно к<х отрезке с фиксированными концами Хо и хп Скорость сходимости алгоритма при пд —> оо определяется

2п1

Задача может быть легко обобщена на двумерный случай введением вектора координат агента аналогично (12).

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

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

Рассматривается группа из п пронумерованных мобильных агентов. Пусть положение каждого агента при t > 0 обозначается через Xi(t) £ й, г = 1,..., п, a xq, x„+i обозначают зафиксированные концы отрезка. Динамическая модель каждого агента описывается интегратором:

¿i = Ui + di(t,x), i = l,...,n, (23)

где щ € R — подлежащий выбору закон управления, х = [ху,х2, ■■ •, агп]т, di(t, х) — ограниченные внешние возмущения

|di(i, х) | < dmax, г = 1,..., п. (24)

Предполагается, что неотрицательное число dmax известно заранее. Решается задача синтеза управления в виде обратной связи, которое

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

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

щ = Ui(xi-i - хи xi+i -xi), i = 1,..., n; (25)

3. является робастным по отношению к ограниченным внешним возмущениям.

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

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

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

z = g(t,z), z{0) = z0, (26)

1 Л. Polyakov, Nonlinear feedback design foi fixed-time stabilization of linear control systems, IEEE Transactions on Automatic Control, 57(8): 2106-2110, 2012

где г € К" и д : R+ х R" —» R" — нелинейная функция (в общем случае разрывная). В этом случае решения (26) понимаются в смысле Филиппова. Пусть точка zq — 0 является положением равновесия системы (26).

Определение1 (Roxin, Bhat and Bernstein, Поляков). Нулевое положение равновесия системы (26) называется глобально финитно устойчивым, если оно глобально асимптотически устойчиво и каждое решение z(í,zq) системы (26) достигает его за финитное время, т.е., Vzo 6 R" 3T(zQ) > 0 : V t > T(zq) z(t,z0) - 0, где Т: Rn R+ U {0} - функция времени установления.

Свойством финитной устойчивости могут обладать однородные системы с отрицательным показателем. Например, всякое решение системы z = — zz, z е R сходится к нулевому положению равновесия за конечное время T(zq) :=

Замечание 5. Ранее в отечественной литературе под финитной устойчивостью (finite, finite-time stability в англоязычной литературе) понимали устойчивость на конечном интервале времени. В диссертационной работе рассматривается иное свойство — свойство асимптотической устойчивости с финитпьим временем достижения положения равновесия и положительной инвариантностью этого положения.

Определение2 (А. Е. Поляков). Нулевое положение равновесия системы (26) называется сверхфинитно устойчивым, если оно глобально финитно устойчиво и функция времени установления T(zq) ограничена, т.е., 3Tmax > 0: T(z0) < Tmax Vz0 6 R".

Например, нулевое положение равновесия системы z = —zs — z3, г е R

является сверхфшштно устойчивым и z(i, Zq) = 0 для Vi > 2.5 и Vz0 € R.

Вводится следующее обозначение: D*tp(t) — верхняя правая производная

Дини для функции ifi(t), т.е. D*(p(t) := lim sup v^tJrh)~'(,{t).

h—>+0

Лемма 1 (A. E. Поляков). Если существует непрерывная радиально неограниченная функция V : R" —► R+ U {0}, такая что 1. V{z) = 0 л = 0,

2. любое решение г(Ь) системы (26) удовлетворяет при всех Ь > 0 неравенству < -аУГ{г{1)) - рУ^)) для некоторых а, р, р, > О: р < 1, q> 1, тогда начало координат является глобально сверхфинитно устойчивъш положением равновесия системы (26) и справедлива следующая оценка:

ТЫ< г/ ч + 1 л а(1 -Р) Р(Я~Ч

Для начала рассмотривается случай й{(1,х) = 0. Для решения задачи синтеза нелинейного закона управления вводится вспомогательная функция е К, которая имеет вид

ф'(я) := авИ + Рз[ч\ 0 < р < 1, д > 1, (27)

где а, Р некоторые положительные константы и := 81§п(з)|зр. Предлагается следующий нелинейный закон управления

Щ = ф - + 5(^+1 _ ■ (28)

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

х = ф(Ах + Ъ), (29)

где матрица А и вектор 6 определены в (4) и (5), соответственно. Векторы ф(г) и г имеют вид ф(г) := [ф{г 1), ф(г2),..., ф(гп)]т, г = [г1: г2,..., гп]т в й", соответственно.

Получен следующий результат.

Теорема 6. Пусть сЩЬ, х) = 0 и закон управления и, имеет вид (28) с параметрами а > 0, /3 > 0, 0 < р < 1, д > 1. Тогда все агенты мультиагентной системы (23) располагаются равноудаленно на отрезке за конечное время, которое глобально ограничено моментом времени Ттах:

Т -_I_+___(30)

где А имеет вид (7).

Приведенная теорема даст довольно консервативную оценку времени установления, поскольку получена с использованием общей Леммы 1. Более точная оценка может быть получена при использовании леммы, приведенной ниже.

Рассматривается особый случай: р = 1 — + 1.

Лемма 2. Если существует непрерывная радиалъно неограниченная функция V : Rn —► ®+ U {0}, такая что

1. V(z) = 0 z = 0,

2. любое решение z{t) системы (26) удовлетворяет неравенству

D*V(z(t)) < -aV*(z(t)) - PV*{z(t))

при некоторых а, /? > 0, р = 1 — <7 = 1 + /i > 1, тогда начало координат является глобально сверхфинитно устойчивым положением равновесия системы (26) и справедлива следующая оценка:

Tmax:= —V^o € R". Va/3

Следствие1. Если соблюдены условия теорем и константы р, q системы (29) выбраны следующим образом: р = 1 — ^ и q — \ + р. > 1, то оценка времени установления имеет вид

<31>

Замечание 6. Формула оценки (31) приводит к заключению: для системы априори может быть задано любое время установления путем надлежащего выбора параметров /х, а и /3.

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

Для обеспечения робастности предлагаемого закона управления по отношению к ограниченным внешним возмущениям предлагается следующая простая модификация функции ф следующего вида:

ф{з) := asH + jSeW +

sign(s), 0 <p < l,q > l,a > 0,0 > 0. Следствие 2. Пусть закон управления щ имеет вид

щ-ф Q(x«-i_ xi)+\(xi+x ~• (з2)

тогда для него справедливы положения Теоремы 6 и Следствия 1 при наличии ограниченных возмущений (24), di(t,x) ^ 0.

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

х — ф ((А ® 1т)х + б) . (33)

Здесь 2 = [гс^, 4,..., х^]Т 6 6 = [0.5хц , 0,..., 0.5х^+1] ТеГи,^~ векторная функция ф{г) := [ф{гх), ф{г2),..., <^(2пт)]т, г = [гг, г2,.. -, гпт]Т е Е1пт, а ф(-) определена в (27).

Матрица А ® 1т является положительно определенной, ее собственные значения определены в (6) и имеют кратность т. Следовательно, все полученные ранее результаты остаются справедливыми. Более того, поскольку система (33) может рассматриваться как совокупность т независимых подсистем, имеющих одинаковые оценки на время установления, зависимости (30) и (31) справедливы при любом т.

Замечание 8. В практических приложениях часто бывает достаточным не точное достижение положения равновесия, а попадание в его некоторую достаточно малую окрестность. Можно по-разному подойти к задаче увеличения скорости сходимости алгоритма равноудаленного расположения на отрезке. Наиболее простым способом ускорения переходных процессов является увеличение коэффициента усиления в линейной системе. Это приведет к увеличению затрат на управление (также как и при использовании сверхфинитного закона управления). С другой стороны, сверхфинитный закон управления позволяет 1) не привязываться к начальным условиям (время установления ограничено глобально) и 2) обеспечивает более высокую скорость сходимости в сравнении с линейным законом как вдали от положения равновесия, так и вблизи него. Более того, модифицированный сверхфинитный закон управления позволяет подавлять ограниченные внешние возмущения. К недостаткам синтезированных нелинейных законов управления можно отнести необходимость точного измерения координат системы.

В заключении диссертации приводятся выводы о проделанной работе.

Основные результаты и выводы

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

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

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

Все теоретические результаты были подтверждены многими численными экспериментами.

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

[1] Квинто Я. И., Парсегов С. Э., Равноудаленное расположение агентов на отрезке: анализ алгоритма и его обобщения // Автоматика и телемеханика, No 11, 2012. С.30-41.

[2j Парсегов С. Э., Сцепление координат и иерархические алгоритмы в задаче равноудаленного расположения агентов на отрезке / / Управление большими системами. Выпуск 39. М.: ИПУ РАН, 2012. C.2G4-287.

[3] Парсегов С. Э., Сверхфинитная стабилизация мультиагентной системы // Проблемы управления, 2012. С.7-12.

[4] S. Parsegov, A. Polyakov, P. Shcherbakov, Nonlinear fixed-time control protocol for uniform allocation of agents on a segment // Proc. CDC-2012, Maui, USA, Dec. 10-13, 2012, pp. 7732-7737.

[5] S. E. Parsegov, Allocation of agents on a line: simple algorithm and generalizations, // Proc. 14th Baltic olympiad on automatic control, Saint-Petersburg, Russia, Sep. 21-23, 2011, pp. 119-125.

[6] Парсегов С. Э., Обобщенные линейные алгоритмы управления формациями // Стохастическая оптимизация в информатике, Т.7 (Вып. 1), 2011. С. 186-203.

[7] Парсегов С. Э., Развитие некоторых алгоритмов управления расположением агентов в мультиагентных системах // Материалы XVIII межд. конф. "Автома.тика-2011", Львов, 2011. С. 317-318.

[8] Парсегов С. 9., Некоторые новые иерархические алгоритмы управления формациями, // Труды международной научно-практической конференции "Теория активных систем-2011", Т.З, Москва, 2011. С. 238-241.

[9] Парсегов С. Э., Равноудаленное расположение на отрезке как задача достижения консенсуса // Управление большими системами. Материалы IX Всероссийской школы-конференции молодых ученых, Т.1, Издательство ЛГТУ, Липецк, 2012. С. 79-84.

[10] Парсегов С. Э., Сверхфинитное управление мультиагентной системой // Материалы конференции "Управление в технических, эргатических, организационных и сетевых системах" (УТЭОСС-2012). - СПб.: ГНЦ РФ ОАО "Концерн "ЦНИИ "Электроприбор", 2012. С.195-198.

Личный вклад автора в совместные публикации

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

Подписано в печать:

01.04.2013

Заказ №8301 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В. А. ТРАПЕЗНИКОВА РОССИЙСКОЙ АКАДЕМИИ НАУК

ПАРСЕГОВ Сергей Эрнестович

АЛГОРИТМЫ УПРАВЛЕНИЯ ФОРМАЦИЕЙ В ЗАДАЧЕ РАВНОМЕРНОГО РАСПОЛОЖЕНИЯ

АГЕНТОВ

Специальность 05.13.01 — Системный анализ, управление

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

Москва 2013

УДК 519.71

ББК 32.965

04201358696

и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

Оглавление

Введение 4

1 Линейные мультиагентные системы 12

1.1 Классификация и сложность................................12

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

систем..........................................................19

1.2.1 Однотипные системы..................................20

1.2.2 Частотный критерий устойчивости..................22

1.2.3 Управляемость и наблюдаемость....................27

1.3 Элементы теории графов и задача

консенсуса......................................................29

1.4 Выводы........................................................39

2 Равномерное расположение

на отрезке 40

2.1 Постановка задачи и предварительные

замечания......................................................40

2.2 Модели агентов второго порядка............................53

2.3 Равноудаленное расположение

на отрезке со сцеплением координат........................61

2.3.1 Модели агентов первого порядка....................61

2.3.2 Модели агентов второго порядка....................63

2.4 Иерархический протокол управления ......................73

2.5 Выводы........................................................84

3 Равномерное расположение

за заданное время 85

3.1 Постановка задачи и предварительные

замечания......................................................85

3.2 Сверхфинитная устойчивость................................89

3.3 Нелинейный сверхфинитный протокол

управления..........................91

3.3.1 Система без внешних возмущений..................91

3.3.2 Робастная модификация протокола управления . 99

3.3.3 Обобщение на многомерный случай ........101

3.4 Выводы............................102

Заключение 104

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

Введение

Актуальность темы. Многие постановки задач современной теории автоматического управления связаны с управлением большими группами объектов. Такими объектами могут быть мобильные роботы, узлы компьютерных сетей, датчики, сенсоры и др. Ранее задачи такого рода решались с использованием только централизованного подхода к управлению. Этот подход подразумевает синтез одного регулятора, управляющего всей совокупностью объектов, и является развитием классической теории управления. Помимо важных достоинств (обеспечение высокого быстродействия системы, наличие детально разработанных методов синтеза), централизованный подход обладает рядом недостатков, к которым можно отнести сложность, а иногда и невозможность построения единого регулятора, а также низкую надежность системы — неполадки в управляющем устройстве могут приводить к нарушению функционирования всей системы.

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

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

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

В работах Р. П. Агаева, П. Ю. Чеботарева, A. JI. Фрадкова, О. Н. Гра-ничина, А. В. Проскурникова, Ш. Хара (S. Нага), Э. Фраццоли (Е. Fraz-zoli), А. Уильяме (A. Williams), Р. В. Верда (R. W. Beard), Ф. Бул-ло (F. Bullo), X. Кортеса (J. Cortes), Р. М. Мюррея (R. М. Murray), Р. Олфати-Сабера (R. Olfati-Saber), В. Рена (W. Ren) и их учеников заложены теоретические основы методов анализа и синтеза децентрализованного управления мультиагентными системами, описан широкий круг возможных практических приложений.

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

боте понимается группа локально взаимодействующих агентов, способная передвигаться в пространстве. Управление формациями включает в себя задачи формирования группой агентов в пространстве некоторых геометрических образов (формообразования), задачи слежения формации за лидером (виртуальным или реальным) с сохранением геометрической конфигурации и многих других. Часто решение таких задач усложняется ограниченными возможностями агентов получать информацию от соседей, наличием запаздываний в каналах связи, необходимостью обхода препятствий агентами, подавления внешних возмущений и др. Существуют разные подходы к решению перечисленных задач: использование методов линейной алгебры (М. Pavone, Е. Fraz-zoli, W. Ren, J. J. P. Veerman, П. С. Щербаков), метода функций Ляпунова (H. Tanner, A. Jadbabaie, G. J. Pappas, C. H. Васильев, P. И. Козлов, H. H. Максимкин, С. A. Ульянов), потенциальных функций (R. Olfati-Saber, X. Wang, Z. Lin, Ю. В. Морозов) и др.

В литературе рассматривается много разных геометрических конфигураций, которые могут образовывать группы агентов. В одной из типовых постановок задач требуется выстроить агенты на прямой линии, расположив их определенным образом на некотором фиксированном отрезке, например, равномерно. Задача равноудаленного расположения агентов на отрезке имеет долгую историю, разные варианты задачи в непрерывном и дискретном времени рассматривались в работах И. А. Вагнера (I. A. Wagner) и А. М. Брукштейна (А. М. Bruckstein), Я. И. Петрикевич, П. С. Щербакова. Похожий алгоритм был впервые описан в работе Г. Дарбу, посвященной геометрической задаче о перестановке вершин многоугольника.

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

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

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

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

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

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

2. синтез законов управления формацией с введением сцепления пространственных координат для агентов первого и второго порядков;

3. синтез двухуровневого иерархического закона управления группами агентов;

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

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

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

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

На защиту выносятся следующие положения:

1. закон управления формацией с моделями агентов второго порядка;

2. закон управления формацией с моделями агентов первого и второго порядков со сцеплением пространственных координат;

3. двухуровневый иерархический закон управления группами агентов;

4. сверхфинитный закон управления мультиагентной системой.

Апробация результатов работы. Результаты диссертационной работы докладывались на семинарах лаборатории 7 ИПУ РАН, III и IV Всероссийских традиционных молодежных летних школах "Управление, информация и оптимизация" (ИПУ им. В. А. Трапезникова РАН, п. Ярополец, 2011, г. Звенигород, 2012); на VIII и IX Всероссийских школах-конференциях молодых ученых "Управление большими системами" (г. Магнитогорск, 2011, г. Липецк, 2012), на XVIII международной конференции "Автоматика-2011", г. Львов, 2011, на 14-й Международной студенческой олимпиаде по теории автоматического управления, г. Санкт-Петербург, 2011, на 5-й Российской мультиконференции "УТЭОСС-2012", г. Санкт-Петербург, 2012, семинарах ИПМаш РАН и математико-механического факультета СПбГУ, г. Санкт-Петербург, семинаре ИДСТУ СО РАН, г. Иркутск.

Публикации. Основные результаты опубликованы в 10 научных работах, в том числе 3 статьи — в рецензируемых журналах из списка, рекомендованного ВАК.

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

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Работа изложена на 120 страницах, содержит 35 иллюстраций. Библиография включает 113 наименований.

Глава 1

Линейные мультиагентные системы

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

1.1 Классификация и сложность

Теория управления мультиагентными системами является одним из направлений современной теории управления и развитием классической. Особенностью мультиагентных систем является наличие не одного объекта управления, как в классической теории, а целой группы объектов, которых называют агентами. Теоретический аппарат этого нового направления базируется как на классических принципах и методах теории управления [8], [22], [47], [70], так и на положениях спектральной теории графов, необходимой для исследования структу-

ры мультиагентных систем [2], [24], [71].

Особенностью мультиагентных систем является их децентрализо-ванность — управление всей системой осуществляется без центрального регулятора, действующего на каждого агента. Достижение цели управления достигается за счет локального взаимодействия агентов. Платой за отсутствие централизованного управления является более высокая сложность задач управления мультиагентными системами. Однако по ряду причин применение такого подхода является более оправданным и многообещающим. Прежде всего, из-за наличие реальных физических ограничений, действующих на агентов, таких как пропускная способность каналов связи, ограниченная зона видимости, большое число взаимодействующих подсистем. К преимуществам распределенного подхода можно отнести робастность к отказу отдельных подсистем, надежность и гибкость [86].

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

• Консенсус/соглашение/синхронизация/рандеву. Направление посвящено различным аспектам приведения агентов в некоторое одинаковое состояние. В многих случаях все четыре термина означают одно и то же. Задача достижения консенсуса является одной из центральных проблем теории мультиагентных систем, многие другие задачи в конечном итоге сводятся к ней. Большинство работ по мультиагентным системам посвящены консенсусу/ синхронизации в той или иной форме; наиболее важные понятия, определения, классификация и обобщения задач приведены в [2], [24],

[71], [86]. В [70], [106], [107] исследуются задачи консенсуса с запаздыванием, работы [72], [105] посвящены анализу скорости сходимости. Задача достижения консенсуса за конечное (финитное) время рассматривается в работах [36], [51], [108];

• Распределенное управление формациями подразумевает определенное поведение агентов, при котором они образуют некоторые геометрические конфигурации в пространстве посредством локального взаимодействия. Алгоритмы такого рода применяются для управления группами колесных роботов, беспилотных летательных и подводных аппаратов [4], [11], [13] и т.д. Управление системами, состоящими из большого числа мобильных объектов является важной задачей в силу коммерческого и военного применения. Управление формациями включает в себя такие задачи, как получение формации и слежение формации. В рамках задачи получения/ образования формации группа агентов в пространстве образует некоторую геометрическую фигуру без какого-либо указания для группы (без лидера, виртуального или реального); в задаче слежения группа агентов достигает желаемого геометрического расположения и следит за задающим воздействием (следует за лидером). Существуют разные подходы к решению перечисленных задач: использование методов линейной алгебры [73], [83], [84], метода функций Ляпунова [4], [11], [40], [43], [96], потенциальных функций [69], [94] и др.

• Распределенная оптимизация. Оптим