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

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

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

В.В. Еремина, канд. физ.-мат. наук,

К.К. Мокронос

Аннотация

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

Ключевые слова: квадрокоптер, автономный полет, дрон, алгоритм, гистограмма, облако точек. беспилотник алгоритм полет

Введение

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

Обзор существующих решений

Наиболее распространенной стратегией для уклонения от препятствий в автономном режиме является VFH (гистограмма векторного поля), введенная Боренштейном и Кореном [1]. В данной стратегии используется сонар для создания двухмерной сетки окружающей среды, которая затем отображается на одномерной полярной гистограмме. Из этой гистограммы можно извлечь свободные направления движения. Последующее усовершенствование Ульриха и Боренштейна под названием "VFH +" учитывает максимальный радиус поворота робота и пределы безопасности (рис. 1).

Рис. 1. Гистограмма векторного поля +(VFH+) [2].

На основе алгоритма VFH + (гистограмма векторного поля +) было много доработок и вариантов. К примеру, ученые Сонг и Хуанг [3] используют алгоритм оптического потока для создания полярной гистограммы и адаптируют запас безопасного пространства вокруг препятствий к его расстоянию; Ямаути также использует зависящие от расстояния запасы безопасного пространства вокруг препятствий (рис. 2).

Рис. 2. Применение алгоритма оптического потока [4].

Метод подвижного и статического векторного поля (MSV) [5], рассматривается далее, представляет собой адаптацию к VFH+, которая способна справляться с движущимися препятствиями, оценивая их скорость по последовательным гистограммам. Другой вариант - VFH*, введенный Ульрихом и Боренштейном. Этот алгоритм сочетает в себе преимущество алгоритма планирования A* с локальными свойствами алгоритма VFH+. В данном подходе строится упреждающее дерево, на каждом узле которого выполняется алгоритм VFH+ для поиска возможных направлений, а затем выполняется поиск наилучшего пути с использованием алгоритма A* (рис. 3).

Рис. 3. Смоделированная ситуация для локальных препятствий с использованием алгоритма VFH * [6].

Были попытки улучшить алгоритм VFH* для учета движущихся препятствий. Д. Джи и др. [7] разработали алгоритм IVFH*, который использует пружинные силы на узлах дерева поиска, чтобы адаптировать их к движущимся препятствиям. Бабинек и его команда определяют скорость препятствий из нескольких последующих состояний и используют эти знания при построении дерева поиска. Вырез активного окна на рис. 4 иллюстрирует положение робота (синий), препятствие (черный) и различные сектора (желтый, оранжевый).

Рис. 4. Принцип алгоритма IVFH * [8, 9].

В некоторых недавних исследованиях также использовались подходы машинного обучения для определения правильного маневра уклонения от препятствий на основе сенсорных данных. Была проведена работа по объединению метода VFH с машинным обучением и нечеткой логикой [12, 13]. Ранняя версия метода нечеткой логики под влиянием потенциальных полей была представлена Завлангасом и др. [14]. С другой стороны, Росс и др. [15] узнают правильный управляющий вход непосредственно из данных датчиков и демонстраций полетов.

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

В 2015 г. была представлена стратегия Олейниковой и др., в которой положения препятствий определяются путем преобразования карты диспаратности в U-карту. На U-карте ограничительные рамки расположены вокруг отличительных областей. Летные испытания показали, что БПЛА может избегать редких препятствий при выборе путевых точек за пределами эллипсов.

На рис. 6 продемонстрирован сегмент U-карты, представляющий препятствие с ограничивающей рамкой его обнаружения (рис. 6a), наложенной красным цветом. Наложение эллипса на препятствие (рис. 6б), показывает различные величины, используемые для расчета препятствия - и ₁, и ₂, крайние левый и правый края препятствий в и, d₁ - максимальное несоответствие и d₂ - среднее несоответствие объекта. Справа (рис. 6в) изображен результирующий эллипс в мировой системе координат и пять значений, описывающих его центр GP_e и размер ES_e.

Рис. 6. Стратегия Олейниковой по избеганию локальных препятствий [16].

