Управление движением строя в мультиагентных системах тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Морозова Наталья Сергеевна

• Морозова Наталья Сергеевна
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Морозова Наталья Сергеевна

Введение

1 Постановка задачи, управление движением строя автономных агентов в случае управления по скорости

1.1 Основные определения

1.1.1 Общие понятия и класс допустимых управлений

1.1.2 Геометрическая структура строя

1.1.3 Виртуальные лидеры

1.1.4 Формализация постановки задачи

1.2 Правило управления

1.2.1 Основные идеи предлагаемого закона управления

1.2.2 Правило расчёта положения виртуальных лидеров

1.2.3 Итоговое правило управления

1.2.4 Формулировка правила управления в матричной форме

1.2.5 Процедура расчёта коэффициентов приоритета виртуальных лидеров

для агента

1.3 Анализ правила управления

1.3.1 Формальное обоснование применимости правила управления по скорости

2 Дискретизация задачи, разработка среды моделирования

2.1 Выбор способа апробации разработанных правил управления мультиагентной системой

2.2 Основные принципы разработки среды моделирования

2.2.1 Разработка среды моделирования

2.2.2 Процедура внедрения новых алгоритмов в среду моделирования

2.2.3 Архитектура классов программы моделирования

2.3 Переход к дискретной модели

2.3.1 Правило управления в дискретной форме

2.3.2 Алгоритм управления

2.4 Результаты моделирования

2.4.1 Ключевые параметры оценки эффективности алгоритма управления мультиагентной системой

2.4.2 Зависимость эффективности управления от параметров управления

2.4.3 Взаимодействие различных групп связности

2.4.4 Переключение текущей целевой точки

2.4.5 Моделирование внештатных ситуаций

3 Модификации правила управления и исследование правила управления

при вводе в модель ошибок изменения и шумов

3.1 Огибание препятствий

3.1.1 Основные определения и модель препятствия

3.1.2 Модификация правила управления для огибания препятствий

3.1.3 Результаты моделирования для одиночных неподвижных препятствий среднего размера

3.1.4 Результаты моделирования для одиночных неподвижных препятствий малого размера

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

3.1.6 Огибание движущихся препяствий малого и среднего размера

3.2 Избежание коллизий между агентами

3.3 Результаты модификации правила управления для избежания коллизий между

агентами и огибания препятствий

3.4 Ошибки измерения и шумы

3.4.1 Математическая модель ошибок измерений и шумов

3.4.2 Моделирование и анализ работы алгоритма в случае введения ошибок измерений и шумов

3.4.3 Итоги анализа работоспособности алгоритма при наличии ошибок измерений и шумов

3.5 Фиксированная структура строя

3.5.1 Количество агентов меньше числа точек целевой геометрической структуры

3.5.2 Количество агентов больше числа точек целевой геометрической структуры

3.5.3 Переходы между фиксированной и динамической ЦГС

4 Управление строем автономных агентов в случае управления по ускорению

4.1 Модель динамики агента с учётом ускорения и правило управления по ускорению

4.1.1 Ограничения и допустимый класс управлений

4.1.2 Адаптация разработанных принципов управления к управлению по ускорению

4.1.3 Дискретизация правила управления в случае управления по ускорению

и моделирование

4.1.4 Анализ результатов моделирования

4.1.5 Лидер в прямом преследовании

4.2 Сравнение двух реализаций управления по ускорению

4.2.1 Методика проведения исследования при помощи моделирования

4.2.2 Результаты анализа немодифицированного управления по ускорению

4.2.3 Результаты анализа модифицированного управления по ускорению и сравнение с немодифицированным

4.3 Модификация базового алгоритма управления по ускорению для огибания препятствий и избежания коллизий

4.3.1 Огибание препятствий разного размера

4.3.2 Избежание коллизий между агентами при управлении по ускорению

4.3.3 Огибание движущихся препятствий малого и среднего размера при управлении по ускорению

4.4 Анализ немодифицированного управления по ускорению в условиях наличия шумов и ошибок измерения

4.4.1 Исследование помехоустойчивости управления по ускорению при помощи компьютерного моделирования

4.4.2 Сравнительный анализ помехоустойчивости управления по скорости и

по ускорению

