Размещено на http://www.allbest.ru/



Аннотация

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

Объем работы - 50 страниц. В работе содержится 34 иллюстрации, использовано 40 источников.

The work considers the multi-agent autonomous navigation problem, which is one of the key in the field of multi-agent intelligent systems. The main purpose of this work is to develop a decentralized navigation system for a group of mobile agents. The work includes an analysis of the scientific and technical literature on autonomous navigation and the selection of algorithms and methods for developing the system. Based on the selected algorithms, a navigation system is developed in the form of a standalone program and in the form of a module for Robot Operating System (ROS). An experimental study of the developed system is carried out.

The work consists of 50 pages, contains 34 images. The 40 sources were used.



Оглавление

Введение

1. Обзор источников и анализ предметной области

1.1 Описание задачи

1.2 Обзор литературы

1.3 Выбор методов и алгоритмов

2. Методы и алгоритмы

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

2.2 Планирование траектории индивидуального агента

2.3 Избегание столкновений

2.4 Метод автономной навигации групп агентов

3. Программная реализация

3.1 Обоснование средств реализации

3.2 Реализация алгоритмов и прототипа системы

3.3 Тестирование и документация исходного кода

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

3.5 Реализация прототипа системы в виде модуля ROS

Заключение

Список используемых источников



Введение

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

Рис. 1. Роботы на складах компании Amazon (фотография из [1])

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

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

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

- проведен выбор алгоритмов для создания компонентов системы навигации: алгоритма планирования траектории индивидуального агента и алгоритма избегания столкновений при следовании по траектории;

- произведен выбор средств разработки системы;

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

- разработан прототип системы автономной навигации группы мобильных агентов в виде отдельной C++ программы;

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

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

- прототип системы автономной навигации группы мобильных агентов реализован в виде модуля операционной системы роботов (ROS) и выполнено описание прототипа системы.



1. Обзор источников и анализ предметной области

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

1.1 Описание задачи

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

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



1.2 Обзор литературы

Подходы к решению задачи навигации можно разделить на две категории: централизованные и децентрализованные [2-3]. Централизованные подходы предполагают существование центрального планировщика, обладающего полной информацией о состоянии всей системы в каждый момент времени. В этом случае осуществляется планирование траекторий для всех агентов, после чего агенты приступают к выполнению плана. К наиболее распространенным методам многоагентного планирования относятся алгоритмы, основанные на поиске конфликтов в траекториях [4], или алгоритмы с распределением приоритетов между агентами [5]. Заметим, что при использовании централизованных методов, предполагается наличие постоянной связи между центральным планировщиком и всеми агентами, что не всегда реализуемо на практике. Более гибким подходом в таком случае является децентрализованный, когда каждый агент ищет решение индивидуально, используя лишь доступную ему информацию об окружающей среде [6-8].

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

Планирование траектории

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

Рассмотрим методы представления в виде графа. Один из таких методов заключается в построении графа видимости [9]. Вершинами графа видимости являются точки, находящиеся на фиксированном расстоянии от вершин препятствий, а также начальное и целевое положения агента (рис. 3). Ребрами графов видимости являются отрезки прямых, соединяющие вершины графа без пересечения со статическими препятствиями. Использование графов видимости позволяет получать наиболее короткие пути для данной местности, но построение такого графа может быть затруднительно при большом числе статических препятствий или при наличии препятствий сложной формы [10].

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

Рис. 3. Иллюстрация построения графа видимости (б) на основе плана местности (а)

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

Рис. 4. Иллюстрация диаграмм Вороного для (а) точечных препятствий и (б) препятствий сложной формы. Иллюстрация из [11].

Альтернативный вариант представления среды в качестве графа описанный в [12], заключается в разбиении пространства на ячейки одинаковой формы. Центры полученных ячеек являются вершинами графа, а перемещения между центрами соседних ячеек являются ребрами (рис. 5). Подобные графовые представления, именуемые в дальнейшем графы регулярной декомпозиции, являются простыми и информативными моделями, причем сложность их построения не зависит от числа/формы статических препятствий.

Рис. 5. Иллюстрация разбиения плана местности (а) на ячейки квадратной формы для графа регулярной декомпозиции (б). Светлыми участками обозначены проходимые области, темными указаны непроходимые.

