Планирование движения

Вычислительная задача

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

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

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

Концепции

Пример рабочего пространства

Конфигурационное пространство точечного робота. Белый = C _free , серый = C _obs .

Конфигурационное пространство для прямоугольного транслирующего робота (на фото красный). Белый = C _free , серый = C _obs , где темно-серый = объекты, светло-серый = конфигурации, при которых робот касается объекта или покидает рабочее пространство.

Пример допустимого пути

Пример недопустимого пути

Пример дорожной карты

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

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

Конфигурация описывает позу робота, а конфигурационное пространство C — это набор всех возможных конфигураций. Например:

• Если робот представляет собой одну точку (нулевого размера), перемещающуюся в двухмерной плоскости (рабочем пространстве), то C является плоскостью, а конфигурация может быть представлена ​​с помощью двух параметров (x, y).
• Если робот представляет собой двумерную форму, которая может перемещаться и вращаться, рабочее пространство по-прежнему будет двумерным. Однако C — это специальная евклидова группа SE (2) = R ² SO (2) (где SO (2) — это специальная ортогональная группа двумерных вращений), а конфигурация может быть представлена ​​с использованием 3 параметров (x, y, θ). ${\displaystyle \times }$
• Если робот представляет собой сплошную трехмерную фигуру, которая может перемещаться и вращаться, то рабочее пространство будет трехмерным, но C — это специальная евклидова группа SE(3) = R ³ SO (3), а для конфигурации требуется 6 параметров: (x, y, z) для перемещения и углы Эйлера (α, β, γ). ${\displaystyle \times }$
• Если робот представляет собой манипулятор с фиксированным основанием и N вращающимися сочленениями (и без замкнутых контуров), то C имеет N-мерность.

Свободное место

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

Эти подходы похожи на подходы поиска на основе сетки, за исключением того, что они генерируют мощение, полностью покрывающее пространство конфигураций вместо сетки. ^[1] Мощение разлагается на два подмощения X ⁻ ,X ^{+ ,} сделанные с помощью коробок, таких что X ⁻ ⊂ C _free ⊂ X ⁺ . Характеризация C _free сумм для решения задачи инверсии множеств . Таким образом, интервальный анализ может быть использован, когда C _free не может быть описан линейными неравенствами, чтобы иметь гарантированное ограждение.

Таким образом, роботу разрешено свободно перемещаться в X ⁻ и он не может выходить за пределы X ⁺ . Для обоих подмощений строится граф соседей, и пути могут быть найдены с помощью таких алгоритмов, как Дейкстра или A* . Когда путь возможен в X ⁻ , он также возможен в C _free . Когда не существует пути в X ⁺ от одной начальной конфигурации до цели, у нас есть гарантия, что не существует допустимого пути в C _free . Что касается подхода на основе сетки, интервальный подход не подходит для задач высокой размерности из-за того, что количество генерируемых ящиков растет экспоненциально по отношению к размерности конфигурационного пространства.

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

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

Разложение с блоками, покрывающими конфигурационное пространство: Подмост X ⁻ — это объединение всех красных блоков, а подмост X ⁺ — это объединение красных и зеленых блоков. Путь соответствует движению, представленному выше.

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

Николя Делану показал, что разложение с подмостями с использованием интервального анализа также позволяет охарактеризовать топологию C _free , например, подсчитать количество его связных компонентов. ^[2]

Геометрические алгоритмы

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

• График видимости
• Разложение клеток
• Диаграмма Вороного

Перемещение объектов среди препятствий

• сумма Минковского

Как выбраться из здания

• самая дальняя трассировка луча

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

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

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

Алгоритмы, основанные на выборке

Алгоритмы на основе выборки представляют конфигурационное пространство с дорожной картой выбранных конфигураций. Базовый алгоритм выбирает N конфигураций в C и сохраняет их в C _free для использования в качестве вех . Затем строится дорожная карта, которая соединяет две вехи P и Q, если отрезок линии PQ полностью находится в C _free . Опять же, обнаружение столкновений используется для проверки включения в C _{free . Чтобы найти путь, соединяющий S и G, они добавляются в дорожную карту. Если путь в дорожной карте связывает S и G, планировщику это удается, и он возвращает этот путь. Если нет, причина не определена: либо в C free} нет пути , либо планировщик не выбрал достаточно вех.

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

