Планування руху

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

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

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

Часто буває важко чітко обчислити форму С_{вільного}. Однак тестування того, чи є дана конфігурація С_вільн, є ефективним. По-перше, пряма кінематична анімація визначає положення геометрії робота і тести на виявлення зіткнень, якщо геометрія робота стикається з геометрією середовища.

Простір — це лінійний підпростір вільного простору, який позначає, куди ми хочемо перемістити робота. У глобальному плануванні руху простір сприймається за допомогою датчиків роботів. Однак при локальному плануванні руху робот не може сприймати простір у деяких станах. Щоб розв'язати цю проблему, робот проходить через кілька віртуальних просторів, кожен з яких розташований у зоні спостереження (навколо робота). Віртуальний цільовий простір називається підціллю.

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

Небезпечний простір — це простір, до якого робот може рухатися, але це не бажано. Небезпечний простір — це ані перешкода, ані вільний простір. Наприклад, грязьові ями в лісистій місцевості та жирна підлога на заводі може вважатися небезпечним простором. Якщо робот не може знайти траєкторію, яка повністю належить до вільного простору, він повинен пройти через небезпечний простір. У деяких випадках при плануванні руху з обмеженням часу / енергії робот може вважати за краще пройти коротку траєкторію в небезпечному просторі, а не довгий шлях у вільному просторі.[1]

Підходи на основі сітки накладають сітку на конфігураційний простір і припускають, що кожна конфігурація ототожнюється з точкою сітки. У кожній точці сітки роботу дозволяється переміщуватися до сусідніх точок сітки до тих пір, поки лінія між ними повністю міститься в межах C_вільн (це перевіряється при виявленні зіткнень). Це дискретизує набір дій, і алгоритми пошуку (як A *) використовуються для пошуку шляху від початку до мети.

Ці підходи потребують встановлення роздільної здатності сітки. Можливо застосувати швидший пошук за допомогою більш грубої сітки, але алгоритм у цьому разі не зможе знайти шляхи через вузькі ділянки C_вільн. Крім того, кількість точок на сітці зростає експоненційно в розмірі конфігураційного простору, що робить їх неприйнятними для задач з високими розмірами.

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

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

Ці підходи схожі з підходами пошуку на основі сітки, за винятком того, що вони генерують замощення, повністю покриваючи конфігураційний простір замість сітки.[2] Бруківка розкладається на дві підбруківки X ^-, X ^+, виготовлені з ящиків таким чином, що X⁻ ⊂ C_вільн ⊂ X⁺. Характеризація сум C_вільн для вирішення заданої інверсії. Таким чином, інтервальний аналіз може бути використаний, коли C_вільн не може бути описаний лінійними нерівностями для того, щоб мати гарантований корпус.

Таким чином, роботу дозволяється вільно рухатися в X ^- і не можна виходити за межі X ⁺. На обох підбруківках будується сусідній графік, і шляхи можна знайти за допомогою таких алгоритмів як Алгоритм Дейкстри або A *. Коли шлях можливий у X ^-, він також можливий у C_вільн . Коли в X ⁺ від однієї початкової конфігурації до цілі немає шляху, ми маємо гарантію, що у C_вільн немає жодного підхожого шляху. Що стосується підходу на основі сітки, то інтервальний підхід недоцільний для задач з великими розмірами, через те, що кількість скриньок, які потрібно створити, експоненціально зростає відносно розмірності конфігураційного простору.

Ілюстрацію подають три фігури праворуч, де гачок з двома ступенями свободи повинен рухатися зліва направо, уникаючи двох маленьких горизонтальних сегментів.

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

Декомпозиція з полями, що охоплюють конфігураційний простір: Піддоріжка X ^- це об'єднання всіх червоних полів, а підпокриття X ⁺ — об'єднання червоних та зелених полів. Шлях відповідає руху, представленому вище.

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

Розкладання за допомогою підкладок за допомогою інтервального аналізу також дає змогу схарактеризувати топологію C_вільн , наприклад підрахунок його кількості з'єднаних компонентів.[3]

Ведення роботів серед полігональних перешкод

• Граф видимості
• Розпад клітин

Переміщування предметів серед перешкод

• Сума Мінковського

Пошук виходу з будівлі

• найдальший променевий слід

Враховуючи пучок променів навколо поточної позиції, який пояснюється їх довжиною, що вдаряється об стіну, робот рухається в напрямку найдовшого променя, якщо не буде встановлено двері. Такий алгоритм був використаний для моделювання аварійного виходу з будівель.