Рассмотрим теперь алгоритмы поиска пути на графе. Наиболее известным алгоритмом поиска пути на взвешенном графе является алгоритм Дейкстры [13]. Этот алгоритм позволяет находить кратчайшие пути на произвольном взвешенном графе с неотрицательными весами, что позволяет применять его во многих областях, в том числе при планировании траектории. Однако в задачах навигации зачастую известна дополнительная информация, использование которой может значительно ускорить процедуру поиска пути при сохранении оптимальности получаемых решений. Так, алгоритм эвристического поиска A* [14-15] использует оценочные данные о расстоянии до целевой вершины за счет чего существенно сокращается время работы алгоритма (в большинстве случаев на практике). Существуют различные модификации алгоритма A*, позволяющие работать в условиях частичной наблюдаемости и/или изменения среды [16-17], либо учитывающих особенности тех или иных методов построения графов [18-19]. Одной из основных проблем использования классических алгоритмов (Дейкстры, A*) на графах регулярной декомпозиции является то, что получаемые пути состоят из множества фрагментов-переходов между смежными ячейками. В [19] описывается ряд алгоритмов семейства A*, позволяющих получать “сглаженные” пути, состоящие из более продолжительных прямых секций. Одним из таких алгоритмов является алгоритм Theta* (рис. 6). Он позволяет получать пути, близкие, либо равные кратчайшим, полученным при использовании графов видимости за время, сравнимое с временем работы A* на графах регулярной декомпозиции.

Рис. 6. Иллюстрация траекторий, полученных с использованием алгоритма A* (а) и Theta* (б) на графе регулярной декомпозиции

Избегание столкновений при следовании траектории

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

На данный момент широкое распространение получили алгоритмы избегания столкновений на основе теории скоростных препятствий. Один из первых алгоритмов, основанных на скоростном подходе, Reciprocal Velocity Obstacles (RVO) описан в [20]. И хотя он гарантировал при некоторых условиях отсутствие столкновений, более общий, доработанный, подход Optimal Reciprocal Collision Avoidance был представлен в [21]. Данные подходы основаны на циклическом выборе новых скоростей из множества так называемых безопасных скоростей, которые вычисляются автоматически.

Хотя базовые алгоритмы предполагают решение задачи для голономных роботов, без учета неопределенности в данных о расположении и скоростях агентов, существует ряд модифицированных алгоритмов, основанных на ORCA и RVO, которые решают эту проблему. Зачастую эти решения требуют небольших изменений в процедуре поиска безопасных скоростей, либо увеличений радиуса агента/изменение формы агента [22-28]. Подходы, основанные на выборе скоростей, помимо избегания столкновений между агентами, имеют механизмы избегания столкновений со статическими препятствиями, базовые версии алгоритмов имеют открытые реализации, доступные в сети Интернет.

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



Рис. 7. Иллюстрация построения ячеек Вороного для группы агентов (иллюстрация из [29])

В работах [30-31] были предложены подходы, основанный на идее применения обучения с подкреплением в задачах многоагентной навигации, в том числе избеганию столкновению. Авторы работ указывают, что их алгоритм либо сравним, либо превосходит алгоритмы основанные на поиске скоростей не приводящих к столкновению по числу решаемых задач (в том числе на картах с препятствиями) и времени работы, к тому же входными данными алгоритма [31] являются не информация о положениях или скоростях агентов, а данные с датчиков расстояния. С другой стороны, данный алгоритм также не обладает открытой реализацией и требует более обширного тестирования в различных условиях.

1.3 Выбор методов и алгоритмов

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

Наиболее подходящим способом представления среды в качестве графа является граф регулярной декомпозиции, т.к. построение этой графовой модели не требует применения трудоемких алгоритмов. Для поиска пути на указанном графе целесообразно использование алгоритма Theta*, так как он позволяет находить пути, близкие к путям на графах видимости, но сохраняет скорость работы алгоритма A* на графах регулярной декомпозиции. Для избегания столкновений при следовании по траектории представляется разумным использовать алгоритмы, основанные на теории скоростных препятствий, так как подходы данного класса широко исследованы, а для базовых версий алгоритмов существуют открытые реализации и подробные описания. Среди алгоритмов этого класса алгоритм ORCA в наибольшей степени применим, так как он включает в себя многие улучшения первоначальной концепции скоростных препятствий и открыт для многих дальнейших усовершенствований.



