Планирование движения, планирование пути (а также задача навигации или задача о передвижении рояля) — это по поиску последовательности допустимых конфигураций, позволяющих переместить объект из начальной точки в конечную. Термин используется в вычислительной геометрии, компьютерной анимации, робототехнике и компьютерных играх.
Например, рассмотрим навигацию внутри здания к удалённой точке. Робот должен выполнить эту задачу избегая стен и не падая с лестницы. Алгоритм планирования движения получает описание этих задач в качестве входных данных и выдаёт команды скорости и поворота, которые будут отправлены на колёса робота. Алгоритмы планирования движения могут быть применены к роботам с большим количеством сочленений (например, промышленные манипуляторы), к роботам с более сложным задачам (например, манипулирование объектами), к роботам, имеющим определённые ограничения (например, автомобиль, который может двигаться только вперёд), и к неопределённости (например, несовершенные модели окружающей среды или робота).
Планирование движения находит применение в различных областях робототехники, таких как автономия, автоматизация и проектирование роботов в системах САПР, а также в других сферах, таких как анимация , видеоигры, , роботизированную хирургию и изучение биомолекул.
Концепции
Основная задача планирования движения заключается в нахождении непрерывного пути, соединяющего начальное положение S с целевым положением G, при этом избегая столкновений с известными препятствиями. Геометрия робота и препятствий описывается в двухмерном или трёхмерном рабочем пространстве, тогда как само движение представляется как путь в (возможно, многомерном) конфигурационном пространстве.
Конфигурационное пространство Конфигурация определяет положение робота, а конфигурационное пространство C — это это совокупность всех возможных конфигураций. Например: Если робот представляет собой точку (нулевые размеры) перемещающуюся в двухмерной плоскости (рабочем пространстве), то C также является плоскостью, и конфигурацию можно описать двумя параметрами (x, y). Если робот — это двухмерная фигура, способная перемещаться и вращаться, рабочее пространство остаётся двухмерным, но C, однако, является евклидовой группой SE(2) = R2 SO(2) (где SO(2) — специальная ортогональная группа двухмерных вращений), и конфигурация может быть представлена тремя параметрами (x, y, θ). Если робот — это твёрдое трёхмерное тело, способное перемещаться и вращаться, рабочее пространство трёхмерно, но C — это специальная евклидова группа SE(3) = R3 SO(3), и для описания конфигурации требуется 6 параметров — (x, y, z) для параллельного переноса и углы Эйлера (α, β, γ). Если робот представляет собой манипулятор с фиксированным основанием и N вращательными соединениями без замкнутых контуров), то C является N-мерным. Если эффект «карданного подвеса» неприемлем (например, в RN где N ≥ 3), может потребоваться использование кватернионов или других обходных решений, что увеличивает количество измерений для вращения или сложность решения.
Свободное пространство Множество конфигураций, позволяющих избежать столкновений с препятствиями, называется свободным пространством Cfree. Дополнение Cfree в C называется областью препятствий или запретной областью.
Часто явное вычисление формы Cfree является чрезвычайно сложной задачей. Однако, проверка принадлежности заданной конфигурации к Cfree выполняется эффективно. Сначала прямая кинематика определяет положение робота, а затем обнаружение столкновений проверяет, сталкивается ли геометрия робота с геометрией окружающей среды.
Целевое пространство Целевое пространство — это подпространство свободного пространства, обозначающее желаемое местоположение робота. При глобальном планировании движения целевое пространство наблюдаемо датчиками робота, однако при локальном планировании движения робот не может наблюдать целевое пространство в некоторых состояниях. Для решения этой проблемы робот проходит через несколько виртуальных целевых пространств, каждое из которых расположено в пределах наблюдаемой области (вокруг робота). Виртуальное целевое пространство называется подцелью.
Пространство препятствий Пространство препятствий — это пространство, в которое робот не может перемещаться. Пространство препятствий не является противоположностью свободного пространства.
Алгоритмы Низкоразмерные задачи могут быть решены с помощью сеточных алгоритмов, которые накладывают сетку на конфигурационное пространство, или геометрических алгоритмов, которые вычисляют форму и связность Cfree.
Точное планирование движения для систем высокой размерности при сложных ограничениях является вычислительно неразрешимой задачей. Алгоритмы потенциальных полей эффективны, но подвержены проблеме локальных минимумов (исключением являются гармонические потенциальные поля). Алгоритмы, основанные на выборке, избегают проблемы локальных минимумов и довольно быстро решают многие задачи. Они не способны определить отсутствие пути, но вероятность их отказа стремится к нулю по мере увеличения затраченного времени.
Алгоритмы, основанные на выборке, в настоящее время считаются передовыми для планирования движений в многомерных пространствах и применялись для решения задач с десятками или даже сотнями измерений (роботизированные манипуляторы, биологические молекулы, анимированные цифровые персонажи и ).
Поиск на основе сетки Подходы, основанные на сетке, накладывают сетку на конфигурационное пространство и предполагают, что каждая конфигурация идентифицируется с точкой сетки. В каждой точке сетки роботу разрешено перемещаться в соседние точки сетки при условии, что линия между ними полностью содержится в Cfree (это проверяется с помощью обнаружения столкновений). Это дискретизирует набор действий, и алгоритмы поиска (например, A*) используются для нахождения пути от начальной до целевой точки.
Эти методы требуют определения разрешающей способности сетки. Поиск быстрее при использовании более грубых сеток, но алгоритм не сможет найти пути через узкие участки свободного пространства Cfree. Кроме того, количество точек на сетке экспоненциально увеличивается с размерностью конфигурационного пространства, что делает их непригодными для задач высокой размерности.
Традиционные подходы, основанные на сетке, создают траектории, изменения направления которых ограничены кратными заданного базового угла, что часто приводит к неоптимальным путям. Методы находят более короткие пути, распространяя информацию вдоль рёбер сетки (для быстрого поиска) без привязки траекторий к рёбрам сетки (для нахождения коротких путей).
Подходы, основанные на сетке, часто требуют повторного поиска, например, когда знания робота о конфигурационном пространстве меняются или само конфигурационное пространство изменяется во время следования по пути. Алгоритм быстро перепланирует путь, используя опыт предыдущих задач планирования пути для ускорения поиска текущего решения.
Поиск на основе интервалов Эти подходы схожи с методами поиска на основе сетки, но вместо сетки они создают замощение, полностью покрывающее конфигурационное пространство. Замощение разбивается на два подзамощения X−,X+ состоящих из плиток замощения, таких что X− ⊂ Cfree ⊂ X+. Описание Cfree сводится к решению . Если Cfree не может быть описан линейными неравенствами, для получения гарантированного охвата может быть использована интервальная арифметика.
Роботу разрешено свободно перемещаться в пределах X− и запрещено выходить за пределы X+. Для обоих подзамощений строится граф смежности, и пути могут быть найдены с помощью, например, алгоритма Дейкстры или A*. Если путь допустим в X−, то он также допустим и в Cfree. Если же путь из начальной конфигурации в целевую не существует в X+, то существует гарантия отсутствия допустимого пути в Cfree. Как и в случае с подходом на основе сетки, интервальный подход не подходит для задач высокой размерности, поскольку количество требуемых областей растет экспоненциально с увеличением размерности конфигурационного пространства.
Иллюстрация представлена тремя изображениями справа, где крюк с двумя степенями свободы должен переместиться слева направо, избегая двух горизонтальных небольших отрезков.
Николя Делану показал, что декомпозиция с использованием подзамощения на основе интервального анализа также позволяет характеризовать топологию Cfree например, подсчитывать количество его связных компонент.
Геометрические алгоритмы Точечные роботы среди многоугольных препятствий. Граф видимости
Диаграмма Вороного
Передвижешие объекта среди препятствий Сумма Минковского
Поиск выхода из здания самый дальний след луча Учитывая пучок лучей вокруг текущего положения, каждому из которых приписана длина до столкновения со стеной, робот движется в направлении самого длинного луча, если только не обнаружена дверь. Подобный алгоритм использовался для моделирования аварийного выхода из зданий.
Искусственные потенциальные поля Один из подходов заключается в рассмотрении конфигурации робота как точки в потенциальном поле, которое сочетает притяжение к цели и отталкивание от препятствий. Полученная траектория выводится как путь. Этот подход имеет преимущества, поскольку траектория генерируется с минимальными вычислительными затратами. Однако робот может застрять в локальном минимуме потенциального поля и не найти путь, или же найти неоптимальный путь. Искусственные потенциальные поля можно рассматривать как непрерывные уравнения, аналогичные электростатическим потенциальным полям (рассматривая робота как точечный заряд), или движение в поле можно дискретизировать с помощью набора лингвистических правил. или вероятностная навигационная функция являются разновидностями искусственных потенциальных функций, которые обладают свойством отсутствия точек минимума, кроме целевой точки.
Алгоритмы на основе выборки Алгоритмы на основе выборки представляют конфигурационное пространство с помощью дорожной карты из выбранных конфигураций. Базовый алгоритм выбирает N конфигураций в C и сохраняет те, которые находятся в Cfree, для использования в качестве контрольных точек. Затем строится дорожная карта, соединяющая две контрольные точки P и Q, если отрезок PQ полностью находится в Cfree. Опять же, для проверки принадлежности к Cfree используется обнаружение столкновений. Чтобы найти путь, соединяющий S и G, они добавляются к дорожной карте. Если путь на дорожной карте связывает S и G, планировщик успешно завершает работу и возвращает этот путь. Если нет, причина не является окончательной: либо пути в Cfree не существует, либо планировщик не выбрал достаточно контрольных точек.
Эти алгоритмы работают хорошо для конфигурационных пространств высокой размерности, поскольку, в отличие от комбинаторных алгоритмов, их время выполнения не зависит (явно) экспоненциально от размерности C. Они также (как правило) значительно проще в реализации. Они являются вероятностно полными, что означает, что вероятность получения решения приближается к 1 по мере увеличения затраченного времени. Однако они не могут определить, существует ли решение.
При соблюдении базовых условий видимости в Cfree, было доказано, что по мере увеличения числа конфигураций N вероятность того, что вышеупомянутый алгоритм найдет решение, экспоненциально приближается к 1. Видимость не зависит явно от размерности C — пространство высокой размерности может иметь «хорошую» видимость, а пространство низкой размерности иметь «плохую» видимость. Экспериментальный успех методов, основанных на выборке, предполагает, что большинство часто встречающихся пространств имеют хорошую видимость.
Существует множество вариантов этой базовой схемы: Обычно гораздо быстрее проверять только отрезки между соседними парами контрольных точек, а не все пары. Неравномерные распределения выборки стремятся разместить больше контрольных точек в областях, улучшающих связность дорожной карты.