Еще одно семейство вычислительно дешевых алгоритмов для локального обхода препятствий в 2D - это алгоритмы ошибок (Bug). Сравнение различных алгоритмов ошибок можно найти в исследованиях Томаса Браун- ла и др. [17]. Буньямин и др. разработали алгоритм PointBug, который смог превзойти другие алгоритмы Bug, особенно в средах с небольшими резкими краями и поворотами. Датчик дальности обнаруживает препятствие слева направо и справа налево, как показано на рис. 7.

Рис. 7. Алгоритм PointBug [18].

В исследовании применяется наиболее распространенный алгоритм гистограммы векторного поля (VFH) и его усовершенствованная трехмерная версия (3DVFH).

Первоначальная модификация VFH

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

1) самый высокий уровень содержит подробное описание окружения робота. На этом уровне двумерная декартова сетка гистограммы постоянно обновляется в режиме реального времени, получая данные от встроенных датчиков дальности о расстоянии до препятствия;

2) на промежуточном уровне вокруг текущего местоположения робота строится одномерная полярная гистограмма. Она состоит из n угловых секторов шириной а;

3) нижний уровень представления данных - это выходные данные алгоритма VFH: эталонные значения для контроллеров привода и рулевого управления транспортного средства.

На первом этапе обработки данных активная область сетки гистограммы отображается на полярной гистограмме, как изображено на рис. 8. Содержимое каждой активной ячейки в сетке гистограммы теперь рассматривается как вектор препятствия, направление которого определяется направлением В от ячейки к центральной точке мобильного робота.

Рис. 8. Гистограмма векторного поля (VFH).

Направление вектора В и величина вектора препятствия в ячейке m, вычисляются по формулам:

где a, b - положительные константы; c_tj - значение достоверности активной ячейки (i, j); d_ij - расстояние между активной ячейкой (i, j) и центральной точкой мобильного робота; m_tj - величина вектора препятствия в ячейке (i, j); x₀, y₀ - текущие координаты мобильного робота; x, yj - координаты активной ячейки (i, j); B,j - направление от активной ячейки (i, j) к точке мобильного робота.

Улучшенная модификация 3DVFH

Рассмотрим подробно математическую модель алгоритма трехмерной гистограммы векторного поля 3DVFH, созданного на основе его первоначальной версии VFH (Vector Field Histogram).

До сих пор все алгоритмы VFH использовались в 2D-среде для наземных роботов, однако Ваннест и др. [10] разработали алгоритм 3DVFH, позволяющий расширить область зрения до трехмерной среды и применять алгоритм на летающих роботах. Этот алгоритм нельзя считать полностью локальным, поскольку он строит карту окружающей среды в виде Octomap (эффективный вероятностный каркас трехмерного картографирования на основе октодеревьев) [11].

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

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

Рис. 10. Результат работы алгоритма 3DVFH.

В своем исследовании Танджа Бауман и др. [19] улучшили алгоритм 3DVFH, добавив в него использование памяти дрона. Данный подход использует данные из последнего временного шага для улучшения гистограммы, построенной на текущем временном шаге. Однако сохраненные старые данные представлены в виде гистограммы. Старая гистограмма являет собой полярное представление препятствий, замеченных на предыдущем временном шаге. Поскольку угловое направление препятствия зависит от местоположения дрона, старая гистограмма привязана к старому местоположению, в котором она была построена. Чтобы использовать данные старой гистограммы для вычислений на текущем временном шаге, ее необходимо преобразовать в гистограмму текущего местоположения дрона.

Это может быть достигнуто путем повторного проецирования занятых ячеек старой гистограммы в трехмерные точки и последующего построения из них гистограммы памяти. Чтобы получить повторно спроецированные точки, старая гистограмма сканируется на предмет занятых ячеек. Каждая из этих занятых ячеек характеризуется є углом возвышения и углом азимута ж В дополнение к этим углам расстояние сохраняется в слое расстояний старой гистограммы, а возраст - в слое возраста. Если возраст занятой ячейки не превышает определенного предела, ячейка повторно проецируется на четыре трехмерные точки, соответствующие углам ячеек. Углы возвышения и азимута четырех угловых точек могут быть вычислены путем добавления/вычитания половины углового разрешения а гистограммы из углов возвышения и азимута занятой ячейки:

где е_{i -} угол возвышения занятой ячейки; ж- угол азимута занятой ячейки.

Затем эти четыре точки можно повторно спроецировать в трехмерное пространство:

где Pi - вычисление трехмерной точки; pos - положение дрона.

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

После определения углов трехмерной точки их необходимо преобразовать в индексы гистограммы. Расчетные углы находятся в диапазонах ж є [-180, 180] и [-90, 90]. Сначала эти углы нужно преобразовать в положительные диапазоны Z є [0, 360] и [0, 180]. По этим положительным углам могут быть рассчитаны индексы гистограммы:

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

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

Алгоритм 3DVFH начинает использовать новое полное облако точек с камеры. Затем он обновляет параметры функции стоимости в соответствии с достигнутым прогрессом. Это позволяет дрону подняться, если невозможно найти дорогу для обхода препятствия. Алгоритм 3DVFH строит дерево поиска, чтобы предложить различные возможности перемещения. Рассматриваемое дерево имеет корень в текущей позиции беспилотного летательного аппарата. Текущая позиция вводится в дерево как первая точка отсчета и устанавливается функция стоимости дерева, а также эвристика для первого узла. Оттуда новые узлы вводятся в древовидную структуру до тех пор, пока заданное количество узлов N не будет расширено (рис. 11).

Рис. 11. Алгоритм построения гистограммы 3DVFH.

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

Чтобы расширить узел, рассчитывается FOV (поле зрения) в его положении. Гистограмма строится как комбинация гистограммы обрезанного облака точек и гистограммы повторно спроецированных точек. Чтобы объединить эти две гистограммы, необходимо поле обзора дрона в позиции узла. Гистограмма имеет пониженную дискретизацию до половины разрешения, чтобы уменьшить количество возможных направлений и сделать их более четкими. Направления-варианты извлекаются и оцениваются в соответствии с той же функцией стоимости, что и для алгоритма 3DVFH. Для уменьшения фактора ветвления дерева поиска, не все варианты добавляются как узлы.

Архитектура всего алгоритма избегания препятствий со всеми функциями показана на рис. 12.

Рис.12. Общая структура алгоритма выбора пути.

Потенциал возможного улучшения алгоритма 3DVFH

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

Алгоритм гистограммы векторного поля (VFH) был расширен до трехмерной среды, а преимущества функции памяти были воспроизведены в алгоритме 3DVFH. Благодаря этой возможности упреждения алгоритм хорошо справляется в более сложных сценариях. Реализован простой в вычислительном отношении метод обнаружения Земли с использованием только данных с передней камеры. Было показано, что этот метод обнаружения может поддерживать минимальное расстояние до Земли. Реализованы различные функции, чтобы повысить надежность предлагаемого подхода и сделать возможным его применение на беспилотных летательных аппаратах.

Однако у алгоритма имеются недостатки. Производительность алгоритма сильно ограничена доступной информацией о датчике. Вероятность столкновения может быть уменьшена, а скорость полета увеличена за счет использования дополнительных датчиков увеличения поля зрения. Хоть алгоритм и определяет окружение почти на 360 градусов, для анализа такого пространства ему необходимо вращаться вокруг своей оси постоянно осматриваясь, на что уходит лишнее время. Дрон не может моментально рассчитать возникшее препятствие, - например, встречно движущегося объекта, что приведет к столкновению и потере БПЛА. Алгоритм тратит много времени и на вычисление лучшей из возможных траекторий.

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

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

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

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

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

Заключение

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

Литература

1. Borenstein J., Koren Y. The Vector Field Histogram - Fast Obstacle Avoidance for Mobile Robots // IEEE Transactions on Robotics and Automation. - 1991. - Vol. 7, №. 3. - P. 278288.

2. Ulrich I., Borenstein J. VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots // IEEE International Conference on Robotics and Automation (ICRA). - 1998. - Vol. 2 - P. 1572-1577.

