Ця стаття є сирим перекладом з англійської мови Можливо вона створена за допомогою машинного перекладу або перекладачем

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

Наприклад, розглянемо навігацію ^[en], який знаходиться всередині будівлі до віддаленої точки. Слід виконати це завдання, уникаючи стін і падіння зі сходів. Алгоритм планування руху повинен описувати ці завдання як вхідні дані та створювати команди швидкості та повороту, що надсилаються на колеса робота. Алгоритми планування руху можуть звертатися до роботів із більшою кількістю суглобів (наприклад, промислових маніпуляторів), складнішими завданнями (наприклад, маніпулювання предметами), різними обмеженнями (наприклад, автомобілем, який може рухатись лише вперед) та невизначеністю (наприклад, недосконалі моделі оточення робота).

Планування руху має кілька додатків з робототехніки, таких як автономія, автоматизація та дизайн роботів у програмному забезпеченні CAD, а також додатки в інших сферах, такі як анімація^[en], відеоігри, штучний інтелект, ^[en], роботизована хірургія та вивчення біологічних молекул.

Поняття

Простір конфігурації робота точкового розміру. Білий = *C _{вільний}*, сірий = *C _вільн*.

Простір конфігурації для прямокутного робота, що перекладається (на зображенні червоного кольору). Білий = *C _вільн*, сірий = *_Cs*, де темно-сірий = об'єкти, світло-сірий = конфігурації, де робот торкнеться предмета або покине робочу область.

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

Конфігураційний простір

Докладніше: Конфігураційний простір

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

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

Вільний простір

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

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

Цільовий простір

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

Простір перешкод

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

Небезпечний простір

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

Алгоритми

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

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

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

Пошук на основі сітки

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

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

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

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

Інтервальний пошук

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

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

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

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

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

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

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

Геометричні алгоритми

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

^[en]
^[en]

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

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

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

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

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

Алгоритми на основі нагороди

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

Штучні потенційні поля

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

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

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

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

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

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

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

Список помітних алгоритмів

A *
D *
^[en]
^[en]

Повнота та продуктивність

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

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

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

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

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

Для розробки варіантів цієї основної проблеми було розроблено багато алгоритмів.

Диференціальні обмеження

Голономні

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

^[en]

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

Обмеження оптимальності

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

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

Невизначеність

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

Програми

^[en]
Автоматизація
Самокерований автомобіль
Робототехнічна хірургія
Комп'ютерна анімація
Згортання білків
Безпека та доступність в комп'ютерному архітектурному дизайні

Див. також

Блокування обертання — подібний традиційний випуск у машинобудуванні
^[en]
^[en]
^[en] — Бібліотека планування відкритого руху
Пошук шляху
^[en] — багатопланове планування руху
Задача про найкоротший шлях
Взаємозавадна швидкість
Конфігурація (розбиття простору)
Задача про голку

Список літератури

Jahanshahi, Hadi; Jafarzadeh, Mohsen; Najafizadeh Sari, Naeimeh; Viet-Thanh, Pham; Huynh, Van; Nguyen, Xuan (2019). Robot Motion Planning in an Unknown Environment with Danger Space. Electronics. 8 (2): 201. doi:10.3390/electronics8020201.{{}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом ()
Jaulin, L. (2001). Path planning using intervals and graphs (PDF). Reliable Computing. 7 (1).
Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). Counting the Number of Connected Components of a Set and Its Application to Robotics (PDF). Lecture Notes in Computer Science. Т. 3732. с. 93—101. doi:10.1007/11558958_11. ISBN . {{}}: Проігноровано |journal= ()
Fakoor, Mahdi; Kosari, Amirreza; Jafarzadeh, Mohsen (2016). Humanoid robot path planning with fuzzy Markov decision processes. Journal of Applied Research and Technology. 14 (5): 300—310. doi:10.1016/j.jart.2016.06.006.
Fakoor, Mahdi; Kosari, Amirreza; Jafarzadeh, Mohsen (2015). Revision on fuzzy artificial potential field for humanoid robot path planning in unknown environment. International Journal of Advanced Mechatronic Systems. 6 (4): 174—183. doi:10.1504/IJAMECHS.2015.072707.
Wolf, Joerg Christian; Robinson, Paul; Davies, Mansel (2004). Vector Field path planning and control of an autonomous robot in a dynamic environment. Proc. 2004 FIRA Robot World Congress. Busan, South Korea: Paper 151.
Hsu, D.; , J.C.; Motwani, R. (1997). Path planning in expansive configuration spaces. Proceedings of International Conference on Robotics and Automation. Т. 3. с. 2719—2726. doi:10.1109/ROBOT.1997.619371. ISBN .
Shvalb, N.; Ben Moshe, B.; Medina, O. (2013). A real-time motion planning algorithm for a hyper-redundant set of mechanisms. Robotica. 31 (8): 1327—1335. CiteSeerX 10.1.1.473.7966. doi:10.1017/S0263574713000489.
Steven M. LaValle (29 травня 2006). Planning Algorithms. Cambridge University Press. ISBN .