2. Методы и алгоритмы

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

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

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

.

где - кратчайшее расстояние от точки до статического препятствия.

Вводится дискретное время . Считается, что в каждый момент времени агенту , доступна информация о всех статических препятствиях и состоянии агентов, , которые находятся в радиусе видимости :



.

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

.

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

Причем в каждый момент времени агенты не должны пересекаться между собои? и со статическими препятствиями:



,

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

,

,

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

2.2 Планирование траектории индивидуального агента

В качестве алгоритма планирования индивидуальных траекторий предлагается использовать алгоритм Theta*, производящий поиск на графах регулярной декомпозиции. Для построения такого графа производится разбиение участка плоскости, на котором проводится поиск, на равные квадратные ячейки. Те ячейки, которые в процессе разбиения накладываются на статические препятствия обозначим непроходимыми, в обратном случае - проходимыми. Центр каждой проходимой ячейки становится вершиной графа, а элементарные переходы между соседними ячейками - ребрами графа. Весами ребер графа будут являться евклидовы расстояния между вершинами. Таким образом, произвольный прямоугольный участок можно записать как прямоугольную матрицу размером на элементов, где , 0 - проходимые, а 1 - непроходимые ячейки. Однако, несмотря на простоту и понятность такой графовой модели, пути, полученные с помощью классических алгоритмов (например A*), будут состоять из множества фрагментарных переходов. Алгоритм Theta* решает эту проблему, сглаживая траектории. Алгоритм Theta* основан на алгоритме A*.

Рис. 9. Псевдокод алгоритма A*/Theta*. Иллюстрация из [19].

В процессе работы алгоритма A* для поиска пути осуществляется итеративный обход графа, при этом используется эвристическая функция оценки длины пути между текущей вершиной и конечной, влияющая на то, какую вершину обрабатывать на очередном шаге. В процессе обхода выбирается вершина v? минимизирующая функцию где - это вес пути из начальной вершины в вершину , известный к текущей итерации, а - это эвристическая функция. После этого происходит ее раскрытие, в ходе которого перебираются все смежные с вершины . Для каждой вершины сравниваются значения и где - вес ребра, соединяющего и . Если меньше, чем , то считается, что найден более короткий путь к , после чего становится равным , и для вершины вершина становится "родительской" вершиной. С использованием ссылок на родительские вершины происходит восстановление пути после окончания расчёта g-значений. Это окончание происходит, когда к раскрытию выбирается целевая вершина. Псевдокод алгоритма A* представлен на рис. 9.

Основное отличие алгоритма Theta* от алгоритма A* заключается в выборе "родительской" вершины. Этой вершиной может быть не только смежная, но и та, до которой существует прямая видимость (т.е. агент может перемещаться между двумя точками по прямой, не сталкиваясь с препятствиями). Псевдокод процедуры выбора "родительской" вершины представлен на рис. 10.

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

Рис. 10. Псевдокод процедуры выбора родительской вершины для алгоритма Theta*. Иллюстрация из [19].

2.3 Избегание столкновений

В качестве алгоритма следования траектории с избеганием столкновений был выбран алгоритм Optimal Reciprocal Collision Avoidance (ORCA). Данный алгоритм обеспечивает движение от одной точки пространства к другой при условии существования возможности прямого перемещения между этими двумя точками без пересечения со статическими препятствиями. В процессе работы алгоритм производит циклический выбор новой скорости , причем для каждого агента выбор скорости производится независимо, основываясь лишь на информации доступной конкретному отдельному агенту.

Скорость выбирается таким образом, чтобы быть близкой к некоторой желаемой скорости и не приводить к столкновению с другими агентами и статическими препятствиями за некоторый конечный промежуток времени [21]. Для поиска такой скорости в пространстве скоростей строятся области скоростных препятствий (рис. 11).

Рис. 11. Иллюстрация построения скоростного препятствия в пространстве скоростей и полуплоскостей, образующих область безопасных скоростей. Иллюстрация из [21].

