Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Система должна состоять из 3 основных компонент:

• Модуль работы алгоритма

• Модуль анализа

• М
  

  Рисунок 3. Схема системы.

  одуль вывода графических результатов

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

Реализация

Рассмотрим теперь более подробно стадии реализации данной системы.

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

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

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

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

   1. Разработка простого алгоритма

   2. Разработка группового алгоритма

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

Система симуляции была реализована с помощью SimPy. Система поддерживает загрузку класса алгоритма с интерфейсами для взаимодействия с симуляцией. Для взаимодействия используется интерфейсы: run, get_result. Первый запускает модель в среде симуляции, второй возвращает результаты моделирования.

class Copter(object):

#Список параметров

#Скорость зарядки

CHARGE_SPEED = 0.6

#Скорость замены груза

EXCHANGE_TIME = 2

#Скорость разрядки

DISCHARGE_SPEED = 0.01

#Максимальная скоость

MAX_SPEED = 10

#Максимальная масса

MAX_MASS = 5

#Инициализация

def __init__(self, args):

#Старт симуляции

def run(self):

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

Класс квадрокоптера(Copter) инициализируется с параметрами модели, в данном случае есть параметры CHARGE_SPEED(скорость зарядки), EXCHANGE_TIME(скорость обмена грузами), DISCHARGE_SPEED(скорость разрядки квадрокоптера), MAX_SPEED(максимальная скорость полета, при условии отсутствия груза), MAX_MASS(максимальная масса груза). Метод run запускает работу модели в среде SimPy. Модуль запускает модель несколько раз с различными параметрами: различными маршрутами, меняется скорость квадрокоптеров, скорость разрядки квадрокоптера, максимальная масса, скорость зарядки. По результатам работы метода выводятся результаты работы модели.

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

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

Рисунок 4. Аналитический модуль

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

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

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

Рисунок 5.

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

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

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

Алгоритм работает на дискретном рабочем поле (ДРП), представляющем собой ограниченную замкнутой линией фигуру, не обязательно прямоугольную, разбитую на прямоугольные ячейки, в частном случае - квадратные. Множество всех ячеек ДРП разбивается на подмножества: «проходимые» (свободные), т. е при поиске пути их можно проходить, «непроходимые» (препятствия), путь через эту ячейку запрещён, стартовая ячейка (источник) и финишная (приемник). Назначение стартовой и финишной ячеек условно, достаточно - указание пары ячеек, между которыми нужно найти кратчайший путь.

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

Работа алгоритма включает в себя три этапа: инициализацию, распространение волны и восстановление пути.

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

Далее, от стартовой ячейки порождается шаг в соседнюю ячейку, при этом проверяется, проходима ли она, и не принадлежит ли ранее меченной в пути ячейке.

Соседние ячейки принято классифицировать двояко: в смысле окрестности Мура и окрестности фон Неймана, отличающийся тем, что в окрестности фон Неймана соседними ячейками считаются только 4 ячейки по вертикали и горизонтали, в окрестности Мура - все 8 ячеек, включая диагональные.

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

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

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

Имеется карта, на которой расположены точки заправки квадрокоптеров. Точки расположены сеткой n на n.

Рисунок 6. Карта

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

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

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

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

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

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

Алгоритм поиска таков:

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

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

3. Проводим поиск по соседним точкам. Точка считается соседней, если квадрокоптер с текущего момента до времени прилета коптера с грузом успевает зарядиться. Если находим такой квадрокоптер, то резервируем отправляем ему задачу перелететь в точку С. Резервируем его под задачу.

Далее алгоритм повторяется для маршрута от С до В.

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

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

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

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

Также легко подключить систему к системе симуляции роботов. Допустим к ROS, или любой другой.

Анализ системы.

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

%matplotlib inline

import ipywidgets

import copter1 as c1

import copter2 as c2

import math

from multiprocessing import Lock

from numpy import mean, linspace

import random

import matplotlib.pyplot as plt

import simpy

from config import Config

import numpy

numpy.seterr(divide='ignore', invalid='ignore')

tasks = []

jo = 0

for i in range(0, 1000):

tasks.append((

(1240 * random.random(), 1240 * random.random()), (5000 + 5000 * random.random(), 5000 + 5000 * random.random()),

(3 * random.random()), i))

test2 = c2.TestModel3d(tasks, 10240, 10240, 8 * 8, linspace(80, 150, num=5), linspace(0.01, 0.1, num=10), linspace(15, 25, num=10))

ipywidgets.StaticInteract(test2.plot, discharge_time=ipywidgets.RangeWidget(0.01, 0.06, 0.01), color=ipywidgets.RadioWidget(['green']))

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

Рисунок 7. График1

На графике демонстрируется зависимость средней скорости доставки от максимальной скорости полета квадрокоптера и времени зарядки, также график меняется в зависимости от скорости разрядки квадрокоптера, т.е. от максимально дистанции полета.

Аналогичный график был получен для первого алгоритма.

Рисунок 8. График2

Характеристики

Список файлов ВКР