3. Song K. Huang J. Fast optical flow estimation and its application to real-time obstacle avoidance // IEEE International Conference on Robotics and Automation (ICRA). - 2001. - Vol. 3. - P. 2891-2896.

4. Yamauchi B. The Wayfarer modular navigation payload for intelligent robot infrastructure // Unmanned Ground Vehicle Technology VII, Proceedings of International Society for Optics and Photonics. - 2005. - Vol. 5804, № 781. - P. 85-96.

5. You B., Qiu J., Li D. A novel obstacle avoidance method for low-cost household mobile robot // IEEE International Conference on Automation and Logistics, ICAL. - 2008 - P. 111116.

6. Ulrich I. and Borenstein I. VFH*: Local obstacle avoidance with lookahead verification // IEEE International Conference on Robotics and Automation (ICRA). - 2000. - Vol. 2. - P. 1572-1577.

7. Jie D., XuemingM., Kaixiang P. IVFH*: Real-time Dynamic Obstacle Avoidance for Mobile robots // International Conference on Control Automation Robotics & Vision (ICARCV). - 2010. - P. 7-10.

8. Modifications of VFH navigation methods for mobile robots / Babinec A., Dekan M., Du- cho'nF., VitkoaA. // Procedia Engineering. - 2012. - Vol. 48. - P. 10-14.

9. VFH*TDT (VFH* with Time Dependent Tree): A new laser rangefinder-based obstacle avoidance method designed for environment with non-static obstacles / Babinec A., Du- cho'n F., Dekan M. and etc. // Robotics and Autonomous Systems. - 2014. - Vol. 62, №. 8. - P. 1098-1115.

10. Vanneste S., Bellekens B., Weyn M. 3DVFH+: Real-Time Three-Dimensional Obstacle

11. Avoidance Using an Octomap // MORSE 1st International Workshop on Model-Driven Robot Software Engineering. - 2014. - Vol. 1319

12. OctoMap: An efficient probabilistic 3D mapping framework based on octrees / Hornung A., Wurm K.M., Bennewitz M. and etc. // Autonomous Robots. - 2013. - Vol. 34, №. 3. - P. 189-206.

13. Kazem B.I., Hamad A.H., Mozael M.M. Modified Vector Field Histogram with a Neural Network Learning Model for Mobile Robot Path Planning and Obstacle Avoidance // International Journal of Advancements in Computing Technology. - 2010. - Vol. 2, №. 5. - P. 99-110.

14. Hamad A.H., Ibrahim F. B. Path Planning of Mobile Robot Based on Modification of Vector Field Histogram using Neuro-Fuzzy Algorithm // International Journal of Advancements in Computing Technology. - 2010. - Vol. 2, № 3. - P. 1-10.

15. Zavlangas P.G., Tzafestas S.G., Althoefer K. Fuzzy Obstacle Avoidance and Navigation for Omnidirectional Mobile Robots // European Symposium on Intelligent Techniques. - 2000.

16. P. 14-15.

17. Learning monocular reactive UAV control in cluttered natural environments / Ross S., Me- lik-Barkhudarov N., Shankar K.S. and etc. // IEEE International Conference on Robotics and Automation (ICRA). - 2013. - P. 1765-1772.

18. Oleynikova H., Honegger D., Pollefeys M. Reactive avoidance using embedded stereo vision for MAV flight // IEEE International Conference on Robotics and Automation (ICRA).

19. 2015. - P. 50-56.

20. Ng J., Br aunl T. Performance comparison of Bug navigation algorithms // Journal of Intelligent and Robotic Systems. - 2007. - Vol. 50, №. 1. - P. 73-84.

21. A simple local path planning algorithm for autonomous mobile robots / Buniyamin N., Wan Ngah W.A.J., Sariff N., Mohamad Z.// International journal of systems applications, Engineering & development. - 2011. - Vol. 5, №. 2. - P.151-159.

22. Baumann T. Obstacle Avoidance for Drones Using a 3DVFH* Algorithm // https://drive.google.com/file/d/1yjDtxRrIntr5Mdaj9CCB4IFJn0Iy2-bR/view. - Master Thesis. - 2018.

Размещено на Allbest.ru