Лагузина Е.А.
ОБЗОР МЕТОДОВ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ ДВИЖЕНИЯ МОБИЛЬНЫХ РОБОТОВ *
Аннотация:
автоматизация сложных технических процессов, интерес к которой значительно возрос в последнее время, невозможна без решения задачи планирования пути. Работа посвящена обзору современных методов планирования траектории. Рассмотрены три класса методов: на основе клеточной декомпозиции, на основе графов и методы потенциальных полей.
Ключевые слова:
планирование траектории, мобильные роботы, поиск пути, среда с препятствиями, дорожная карта
Планирование траектории – это задача синтеза траектории перевода объекта из некоторого исходного состояния, в целевое, путем изменения его координат в некотором пространстве.Данная статья посвящена обзору и сравнительному анализу основных методов планирования движения.Методы на основе клеточной декомпозиции.Наиболее простой и в то же время распространенный подход к планированию движения состоит в применении методов клеточной декомпозиции. В общем случае окружающую среду делят на клетки, используя грани выявленных препятствий. При решении задачи планирования по методам на основе клеточной декомпозиции можно использовать множество различных стратегий поиска относительного оптимального решения, например: поиск в ширину (BFS), поиск в глубину (DFS), алгоритм Дейкстры, алгоритм А*.Алгоритм Дейкстры.Алгоритм Дейкстры позволяет находить наикратчайшее расстояние из одной до всех остальных вершин графа. Принцип его работы ограничен графами без рёбер отрицательного веса. Все рабочее поле предварительно разбивается и получаемым ребрам присваиваются значения меток в соответствии с удаленностью от искомой точки. Шаги алгоритма можно описать следующим образом: если все вершины посещены, то алгоритм завершает работу. В противном случае, из еще не посещенных вершин выбирается вершина, имеющая минимальную метку. Происходит рассмотрение всех возможных маршрутов, в которых данная вершина бы являлась предпоследним узлом. Вершины, в которые ведут рёбра из неё, обычно называют соседями этой вершины. Для каждого соседа рассматриваемой вершины, если он не отмечен в качестве уже посещенного, необходимо рассмотреть новую длину пути, получаемую из суммы значений текущей метки вершины и длины ребра, соединяющего её с этим соседом. Если мы получаем меньшее значение длины в сравнение в меткой соседа, то производим замену значения текущей метки получаемым значением новой длины. Завершив осмотр всех соседей, помечаем выбранную вершину как посещённую и повторяем шаг алгоритма. Граф строится в пространствах с полигональными препятствиями, то есть необходимо, чтобы препятствия представляли собой многоугольники, либо многогранники в трехмерном случае. При движении в неизвестном окружении робот может в ходе перемещения дополнять граф видимости новыми вершинами по мере того, как они будут открываться.Алгоритм поиска А*.Алгоритм поиска A* в своем функционировании опирается на предыдущей подход и позволяет подсчитать стоимость пути от начальной точки до финальной, при этом используя первое наиболее подходящее совпадение в дереве. Главная особенность данного подхода в том, что порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемая как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной и функции эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. В начале работы просматриваются узлы, смежные с начальным, выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых вершин графа — множеством частных решений, — которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди, либо пока всё дерево не будет просмотрено. Из множества решений выбирается решение с наименьшей стоимостью.Алгоритм поиска D*.Алгоритм поиска D* также является алгоритмом поиска наикратчайшего пути во взвешенном ориентированном графе, где его основной особенностью является то, что структура графа не известна нам заранее или будет постоянно изменяться. Примером может служить задача навигации мобильного робота, получающего информацию об окружении с датчиков в режиме реального времени. D* использует меньше клеток, чем A*, по той причине, что в нем не планируется весь путь до цели. Данный алгоритм улучшен за счет более эффективных расширений, он требует меньше времени вычислений и в нем сокращено число расширенных узлов, что позволяет считать его эффективной модификацией А*.Метод распространения волнового фронта.Особенностью метода распространения волнового фронта является отсутствие этапа поиска. Работа алгоритма включает его инициализацию, распространение волны и обратное восстановление финального пути. Сначала происходит построение множества ячеек поля, где каждой из них приписываются атрибуты наличия проходимости, запоминаются стартовая и целевая ячейки. Далее, от стартовой ячейки выполняется шаг в соседнюю, также с проверкой на её проходимость и принадлежность к ранее выявленным путевым ячейкам маршрута. При успешном прохождении данных условий ячейку добавляют к ранее помеченным в пути, а в атрибут записывается число шагов до стартовой ячейки. При последовательном функционировании будет найден искомый путь от начальной до конечной ячейки, либо исполнение будет приостановлено по причине невозможности построения пути. Последним этапом является обратное восстановление кратчайшего пути, исходя из записанных в ячейках значений атрибутов.Методы на основе графов.Важное семейство методов глобального планирования движения составляют методы на основе графов. Подобные сети объединяют в себе бесконфликтные переходы или участки путей и расширяются по мере совершения новых успешных попыток перемещения. Иногда сети накапливают также информацию о предпринятых неудачных попытках и связанных с ними вычислительных затратах, что позволяет в дальнейшем выбирать более перспективные направления и ускорить процесс маршрутизации при решении как одиночных, так и множественных задач планирования движения.Диаграммы видимости.Один из известных методов организации маршрутных сетей основан на применении графов видимости. В простейших случаях граф видимости строится на множестве вершин полигонов или полиэдров, являющихся геометрическими моделями препятствий сцены, и дополняется начальными и конечными точками маршрутов. Все вершины попарно соединяются линейными отрезками, которые принимаются в качестве ребер графа при условии попарной “видимости” инцидентных им вершин и отсутствия пересечения с препятствиями сцены. Преобразование топологического графа в маршрутную сеть представляет собой сложную задачу, поскольку ребра графа видимости проходят точно через вершины препятствий, и для успешной навигации требуется коррекция путей или предварительное расширение границ препятствий.Диаграммы Вороного.Диаграмма Вороного подразумевает разбиение плоскости с определенным числом точек, называемых центрами, на множество выпуклых многогранников или ячеек таким образом, что каждый из многогранников содержит один центр и любая точка внутри ячейки ближе к своему центру, чем к любому другому. Разбиение может быть точным либо приближенным. При приближенном разбиении пространство разбивается, пока каждая ячейка не окажется внутри свободного пространства или же внутри препятствия. Процесс рекурсивного деления останавливается по достижении заданной точности. Точное разбиение на ячейки работает несколько быстрее приближенного, но получаемые траектории будут иметь большую длину. Ее применение для навигации в эвклидовых пространствах размерности выше двух является затруднительным, но возможным.Вероятностная дорожная карта.Метод вероятностной дорожной карты (Probabilistic Roadmap Method) широко применяется для решения задач поиска путей как в локальной, так и глобальной постановке. На каждом шаге алгоритма генерируется случайная точка в пространстве объекта планирования. Затем выполняется проверка найденной конфигурации на столкновения с препятствиями. Если точка оказывается конфликтной, то она отбрасывается. В успешном случае она включается в сформированное на текущий момент представление вершин маршрутной сети. На следующей фазе проводится попытка расширить множество ребер маршрутной сети путем отыскания бесконфликтных переходов между ее вершинами. В простейшем случае определяется k ближайших вершин относительно изначальной случайной точки. Возможность создания ребра с одной из ближайших вершин определяется локальным планировщиком, в качестве которого обычно используют относительно простой и быстрый эвристический алгоритм поиска прямолинейного бесконфликтного пути.Метод быстро исследующих случайных деревьев.К следующей группе относится метод быстро исследующих случайных деревьев (RRT). В нем процесс построения пути состоит из генерации дерева опорных точек, которое последовательно расширяется от начальной до конечной точки. Процесс построения дерева начинается со стартового дерева состоящего исключительно из начального пункта. На каждом шаге процесса построения выбирается какая-либо новая случайная путевая точка (данные точки в рассматриваемой области генерируются, пока очередная из них не окажется вне препятствий). В текущем дереве выбирается оптимальная достижимая точка по отношению к случайной. Если она не найдена, либо случайная точка не достижима из текущих узлов дерева, то подобная точка отбрасывается. Если же она успешно найдена, то данная точка добавляется к дереву и соединяется ребром с выбранным оптимальным узлом дерева. Процесс построения дерева прекращается, если из последней добавленной точки достижима конечная точка или если достигнуто предельное количество вершин дерева. Если целевая точка достигнута, путь восстанавливается обратным ходом, исходя из используемой структуры дерева.Методы потенциальных полей.Важное семейство методов планирования движения составляют методы потенциальных полей, первоначально разработанные для навигации мобильных роботов и обхода локальных препятствий в режиме реального времени. Методы основаны на физической аналогии с движением заряженной частицы в электростатическом поле. Препятствия сцены генерируют отталкивающие силы, а целевая точка маршрута – значительную притягивающую силу. Направление и скорость движения тела определяются градиентом потенциального поля. Данное поле при помощи собственной потенциальной функции определяет конкретную организацию препятствий и их форму, а также конечную цель движения. Суть данного алгоритма состоит в том, что каждое препятствие имеет вокруг себя отталкивающее потенциальное поле, сила которого уменьшается согласно расстоянию, что отражает отрицательный вектор, а также существует однородная сила притяжения к цели, что характеризуется положительным вектором. Для функционирования в динамической среде через короткие промежутки времени вычисляется сумма этих положительных и отрицательных векторов, исходя из которой выбирается направление передвижения объекта. Данные относительно векторов рассчитываются по показаниям сенсоров мобильного устройства в текущий момент времени.Заключение.Методы на основе пространственной декомпозиции используют упрощенное дискретное представление исходной точной модели геометрической сцены, что упрощает процесс определения маршрута следования. Однако, разрешение сетки оказывает прямое влияние на объем вычислений: с уменьшением размера клеток уменьшается также быстродействие алгоритма, что делает его неэффективным для реализаций, функционирующих в условиях реального времени. Как правило, методы данной группы требуют дополнительного этапа, состоящего в поиске пути на графе. Использование для этого эвристических стратегий способно повысить эффективность алгоритма.Алгоритмы планирования на основе графов предназначены преимущественно для использования в условиях статического известного окружения, однако некоторые из них могут быть преобразованы для использования в динамической среде. Такие методы имеют достаточно простую практическую реализацию и направлены, как правило, на поиск кратчайшего пути. Результирующая траектория представляет собой набор ломаных линий, что накладывает ограничения на допустимую скорость движения робота. С увеличением количества препятствий наблюдается рост сложности графа. Спланированный путь, в связи с особенностями некоторых методов группы, может совпадать с краями препятствий. Существующие модификации способны сделать маршрут безопасным, но приводят к увеличению его длины. Таким образом, подходы данной группы дают относительно оптимальные решения.Методы поиска пути на основе потенциальных полей подходят как для двумерного, так и для трехмерного случаев. Позволяют строить гладкие траектории, тем не менее они могут привести к резкому изменению направления движения, которое не может быть точно отработано СУ. Подходы такого рода не позволяют управлять траекторией в процессе движения.
Номер журнала Вестник науки №6 (87) том 1
Ссылка для цитирования:
Лагузина Е.А. ОБЗОР МЕТОДОВ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ ДВИЖЕНИЯ МОБИЛЬНЫХ РОБОТОВ // Вестник науки №6 (87) том 1. С. 1467 - 1475. 2025 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/23758 (дата обращения: 12.07.2025 г.)
Вестник науки © 2025. 16+