Заключение

Список рисунков

Список таблиц

Литература

А Некоторые таблицы с результатами моделирования

Введение диссертации (часть автореферата) на тему «Управление движением строя в мультиагентных системах»

Введение

Актуальность избранной темы. В широком смысле под мультиагентной системой (от англ. MAS — Multi-agent system) понимается набор единиц (сущностей) программного обеспечения или физических устройств, которые помещены в некую среду, в которой они могут осуществлять информационный обмен друг с другом и взаимодействовать определённым образом со средой. При этом, компоненты мультиагентной системы обладают следующими свойствами: они автономны, управляются по децентрализованному принципу и могут получать информацию лишь из ограниченной части окружающей среды. В настоящее время управление мультиагентными системами является крайне динамично развивающимся и востребованным направлением в теории управления.

Повышенный интерес в научном сообществе к мультиагентным системам стал проявляться после ключевых работ ряда учёных в конце 20 века. В 1987 году Крейг Рейнол-дс (Craig Reynolds), вдохновлённый примерами из живой природы, представил результаты компьютерного моделирования «стайного» поведения [1]. В 1995 году Тамаш Вичек (Tamas Vicsek) математически описал и обосновал наблюдаемые при моделировании результаты [2]. Это положило начало активной разработке теории самоорганизующихся мультиагентных систем, основными принципами которых является самостоятельность каждого объекта системы, возможность получения только локальной информации, в том числе от ближайших агентов-соседей, и децентрализация управления. В скором времени полученные результаты начали применяться для управления робототехническими системами, состоящими из большого числа относительно небольших и недорогостоящих элементов.

Интерес научного сообщества к решению проблем управления при помощи мультиагент-ного подхода обусловлен его эффективностью и надёжностью в сочетании с относительной простотой. Количество публикаций по данной теме неуклонно растёт в течение последних нескольких десятилетий. Мультиагентные системы находят множество областей применения: робототехника, производство [3], моделирование социальных процессов [4] и природных процессов, управление сенсорными сетями, интеллектуальный анализ данных (data mining) [5].

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

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

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

Данная работа посвящена задаче управления строем агентов (англ. formation control problem) — одной из наиболее актуальных и важных задач в управлении мультиагентны-ми системами, имеющей широкое прикладное значение для робототехники при управлении беспилотными летательными аппаратами, автономными подводными аппаратами и группами мобильных роботов небольшого размера [6]. Для равномерного распределения в зоне выполнения миссии, поддержания устойчивой связи внутри группы и избежания столкновений роботы должны при движении соблюдать некоторую геометрическую структуру строя (определённое расположение относительно друг друга или относительно центра масс группы, образующее определённую геометрическую фигуру). Возникает необходимость разработать децентрализованное правило управления и алгоритм, которые бы позволили осуществлять эффективное управление движением агентов с сохранением геометрической формы строя при условиях полной автономности агента и возможности получения информации только от своих ближайших соседей.

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

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

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

Централизованный и децентрализованный подходы. В целом, подходы к управлению группой роботов делят на централизованное управление и децентрализованное, а также можно выделить некоторые подходы, комбинирующие в себе централизованное и децентрализованное управление. Принципы централизованного, децентрализованного и комбинированного управления детально рассмотрены в книге И. А. Каляева [7]. Для постановки задачи принципиальным является то, при помощи какого управления необходимо решить задачу: централизованного, децентрализованного или смешанного, так как это накладывает существенные ограничения. На практике, принципы централизованного управления могут быть реализованы следующим образом: управление группой возлагается на некий центр управления (командный пульт), который осуществляем расчёт траектории каждого робота из группы и передаёт команды к исполнению каждому роботу по каналам связи. Достоинствами централизованного подхода являются: возможность строгого контроля над ситуацией, постоянной координации роботов между собой и возможность немедленной коррекции управления в нестандартной ситуации с привлечением оператора. К недостаткам централизованного подхода можно отнести следующие аспекты:

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

2. наличие ограничений, связанных с ограничениями на радиус действия связи (например, беспилотный летательный аппарат, не может значительно отдалиться от наземного пункта управления) или со слишком длительным временем получения сигнала (например, время задержки сигнала для управления марсоходом составляет около 13 минут, окно для связи с марсоходом составляет около 8 минут в день [8]);

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

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

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

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

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

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

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

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

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

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

