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

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

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

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

Концепции

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

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

Пространство конфигурации

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

  • Если робот представляет собой единственную точку (нулевого размера), перемещающуюся в 2-мерную плоскость (рабочее пространство), C - это плоскость, и конфигурация может быть представлена ​​с использованием двух параметров (x, y).
  • Если робот представляет собой двухмерную фигуру, которая может перемещаться и вращаться, рабочее пространство по-прежнему остается двухмерным. Однако C - специальная евклидова группа SE(2) = р2 ТАК(2) (где ТАК(2) - это специальная ортогональная группа 2D-поворотов), а конфигурацию можно представить с помощью трех параметров (x, y, θ).
  • Если робот представляет собой твердую трехмерную форму, которая может перемещаться и вращаться, рабочая область трехмерна, но C - это особая евклидова группа. SE (3) = р3 ТАК(3), а конфигурация требует 6 параметров: (x, y, z) для перевода и Углы Эйлера (α, β, γ).
  • Если робот представляет собой манипулятор с фиксированным основанием с N поворотными шарнирами (и без замкнутых контуров), C является N-мерным.

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

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

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

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

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

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

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

Алгоритмы

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

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

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

Есть параллельный алгоритм планирования движения (А1-А2) для манипулирования объектами (для ловли летающего объекта). [1]

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

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

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

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

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

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

Эти подходы аналогичны подходам поиска по сетке, за исключением того, что они создают мощение, полностью покрывающее пространство конфигурации, а не сетку.[2] Мощение раскладывается на два подмостки Икс−,ИКС+ сделано с такими коробками, что X− ⊂ Cсвободный ⊂ X+. Характеризуя Cсвободный суммы для решения установить проблему инверсии. Интервальный анализ Таким образом, можно использовать, когда Cсвободный не могут быть описаны линейными неравенствами, чтобы иметь гарантированную замкнутость.

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

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

Перемещение от начальной конфигурации (синий) к окончательной конфигурации крюка, избегая двух препятствий (красные сегменты). Левый нижний угол крючка должен оставаться на горизонтальной линии, что дает крючку две степени свободы.
Декомпозиция с блоками, покрывающими конфигурационное пространство: Подмощение X− является объединением всех красных ящиков и подмостки X+ представляет собой объединение красных и зеленых ящиков. Путь соответствует изображенному выше движению.
Этот рисунок соответствует тому же пути, что и выше, но получен с гораздо меньшим количеством блоков. Алгоритм избегает деления прямоугольников пополам в частях конфигурационного пространства, которые не влияют на конечный результат.

Разложение по подобластям с использованием интервального анализа также позволяет охарактеризовать топологию Cсвободный например, подсчет количества связанных компонентов.[3]

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

Направляйте роботов среди полигональных препятствий

Перевод предметов среди препятствий

В поисках выхода из здания

  • след самого дальнего луча

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

Алгоритмы, основанные на вознаграждении

Алгоритмы на основе вознаграждения предполагают, что робот в каждом состоянии (положение и внутреннее состояние, включая направление) может выбирать между различными действиями (движением). Однако результат каждого действия не определен. Другими словами, результаты (смещение) частично случайны, а частично находятся под контролем робота. Робот получает положительную награду при достижении цели и отрицательную награду при столкновении с препятствием. Эти алгоритмы пытаются найти путь, который максимизирует совокупные будущие вознаграждения. В Марковский процесс принятия решений (MDP) - это популярная математическая структура, которая используется во многих алгоритмах, основанных на вознаграждении. Преимущество MDP перед другими алгоритмами, основанными на вознаграждении, заключается в том, что они генерируют оптимальный путь. Недостатком MDP является то, что они ограничивают выбор робота из конечного набора действий. Следовательно, путь не является гладким (аналогично подходам на основе сетки). Нечеткие марковские процессы принятия решений (FMDP) - это расширение MDP, которые генерируют плавный путь с использованием нечеткая система вывода.[4]

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

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

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

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

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

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

Есть много вариантов этой базовой схемы:

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

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

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

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

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

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

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

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

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

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

Голономический

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

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

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

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

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

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

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

  • Неопределенность движения
  • Недостающая информация
  • Активное зондирование
  • Бессенсорное планирование

Приложения

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

Рекомендации

  1. ^ Бодренко, А. (2019). «Новый способ использования мобильных роботов для перемещения грузов на складе». Вестник науки и практики. 5 (6): 192–211. Дои:10.33619/2414-2948/43/26.
  2. ^ Джаулин, Л. (2001). «Планирование пути с использованием интервалов и графиков» (PDF). Надежные вычисления. 7 (1).
  3. ^ Delanoue, N .; Jaulin, L .; Коттансо, Б. (2006). Подсчет количества связанных компонентов набора и его применение в робототехнике (PDF). Прикладные параллельные вычисления, конспекты лекций по информатике. Конспект лекций по информатике. 3732. С. 93–101. CiteSeerX  10.1.1.123.6764. Дои:10.1007/11558958_11. ISBN  978-3-540-29067-4.
  4. ^ Факур, Махди; Косари, Амирреза; Джафарзаде, Мохсен (2016). «Планирование пути роботов-гуманоидов с нечеткими марковскими процессами принятия решений». Журнал прикладных исследований и технологий. 14 (5): 300–310. Дои:10.1016 / j.jart.2016.06.006.
  5. ^ Факур, Махди; Косари, Амирреза; Джафарзаде, Мохсен (2015). «Ревизия нечеткого искусственного потенциального поля для планирования пути гуманоидного робота в неизвестной среде». Международный журнал передовых мехатронных систем. 6 (4): 174–183. Дои:10.1504 / IJAMECHS.2015.072707.
  6. ^ Вольф, Йорг Кристиан; Робинсон, Пол; Дэвис, Мансель (2004). «Планирование траектории векторного поля и управление автономным роботом в динамической среде». Proc. 2004 Всемирный конгресс роботов FIRA. Пусан, Южная Корея: Документ 151.
  7. ^ Лаваль, Стивен, Алгоритмы планирования Глава 8
  8. ^ Хакоэн, Шломи; Шовал, Шрага; Швалб, Нир (2019). «Функция вероятностной навигации для стохастических статических сред». Международный журнал управления, автоматизации и систем. 17 (8): 2097–2113. Дои:10.1007 / s12555-018-0563-2. S2CID  164509949.
  9. ^ Hsu, D .; J.C. Latombe, J.C.; Мотвани, Р. (1997). «Планирование пути в обширных конфигурационных пространствах». Материалы Международной конференции по робототехнике и автоматизации. 3. С. 2719–2726. Дои:10.1109 / ROBOT.1997.619371. ISBN  978-0-7803-3612-4. S2CID  11070889.
  10. ^ Лай, Тин; Морере, Филипп; Рамос, Фабио; Фрэнсис, Гилад (2020). «Байесовское планирование на основе местной выборки». Письма IEEE по робототехнике и автоматизации. 5 (2): 1954–1961. arXiv:1909.03452. Дои:10.1109 / LRA.2020.2969145. ISSN  2377-3766. S2CID  210838739.
  11. ^ Швалб, Н .; Бен Моше, Б .; Медина, О. (2013). «Алгоритм планирования движения в реальном времени для гипер-избыточного набора механизмов». Роботика. 31 (8): 1327–1335. CiteSeerX  10.1.1.473.7966. Дои:10.1017 / S0263574713000489.
  12. ^ Стивен М. ЛаВалль (29 мая 2006 г.). Алгоритмы планирования. Издательство Кембриджского университета. ISBN  978-1-139-45517-6.

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

внешняя ссылка