Скорости, попадающие в данные области, обязательно приведут к столкновению с другими агентами или статическими препятствиями за временной промежуток . На основе каждого скоростного препятствия строятся полуплоскости, которые образуют область , содержащую безопасные для движения скорости (рис. 12). Помимо этого, область ограничивается теми скоростями, что не превышают по модулю . В полученной области производится поиск значения близкого к . Для нахождения такого значения используется метод решения задач линейного программирования, описанный в [33]. Таким образом можно выразить через следующую формулу:

,

При невозможности найти решение условия ослабляются, в этом случае алгоритм не гарантирует отсутствие столкновений.

Рис. 12. Иллюстрация построения области безопасных скоростей для некоторого агента A. Рисунок (a) демонстрирует положение агентов в пространстве. Рисунок (b) демонстрирует набор полуплоскостей для каждого соседнего агента, которые образуют область безопасных скоростей. Иллюстрация из [21].

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

Рис. 13. Блок-схема, иллюстрирующая работу алгоритма ORCA

Так как алгоритм ORCA допускает ослабление ограничений для области безопасных скоростей, то на практике в ряде случаев все же происходят столкновения. Одним из способов снижения числа таких столкновений является увеличение радиуса агента на некоторое (рис. 14).

Рис. 14. Иллюстрация добавления буферного радиуса агента

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

2.4 Метод автономной навигации групп агентов

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

Рис. 15. Блок схема разработанного алгоритма автономной навигации групп мобильных агентов

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

Выбор текущей цели производится следующим образом. На первой итерации работы алгоритма достигнутой считается начальная точка и она извлекается из последовательности, задающей спланированную траекторию. Текущей же становится первая точка последовательности. Агент начинает движение к ней. Как только она будет достигнута, то текущей полагается следующая точка в траектории. Если же в процессе следования к текущей цели агент отклоняется от прямолинейной траектории между послей точкой и выбранной текущей целью в результате избегания столкновений с другими агентами, и текущая цель оказывается не в зоне прямой видимости агента, то заново запускается процедура планирования траектории до текущей цели с учетом статических препятствии?. После этого новый фрагмент траектории добавляется в последовательность. Иллюстрация процесса выбора цели представлена на рис. 16.

Рис. 16. Иллюстрация, изображающая процесс выбора текущей цели: (а) есть прямая видимость до текущей цели A, производится движение в ее сторону; (б) агент отклоняется от изначальной траектории, нет прямой видимости между агентом и его целью, происходит дополнение маршрута; (в) текущая целевая точка C достигнута, целевой точкой становится точка A, (г) агент осуществляет движение к целевой точке A.

Рассмотрим пример, расположенный на иллюстрации. Синий производит движение к текущей целевой точке A, навстречу ему движется другой агент (рис 16а). В результате избегания столкновений агенты отклоняются от первоначальных траекторий, точка A выходит из зоны прямой видимости синего агента, происходит дополнение траектории новым фрагментом, текущая целевая позиция синего агента изменяется с A на C (рис 16б). Синий агент достигает точки C, текущей целевой точкой становится точка A (рис 16в). Агент осуществляет движение к текущей целевой точке A (рис 16г).



3. Программная реализация

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

3.1 Обоснование средств реализации

В качестве основного языка программирования был выбран язык C++, т.к. программы, реализованные на этом языке, имеют высокую скорость работы [34], язык поддерживает парадигму ООП, которая позволяет повысить модульность получаемых решений, помимо чего, этот язык поддерживается многими средствами тестирования и автоматического документирования исходного кода.

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

Рис. 17. Иллюстрация архитектуры робототехнической системы с обозначением уровней абстракции (иллюстрация из [35])

В [35] приведено сравнение большого числа различных систем, а [36] выделяет несколько из них, в том числе: RT-Middleware, OPRoS и ROS. Все эти системы предоставляют возможности по созданию отдельных компонентов и методы связи между отдельными компонентами, а также механизмы взаимодействия с различными стимуляторами работы роботов.

Система RT-Middleware позволяет создавать компоненты на основе концепции конечных автоматов, а для связи между компонентами используются система запросов. Система OPRoS во многом похожа на RT-Middleware, за счет структуры компонента, основанной на конечном автомате, но имеет отличия в системе взаимодействия компонентов и поддерживает меньшее число аппаратных компонентов. Эта система предоставляет фреймворк для коммуникации между различными компонентами, обработки ошибок. траектория тестирование код модуль