Использование большого числа аппаратов позволило бы ускорить выполнение тех миссий, где задачи легко могли бы выполняться несколькими аппаратами параллельно (например, поисково-спасательные а также обзорно-поисковые работы, в которых требуется площадная съёмка участков донной поверхности [9]). На данный момент, применение принципов мультиагентного децентрализованного управления является одним из перспективных направлений развития практики использования роботов в различных операциях, направленных на решение практических задач. По этой причине в данной работе рассматривается именно децентрализованный подход.

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

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

Во-вторых, можно рассматривать управление аппаратом по скорости или по ускорению, что отражается дифференциальным уравнением первого или второго порядка соответственно (рг = щ; рг = щ, где Рг — координаты г-го агента, а иг — управление г-м агентом) [10]. Под управлением по скорости или ускорению понимается возможность управляющего воздействия г-го агента напрямую на его скорость или ускорение соответсвенно.

В-третьих, можно рассматривать решение задачи в двухмерном пространстве или в трёхмерном пространстве. Для решения задач, связанных с подводными и летательными

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

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

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

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

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

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

Степень разработанности темы, существующие подходы и их особенности.

Значительный вклад в управление мультиагентными системами внёс А. Б. Куржанский. В его работах [12,13] задача группового управления рассматривается постановке, отличной от постановки в данной работе: элементы группового движения должны находиться внутри эллипсоидального контейнера в условиях взаимного нестолкновения, при этом расположение элементов относительно друг друга внутри контейнера может варьироваться и не задаётся жёстко.

Одним из крайне распространённых децентрализованных методов управления движением группы роботов является метод потенциальных функций [14, 15]. В литературе, как правило, метод потенциальных функций используется для решения задач сбора агентов в подобие стаи или «стайного» движения к определённой цели [16]. Суть метода заключается в формировании закона управления при помощи искусственной функции, так называемой «потенциальной» функции, которая создаёт некоторое потенциальное силовое поле. Ускорение каждого агента прямо пропорционально значению функции в определенный момент времени (аналогично второму закону Ньютона: F.\ = mai). Под действием силы агенты либо притягиваются (если они далеко друг от друга, но в зоне видимости), либо отталкиваются (если они слишком близко). Например, сила, действующая на агента г может быть рассчитана следующим образом:

t = Е *

1 г i.i +

4 ^ Г1к2 '

V]: гц>Д Рк:

Здесь "у — вектор расстояния между агентами г и ] (имеющими координаты р^ и р^ соответственно), Гц = у ||, а к\,к2 Е К — настраиваемые параметры метода.

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

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

По этой причине в литературе в большинстве случаев для решения задачи управления строем используются следующие подходы: первый — задать заранее желаемое расстояние между парами агентов и применить теорию жесткости графов [17,18]; второй — задать желаемое положение агента относительно его соседей через вектора и воспользоваться правилами консенсуса (усреднения) [19-21]; третий — в каждый момент времени передавать агентам информацию о положении и направлении движения виртуальной формации, на основании чего каждый агент может сконструировать виртуального лидера и следовать за ним [22-24]. Далее кратко излагаются идеи, лежащие в основе данных подходов.

Суть первого подхода, основанного на теории жёсткости графов, состоит в том, чтобы задать геометрическую структуру строя как целевые расстояния между некоторыми парами агентов. Вводится граф, вершины которого соответствуют агентам, а рёбра — заданным целевым расстояниям между агентами, которым соответствуют вершины, соединённые ребром. В данном подходе задачей является определение свойств, которыми должны обладать задаваемые ограничения на расстояния между парами агентов, чтобы геометрическая структура строя была жёсткой, недеформируемой при соблюдении указанных ограничений по мере движения строя. На базе заданных целевых расстояний а^ , а^ = \\pi — pj ||, где pi ,pj — координаты агентов, составляется матрица жёсткости соответствующего графа. Исследования ранга матрицы жёсткости графа позволяет определить, является ли конструкция, заданная исследуемым набором ограничений, жёсткой [17]. Для успешного управления строем заданная при помощи aij система ограничений должна быть осуществимой (должен существовать набор точек, удовлетворяющих всем ограничениям), система ограничений должна задавать жёсткий граф, каждая пара агентов, связанная ограничением по расстоянию, должна быть в состоянии узнать координаты друг друга. За рамками постановок задач в данном подходе обычно остаётся рассмотрение задачи по приведению мультиагентной системы в состояние, соответсвующее системе ограничений. Моделирование, выполненное автором, показало, что задача построения строя, соответствующего заданной геометрической структуре, при помощи данного подхода может быть решена, например, введением следующего управления:

Pi N ' ((Рг — Pi) ——л—~ ). Движение группы агентов при применении данного

• V \\Pi — Pj\\ J

у. задано aij 4 " J " '

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

Второй подход к управлению движением строя был получен модификацией управления, ведущего агентов к консенсусу (достижение консенсуса — приведение к единому значению некоторого параметра состояния, которым обладает каждый агент, при помощи усреднения). Задачи по поиску консенсуса составляют целый отдельный класс задач по управлению мультиагентными системами (с довольно исчерпывающим обзором задач, решаемых при помощи данного подхода, можно ознакомиться в работе [19]). Одна из задач по поиску консенсуса заключается в сборе всех агентов в единой точке, она получила название «задача рандеву» (от англ. rendezvous problem). В таких задачах рассматриваются безразмерные агенты. Управление, обеспечивающее сбор агентов в одной точке при условии того, что каждый агент из группы знает координаты всех остальных агентов, имеет следующий вид:

Рг(^) = (Рз(к) — р())- Если же добавить к данному правилу управления вектор сдвига Ь^ 3=г

(в двухмерном случае вектор Ъ^ = [ 4 ) отражает относительное расположение агентов г

\Угз/

и ] по обеим осям неподвижной мировой системы координат), то вместо сбора в одной точке можно получить определённую геометрическую структуру. Каждый агент будет в итоге сдвинут относительно точки «рандеву» на вектор Ь^ ^ ^ Ь^ . Правило управление в данном

Список литературы диссертационного исследования кандидат наук Морозова Наталья Сергеевна, 2016 год

Литература

1. Reynolds C. Flocks, birds, and schools: A distributed behavioural model // Comput. Graph. 1987. Vol.21, N 4. P. 25-34.

2. Vicsek T., Czirok A., Jacob E. B., et al. Novel type of phase transitions in system of self-driven particles // Phys. Rev. Lett. 1995. Vol. 75, N 6. P. 1226-1229.

3. Wang H., Qiu G., Huang S. Cement industry control system based on multi-agent // Central South University of Technology. 2004. Vol. 11, N 1. P. 4-44.

4. Bosse T., Hoogendoorn M., Klein C. A., et al. Modelling collective decision making in groups and crowds: Integrating social contagion and interacting emotions, beliefs and intentions // Autonomous Agents and Multi-Agent Systems. 2013. Vol.27, N 1. P. 52-84.

5. Cao L., Luo C., Zhang C. Agent-Mining Interaction: An Emerging Area // Autonomous Intelligent Systems: Multi-Agents and Data Mining. 2007. N 4476. P. 60-73.

6. Городецкий В. И., Карсаев О. В., Самойлов В. В., Серебряков С. В. Прикладные мно-гоагентные системы группового управления // Искусственный интеллект и принятие решений. 2009. № 2. С. 3-24.

7. Каляев И. А., Гайдук А. Р., Капустян С. Г. Модели и алгоритмы коллективного управления в группах роботов. М.: ФИЗМАТЛИТ, 2009. - 280 с.

8. Makovsky A., Ilott P., Taylor J. Mars Science Laboratory Telecommunications System Design // Design and Performance Summary Series (Article 14). National Aeronautics and Space Administration Jet Propulsion Laboratory California Institute of Technology. Pasadena, California, 2009. - 118 P.

9. Инзарцев А. В., Павин А. М., Багницкий А. В. Планирование и осуществление действий обследовательского подводного робота на базе поведенческих методов // Подводные исследования и робототехника. 2013. № 1(15). С. 4-16.