Алгоритми, засновані на нагородах, передбачають, що робот у кожному стані (положення та внутрішній стан, включаючи напрямок) може обирати різні дії (рух). Однак результат кожної дії не визначений. Іншими словами, результати (переміщення) частково випадкові та частково під контролем робота. Робот отримує позитивну винагороду, коли досягає мети і отримує негативну винагороду, якщо стикається з перешкодою. Ці алгоритми намагаються знайти шлях, який максимально накопичує майбутні винагороди.Марковський процес вирішування (MDP) — це популярна математична основа, яка використовується у багатьох алгоритмах, заснованих на нагородах. Перевага MDP в порівнянні з іншими алгоритмами на основі винагороди полягає в тому, що вони генерують оптимальний шлях. Недоліком MDP є те, що вони обмежують робота у виборі з обмеженого набору дій. Тому шлях не є рівним (подібний до підходів на основі сітки). Процеси прийняття нечітких рішень Маркова (FDMP) — це розширення MDP, які генерують плавний шлях за допомогою нечіткої системи висновку.[4]

Один із підходів — трактувати конфігурацію робота як точку в потенційному полі, що поєднує в собі притягнення до мети та відштовхування від перешкод. Отримана траєкторія виводиться як шлях. Цей підхід має переваги тим, що траєкторія виробляється з невеликим обчисленням. Однак вони можуть потрапити в екстремуми потенційного поля і не в змозі знайти шлях, або можуть знайти неоптимальний шлях. Поля штучного потенціалу можна розглядати як рівняння континууму, подібні до полів електростатичного потенціалу (трактуючи робота як точковий заряд), або рух через поле можна дискретизувати, використовуючи набір лінгвістичних правил.[5][6]

Алгоритми на основі вибірки представляє простір конфігурації з дорожньою картою вибіркових конфігурацій. Основний алгоритм вибірки N конфігурацій в C, і зберігає такі, що знаходяться C_вільн для використання в якості етапів . Дорожня карта потім побудована, яка з'єднує дві віхи Р і Q, якщо PQ відрізок повністю належить C_вільн. Знову ж таки, виявлення зіткнення використовується для перевірки включення до C_вільн. Щоб знайти шлях, який з'єднує S і G, вони додаються до дорожньої карти. Якщо шлях у дорожній карті пов'язує S і G, планувальник вдається і повертає цей шлях. Якщо ні, то причина не остаточна: або немає шляху в C_вільн, або планувальник не пробив достатню кількість етапів.

Ці алгоритми добре працюють для просторів конфігурації великих розмірів, оскільки на відміну від комбінаторних алгоритмів, їх час роботи не (явно) експоненціально залежить від розмірності С. Вони також (як правило) суттєво простіші в реалізації. Вони ймовірнісно завершені, тобто ймовірність того, що вони вироблять рішення, наближається до 1, оскільки буде витрачено більше часу. Однак вони не можуть визначити, чи існує рішення.

Зазначені основні умови видимості на C_вільн, як було доведено, бо, оскільки число конфігурацій N зростає вище, ймовірність того, що вище алгоритм знаходить рішення наближається до 1 в геометричній прогресії.[7] Видимість прямо не залежить від розмірності С; можлива наявність просторового простору з «хорошою» видимістю або низько мірного простору з «поганою» видимістю. Експериментальний успіх методів на основі вибірки свідчить про те, що найбільш часто видимі простори мають хорошу видимість.

Існує багато варіантів цієї основної схеми:

• Зазвичай набагато швидше випробовувати лише сегменти між сусідніми віхами, а не всіма парами.
• Неоднорідні розподіли вибірки намагаються розмістити більше віх у районах, що покращують сполучуваність дорожньої карти.
• Квазірандомні вибірки, як правило, краще покривають простір конфігурації, ніж псевдовипадкові, хоча деякі останні роботи стверджують, що ефект джерела випадковості мінімальний порівняно з ефектом розподілу вибірки.
• Можна істотно зменшити кількість віх, необхідних для розв'язання заданої проблеми, дозволяючи викривленим прицілом очей (наприклад, повзанням на перешкодах, що перегороджують шлях між двома етапами[8]).
• Якщо потрібно лише один або кілька запитів планування, не завжди потрібно будувати дорожню карту всього простору. Варіанти побудови дерев зазвичай є швидшими для цього випадку (планування одного запиту). Дорожні карти все ще корисні, якщо потрібно робити багато запитів на одному просторі (планування багатьох запитів).

• A *
• D *
• Швидке вивчення випадкового дерева
• Імовірнісна дорожня карта

Голономні

• Руки маніпулятора (з динамікою)

Неголономні

• Автомобілі
• Одноколісні велосипеди
• Літаки
• Системи, обмежені прискоренням
• Переміщення перешкод (час не може йти назад)
• Голка, що керується скошеним накінечником
• Роботи з диференціальним приводом

Гібридні системи - це ті, що поєднують дискретну та безперервну поведінку. Прикладами таких систем є:

• Роботизовані маніпуляції
• Механічна збірка
• Локомоція робочої ноги
• Реконфігурувані роботи

• Невизначеність руху
• Відсутня інформація
• Активне зондування
• Безсенсорне планування