Система ROS является одной из самых распространенных систем с наибольшей поддержкой различного аппаратного обеспечения [36]. Как и описанные выше системы ROS имеет открытый исходный код и позволяет проводить симуляцию, как в своих средах симуляции, так и в сторонних (например, Gazebo и V-REP). Компоненты ROS имеют несколько вариантов коммуникации, среди которых основанные на модели запросов и основанные на модели тем и подписчиков [37].

Таким образом, для реализации был выбран ROS, которые имеет наибольшее распространение среди аналогичных систем. Кроме того, ROS обладает большим числом различных способов коммуникации между модулями и поддержкой различных робототехнических симуляторов. В качестве основы для систем сборки ROS использует CMake, для тестирования C++ кода используется набор библиотек Google C++ Testing Framework (сокращенно Google Test или GTest), генерация документации производится утилитой rosdoc_lite, которая является расширением различных сторонних утилит (для документирования C++ кода использовалась утилита doxygen в качестве основы).

3.2 Реализация алгоритмов и прототипа системы

На начальном этапе был реализован прототип системы без использования средств промежуточного программного обеспечения. Прототип включал в себя модуль планирования траектории индивидуального агента и модуль следования траектории с избеганием столкновений. Помимо этого, были реализованы модули чтения/записи данных и модуль, отвечающий за простую симуляцию работы множества мобильных агентов. Это было необходимо для проверки работы алгоритма и запуска экспериментальных исследований без задействования дополнительных средств промежуточного программного обеспечения. Для чтения входных и записи полных выходных данных прототипа использовались файлы формата XML, для краткого вывода результатов работы при тестировании были использованы файлы txt. Входной файл содержит описание агентов (параметры агента, начальные и конечные точки), описания препятствии? (в формате наборов секции?-отрезков), описание карты для планирования (в формате матрицы с указанными проходными и непроходными ячейками) и параметры алгоритмов. Полный выходной файл содержит копию содержания входного, краткие данные об исполнении (процент агентов, достигнувших финиша, время выполнения, симуляционное время, сумма симуляционных времен для всех агентов, число столкновении? между агентами, число столкновении? между агентами и препятствиями) и положения всех агентов в каждый момент времени симуляции. Подробнее входные и выходные данные описаны в документации к прототипу, которая на данный момент доступна в открытом репозитории. В случае запуска серии экспериментов краткие данные об исполнении каждого могут быть записаны в txt-файл. Далее будет описана структура прототипа системы (структура с указанием основных классов представлена на рис. 18).

Абстрактный класс PathPlanner отвечает за описание поведения планировщика. Данный класс описывает интерфейс взаимодействия с планировщиком, не основываясь на конкретном алгоритме планирования, что позволит в дальнейшем использовать и другие подходы к построению пути индивидуального агента. Содержит в себе метод для запуска алгоритма планирования из начальной точки в конечную (CreateGlobalPath), метод, возвращающий текущую доступную цель (GetNext), и другие служебные методы. Класс ThetaStar наследует у этого класса и реализует поведение алгоритма Theta?.



Рис. 18. Диаграмма, изображающая структуру классов прототипа системы

Абстрактный класс Agent описывает агента и его поведение. Данный класс описывает интерфейс взаимодействия с алгоритмом навигации. Именно в классах-наследниках Agent предполагается реализовывать алгоритм избегания столкновений и взаимодействие между этим алгоритмом и центральным планировщиком. Метод SetPlanner отвечает за установку экземпляра конкретного планировщика в качестве модуля планирования, причем планировщик должен наследовать от класса PathPlanner. Метод InitPath производит запуск процедуры поиска траектории, метод ComputeNewVelocity реализует поиск новой скорости, ApplyNewVelocity и UpdatePrefVelocity отвечают за обновление внутреннего состояния агента, а именно: скорости и текущей цели. Также доступны методы обновления информации об окружающей среде (AddNeighbour, UpdateNeighbourObst) и методы, предоставляющие информацию о самом агенте для среды выполнения задания (GetPosition, GetVelocity, GetRadius и др.). Класс-наследник ORCAAgent реализует поведение агента, использующего алгоритм ORCA в качестве алгоритма избегания столкновений.

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