10. Gazi V., Fidan B. Coordination and Control of Multi-agent Dynamic Systems: Models and Approaches // Swarm Robotics. Lecture Notes in Computer Science. 2007. Vol. 4433. P. 71102.

11. Lambercy F., Tharin J. Khepera 3 user manual [Electronic resource] // K-team mobile robots [Official website]. URL: http://ftp.k-team.com/KheperaIII/UserManual/Kh3.Robot.UserManual.pdf (accessed 18.11.2014).

12. Куржанский А. Б. О задаче группового управления в условиях препятствий // Труды Ин-та матем. и мех. УрО РАН. 2014. Т. 20, № 3. С. 166-179.

13.

14

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25

26

27

Куржанский А. Б. Задача о нестолкновениях при групповом движении в условиях препятствий // Труды Ин-та матем. и мех. УрО РАН. 2015. Т. 21, № 2. С. 134-149. Hengster-Movric K., Bogdan S., Draganjac I. Multi-Agent Formation Control Based on Bell-Shaped Potential Functions // Intelligent Robotic Systems. 2010. Vol.58, N 2. P. 165-189.

Yang J., Lu Q., Lang X. Flocking shape analysis of multi-agent systems // Science China Technological Sciences. 2010. Vol.53, N 3. P. 741-747.

Tanner H. G., Jadbabaie A., Pappas G.J. Flocking in Teams of Nonholonomic Agents // LNCIS. Cooperative control. 2005. Vol. 309. P. 229-239.

Eren T., Belhumeur P., Anderson B. et al. A framework for maintaining formation based on rigidity // Proc. of the 15th IFAC World Congress. Vol. 15. Barcelona: International Federation of Automatic Control, 2002. P. 1306-1306.

Rodrigues J., Figueira D., Neves C., et al. Leader-following graph-based distributed formation control // Robotica. 2009. N 75. P. 8-14.

Olfati-Saber R., Fax J. A., Murray R. M. Consensus and Cooperation in Networked MultiAgent Systems // Proceedings of the IEEE. 2007. Vol. 95, N 1. P. 215-233.

Wang J., Nian X., Wang H. Consensus and formation control of discrete-time multi-agent systems // Journal of Central South University of Technology. 2011. Vol.18, N 4. P. 11611168.

Zhengping W., Zhihong G., Xianyong W., et al. Consensus Based Formation Control and Trajectory Tracing of Multi-Agent Robot Systems // Journal of Intelligent Robotic Systems. 2007. Vol. 48, N 3. P. 397-410.

Lalish E., Morgansen K., Tsukamaki T. Formation tracking control using virtual structures and deconfliction // Proceedings of the 2006 IEEE Conference on Decision and Control. San Diego: IEEE, 2006. P. 5699-5705.

Lewis M. A., Tan K. High precision formation control of mobile robots using virtual structures // Autonomous Robots. 1997. Vol. 4, N 4. P. 387-403.

Zhonghai Z., Jian Y., Wenxia Z., et al. Formation control based on a virtual-leader-follower hierarchical structure for autonomous underwater vehicles // International journal of advancements in computing technology. 2012. Vol. 4, N 2. P. 111-121.

Eren T., Morse A. S., Belhumeur P. N. Closing ranks in vehicle formations based on rigidity // Proc. of the 41st IEEE Conference on Decision and Control. 2002. Vol. 3. P. 2959-2964.

Xue D., Yao J., and Wang J. H^ Formation Control and Obstacle Avoidance for Hybrid Multi-Agent Systems // Journal of Applied Mathematics. 2013. Vol. 2013. Article ID 123072. URL: http://dx.doi.org/10.1155/2013/123072 (accessed 14.11.2015)

Иванов Д. Я. Построение формаций в группах квадрокоптеров с использованием виртуального строя // Труды XII Всероссийского совещания по проблемам управления ВСПУ-2014. М.: ИПУ им. В. А. Трапезникова РАН, 2014. С. 1971-1978.

28. Морозова Н. С. Виртуальные формации и виртуальные лидеры в задаче о движении строем группы роботов // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. 2015. № 1. С. 135-149.

29. Морозова Н. С. Управление движением строя для мультиагентной системы, моделирующей автономных роботов // Вестник московского университета. Серия 15. Вычислительная математика и кибернетика. 2015. № 4. С. 23-31.