Учитывая основные условия видимости на C _free , было доказано, что по мере увеличения числа конфигураций N вероятность того, что указанный выше алгоритм найдет решение, экспоненциально приближается к 1. ^[6] Видимость не зависит явно от размерности C; возможно иметь высокоразмерное пространство с «хорошей» видимостью или низкоразмерное пространство с «плохой» видимостью. Экспериментальный успех методов, основанных на выборках, предполагает, что наиболее часто встречающиеся пространства имеют хорошую видимость.

Существует множество вариантов этой базовой схемы:

• Обычно гораздо быстрее тестировать только сегменты между близлежащими парами контрольных точек, а не все пары.
• Неравномерное распределение выборки позволяет разместить больше контрольных точек в областях, которые улучшают связанность дорожной карты.
• Квазислучайные выборки обычно обеспечивают лучшее покрытие конфигурационного пространства, чем псевдослучайные , хотя в некоторых недавних работах утверждается, что влияние источника случайности минимально по сравнению с влиянием распределения выборки.
• Использует локальную выборку ^[7] путем выполнения направленного случайного блуждания Монте-Карло цепи Маркова с некоторым локальным распределением предложений.
• Можно существенно сократить количество контрольных точек, необходимых для решения данной задачи, если использовать кривые линии зрения (например, преодолевая препятствия, которые блокируют путь между двумя контрольными точками ^[8] ).
• Если требуется только один или несколько запросов планирования, не всегда необходимо строить дорожную карту всего пространства. Варианты с выращиванием деревьев обычно быстрее в этом случае (планирование с одним запросом). Дорожные карты все еще полезны, если необходимо сделать много запросов в одном и том же пространстве (планирование с несколькими запросами)

Список известных алгоритмов

• А*
• Д*
• Быстро исследуемое случайное дерево
• Вероятностная дорожная карта

Полнота и производительность

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

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

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

Полнота разрешения — это свойство, при котором планировщик гарантированно найдет путь, если разрешение базовой сетки достаточно хорошее. Большинство планировщиков с полным разрешением основаны на сетке или интервале. Вычислительная сложность планировщиков с полным разрешением зависит от количества точек в базовой сетке, которое равно O(1/h ^d ), где h — разрешение (длина одной стороны ячейки сетки), а d — размерность конфигурационного пространства.

Вероятностная полнота — это свойство, заключающееся в том, что по мере выполнения большей «работы» вероятность того, что планировщик не сможет найти путь, если таковой существует, асимптотически стремится к нулю. Несколько методов, основанных на выборках, являются вероятностно полными. Производительность вероятностно полного планировщика измеряется скоростью сходимости. Для практических приложений обычно используют это свойство, поскольку оно позволяет устанавливать тайм-аут для сторожевого таймера на основе среднего времени сходимости.

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

Варианты проблем

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

Дифференциальные ограничения

Голономный

• Манипуляторные руки (с динамикой)

Неголономный

• Дроны
• Автомобили
• Моноциклы
• Самолеты
• Системы с ограниченным ускорением
• Движущиеся препятствия (время не может идти вспять)
• Управляемая игла со скошенным кончиком
• Роботы с дифференциальным приводом

Ограничения оптимальности

Гибридные системы

Гибридные системы — это те, которые смешивают дискретное и непрерывное поведение. Примерами таких систем являются:

• Роботизированная манипуляция
• Механическая сборка
• Передвижение робота на ногах
• Реконфигурируемые роботы

Неопределенность

• Неопределенность движения
• Отсутствует информация
• Активное зондирование
• Планирование без датчиков
• Сетевые системы управления ^[9]

Экологические ограничения

• Карты динамики ^[10]

Приложения

• Навигация робота
• Автоматизация
• Беспилотный автомобиль
• Роботизированная хирургия
• Цифровая анимация персонажей
• Сворачивание белка ^[11]
• Безопасность и доступность в автоматизированном архитектурном проектировании

Смотрите также

• Задача о перемещении дивана — математическая задача нахождения наибольшей двумерной фигуры, которую можно переместить за угол.
• Блокировка карданного подвеса – аналогичная традиционная проблема в машиностроении
• Кинодинамическое планирование
• Проблема альпинизма
• OMPL — Открытая библиотека планирования движения
• Поиск пути
• Проблемы движения гальки – планирование движения нескольких роботов
• Задача о кратчайшем пути
• Препятствие скорости

Ссылки

