XVIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Управление роем динамических объектов на базе мультиагентного подхода
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
В соответствии со стратегией научно-технологического развития Российской Федерации в ближайшие 10-15 лет одним из важнейших приоритетов будет «переход к передовым цифровым, интеллектуальным производственным технологиям, роботизированным системам, новым материалам и способам конструирования, создание систем обработки больших объемов данных, машинного обучения и искусственного интеллекта». Для решения этих задач требуется выполнение опережающих исследований, к числу которых можно отнести управление группами роботизированных устройств, функционирующими в динамической среде. Это так называемое мультиагентное управление. Суть мультиагентных технологий заключается в принципиально новом методе решения сложных задач, которые не решаются или трудно решаются классическими математическими методами. На сегодняшний день получили широкое распространение роботизированные системы, состоящие из нескольких устройств, способных реагировать на изменения во внешней среде, самостоятельно обрабатывать данные и взаимодействовать с другими устройствами. Устройства, обладающие описанными свойствами, будем называть в работе динамическими объектами (агентами) (например, беспилотные летательные аппараты, БПЛА).
Актуальность:
Увеличение количества БПЛА предоставляет новые возможности по использованию роботизированных систем для трудных задач, но при этом возникает проблема распределенного управления БПЛА, в частности, в условиях неопределенностей. Это приводит к необходимости создания новых передовых цифровых технологий управления. Повышаются требования по обеспечению устойчивости их функционирования, так как подобные технологии востребованы в жизненно важных областях: распределенные энергетические системы, беспилотное управление автомобилями и летательными аппаратами, мониторинг дорожной сети и территорий, поисково-спасательные операции и т. п.
Проблема:
Применение мультиагентного управления для решения сложных, комплексных задач имеет некоторые трудности, несмотря на наличие явных преимуществ. Во-первых, мультиагентные системы почти всегда опираются на возможность взаимодействия между агентами. Во-вторых, в таких системах зачастую применяют «простые» устройства, которые обладают меньшими вычислительными ресурсами и требуют повышенной энергоэффективности. Поэтому требуется разработка ресурсоэффективных алгоритмов управления, что актуализирует данное исследование.
Цель:
Анализ алгоритмов коллективного поведения групп объектов (агентов) при движении и распределении объектов слежения в условиях наличия неопределенностей внешней среды, получения измерений с помехами и изменения состояния наблюдаемых объектов, рассмотрев три основных подхода управления агентов (объектов) в рое: 1) динамика агента с потенциалом движения и предупреждением столкновений, 2) «протокол локального голосования» 3) и алгоритм управления роем динамических объектов.
Задачи:
исследовать динамику агента с потенциалом движения и предупреждением столкновений в рое;
исследовать свойства оценок циклического алгоритма локального голосования для отслеживания изменений неизвестных параметров системы;
представить алгоритм управления роем динамических объектов.
Гипотеза:
Мультиагентное управление в рое однотипных объектов (агентов) – один из перспективных способ решения сложных задач, использующий принципы самоорганизации, для разработки роботизированных систем.
Методы исследования:
В работе используются методы теорий оценивания, оптимизации, управления, вероятностей и математической статистики; применяются метод локального голосования, имитационное моделирование.
1. Мультиагентный подход и роевое управление
Технология мультиагентных систем (МАС) — это новая модель развития ИТ, ориентированная на совместное использование технологических и технических достижений и преимуществ, которые предоставляют возможности и методы искусственного интеллекта (ИИ), аппаратные и программные средства поддержки распределенности и открытости. В связи с этим, сейчас активно развиваются методы формирования и внедрения сложных адаптивных систем на базе мультиагентных методов и технологий. В качестве исполнительных элементов таких систем используются робототехнические устройства различного назначения, которые могут действовать одновременно в трех средах: на земле (стационарные, колесные и гусеничные устройства), под водой (миниатюрные беспилотные подводные лодки, БППЛ) и в воздухе (беспилотные летательные аппараты).
Роевое управление предполагает собой новый подход, анализирующий возможности построения системы из совокупности автономных интеллектуальных агентов для достижения совместных целей, которые не могут быть достигнуты отдельным роботом или для которых коллективное выполнение поставленной задачи более результативно. Главной идеей роевого управления является «роевой интеллект» (РИ, Swarm Intelligence), широко наблюдаемый в природном мире: косяки рыб, колонии пчел, муравьев и прочие. Роевой интеллект — это система, воплощающая управление коллективным поведением децентрализованной самоорганизующейся совокупностью однородных объектов.
Суть роевого интеллекта заключается в том, что рой, состоящий из динамических объектов (агентов), обладает большими возможностями по сравнению с его отдельными индивидами. Посредством налаживания коммуникаций между членами роя и взаимодействия с внешней средой возможно решение задач, на исполнение которых у отдельного агента не хватает возможностей.
Выделяют два вида роевого управления (рис. 1). Первый из них можно отнести к самоорганизующимся системам, характерным природным образованиям. Признаки биологической самоорганизации:
– каждая особь в рое не обладает индивидуальным сознанием и свободой выбора; – правила поведения определяются генетическим набором, заложенным в каждую особь;
– квазиразумная деятельность роя направлена на сохранение роя как целого и обеспечение его безопасности;
– рой, как правило, состоит из представителей одного вида;
– роли особей в рое могут различаться (в колониях муравьёв, термитов, пчёл и т. д.).
Для такого роя нет какой-либо централизованной системы управления поведением каждой особи. Локальные взаимодействия приводят к возникновению «квазиинтеллектуального» глобального поведения роя, которое может не контролироваться отдельными агентами. Тогда многоагентная система должна обладать самоорганизующимся поведением и проявлять некоторое «разумное» поведение.
Второй вид РИ предполагает наличие управления, причем управляющие воздействия могут поступать как от внешней по отношению к рою управляющей системы, так и от «назначенного» или «локального» лидера (агента), находящегося внутри роя. В первом случае «назначенный» лидер осуществляет команды, поступающие от внешнего управляющего центра, а другие агенты выполняют действия, подчиняясь достаточно банальным правилам. Если агенты перемещаются по плоскости с заданием образовать определенную конфигурацию, то правила могут быть следующими: расчет расстояния от начальной точки; выстраивание в группу; образование заданного градиента плотности; локализация. Если агенты перемещаются в пространстве, то они должны: держать дистанцию между собой и другим объектом; двигаться в том направлении, где находится ближайший объект; стремиться к центру массы группы ближайших объектов; постоянно «общаться с лидером». Основополагающими свойствами управляемого роя обычно являются масштабируемость, гибкость и надежность.
2. Метод потенциального поля
Метод потенциальных полей позволяет в режиме реального времени определять, как правильно облететь аппарат (то есть просто запрещаем аппарат подлетать близко друг к другу). Этот метод не занимает большое количество вычислительных ресурсов в нашей системе.
Формулы для применения данного алгоритма:
– положение i-того аппарата
– положение j-того аппарата
– расстояние (скалярная величина)
– вектор управления
– целевой вектор управления
– вектор потенциального поля
– функция обратно пропорциональная расстоянию
Давайте обсудим, как формируется наше управляющее воздействие при работе потенциальных полей в группе БПЛА.
Для каждого летательного аппарата мы проверяем, попадают ли в расстояние рядом с ним другие ЛА (рис. 2);
для получения управления, которое будет защищать нас от столкновений, а именно скорости, сформированной приближением аппаратов друг к другу в виде нашего потенциального поля, нам необходимо f(d) умножить на ошибку между текущим положением рассматриваемого аппарата и текущим положением аппарата, который мы рассматриваем к данному;
для того, чтобы положить итоговое управление ( ), необходимо прибавить к нему управление , сформированное за счет движения к целевому положению с управлением по полю скоростей, которое позволяет нам защититься от столкновений, после чего необходимо пронормировать данную величину, потому что она может принимать очень большие значения (в системе имеются определённые ограничения);
получаем направление нашего движения, которое затем передаем уже в систему управления аппаратом для его движения по заданной траектории.
Динамические объекты в рое обладают следующими признаками:
Все агенты одинаковы.
Агент может осуществлять обмен сообщениями с некоторым подмножеством агентов, находящихся в пределах некоторой зоны, ограниченной радиусом R, которую обычно называют «зоной видимости» или «радиусом безопасности».
Каждый агент при окончательном определении направления движения старается выбрать маршрут так, чтобы избежать столкновений.
Обратим внимание, как меняется при приближении аппаратов друг к другу функция для скорости, обратно пропорциональной расстоянию, с использованием экспоненциальной зависимости (рис. 3). С помощью этой функции можно получить более плавный наклон функции, а также за счет коэффициентов отредактировать ее.
Существуют другие подходы, например, использование квадратичной зависимости для описания этой функции (рис. 4), то есть для формирования поля скоростей можно использовать не экспоненциальную, а обратную квадратичную зависимость от нашего расстояния, которая тоже будет плавной.
Метод потенциальных полей достаточно легкий алгоритм с вычислительной точки зрения. Для его настройки можно подбирать различные зависимости от расстояния, подбирать коэффициенты, выполнять настройку для разнообразных аппаратов.
За счет простоты этого метода, он до сих пор является одним из самых популярных при формировании команд управления для группы аппаратов и планирования маршрута на этапе предполетного планирования.
3. Протокол локального голосования
Протокол локального голосования был предложен для задачи достижения консенсуса в сети агентов.
Этот протокол с постоянным размером шага исследовался для достижимости асимптотического среднеквадратического консенсуса в задаче с нелинейной динамикой в условиях изменяющейся топологии, помех и задержек.
В качестве примера применения «протокола локального голосования» рассмотрим следующую задачу: перемещение роя агентов из точки A в точку B в условиях неопределенности в отношении преград, встречающихся на пути следования (рис. 5).
Влияние потенциала на движение роя состоит в том, что при его существенном изменении объектам роя необходимо поменять свое направление в сторону, повышающую вероятность выполнения задачи. Другими словами, когда рой встречает преграду, у ближайшего к ней объекта значительно падает потенциал движения по выбранному им пути. В результате, рою необходимо изменить свое направление движения, что может быть достигнуто путем применения протокола локального голосования, рассмотренного выше.
Такой подход дает возможность применения принципов самоорганизации для управления группами роботизированных устройств.
4. Алгоритм управления роем динамических объектов
Предлагается использовать следующий обобщенный алгоритм управления роем агентов на основе консенсуса:
1. Все агенты, входящие в состав роя, получают из некоторого пункта управления задачу, стоящую перед роем.
2. Инициализация протокола голосования, установка связей между соседями, начало обмена сообщениями.
3. Каждый агент diϵ D получает информацию о текущем направлении движения объектов роя, находящихся в зоне его видимости, и числовую характеристику потенциала их движения.
4. Изменение направления движения с применением функции избегания столкновений.
6. Пересчет потенциала движения qtна основе исходной информации агента и дополнительных сведений, получаемых при исследовании окружающего мира и от соседей.
АлгоритмдлярояБПЛА:
# импортируемнеобходимыебиблиотеки
import time
import random
from threading import Thread
# определяемклассдляуправленияроемдронов
class DroneSwarm:
def __init__(self, num_drones):
self.num_drones = num_drones
self.drones = []
self.commands = []
# методдлядобавлениядроновврой
def add_drones(self, drones):
self.drones.extend(drones)
# методдлядобавлениякоманддлядронов
def add_commands(self, commands):
self.commands.extend(commands)
# методдлязапускароядронов
def start_swarm(self):
# запускаемпотокидлякаждогодрона
threads = []
for drone in self.drones:
thread = Thread(target=drone.run, args=(self.commands,))
thread.start()
threads.append(thread)
# ждемзавершениявсехпотоков
for thread in threads:
thread.join()
# определяемклассдлядрона
class Drone:
def __init__(self):
self.id = random.randint(0, 1000)
# методдлязапускадрона
def run(self, commands):
# проходимповсемкомандам
for command in commands:
# проверяем, принадлежитликомандаданномудрону
if self.id == command[0]:
# выполняемкоманду
print('Drone #{} executing command: {}'.format(self.id, command[1]))
time.sleep(1)
# создаемройдронов
swarm = DroneSwarm(3)
# создаемдронов
drones = [Drone() for i in range(swarm.num_drones)]
# добавляемдроновврой
swarm.add_drones(drones)
# добавляемкомандыдлядронов
commands = [(drones[0].id, 'takeoff'), (drones[1].id, 'land'), (drones[2].id, 'hover')]
swarm.add_commands(commands)
# запускаемройдронов
swarm.start_swarm()
Для проверки алгоритма я произвела симуляцию в операционной системе Linux (Ubuntu 15.04) в ROS на платформе Gazebo.
Давайте рассмотрим движения аппарата в группе из пяти штук (рис. 7), где при переходе из одной формации в другую мы будем использовать метод потенциальных полей, а в движении аппарата в целом будем использовать алгоритм управления группой.
Запустим симулятор, в котором уже указано количество ЛА, которые будем использовать для полета.
Сбоку есть бегущая строка, которая определяет местоположение объектов по трём осям координат.
В последствии, аппараты взлетят и будут разлетаться при переходе формации.
Беспилотники при полете постоянно отклоняются друг от друга, но при этом занимают заданные точки.
5. Заключение
Таким образом, в данной работе представлены и проанализированы три наиболее важные и востребованные основы управления агентов (объектов) в рое на базе мультиагентного подхода, включающего метод потенциальных полей, применение «протокола локального голосования» и алгоритма управления роем динамических объектов, который может достаточно успешно использоваться для решения ряда актуальных задач, создания соответствующих методов и технологий управление группами роботизированных устройств, функционирующими в динамической среде. Что в последствии создаст потенциал и возможности для активного мониторинга территории, государственно важных объектов и для оперативного управления инцидентами на земле, под водой и в воздухе.
Список литературы
1. Бендерская Е.Н., Граничин О.Н., Кияев В.И. Мультиагентный подход в вычислительных технологиях: новые грани параллелизма и суперкомпьютинг. // Сборник научных статей 8й Международной научной конференции «Информационные технологии в бизнесе». СПб, издво «Инфода»: 7–13, 2013.
2. Beni G., Wang J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, P. 26–30, 1989.
3. Амелина Н.О., Фрадков А.Л. Приближенный консенсус в стохастической динамической сети с неполной информацией и задержками в измерениях. Автоматика и телемеханика, 2012. №11. С. 6–29.
4. https://gazebosim.org/home
5. https://www.ros.org/
6. https://core.ac.uk/download/pdf/287425642.pdf
7. https://cyberleninka.ru/article/n/algoritmy-roevogo-intellekta-i-ih-primenenie-dlya-analiza-obrazovatelnyh-dannyh
8. https://youtu.be/Lrj5UcOv5Kg
9. https://www.rusnauka.com/25_DN_2008/Economics/28674.doc.htm
10. https://studfile.net/preview/9436925/page:18/
11. https://cyberleninka.ru/article/n/virtualnaya-transportno-logisticheskaya-sistema-logisticheskie-tsentry-kak-punkty-virtualnogo-ekonomicheskogo-analiza
12. https://enterprise.4vision.ru/otrasli/transport-i-infrastruktura/monitoring-dorozhnoj-obstanovki/
13. https://aeromotus.ru/the-use-of-dji-drones-in-road-construction/
Приложения:
[1] Рис. 1. Два вида роевого управления
[2] Рис.2. Траекторное планирование группы агентов (БПЛА) методом векторного поля (карты потенциалов) следования пути.
[3] Рис.3. График зависимости скорости от квадрата экспоненты расстояния между агентами.
[4] Рис.4. График зависимости скорости от обратного квадрата расстояния между агентами.
[5] Рис. 5. Перемещение роя из точки A в точку B по протоколу локального голосования
[6] Рис. 6. Расчет изменения траектории агентом d5
[7] Рис. 7. Полет пяти ЛА в Gazebo.