30. Морозова Н. С. Децентрализованное управление движением строя роботов при динамически изменяющихся условиях // Искусственный интеллект и принятие решений. 2015. № 1. С. 65-74.

31. Морозова Н. С. Формирование строя и движение строем для мультиагентной системы с динамическим выбором структуры строя и положения агента в строю // Труды XII Всероссийского совещания по проблемам управления ВСПУ-2014. М.: ИПУ им. В. А. Трапезникова РАН, 2014. С. 3822-3833.

32. Мисатюк (Морозова) Н. С. К вопросу об управлении группой роботов: комбинирование централизованного и децентрализованного методов // Сборник тезисов XIX Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2012» секция «Вычислительная математика и кибернетика». М.: Издательский отдел Факультета ВМК МГУ им. М. В. Ломоносова. МАКС Пресс, 2012. С. 82-84.

33. Морозова Н. С. Алгоритмы управления движением для мультиагентных систем // Сборник тезисов научной конференции «Тихоновские чтения». М.: Издательский отдел Факультета ВМК МГУ им. М. В. Ломоносова. МАКС Пресс, 2013. С. 10-11.

34. Морозова Н. С. Огибание препятствий при децентрализованном управлении движением строя роботов // Устойчивость и процессы управления: Материалы III международной конференции (Санкт-Петербург, 5-9 октября 2015 г.) / Под ред. А. П. Жабко, Л. А. Петросяна. СПб.: Издательский Дом Фёдоровой Г. В., 2015. С. 537-538.

35. Морозова Н. С. Задача управления движением строя для мультиагентной системы в приложении к робототехнике // Дифференциальные уравнения. О семинаре по проблемам нелинейной динамики и управления при московском государственном университете им. М.В.Ломоносова. 2015. Т. 51, №8. С. 1117-1119.

36. Allan R. Survey of Agent Based Modelling and Simulation Tools [Electronic resource] // Daresbury, Warrington. Computational Science and Engineering Department, STFC Daresbury Laboratory, 2010. - P. 42. URL: http://purl.org/net/epubs/work/50398 (accessed 14.11.2015).

37. Foudil C., Noureddine D., Sanza C., et al. Path finding and collision avoidance in crowd simulation // Journal of Computing and Information Technology. 2009. Vol.17, N3. P. 217228.

38. Cuiqin M., Tao L., Jifeng Z. Consensus control for leader-following multi-agent systems with measurement noises // Journal of Systems Science and Complexity. 2010. Vol.23, N1. P. 3549.

Приложение Л

Некоторые таблицы с результатами моделирования

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

Общие параметры достижение Т 1 достижение Т 2

&>гпах Утах дт 1 + дТ2 ср. е f Иш е f ОМш е f Чт 1 УИш е^ Ят 1 Иш е f Я\[ш е f Чт 2 ЧИш е^ ЯТ 2

0.25 221 0.54 0.08 118 131 0.90 0.11 90 90 1

0.5 189 0.30 0.08 60 107 0.56 0.08 55 82 0.67

0.75 184 0.31 0.15 52 105 0.49 0.06 42 79 0.53

1 181 0.28 0.14 58 102 0.56 0.07 42 79 0.53

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

Общие параметры достижение Т 1 достижение Т 2

{Ьтах Утах Чт 1 + Ят 2 ср. е f Иш е f Чт 1 ЧИш е^ Ят 1 Иш е f Я\[ш е у 0_т2 ЧИш е^ ЯТ 2

0.25 227 0.36 0.01 108 132 0.81 0.01 77 95 0.81

0.5 216 0.20 0.02 46 121 0.38 0.02 44 95 0.46

0.75 235 0.16 0.04 30 132 0.22 0.03 28 103 0.27

1 261 0.16 0.04 52 146 0.35 0.03 36 115 0.31

Таблица А.3: Таблица с результатами моделирования достижения двух целевых точек для немодифицированного алгоритма управления по ускорению (дополнительно по метрике ошибки строя е*)

Общие параметры достижение Т1 достижение Т2

&тах Иш шах» е/ Иш шах» е/

0.25 0.031 0.031

0.5 0.034 0.021

0.75 0.044 0.019

1 0.035 0.035