RoboticsChapter 5 — Планирование траектории и траектории Dr. Amit Goradia

Темы • Введение — 2 часа • Преобразование координат — 6 часов • Прямая кинематика — 6 часов • Обратная кинематика — 6 часов • Скорость кинематики — 2 часа • Планирование траектории — 6 часов • Динамика робота (введение) — 2 часа • Управление силой (введение) — 1 час • Планирование задач — 6 часов

Robot Motion Planning • Планирование пути • Геометрический путь • Проблемы: обход препятствий, кратчайший путь • Планирование траектории, • «интерполировать» или «аппроксимировать» желаемый путь с помощью класса полиномиальных функций • Создать последовательность на основе времени «контрольного набора точки »для управления манипулятором от начальной конфигурации до места назначения.

Мир состоит из… • Препятствий • Уже занятых пространств мира • Другими словами, роботы не могут туда попасть • Свободное пространство • Незанятое пространство в мире • Роботы «могут» уйти здесь • Чтобы определить, куда может пойти робот, нам нужно обсудить, что такое пространство конфигурации

пространство конфигурации • Обозначения: • A: один жесткий объект — (робот) • W: евклидово пространство, в котором движется A; • B1,… Bm: фиксированные жесткие препятствия, распределенные в W • FW — мировая рама (неподвижная рама) • FA — рама робота (движущаяся рама, жестко связанная с роботом) Конфигурация q of A представляет собой спецификацию физического состояния (положение и ориентация ) A w.к.т. фиксированная окружающая среда FW. Пространство конфигурации — это пространство всех возможных конфигураций робота.

Определения • Конфигурация: спецификация всех переменных, которые полностью определяют систему • Пример: Конфигурация робота dof: • Пространство конфигурации (пространство C): Набор всех конфигураций • Свободная конфигурация: конфигурация, которая выполняет не сталкиваться с препятствиями • Свободное пространство (F): набор всех свободных конфигураций • Это подмножество C

C Cfree qslug Cobs qrobot Пространство конфигурации 2D-планировщика Робот Пространство конфигурации A — это пространство (C ) из всех возможных конфигураций А.Точечный робот (свободный полет, без ограничений) Для точечного робота, движущегося в 2-D плоскости, C-space равен

C y Cfree qgoal Z Cobs qstart x Пространство конфигурации робота, движущегося в 3D Для точки Робот, движущийся в 3D, C-spaceis В чем разница между евклидовым и C-пространством?

Пространство конфигурации шарнирного робота 2R манипулятор bbaa 2R Пространство конфигурации топология

Пространство конфигурации 360 qrobot 270 b 180 b 90 a qgoal a 0 45 135 90 180 Две точки в рабочей области робота Torus ( Обтекание по горизонтали и вертикали)

Область конфигурации Если конфигурация робота находится в синей области, он столкнется с препятствием 360 qrobot 270 b 180 b 90 a qslug a 0 45 135 90 180 Препятствие в рабочей области робота a Представление «C-пространство» Каково измерение C-пространства робота-пумы (6R)? Визуализация C-пространства высокой размерности затруднена

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

Робот как точечный объект Расширить препятствие (я) Уменьшить робота не совсем правильно…

Рост препятствий Робот C-препятствия

Суммы Минковского Это расширение одной плоской формы другой называется суммой Минковского ski Прямоугольный робот, который может переводить только P  RRPP  R = { p + r | p  P и r  R} (операция расширения) Используется в робототехнике для обеспечения доступности свободных путей.

Дополнительные размеры Каким будет С-препятствие, если прямоугольный робот (красный) может перемещаться и вращаться в плоскости.(Синий прямоугольник является препятствием.) Y Прямоугольный робот, который может переводить и вращать x

C-препятствие в трехмерном Как будет выглядеть пространство конфигурации прямоугольного робота 3DOF (красного цвета) в этом мире? (Препятствие синее.) 3-D 180º y 0º x мы можем остаться в 2d?

Один кусочек C-препятствия Взятие одного кусочка C-препятствия, в котором робот поворачивается на 45 градусов … P  RR y 45 градусов P x

2-D проекция yx почему не держать это так просто?

Проблемы с проекцией qinit qgoal слишком консервативен!

Методы планирования движения Задача планирования движения состоит из следующего: Входные данные Вывод • Геометрические описания робота и его окружения (препятствия) • Начальная и конечная конфигурации • Путь от начала до конца (или признание того, что ничего не существует) существует) qrobot qgoal Постановка задачи Вычислить путь без столкновений для жесткого или сочлененного движущегося объекта среди статических препятствий Что делать?

