Введение

Планирование движения, также планирование пути (также известное как задача навигации или задача о перемещении пианино) — это вычислительная задача, заключающаяся в поиске последовательности допустимых конфигураций, перемещающих объект из начальной точки в конечную. Этот термин используется в вычислительной геометрии, компьютерной анимации, робототехнике и компьютерных играх. Например, рассмотрим задачу навигации мобильного робота внутри здания к удаленной точке. Он должен выполнить эту задачу, избегая стен и не падая с лестниц. Алгоритм планирования движения принимает описание этих задач в качестве входных данных и выдает команды скорости и поворота, отправляемые колесам робота. Алгоритмы планирования движения могут применяться к роботам с большим количеством звеньев (например, промышленным манипуляторам), для решения более сложных задач (например, манипулирования объектами), с учетом различных ограничений (например, автомобиль, который может двигаться только вперед) и неопределенности (например, неточные модели окружающей среды или робота). Планирование движения имеет множество применений в робототехнике, таких как автономность, автоматизация и проектирование роботов в системах автоматизированного проектирования (САПР), а также в других областях, таких как анимация цифровых персонажей, видеоигры, архитектурное проектирование, роботизированная хирургия и изучение биологических молекул.

Понятия

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

Конфигурационное пространство

Конфигурация описывает позу робота, а конфигурационное пространство C представляет собой множество всех возможных конфигураций. Например: если робот представляет собой одну точку (нулевого размера), перемещающуюся в двухмерной плоскости (рабочее пространство), C является плоскостью, и конфигурация может быть представлена двумя параметрами (x, y). Если робот представляет собой двухмерную форму, способную к перемещению и вращению, рабочее пространство остаётся двухмерным. Однако, C – это специальная евклидова группа SE(2) = R² ⊕ SO(2) (где SO(2) – специальная ортогональная группа двумерных вращений), и конфигурация может быть представлена тремя параметрами (x, y, θ). Если робот представляет собой твердотельную трехмерную форму, способную к перемещению и вращению, рабочее пространство является трехмерным, но C – это специальная евклидова группа SE(3) = R³ ⊕ SO(3), и для описания конфигурации требуется 6 параметров: (x, y, z) для перемещения и углы Эйлера (α, β, γ). Если робот является манипулятором с неподвижным основанием и N вращательными соединениями (без замкнутых кинематических цепей), C является N-мерным.

Свободное пространство

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

Целевое пространство

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

Пространство препятствий

Пространство препятствий — это область, в которую робот не может переместиться. Пространство препятствий не является противоположностью свободного пространства.

Алгоритмы

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

Поиск по сетке

Подходы, основанные на сетке, накладывают сетку на пространство конфигураций и предполагают, что каждая конфигурация идентифицируется с узлом сетки. В каждом узле сетки роботу разрешается перемещаться к соседним узлам, если отрезок, соединяющий их, полностью лежит в пределах Cfree (это проверяется с помощью обнаружения столкновений). Это дискретизирует множество доступных действий, и алгоритмы поиска (например, A*) используются для нахождения пути от начальной до конечной конфигурации. Эти подходы требуют задания разрешения сетки. Поиск выполняется быстрее на более грубых сетках, но алгоритм может не найти пути через узкие области Cfree. Кроме того, количество узлов сетки растет экспоненциально с увеличением размерности пространства конфигураций, что делает их непригодными для задач высокой размерности. Традиционные подходы, основанные на сетке, генерируют пути, изменения направления которых ограничены дискретными углами, что часто приводит к субоптимальным решениям. Методы планирования путей с произвольными углами находят более короткие пути, распространяя информацию вдоль ребер сетки (для ускорения поиска), не ограничивая при этом пути ребрами сетки (для достижения минимальной длины). Подходы, основанные на сетке, часто требуют повторного поиска, например, при изменении знаний робота о пространстве конфигураций или самого пространства конфигураций в процессе следования по пути. Инкрементальные эвристические алгоритмы поиска быстро перепланируют, используя опыт, полученный при решении предыдущих аналогичных задач планирования пути, для ускорения текущего поиска.

Поиск по интервалу