Подальше читання

Latombe, Jean-Claude (2012). Robot Motion Planning. Springer Science & Business Media. ISBN .
Алгоритми планування, Steven M. LaValle, 2006, Cambridge University Press, . .
Принципи руху роботів: теорія, алгоритми та реалізація, H. Choset, W. Burgard, S. Hutchinson, G. Kantor, ^[en], K. Lynch, and S. Thrun, MIT Press, April 2005.
Mark de Berg; Marc van Kreveld; Mark Overmars; Otfried Schwarzkopf (2000). Computational Geometry (вид. 2nd revised). Springer-Verlag. ISBN . Mark de Berg; Marc van Kreveld; Mark Overmars; Otfried Schwarzkopf (2000). Computational Geometry (вид. 2nd revised). Springer-Verlag. ISBN . Глава 13: Планування руху роботів: с. 267—290.

Посилання

«Відкрите віртуальне середовище автоматизації робототехніки», http://openrave.org/
«Бібліотека планування відкритого руху (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
Motion Planning: PRM, RRT, Trajopt — CS287-FA19 Advanced Robotics at UC Berkeley на YouTube

[1] Jahanshahi, Hadi; Jafarzadeh, Mohsen; Najafizadeh Sari, Naeimeh; Viet-Thanh, Pham; Huynh, Van; Nguyen, Xuan (2019). Robot Motion Planning in an Unknown Environment with Danger Space. Electronics. 8 (2): 201. doi:10.3390/electronics8020201.{{}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом ()

[2] Jaulin, L. (2001). Path planning using intervals and graphs (PDF). Reliable Computing. 7 (1).

[3] Delanoue, N.; Jaulin, L.; Cottenceau, B. (2006). Counting the Number of Connected Components of a Set and Its Application to Robotics (PDF). Lecture Notes in Computer Science. Т. 3732. с. 93—101. doi:10.1007/11558958_11. ISBN . {{}}: Проігноровано |journal= ()

[4] Fakoor, Mahdi; Kosari, Amirreza; Jafarzadeh, Mohsen (2016). Humanoid robot path planning with fuzzy Markov decision processes. Journal of Applied Research and Technology. 14 (5): 300—310. doi:10.1016/j.jart.2016.06.006.

[5] Fakoor, Mahdi; Kosari, Amirreza; Jafarzadeh, Mohsen (2015). Revision on fuzzy artificial potential field for humanoid robot path planning in unknown environment. International Journal of Advanced Mechatronic Systems. 6 (4): 174—183. doi:10.1504/IJAMECHS.2015.072707.

[6] Wolf, Joerg Christian; Robinson, Paul; Davies, Mansel (2004). Vector Field path planning and control of an autonomous robot in a dynamic environment. Proc. 2004 FIRA Robot World Congress. Busan, South Korea: Paper 151.

[7] Hsu, D.; , J.C.; Motwani, R. (1997). Path planning in expansive configuration spaces. Proceedings of International Conference on Robotics and Automation. Т. 3. с. 2719—2726. doi:10.1109/ROBOT.1997.619371. ISBN .

[8] Shvalb, N.; Ben Moshe, B.; Medina, O. (2013). A real-time motion planning algorithm for a hyper-redundant set of mechanisms. Robotica. 31 (8): 1327—1335. CiteSeerX 10.1.1.473.7966. doi:10.1017/S0263574713000489.

[LaValle2006-9] Steven M. LaValle (29 травня 2006). Planning Algorithms. Cambridge University Press. ISBN .