Абстрактные классы Reader и Logger отвечают за описание, соответственно, взаимодействия между источником данных о задании и средой выполнения или взаимодействия среды выполнения и средой получения результатов выполнения. За чтение и получение данных в нужном формате выступают методы: ReadData, GetMap, GetEnvironmentOptions, GetAgents класса Reader и его наследников. За предоставление и передачу информации о выполнении в нужном формате отвечают методы SetSummary, SetResults, GenerateLog класса Logger и его наследников. В нашем случае загрузка и выгрузка информации происходит в XML-фаи?лы, для этого были реализованы классы наследники XMLReader и XMLLogger для чтения и сохранения соответственно. В случае потребности дальнейшего изменения формата приема и сохранения данных будут реализованы другие классы-наследники, а их использование вместо (или в дополнение) к текущему варианту не потребует больших усилии?.

Класс Mission является представлением среды выполнения задания, отвечает за выполнение алгоритма множеством агентов, соответственно представленному подходу, взаимодействие между различными частями прототипа, предоставляет методы взаимодействия со средой выполнения задания для запуска тестирования и экспериментов (такие как: ReadTask для загрузки данных о задании, StartMission для запуска выполнения задания и SaveLog для сохранения результатов выполнения).

Также реализация включает несколько служебных классов, отвечающих за простые геометрические объекты (Point, Node, Vertex, Line, ObstacleSegment), проверку видимости (LineOfSight), структуры, отвечающие за хранение параметров среды (EnvironmentOptions), параметры агентов (AgnetParam), информации о результатах выполнения (Summary).

3.3 Тестирование и документация исходного кода

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

Для тестирования были выбраны модули, работу которых необходимо проверить. Были выбраны модули, отвечающие за файловый ввод/вывод, представление окружающей среды, области локального планирования, построение маршрута единичного агента, модуль, реализующий работу агента целиком, а также проводилось тестирование системы целиком на заранее рассчитанном задании. Тестирование проводилось с использованием открытой библиотеки Google C++ Testing Framework.

Рис. 19. Листинг главного тестового файла, запускающего тестирование всех компонентов

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

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

Рис. 20. Листинг класса, реализующего инициализацию объекта карты

Тесты построенные на базе библиотеки GTest состоят из проверки утверждений (ASSERT) различного вида. Они могут проверять равенство значений, правильность утверждений, наличие вызова исключений. На рис. 21 продемонстрирована проверка заполнения объекта карты значениями о проходимости ячеек карты. Для этого используется сравнение результатов методов, возвращающих проходимость ячеек, и элементов матрицы проходимости, с помощью которой была инициализирована карта.



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

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

Рис. 22. Результат запуска тестирования

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

Рис. 23. Фрагмент описания класса EnvironmentOptions для автоматической генерации документации исходного кода

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

Рис. 24. Фрагмент веб-страницы с описанием класса EnvironmentOptions созданной при автоматической генерации документации

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

Для проверки качества работы было произведено экспериментальные запуски прототипа системы. Запуски производились на 2 различных картах. Первая карта (warehouse), имитирующая складские помещения, представляла собой открытое пространство 64 на 64 клетки с препятствиями прямоугольной формы, расположенными в 2 ряда (рис. 25).

Рис. 25. Иллюстрация карты, имитирующей складские помещения

Вторая карта (rooms), общим размером так же 64 на 64 клетки, состояла из 16 комнат, соединенных узкими проходами (рис. 26). Карта была получена из открытого набора movingai для проверки систем навигации [38].

Рис. 26. Иллюстрация карты, состоящей из комнат, соединенных узкими проходами



Для каждой карты было сгенерировано 250 различных заданий, состоящих из 40 пар начальных и конечных позиций. Для каждого агента гарантировалось существование пути между его начальным и конечным положением в каждом задании. Для каждого задания производился запуск 5, 10, 15, 20, 25, 30, 35 и 40 агентов. Число шагов симуляции было ограничено 12800 . Запуски производились на персональном компьютере под управлением ОС macOS Mojave на базе Intel Core i5-8259U (2.3 ГГц) с 16 Гб ОЗУ. Эксперименты проводились для агентов размером 0.3 от размера клетки на двух версиях алгоритма: без буферного радиуса и с буферным радиусом размером 0.19 от размера клетки (таким образом агент с буферным радиусом был близок по размеру к одной клетке).

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