Эти подходы аналогичны методам поиска на основе сетки, за исключением того, что они генерируют покрытие, полностью покрывающее пространство конфигураций, а не сетку. Покрытие разбивается на два подпокрытия X− и X+, состоящие из блоков, таких что X− ⊂ Cfree ⊂ X+. Характеризация Cfree сводится к решению задачи инверсии множества. Таким образом, интервальный анализ может быть использован, когда Cfree нельзя описать линейными неравенствами, чтобы обеспечить гарантированное включение. Роботу, таким образом, разрешено свободно перемещаться в X−, и он не может выйти за пределы X+. Для обоих подпокрытий строится граф смежности, и пути могут быть найдены с использованием алгоритмов, таких как алгоритм Дейкстры или A*. Если путь выполним в X−, то он также выполним в Cfree. Если в X+ не существует пути от начальной конфигурации к цели, то мы имеем гарантию, что в Cfree не существует выполнимого пути. Как и в случае подхода на основе сетки, интервальный подход не подходит для задач высокой размерности из-за того, что количество блоков, которые необходимо сгенерировать, растет экспоненциально с увеличением размерности пространства конфигураций. Пример иллюстрируется тремя рисунками справа, где крючок с двумя степенями свободы должен переместиться слева направо, избегая двух небольших горизонтальных сегментов. Николас Делану показал, что разложение на подпокрытия с использованием интервального анализа также позволяет характеризовать топологию Cfree, например, подсчитывать количество связных компонент.

Искусственные потенциальные поля

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

Полность и исполнение

Планировщик движения считается полным, если он за конечное время либо находит решение, либо корректно сообщает об его отсутствии. Большинство полных алгоритмов основаны на геометрии. Эффективность полного планировщика оценивается по его вычислительной сложности. При математическом доказательстве этого свойства необходимо убедиться, что оно выполняется за конечное время, а не только в асимптотическом пределе. Это особенно проблематично, если в процессе применения конкретного метода доказательства возникают бесконечные последовательности (сходящиеся лишь в предельном случае), поскольку тогда алгоритм теоретически никогда не остановится. Интуитивные "трюки" (часто основанные на индукции) обычно ошибочно принимаются за сходящиеся, хотя они сходятся только в бесконечном пределе. Иными словами, решение существует, но планировщик никогда его не выдаст. Это свойство, следовательно, связано с полнотой Тьюринга и в большинстве случаев служит теоретической основой или руководством. Планировщики, основанные на методе полного перебора, всегда полны, но реализуемы только для конечных и дискретных задач. На практике завершение алгоритма всегда можно гарантировать с помощью счетчика, ограничивающего максимальное количество итераций, после чего алгоритм останавливается, независимо от наличия решения. В системах реального времени это обычно достигается с помощью сторожевого таймера, который просто завершает процесс. Сторожевой таймер должен быть независим от всех процессов (обычно реализуется с помощью низкоуровневых обработчиков прерываний). Однако описанный в предыдущем абзаце асимптотический случай таким образом достигнут не будет. Он сообщит о наилучшем найденном решении (что лучше, чем ничего) или об отсутствии решения, но не сможет корректно сообщить об отсутствии решения. Все реализации, включающие сторожевой таймер, всегда неполны (за исключением случаев, когда все возможные ситуации могут быть оценены за конечное время). Полнота может быть обеспечена только очень строгим математическим доказательством корректности (часто с использованием инструментов и методов, основанных на графах) и должна выполняться только специализированными экспертами, если приложение связано с безопасностью. С другой стороны, опровергнуть полноту легко, достаточно найти один бесконечный цикл или один неверный результат. Формальная верификация/проверка корректности алгоритмов – это самостоятельная область исследований. Правильная настройка этих тестовых случаев – сложная задача. Полнота по разрешению – это свойство, гарантирующее, что планировщик найдет путь, если разрешение базовой сетки достаточно велико. Большинство планировщиков с полнотой по разрешению основаны на сетках или интервалах. Вычислительная сложность планировщиков с полнотой по разрешению зависит от количества точек в базовой сетке и составляет O(1/hd), где h – разрешение (длина стороны ячейки сетки), а d – размерность пространства конфигураций. Вероятностная полнота – это свойство, согласно которому по мере увеличения объема выполненной "работы" вероятность того, что планировщик не найдет путь, если он существует, асимптотически стремится к нулю. Некоторые методы, основанные на выборке, являются вероятностно полными. Эффективность вероятностно полного планировщика измеряется скоростью сходимости. Для практических приложений обычно используется это свойство, поскольку оно позволяет установить время ожидания для сторожевого таймера на основе среднего времени сходимости. Неполные планировщики не всегда находят допустимый путь, даже если он существует (см. первый абзац). Иногда неполные планировщики хорошо работают на практике, поскольку они всегда останавливаются за гарантированное время и позволяют другим подпрограммам взять на себя управление.

Проблематические варианты

Для решения различных вариантов этой основной проблемы разработано множество алгоритмов.