МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ФИЗИКО - ТЕХНИЧЕСКИЙ ИНСТИТУТ

(национальный исследовательский университет)

КАФЕДРА ИНФОРМАТИКИ

Разработка системы моделирования группового поведения беспилотных летательных аппаратов

Выпускная квалификационная работа на степень магистра студента 873 группы ФУПМ

Кульченкова Кирилла Геннадьевича

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

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

доцент Устюжанин А. Е.

Оглавление

Введение 3

Обзор 5

Parrot AR.Drone 5

Aeryon SkyRanger 7

Основные понятия и постановка задачи 8

Обзор систем имитации многоагентных систем 10

Simpy 10

NetLogo 11

AnyLogic 11

Результаты сравнения 12

Теоретическая часть: описание проделанной работы 13

Реализация 14

Разработка системы симуляции 14

Разработка аналитического модуля 15

Разработка модуля вывода данных. 17

Разработка алгоритмов. 18

Волновой алгоритм 18

Простой алгоритм 19

Групповой алгоритм 20

Тестирование системы. 22

Заключение 25

Список литературы 26

Введение

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

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

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

Целью работы является создание имитационной системы для оценки и сравнения различных характеристик алгоритмов управления группой роботов/квадрокоптеров и произвести тестирование системы алгоритмами:

• Обычный полет квадрокоптера от пункта 1 к пункту 2 с подзарядкой при необходимости.

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

Для достижения цели была проделана следующая работа:

• Разработан алгоритм группового поведения роботов.

• Реализован алгоритм тривиальной доставки.

• Реализован алгоритм групповой доставки.

• Проведен анализ результатов тестирования алгоритмов.

Обзор

Многовинтовые вертолёты разрабатывались ещё в первые годы вертолётостроения. Первый квадрокоптер, который реально оторвался от земли и мог держаться в воздухе, был создан Георгием Ботезатом и испытан в 1922 году. Недостатком этих аппаратов была сложная трансмиссия, передававшая вращение одного мотора на несколько винтов. Изобретение хвостового винта и автомата перекоса положило конец этим попыткам. Новые разработки начались в 1950-е годы, но дальше прототипов дело не продвинулось.

Новое рождение мультикоптеры получили в XXI веке, уже как беспилотные аппараты. Благодаря простоте конструкции квадрокоптеры часто используются в любительском моделировании. Мультикоптеры удобны для недорогой аэрофото и киносъёмки — громоздкая камера вынесена из зоны действия винтов.

Современные квадрокоптеры можно разделить на две группы: управляемые и автономные. Первые во многом «игрушки», они позволяют получать изображение с камеры, установленной на коптере, летают 10-20 минут. Очевидно, что с помощью таких коптеров невозможно создать полноценно рабочее решение . Однако, есть среди них и более продвинутые решения, которые имеют большой радиус полета. Вторые представляют больший интерес, т.к. имеют на борту компьютер, позволяющий управлять квадрокоптером, а также обычно имеют достаточно большой радиус полета.

Рассмотрим примеры квадрокоптеров.

Parrot AR.Drone

В

Рисунок 1. AR.Drone

2010 году произошел настоящий бум радиоуправляемых игрушек, а в частности, летающих. Компания Parrot представила AR.Drone. На CES 2011 устройство оказалось признано одним из лучших развлекательных гаджетов, публика была в восторге.

Спецификация:

Размеры:

С защитным кожухом: 52,5x51,5 см

Без кожуха: 45x29 см

Масса:

380 г — с корпусом для улицы

420 г — с корпусом для помещения

Скорость полёта: 5 м/с; 18 км/ч
Максимальный радиус полета: ограничен радиусом работы wifi (50-120 метров в зависимости от погодных условий)
Длительность полёта: около 12 минут

Совершенно очевидно, что квадрокоптер с такой конфигурацией не в состоянии выполнять какие-либо промышленные задачи. Даже если учесть, что на него можно будет установить бортовой компьютер, который сможет убрать ограничение полета дальностью работы wi-fi , коптер сможет лететь не больше 12 минут, т.е пролететь около 6км.

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

Aeryon SkyRanger

S

Рисунок 2. SkyRanger

kyRanger представляет собой квадрокоптер, предназначенный для видеонаблюдения. Он оснащён четырьмя пропеллерами; заряда аккумуляторной батареи, как утверждается, хватает на 50 минут пребывания в воздухе. В сложенном виде ЛА помещается в рюкзак, который оператор может носить за спиной.

SkyRanger сохраняет стабильность полёта при постоянном ветре, дующем со скоростью 65 км/ч. Более того, устройство способно противостоять порывам до 90 км/ч. Диапазон рабочих температур — от минус 30 до плюс 50 градусов Цельсия. Квадрокоптеру не страшны влага и пыль, а также удары.

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

Основные понятия и постановка задачи

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

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

Итак, простой алгоритм полета – это алгоритм полета, в котором при разрядке квадрокоптера он останавливается для зарядки. Групповой алгоритм полета – алгоритм, в котором квадрокоптеры решают задачу доставки коллективно.

Python – высокоуровневый язык программирования общего назначения. Ipython – интерактивная оболочка для python. Notebook – веб среда, в которой можно запускать код на python и отслеживать результаты его работы, в том числе выводить графики.

В работе рассматриваются алгоритмы работающие на некоторой территории, в которой расположены точки O_i(координаты каждой точки O_i_x, O_i_y). Точки используются для зарядки и дислокации квадрокоптеров. Квадрокоптеры выполняют задачи по доставке груза из точки [s_x, s_y] в точку [e_x, e_y]. Квадрокоптер обладает следующими параметрами:

1. Максимальная скорость полета MAX_SPEED.

2. Скорость разрядки батарей квадрокоптера DISCHARGE_SPEED

3. Скорость зарядки батарей квадрокоптера CHARGE_SPEED

4. Максимальная масса груза MAX_MASS

Скорость полета квадрокоптера линейно зависит от массы груза, который квадрокоптер переносит.

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

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

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

Обзор систем имитации многоагентных систем

Simpy

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

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

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

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

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

NetLogo

Система NetLogo[1] разработана в духе языка программирования Logo. Система разрабатывалась во многом для обучения разработки многоагентных сетей. Обучение программированию происходит через концепты: turtle, patches, links, observers. Огромным плюсом данной системы является то, что система используется как для обучения, так и для моделирования в научных целях. Система позволяет моделировать связные явления.

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

NetLogo находится в свободном доступе на веб-сайте NetLogo . Это используется в широком спектре образовательных контекстах из начальной школы в аспирантуру.

AnyLogic

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

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

Результаты сравнения

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

	NetLogo	SimPy	AnyLogic
Язык разработки	Logo	Python	AnyLogic
Платформа	Win, Linux, MacOS	Win, Linux, MacOS	Win, MacOS
Графический интерфейс	Есть	Нет	Есть
Стоимость	Бесплатная	Бесплатная	Платная
3D симуляция	Есть	Нет	да
Используется в целях	Академические, любительские	Академические, любительские	Академические
Модульная расширяемость	Нет	Есть	Нет

Большим плюсом Simpy является модульное расширение, поэтому для разработки системы был выбран именно он.

Теоретическая часть: описание проделанной работы

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