,

где - число агентов, достигших целевых позиций; - число столкновений, произошедших в процессе выполнения.

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

,

На рис. 27-28 представлены графики, демонстрирующие результаты запусков на 2-х картах.



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

Рис. 28. График зависимости средней доли агентов, достигших целевых позиций, от числа агентов для карты, состоящей из комнат с узкими проходами

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

Помимо этого, для оценки качества решений на картах различного типа было рассчитано среднее значение flowtime и makespan для каждого числа агентов на обоих картах. Задания, выполненные со столкновениями, при расчетах не учитывались. Результаты для алгоритма с использованием буферного радиуса представлены на рис. 29-30.

Рис. 29. График зависимости makespan от числа агентов для различных карт

Рис. 30. График зависимости flowtime от числа агентов для различных карт



На графиках видно, что на карте warehouse оба показателя (makespan и flowtime) показывают медленный рост. При увеличении числа агентов в 8 раз, показатель makespan вырос примерно в 2,5 раза, а flowtime выросл примерно в 10 раз. С другой стороны, те же показатели на карте rooms растут быстрее (makespan: 3,5 раза, flowtime: 18 раз), в особенности показатель flowtime. Это так же может свидетельствовать о том, что большое число агентов в процессе выполнения заданий скапливались около узких проходов, что заметно замедляло движение всех агентов в целом.

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

3.5 Реализация прототипа системы в виде модуля ROS

Базовые инструменты ROS

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

Пакеты ROS построены на базе распределенной модели вычислительных графов. Каждая вершина такого графа называется узлом (node) и представляет из себя независимый процесс, который производит обмен информацией с другими узлами пакета или других пакетов. В ROS выделяются четыре базовых инструмента обмена информацией: темы (topics), сервисы (services), действия (actions), сервер параметров (parameter server). Для работы всех методов коммуникации необходим запуск главного процесса (ROS Master). Рассмотрим подробнее эти инструменты.

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

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

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

Помимо этого, ROS включает множество дополнительных утилит для сборки, отладки, визуализации, работы с файловой системой и зависимостями [39]. Также возможно взаимодействие со сторонним программным обеспечением (например, робототехнические симуляторы Gazebo и V-REP).

Модуль автономной навигации одиночного агента

Главным модулем в распределенной системе навигации является модуль навигации единичного агента. Этот компонент необходим, как для встраивания в систему отдельного робота в случае полностью независимого выполнения, так и при централизованном расчете траекторий, но с использование распределенных вычислений. Ниже будет описана разработанная архитектура модуля навигации одиночного агента. Иллюстрация работы узла представлена на рис. 31.

Рис. 31. Блок схема работы узла автономной навигации одиночного агента в ROS

Модуль навигации одиночного агента представляет из себя узел ROS. На первом этапе происходит инициализация параметров системы и данных о статической среде, в которой будет действовать агент. Происходит обращение через модель сервисов к узлу, предоставляющего данные о карте в виде графа регулярной декомпозиции (узел map_server предоставляется системой ROS [40]). Происходит обращение через модель сервисов к узлу, предоставляющему информацию о параметрах алгоритма и о статических препятствиях в формате многоугольников (подобный узел должен быть реализован отдельно, пример такого узла описан в следующем разделе). После инициализации узла запускается процесс планирования траектории одиночного агента без учета динамических препятствий. Происходит вызов методов, описанные в разделах выше, отвечающих за поиск пути алгоритмом Theta*. На следующем этапе начинается выполнение полученной траектории с использованием алгоритма ORCA. Узел производит подключение к теме, в которой публикуются данные о текущем положении и скорости агента, а также о состоянии соседних агентов и к теме, в которую будет опубликована информации о новой скорости агента. При появлении новых сообщений в теме входных данных производится запуск процедуры обновления информации об окружающей среде и расчета новой скорости агента. После расчета новая скорость публикуется в соответствующую тему. Этот процесс повторяется циклически, пока узел не будет отключен.

...