Перегляд вихідного коду сторінки Планування руху

{{Сирий переклад|en|дата=січень 2022}}
'''Планування руху''' (також відоме як '''проблема навігації''' або '''проблема''' '''руху піаніно''')&nbsp;— це термін, який використовується в [[Робототехніка|робототехніці]], щоб знайти послідовність дійсних конфігурацій, які переміщують робота від початку до місця призначення.

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

Планування руху має кілька додатків з робототехніки, таких як [[Автономний робот|автономія]], [[автоматизація]] та дизайн роботів у [[Система автоматизованого проектування і розрахунку|програмному забезпеченні CAD]], а також додатки в інших сферах, такі як анімація{{Нп|Цифрові символи|  цифрових символів|en|Character animation|}}, [[Відеогра|відеоігри]], [[штучний інтелект]], {{Нп|Архітектурний дизайн|архітектурний дизайн|en|Architectural design values|}}, [[роботизована хірургія]] та вивчення [[Біомолекули|біологічних молекул]].

== Поняття ==
[[Файл:Motion planning workspace 1.svg|міні| Приклад робочої області.]]
[[Файл:Motion planning workspace 1 configuration space 1.svg|міні| Простір конфігурації робота точкового розміру. Білий = ''C <sub>вільний</sub>'', сірий = ''C <sub>вільн</sub>''.]]
[[Файл:Motion planning workspace 1 configuration space 2.svg|міні| Простір конфігурації для прямокутного робота, що перекладається (на зображенні червоного кольору). Білий = ''C <sub>вільн</sub>'', сірий = ''<sub>Cs</sub>'', де темно-сірий = об'єкти, світло-сірий = конфігурації, де робот торкнеться предмета або покине робочу область. ]]
[[Файл:Motion planning configuration space curved valid path.svg|міні| Приклад дійсного шляху.]]
[[Файл:Motion planning configuration space curved invalid path.svg|міні| Приклад недійсного шляху.]]
[[Файл:Motion planning configuration space road map path.svg|міні| Приклад дорожньої карти.]]
Основна проблема планування руху полягає в створенні безперервного руху, який з'єднує стартову конфігурацію S і цільову конфігурацію G, уникаючи зіткнення з відомими перешкодами. Геометрія робота і перешкод описана в ''робочій області'' 2D або 3D, тоді як рух представлений у вигляді контуру в (можливо, більш розмірному) [[Конфігураційний простір|конфігураційному просторі]].

=== Конфігураційний простір ===
{{Докладніше|Конфігураційний простір}}
Конфігурація описує положення робота, а [[Конфігураційний простір|конфігураційний простір]] C&nbsp;— це набір усіх можливих конфігурацій. Наприклад:

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

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

Часто буває важко чітко обчислити форму С<sub>вільного</sub>. Однак тестування того, чи є дана конфігурація С<sub>вільн</sub>, є ефективним. По-перше, {{Нп|Пряма кінетична анимація|пряма кінематична анімація|en|Forward kinematics|}} визначає положення геометрії робота і тести на [[Виявлення зіткнень|виявлення зіткнень,]] якщо геометрія робота стикається з геометрією середовища.

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

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

=== Небезпечний простір ===
Небезпечний простір&nbsp;— це простір, до якого робот може рухатися, але це не бажано. Небезпечний простір&nbsp;— це ані перешкода, ані вільний простір. Наприклад, грязьові ями в лісистій місцевості та жирна підлога на заводі може вважатися небезпечним простором. Якщо робот не може знайти траєкторію, яка повністю належить до вільного простору, він повинен пройти через небезпечний простір. У деяких випадках при плануванні руху з обмеженням часу / енергії робот може вважати за краще пройти коротку траєкторію в небезпечному просторі, а не довгий шлях у вільному просторі.<ref>{{Cite journal|last=Jahanshahi|first=Hadi|last2=Jafarzadeh|first2=Mohsen|last3=Najafizadeh Sari|first3=Naeimeh|last4=Viet-Thanh|first4=Pham|last5=Huynh|first5=Van|last6=Nguyen|first6=Xuan|date=2019|title=Robot Motion Planning in an Unknown Environment with Danger Space|journal=Electronics|volume=8|issue=2|pages=201|doi=10.3390/electronics8020201}}</ref>

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

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

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

=== Пошук на основі сітки ===
Підходи на основі сітки накладають сітку на [[конфігураційний простір]] і припускають, що кожна конфігурація ототожнюється з точкою сітки. У кожній точці сітки роботу дозволяється переміщуватися до сусідніх точок сітки до тих пір, поки лінія між ними повністю міститься в межах C<sub>вільн</sub> (це перевіряється при виявленні зіткнень). Це дискретизує набір дій, і [[Алгоритм пошуку|алгоритми пошуку]] (як [[Алгоритм пошуку A*|A *]]) використовуються для пошуку шляху від початку до мети.

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

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

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

=== Інтервальний пошук ===
Ці підходи схожі з підходами пошуку на основі сітки, за винятком того, що вони генерують замощення, повністю покриваючи конфігураційний простір замість сітки.<ref>{{Cite journal|last=Jaulin|first=L.|year=2001|title=Path planning using intervals and graphs|url=http://www.ensta-bretagne.fr/jaulin/paper_cameleon.pdf|journal=Reliable Computing|volume=7|issue=1}}</ref> Бруківка розкладається на дві {{Нп|Підбруківка|підбруківки||Subpaving}} X <sup>-</sup>, X <sup>+,</sup> виготовлені з ящиків таким чином, що X<sup>−</sup> ⊂ C<sub>вільн</sub> ⊂ X<sup>+</sup>. Характеризація сум C<sub>вільн</sub> для вирішення заданої інверсії. Таким чином, [[Інтервальна арифметика|інтервальний аналіз]] може бути використаний, коли C<sub>вільн</sub> не може бути описаний лінійними нерівностями для того, щоб мати гарантований корпус.

Таким чином, роботу дозволяється вільно рухатися в X <sup>-</sup> і не можна виходити за межі X <sup>+</sup>. На обох підбруківках будується сусідній графік, і шляхи можна знайти за допомогою таких алгоритмів як [[Алгоритм Дейкстри]] або [[Алгоритм пошуку A*|A *]]. Коли шлях можливий у X <sup>-</sup>, він також можливий у C<sub>вільн</sub> . Коли в X <sup>+</sup> від однієї початкової конфігурації до цілі немає шляху, ми маємо гарантію, що у C<sub>вільн</sub> немає жодного підхожого шляху. Що стосується підходу на основі сітки, то інтервальний підхід недоцільний для задач з великими розмірами, через те, що кількість скриньок, які потрібно створити, експоненціально зростає відносно розмірності конфігураційного простору.

Ілюстрацію подають три фігури праворуч, де гачок з двома ступенями свободи повинен рухатися зліва направо, уникаючи двох маленьких горизонтальних сегментів.
[[Файл:Graph2displaycolor.jpg|міні| Рух від початкової конфігурації (синій) до кінцевої конфігурації гака, уникаючи двох перешкод (червоних сегментів). Лівий нижній кут гака повинен залишатися на горизонтальній лінії, що робить гачок двома ступенями свободи.]]
[[Файл:Graph1sivia.jpg|міні| Декомпозиція з полями, що охоплюють конфігураційний простір: Піддоріжка X <sup>-</sup> це об'єднання всіх червоних полів, а підпокриття X <sup>+</sup>&nbsp;— об'єднання червоних та зелених полів. Шлях відповідає руху, представленому вище.]]
[[Файл:Graph3cameleon.jpg|міні| Цей показник відповідає тому ж шляху, що і вище, але отриманий із значно меншою кількістю коробок. Алгоритм дозволяє уникнути розбиття коробок у частинах конфігураційного простору, які не впливають на кінцевий результат. ]]
Розкладання за допомогою підкладок за допомогою інтервального аналізу також дає змогу схарактеризувати топологію C<sub>вільн</sub> , наприклад підрахунок його кількості з'єднаних компонентів.<ref>{{Cite book|url=http://www.ensta-bretagne.fr/jaulin/delanoueCounting.pdf|title=Counting the Number of Connected Components of a Set and Its Application to Robotics|last=Delanoue|first=N.|last2=Jaulin|first2=L.|last3=Cottenceau|first3=B.|year=2006|series=Lecture Notes in Computer Science|volume=3732|pages=93–101|doi=10.1007/11558958_11|isbn=978-3-540-29067-4|journal=Applied Parallel Computing, Lecture Notes in Computer Science}}</ref>

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

* {{Нп|Граф видимості|Граф видимості|en|Visibility graph|}}
* {{Нп|Розпад клітин|Розпад клітин|en|Boustrophedon cell decomposition|}}

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

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

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

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

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

=== Алгоритми на основі нагороди ===
Алгоритми, засновані на нагородах, передбачають, що робот у кожному стані (положення та внутрішній стан, включаючи напрямок) може обирати різні дії (рух). Однак результат кожної дії не визначений. Іншими словами, результати (переміщення) частково випадкові та частково під контролем робота. Робот отримує позитивну винагороду, коли досягає мети і отримує негативну винагороду, якщо стикається з перешкодою. Ці алгоритми намагаються знайти шлях, який максимально накопичує майбутні винагороди.[[Марковський процес вирішування]] (MDP)&nbsp;— це популярна математична основа, яка використовується у багатьох алгоритмах, заснованих на нагородах. Перевага MDP в порівнянні з іншими алгоритмами на основі винагороди полягає в тому, що вони генерують оптимальний шлях. Недоліком MDP є те, що вони обмежують робота у виборі з обмеженого набору дій. Тому шлях не є рівним (подібний до підходів на основі сітки). Процеси прийняття нечітких рішень Маркова (FDMP)&nbsp;— це розширення MDP, які генерують плавний шлях за допомогою нечіткої системи висновку.<ref>{{Cite journal|last=Fakoor|first=Mahdi|last2=Kosari|first2=Amirreza|last3=Jafarzadeh|first3=Mohsen|date=2016|title=Humanoid robot path planning with fuzzy Markov decision processes|journal=Journal of Applied Research and Technology|volume=14|issue=5|pages=300–310|doi=10.1016/j.jart.2016.06.006}}</ref>

=== Штучні потенційні поля ===
Один із підходів&nbsp;— трактувати конфігурацію робота як точку в потенційному полі, що поєднує в собі притягнення до мети та відштовхування від перешкод. Отримана траєкторія виводиться як шлях. Цей підхід має переваги тим, що траєкторія виробляється з невеликим обчисленням. Однак вони можуть потрапити в [[Екстремум|екстремуми]] потенційного поля і не в змозі знайти шлях, або можуть знайти неоптимальний шлях. Поля штучного потенціалу можна розглядати як рівняння континууму, подібні до полів електростатичного потенціалу (трактуючи робота як точковий заряд), або рух через поле можна дискретизувати, використовуючи набір лінгвістичних правил.<ref>{{Cite journal|last=Fakoor|first=Mahdi|last2=Kosari|first2=Amirreza|last3=Jafarzadeh|first3=Mohsen|date=2015|title=Revision on fuzzy artificial potential field for humanoid robot path planning in unknown environment|journal=International Journal of Advanced Mechatronic Systems|volume=6|issue=4|pages=174–183|doi=10.1504/IJAMECHS.2015.072707}}</ref><ref>{{Cite journal|last=Wolf|first=Joerg Christian|last2=Robinson|first2=Paul|last3=Davies|first3=Mansel|date=2004|title=Vector Field path planning and control of an autonomous robot in a dynamic environment|journal=Proc. 2004 FIRA Robot World Congress|location=Busan, South Korea|page=Paper 151}}</ref>

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

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

Зазначені основні умови ''видимості'' на C<sub>вільн</sub><sub>,</sub> як було доведено, бо, оскільки число конфігурацій N зростає вище, ймовірність того, що вище алгоритм знаходить рішення наближається до 1 в геометричній прогресії.<ref>{{Cite book|title=Proceedings of International Conference on Robotics and Automation|last=Hsu|first=D.|last2=[[Jean-Claude Latombe|J.C. Latombe]]|first2=J.C.|last3=Motwani|first3=R.|year=1997|volume=3|pages=2719–2726|chapter=Path planning in expansive configuration spaces|doi=10.1109/ROBOT.1997.619371|isbn=978-0-7803-3612-4}}</ref> Видимість прямо не залежить від розмірності С; можлива наявність просторового простору з «хорошою» видимістю або низько мірного простору з «поганою» видимістю. Експериментальний успіх методів на основі вибірки свідчить про те, що найбільш часто видимі простори мають хорошу видимість.

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

* Зазвичай набагато швидше випробовувати лише сегменти між сусідніми віхами, а не всіма парами.
* Неоднорідні розподіли вибірки намагаються розмістити більше віх у районах, що покращують сполучуваність дорожньої карти.
* [[Послідовність із низькою розбіжністю|Квазірандомні вибірки]], як правило, краще покривають простір конфігурації, ніж {{Нп|Pseudorandomness|псевдовипадкові|en|}}, хоча деякі останні роботи стверджують, що ефект джерела випадковості мінімальний порівняно з ефектом розподілу вибірки.
* Можна істотно зменшити кількість віх, необхідних для розв'язання заданої проблеми, дозволяючи викривленим прицілом очей (наприклад, повзанням на перешкодах, що перегороджують шлях між двома етапами<ref>{{Cite journal|last=Shvalb|first=N.|last2=Ben Moshe|first2=B.|last3=Medina|first3=O.|year=2013|title=A real-time motion planning algorithm for a hyper-redundant set of mechanisms.|journal=Robotica|volume=31|issue=8|pages=1327–1335|citeseerx=10.1.1.473.7966|doi=10.1017/S0263574713000489}}</ref>).
* Якщо потрібно лише один або кілька запитів планування, не завжди потрібно будувати дорожню карту всього простору. Варіанти побудови дерев зазвичай є швидшими для цього випадку (планування одного запиту). Дорожні карти все ще корисні, якщо потрібно робити багато запитів на одному просторі (планування багатьох запитів).

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

* [[Алгоритм пошуку A*|A *]]
* [[Алгоритм пошуку D*|D *]]
* {{Нп|Швидке вивчення випадкового дерева|Швидке вивчення випадкового дерева|en|Rapidly-exploring random tree|}}
* {{Нп|Імовірнісна дорожня|Імовірнісна дорожня карта|en|Probabilistic roadmap|}}

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

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

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

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

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

=== Диференціальні обмеження ===
[[Ступені вільності (механіка)|Голономні]]

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

{{Нп|Неголономна система|Неголономні|en|Nonholonomic system}}

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

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

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

* [[Робототехніка|Роботизовані маніпуляції]]
* {{Нп|Проектування для сбірки|Механічна збірка|en|Design for assembly|}}
* Локомоція робочої ноги
* [[Реконфігурувані роботи]]

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

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

== Програми ==

* {{Нп|Навігація роботів|Навігація роботів|en|Robot navigation|}}
* [[Автоматизація]]
* [[Самокерований автомобіль]]
* [[Роботизована хірургія|Робототехнічна хірургія]]
* [[Комп'ютерна анімація]]
* [[Згортання білків]]<ref name="LaValle2006">{{Cite book|url=https://books.google.com/?id=-PwLBAAAQBAJ&printsec=frontcover&dq=%22protein+folding%22+%22motion+planning%22#v=onepage&q=%22protein%20folding%22&f=false|title=Planning Algorithms|last=Steven M. LaValle|date=29 травня 2006|publisher=Cambridge University Press|isbn=978-1-139-45517-6}}</ref>
* Безпека та доступність в комп'ютерному архітектурному дизайні

== Див. також ==

* [[Блокування обертання]]&nbsp;— подібний традиційний випуск у машинобудуванні
* {{Нп|Кінодинамічне планування|Кінодинамічне планування|en|Kinodynamic planning|}}
* {{Нп|Проблема альпінізму|Проблема альпінізму|en|Mountain climbing problem|}}
* {{Нп|OMPL|OMPL|en|}}&nbsp;— Бібліотека планування відкритого руху
* [[Пошук шляху]]
* {{Нп|Проблеми з гальковим рухом|Проблеми з гальковим рухом|en|Pebble motion problems|}}&nbsp;— багатопланове планування руху
* [[Задача про найкоротший шлях]]
* [[Взаємозавадна швидкість]]
* [[Конфігурація (розбиття простору)]]
* [[Задача про голку]]

== Список літератури ==
{{Reflist}}

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

* {{Cite book|url=https://books.google.com/books?id=nQ7aBwAAQBAJ|title=Robot Motion Planning|last=Latombe|first=Jean-Claude|year=2012|publisher=Springer Science & Business Media|isbn=978-1-4615-4022-9}} <bdi> </bdi>
* ''[http://planning.cs.uiuc.edu/ Алгоритми планування]'', Steven M. LaValle, 2006, Cambridge University Press, {{ISBN|0-521-86205-1}}. {{ISBN|0-521-86205-1}} .
* ''[https://books.google.com/books?id=S3biKR21i-QC Принципи руху роботів: теорія, алгоритми та реалізація]'', H. Choset, W. Burgard, S. Hutchinson, G. Kantor, {{iw|Лідія Кавракі|L. E. Kavraki|en|Lydia Kavraki}}, K. Lynch, and S. Thrun, MIT Press, April 2005.
* {{Cite book|url=https://archive.org/details/computationalgeo00berg|title=Computational Geometry|last=Mark de Berg|last2=Marc van Kreveld|last3=Mark Overmars|last4=Otfried Schwarzkopf|year=2000|publisher=[[Springer-Verlag]]|edition=2nd revised|isbn=978-3-540-65620-3}} {{Cite book|url=https://archive.org/details/computationalgeo00berg|title=Computational Geometry|last=Mark de Berg|last2=Marc van Kreveld|last3=Mark Overmars|last4=Otfried Schwarzkopf|year=2000|publisher=[[Springer-Verlag]]|edition=2nd revised|isbn=978-3-540-65620-3}} <bdi> </bdi> Глава 13: Планування руху роботів: с. &nbsp; 267—290.

== Посилання ==

* «Відкрите віртуальне середовище автоматизації робототехніки», http://openrave.org/ 
* [https://web.archive.org/web/20070929091715/http://www.researchchannel.org/prog/displayevent.aspx?rID=2132&fID=567 Жан-Клод Латомб розповідає про свою роботу з роботами та плануванням руху, 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 
* {{YouTube|ZDuoQRutcfk|Motion Planning: PRM, RRT, Trajopt&nbsp;— CS287-FA19 Advanced Robotics at UC Berkeley}}

[[Категорія:Автоматизоване планування та диспетчеризація]]
[[Категорія:Теоретична інформатика]]
[[Категорія:Сторінки з неперевіреними перекладами]]