Методы планирования движения (1) Подходы к дорожной карте (2) Разложение ячеек (3) Потенциальные поля (4) Алгоритмы ошибок Цель — уменьшить пространство N-мерной конфигурации до набора одномерных путей для поиска.2) N = количество вершин в C-пространстве. Дорожная карта: графы видимости Графы видимости: в многоугольном (или многогранном) конфигурационном пространстве постройте все отрезки, которые соединяют вершины друг с другом (и которые не пересекают сами препятствия). ). • Формируется путем соединения всех «видимых» вершин, начальной и конечной точек друг с другом. • Чтобы две точки были «видимыми», между ними не должно быть никаких препятствий. • По периметру препятствий существуют пути. Из Cfree определяется граф. Преобразует задачу в поиск в графе.

График видимости в действии • Сначала нарисуйте линии видимости от начала и цели до всех «видимых» вершин и уголков мира. начало цели

График видимости в действии • Во-вторых, нарисуйте линии видимости из каждой вершины каждого препятствия, как прежде. Помните, что линии по краям также являются линиями обзора. начало цели

цель старт График видимости • Повторяйте, пока не закончите. Поскольку карта была в C-пространстве, каждая строка потенциально представляет часть пути от начала до цели.

Недостатки графа видимости Графики видимости не сохраняют свою оптимальность в больших измерениях: кратчайший путь кратчайший путь в графе видимости Кроме того, пути, которые они находят, являются «полусвободными», то есть в контакте с препятствиями. Без зазоров

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

Дорожная карта: диаграммы Вороного • GVG формируется путями, равноудаленными от двух ближайших объектов • максимизируя расстояние между препятствиями. • Это создает очень безопасную дорожную карту, которая максимально избегает препятствий.

Диаграмма Вороного: Метрики • Множество способов измерения расстояния; два: • L1 метрика • (x, y): | x | + | y ​​| = const • Метрика L2 • (x, y): x2 + y2 = const

Диаграмма Вороного (L1) Обратите внимание на отсутствие изогнутых ребер

Диаграмма Вороного (L2) Обратите внимание на изогнутые ребра

Методы планирования движения • Подходы к дорожной карте • График видимости • Диаграмма Вороного • Разложение ячеек • Точное разложение ячеек (трапециевидное) • Приблизительное разложение ячеек (квадродерево) • Потенциальные поля • Гибридные локальные / глобальные

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

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

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

Оптимальность Трапецеидальная декомпозиция: 15 ячеек 9 ячеек Получение минимального количества выпуклых ячеек является NP-полным. Трапецеидальная декомпозиция является точной и полной, но не оптимальной, в мире может быть больше деталей, чем нужно беспокоить о задаче …

Приблизительная декомпозиция соты Декомпозиция квадродерева: рекурсивно подразделяет каждое смешанное препятствие / свободно (под) область на четыре четверти… Quadtree:

Дальнейшее разложение Разложение Quadtree: рекурсивно делит каждое смешанное препятствие / свободную (под) область на четыре четверти … Quadtree:

Даже дальнейшее разложение Ячейка Quadtree Разложение: • Прямоугольное рекурсивно разлагается на меньшие прямоугольники. • При определенном уровне разрешения используются только ячейки, внутренности которых полностью находятся в свободном пространстве. • Поиск в этом графе дает путь без столкновений. Опять же, используйте алгоритм поиска в графе, чтобы найти путь. от начала до цели это полный алгоритм планирования пути? я.находит ли он путь, когда он существует? Quadtree

Вероятностные методы дорожной карты • Что такое PRM (вероятностный метод дорожной карты) • Вероятностная дорожная карта — это дискретное представление непрерывного пространства конфигурации, генерируемого путем случайной выборки свободных конфигураций C-пространства и соединения этих точек в график • Полное планирование пути в многомерных C-пространствах очень сложно • Методы PRM повышают производительность за счет обмена полнотой на вероятностную полноту • Двухфазный подход: фаза обучения, фаза запроса

с ~ s ~ gg Вероятностная дорожная карта Методы • Вероятностные методы для поэтапного построения дорожной карты в свободном пространстве робота. • Управляемый эффективностью. • Роботы с большим количеством степеней свободы (C-пространства с высокой яркостью). • Статические среды.

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

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

Методы планирования движения • Подходы к дорожной карте • Разложение ячеек • Точное разложение ячеек (трапециевидное) • Приблизительное разложение ячеек (квадродерево) • Потенциальные поля • Гибридные локальные / глобальные

Метод потенциального поля (рабочее поле ) Принцип) — Местоположение цели создает привлекательный потенциал — притягивает робота к цели — Препятствия создают отталкивающий потенциал — отталкивает робота от препятствий — Отрицательный градиент общего потенциала рассматривается как искусственная сила, прикладываемая к робот — пусть сумма сил управляет роботом С-препятствия

Метод потенциального поля • Вычисление силы притяжения к цели С-препятствия Привлекательный потенциал

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

Метод потенциального поля • Вычислить a сила отталкивания от препятствий • Потенциал отталкивания

Метод потенциального поля • Сумма потенциала Потенциал притяжения Потенциал отталкивания C-препятствие Сумма потенциалов