1. Жолен, Л. (2001). "Планирование пути с использованием интервалов и графиков" (PDF) . Надежные вычисления . 7 (1).
2. Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). «Подсчет количества связанных компонентов множества и его применение в робототехнике». Прикладные параллельные вычисления. Состояние науки в области вычислений (PDF) . Конспект лекций по информатике. Том 3732. С. 93–101. CiteSeerX 10.1.1.123.6764 . doi :10.1007/11558958_11. ISBN  978-3-540-29067-4. {{cite book}}: |journal=проигнорировано ( помощь )
3. Вольф, Йорг Кристиан; Робинсон, Пол; Дэвис, Мансел (2004). «Планирование пути векторного поля и управление автономным роботом в динамической среде». Труды Всемирного конгресса робототехники FIRA 2004 года . Пусан, Южная Корея: Доклад 151.
4. Лаваль, Стивен, Алгоритмы планирования Глава 8 Архивировано 15 апреля 2021 г. на Wayback Machine
5. Хакоэн, Шломи; Шовал, Шрага; Швалб, Нир (2019). «Вероятностная навигационная функция для стохастических статических сред». Международный журнал управления, автоматизации и систем . 17 (8): 2097–2113. doi :10.1007/s12555-018-0563-2. S2CID  164509949.
6. Hsu, D.; JC Latombe, JC ; Motwani, R. (1997). «Планирование пути в обширных конфигурационных пространствах». Труды Международной конференции по робототехнике и автоматизации . Том 3. С. 2719–2726. doi :10.1109/ROBOT.1997.619371. ISBN 978-0-7803-3612-4. S2CID  11070889.
7. Лай, Тин; Морере, Филипп; Рамос, Фабио; Фрэнсис, Гилад (2020). «Байесовское локальное выборочное планирование». IEEE Robotics and Automation Letters . 5 (2): 1954–1961. arXiv : 1909.03452 . doi : 10.1109/LRA.2020.2969145. ISSN  2377-3766. S2CID  210838739.
8. Швалб, Н.; Бен Моше, Б.; Медина, О. (2013). «Алгоритм планирования движения в реальном времени для гиперизбыточного набора механизмов». Robotica . 31 (8): 1327–1335. CiteSeerX 10.1.1.473.7966 . doi :10.1017/S0263574713000489. S2CID  17483785. 
9. Scordamaglia, V.; Nardi, VA (2021). «Алгоритм планирования траектории на основе набора для гусеничного мобильного робота с бортовым поворотом, управляемого по сети, подверженного явлениям скольжения и проскальзывания». Журнал интеллектуальных и робототехнических систем . 101. Springer Nature BV doi :10.1007/s10846-020-01267-0. S2CID  229326435.
10. Куцнер, Томаш Петр; Лилиенталь, Ахим Дж.; Магнуссон, Мартин; Пальмиери, Луиджи; Шринивас Сваминатан, Читтаранджан (2020). Вероятностное картирование пространственных моделей движения для мобильных роботов. Cognitive Systems Monographs. Том 40. doi :10.1007/978-3-030-41808-3. ISBN 978-3-030-41807-6. ISSN  1867-4925. S2CID  52087877.
11. Стивен М. ЛаВаль (29 мая 2006 г.). Алгоритмы планирования. Cambridge University Press. ISBN 978-1-139-45517-6.

Дальнейшее чтение

• Латомб, Жан-Клод (2012). Планирование движения робота. Springer Science & Business Media. ISBN 978-1-4615-4022-9.
• Алгоритмы планирования , Стивен М. ЛаВалль, 2006, Cambridge University Press, ISBN 0-521-86205-1 . 
• Принципы движения робота: теория, алгоритмы и реализация , Х. Чосет, В. Бургард, С. Хатчинсон, Г. Кантор, Л. Е. Кавраки , К. Линч и С. Трун, MIT Press, апрель 2005 г.
• Марк де Берг; Марк ван Кревелд; Марк Овермарс и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е исправленное изд.). Спрингер-Верлаг . ISBN 978-3-540-65620-3.Глава 13: Планирование движения робота: стр. 267–290.

Внешние ссылки

• «Открытая виртуальная среда автоматизации робототехники», http://openrave.org/
• Жан-Клод Латомб рассказывает о своей работе с роботами и планировании движения, 5 апреля 2000 г.
• «Открытая библиотека планирования движения ( OMPL )», http://ompl.kavrakilab.org
• «Библиотека стратегии движения», http://msl.cs.uiuc.edu/msl/
• «Комплект для планирования движения», https://ai.stanford.edu/~mitul/mpk
• «Симокс», http://simox.sourceforge.net
• «Планирование и управление движением робота», http://www.laas.fr/%7Ejpl/book.html