Robot Path Planning - Історія редагувань

111 в 21:03, 18 лютого 2018

2018-02-18T21:03:10Z

111 в 21:01, 18 лютого 2018

2018-02-18T21:01:16Z

111 в 17:05, 18 лютого 2018

2018-02-18T17:05:49Z

111 в 16:08, 18 лютого 2018

2018-02-18T16:08:33Z

111 в 15:58, 18 лютого 2018

2018-02-18T15:58:45Z

111 в 14:55, 18 лютого 2018

2018-02-18T14:55:28Z

Показати зміни

111 в 14:38, 18 лютого 2018

2018-02-18T14:38:25Z

111 в 14:36, 18 лютого 2018

2018-02-18T14:36:52Z

111 в 14:32, 18 лютого 2018

2018-02-18T14:32:39Z

111 в 14:31, 18 лютого 2018

2018-02-18T14:31:58Z

← Попередня версія		Версія за 21:03, 18 лютого 2018
Рядок 81:		Рядок 81:


−	~~'''~~Виконав [[Цимбаленко Денис\|Цимбаленко Денис]]~~''' 18 лютого 2018~~	+	Виконав: [[Цимбаленко Денис\|Цимбаленко Денис]]

@@ Рядок 64: / Рядок 64: @@
 Рандомізований підхід використовується для зменшення значної кількості досліджуваних станів під час пошуку. Цей підхід здатний легко обробляти ситуації, коли пошук стає неможливим через збільшенням простору станів та надто багатьох досліджених станів. '''Rapidly-Exploring Random Tree(RRT)''' - це рандомізований алгоритм вибірки. Механізм цього [[Алгоритм|алгоритму]] для пошуку створює та розширюється за межі випадкового дерева з початкового стану.
-Хоча розширення дерева відбувається випадковим чином, нерозвідані регіони мають більше значення, ніж інші регіони, і [[Алгоритм|алгоритм]] пошуку упереджений до них. '''RRT''' є одним з найвідоміших алгоритмів рандомізованих вибірок в роботизованому співтоваристві і цей [[Алгоритм|алгоритм]] використовується в різних платформах робототехніки.'''RRT''' не може гарантувати виконання в реальному часі, і це продемонструвало найкраще рішення, яке вивчається даним [[Алгоритм|алгоритмом]], майже завжди є не оптимальним рішенням. Крім того, '''RRT''' не враховує витрати на розширення дерева; тому оснований шлях може бути розміщений у дорогих областях.Остання версія '''RRT''' - '''ERRT'''. Під час кожної ітерації пошуку '''ERRT''' записує деяку інформацію та використовує записану інформацію з попередньої ітерацій, щоб знайти кращий шлях. Алгоритм The '''Metric Adaptive RRT (MA-RRT)''' є модифікованою версією '''RRT'''. Цей [[Алгоритм|алгоритм]] звертається до проблем '''RRT'''. '''MA-RRT''', як і '''ERRT''' використовує інформацію про попередню ітерацію та за допомогою попередньої інформації, '''MA-RRT''' здатний керувати пошуком (дерева) у напрямках, де містяться кращі та найближчі оптимальні шляхи. '''RRT*''' має інший підхід до розширення дерева. За даними '''RRT*''', дерево росте випадково через одну вершину. Також '''RRT*''' спочатку виростає дерево з однієї вершини і оцінює це розширення, і якщо розширення з цієї вершини вважається успішним, тоді RRT* прагне одночасно досліджувати і ростити дерево від усіх інших вершин де їх відстані до запропонованої вершини не перевищує певного порогу.Хоча цей [[Алгоритм|алгоритм]] знаходить краще рішення, ніж '''RRT''', особливо якщо час пошуку збільшується, він має високу обчислювальну вартість.
+Хоча розширення дерева відбувається випадковим чином, нерозвідані регіони мають більше значення, ніж інші регіони, і [[Алгоритм|алгоритм]] пошуку упереджений до них. '''RRT''' є одним з найвідоміших алгоритмів рандомізованих вибірок в роботизованому співтоваристві і цей [[Алгоритм|алгоритм]] використовується в різних платформах робототехніки.'''RRT''' не може гарантувати виконання в реальному часі, і це продемонструвало найкраще рішення, яке вивчається даним [[Алгоритм|алгоритмом]], майже завжди є не оптимальним рішенням. Крім того, '''RRT''' не враховує витрати на розширення дерева; тому оснований шлях може бути розміщений у дорогих областях.Остання версія '''RRT''' - '''ERRT'''. Під час кожної ітерації пошуку '''ERRT''' записує деяку інформацію та використовує записану інформацію з попередньої ітерацій, щоб знайти кращий шлях. Алгоритм The '''Metric Adaptive RRT (MA-RRT)''' є модифікованою версією '''RRT'''. Цей [[Алгоритм|алгоритм]] звертається до проблем '''RRT'''. '''MA-RRT''', як і '''ERRT''' використовує інформацію про попередню ітерацію та за допомогою попередньої інформації, '''MA-RRT''' здатний керувати пошуком (дерева) у напрямках, де містяться кращі та найближчі оптимальні шляхи. '''RRT*''' має інший підхід до розширення дерева. За даними '''RRT*''', [[Дерево|дерево]] росте випадково через одну вершину. Також '''RRT*''' спочатку виростає [[Дерево|дерево]] з однієї вершини і оцінює це розширення, і якщо розширення з цієї вершини вважається успішним, тоді RRT* прагне одночасно досліджувати і ростити [[Дерево|дерево]] від усіх інших вершин де їх відстані до запропонованої вершини не перевищує певного порогу.Хоча цей [[Алгоритм|алгоритм]] знаходить краще рішення, ніж '''RRT''', особливо якщо час пошуку збільшується, він має високу обчислювальну вартість.
 === '''Reactive methods''' ===

@@ Рядок 15: / Рядок 15: @@
 === '''Heuristic methods''' ===
-Евристичні методи розглядаються багатьма дослідниками і значною мірою проводяться багатьма дослідженнями. Проста ідея для знаходження шляху є застосування базового [[Алгоритм|алгоритму]] пошуку з рівномірною вартістю. Хоча цей метод пошуку є повним і оптимальним, він розширює багато вузлів, які недуже близькі до шляху розв'язку. Евристична функція - це альтернативний метод, який дозволяє оцінити найменш витратний маршрут від будь-якого вузла в пошуковому просторі до цілі. Евристична функція розроблена на основі проблем обмежень. Крім того, евристична функція спрямовує пошук до мети, не розширюючи багатьох вузлів, відвіданих найменш витратним пошуком. Тому евристична функція здатна скоротити час пошуку та використовуватися як [[Алгоритм|алгоритм]] пошук в реальному часі. Ця категорія поділяється на три класи; а саме - евристичні(Heuristic), неавтономні(On-Line) та автономні(Off-Line). Неавтономні методи поділяються на евристичний пошук в реальному часі(Real-Time Heuristic) та класи [[Алгоритм|алгоритмів]] будь-якого часу(Any-Time).
+Евристичні методи розглядаються багатьма дослідниками і значною мірою проводяться багатьма дослідженнями. Проста ідея для знаходження шляху є застосування базового [[Алгоритм|алгоритму]] пошуку з рівномірною вартістю. Хоча цей метод пошуку є повним і оптимальним, він розширює багато вузлів, які недуже близькі до шляху розв'язку. Евристична функція - це альтернативний метод, який дозволяє оцінити найменш витратний маршрут від будь-якого вузла в пошуковому просторі до цілі. Евристична функція розроблена на основі проблем обмежень. Крім того, евристична функція спрямовує пошук до мети, не розширюючи багатьох вузлів, відвіданих найменш витратним пошуком. Тому евристична функція здатна скоротити час пошуку та використовуватися як [[Алгоритм|алгоритм]] пошук в реальному часі. Ця категорія поділяється на три класи; а саме - евристичні(Heuristic), неавтономні([[Онлайн|On-Line]]) та автономні([[Офлайн|Off-Line]]). Неавтономні методи поділяються на евристичний пошук в реальному часі(Real-Time Heuristic) та класи [[Алгоритм|алгоритмів]] будь-якого часу(Any-Time).
 ==== Heuristic ====

← Попередня версія		Версія за 16:08, 18 лютого 2018
Рядок 81:		Рядок 81:


−	'''Виконав Цимбаленко Денис''' 18 лютого 2018	+	'''Виконав [[Цимбаленко Денис\|Цимбаленко Денис]]''' 18 лютого 2018

@@ Рядок 2: / Рядок 2: @@
 == Введення ==
-'''Robot Path Planning (RPP)''' у динамічних середовищах - це проблема пошуку, заснована на вивченні шляхів без зіткнень за наявності динамічних та статичних перешкод. Багато методів були розроблені, щоб вирішити цю проблему. Пастки в локальних мінімумах і підтримка продуктивності в режимі реального часу відомі, як дві найбільш важливі проблеми, з якими стикаються ці методи. '''RPP''' планує поведінку робота, щоб він міг виконувати завдання. Отже, якщо поточний стан робота вважається початковим станом і станом робота після завершення завдання як кінцевий стан, RPP повинен планувати пошук можливого шляху і через цей шлях; робот зможе досягти кінцевого стану.
+'''Robot Path Planning (RPP)''' у динамічних середовищах - це проблема пошуку, заснована на вивченні шляхів без зіткнень за наявності динамічних та статичних перешкод. Багато [[Метод|методів]] були розроблені, щоб вирішити цю проблему. Пастки в локальних мінімумах і підтримка продуктивності в режимі реального часу відомі, як дві найбільш важливі проблеми, з якими стикаються ці [[Метод|методи]]. '''RPP''' планує поведінку робота, щоб він міг виконувати завдання. Отже, якщо поточний стан робота вважається початковим станом і станом робота після завершення завдання як кінцевий стан, RPP повинен планувати пошук можливого шляху і через цей шлях; робот зможе досягти кінцевого стану.
 '''RPP''' вивчається в різних середовищах, таких як статичне середовище,статичне середовище містить рухливі перешкоди, динамічне середовище містить статичні та динамічні перешкоди.  У цих середовищах шлях динамічних перешкод невідомий і відомий як найважча проблема пошуку в порівнянні з іншими середовищами. У динамічних середовищах автономні роботи повинні надійно переміщатися між динамічними і статичними перешкодами. У динамічних середовищах було запропоновано дві проблеми, що стоять перед '''RPP'''. Це пастки в локальних мінімумах та підтримання ефективності в реальному часі.
 == Прикладні алгоритми для вирішення проблем планування шляху ==
-Декілька підходів використовуються для вирішення проблеми планування маршуту в динамічному середовищі,які зображені на малюнку 3.1. Дивлячись на це зображення, методи та [[Алгоритм|алгоритми]] поділяються на 3 категорії: Евристичні методи(Heuristic methods), Випадково вибіркові методи(Randomized Sampling methods) та Реактивний методи(Reactive methods).
+Декілька підходів використовуються для вирішення проблеми планування маршруту в динамічному середовищі,які зображені на малюнку 3.1. Дивлячись на це зображення, [[Метод|методи]] та [[Алгоритм|алгоритми]] поділяються на 3 категорії: Евристичні методи(Heuristic methods), Випадково вибіркові методи(Randomized Sampling methods) та Реактивний методи(Reactive methods).
 [[Файл:3.1.png]]

← Попередня версія		Версія за 14:38, 18 лютого 2018
Рядок 75:		Рядок 75:
	Показано, що деякі алгоритми, такі як інкрементний евристичний пошук та алгоритми евристичного пошуку в режимі реального часу в цій галузі, є більш корисними і тому мають більш широкі можливості для проведення деяких досліджень про них. Крім того, ці алгоритми мають більш високу продуктивність в порівнянні з іншими алгоритмами, що стоять перед зазначеними проблемами. З іншого боку, здається, що кожен підхід, особливо реактивний метод, страждають від багатьох недоліків.		Показано, що деякі алгоритми, такі як інкрементний евристичний пошук та алгоритми евристичного пошуку в режимі реального часу в цій галузі, є більш корисними і тому мають більш широкі можливості для проведення деяких досліджень про них. Крім того, ці алгоритми мають більш високу продуктивність в порівнянні з іншими алгоритмами, що стоять перед зазначеними проблемами. З іншого боку, здається, що кожен підхід, особливо реактивний метод, страждають від багатьох недоліків.

−	[[Файл:Rpp.png]]	+	[[Файл:Rpp.png\|500px\|thumb\|center\|\|Таблиця: Порівняння Розглянутих Підходів В Галузі '''RPP''' В Динамічних Середовищах На Основі Часу Пошуку Та Середньої Вартості]]

← Попередня версія		Версія за 14:36, 18 лютого 2018
Рядок 75:		Рядок 75:
	Показано, що деякі алгоритми, такі як інкрементний евристичний пошук та алгоритми евристичного пошуку в режимі реального часу в цій галузі, є більш корисними і тому мають більш широкі можливості для проведення деяких досліджень про них. Крім того, ці алгоритми мають більш високу продуктивність в порівнянні з іншими алгоритмами, що стоять перед зазначеними проблемами. З іншого боку, здається, що кожен підхід, особливо реактивний метод, страждають від багатьох недоліків.		Показано, що деякі алгоритми, такі як інкрементний евристичний пошук та алгоритми евристичного пошуку в режимі реального часу в цій галузі, є більш корисними і тому мають більш широкі можливості для проведення деяких досліджень про них. Крім того, ці алгоритми мають більш високу продуктивність в порівнянні з іншими алгоритмами, що стоять перед зазначеними проблемами. З іншого боку, здається, що кожен підхід, особливо реактивний метод, страждають від багатьох недоліків.

−	[[Файл:~~Example~~.~~jpg~~]]	+	[[Файл:Rpp.png]]

← Попередня версія		Версія за 14:32, 18 лютого 2018
Рядок 9:		Рядок 9:
	Декілька підходів використовуються для вирішення проблеми планування маршуту в динамічному середовищі,які зображені на малюнку 3.1. Дивлячись на це зображення, методи та алгоритми поділяються на 3 категорії: Евристичні методи(Heuristic methods), Випадково вибіркові методи(Randomized Sampling methods) та Реактивний методи(Reactive methods).		Декілька підходів використовуються для вирішення проблеми планування маршуту в динамічному середовищі,які зображені на малюнку 3.1. Дивлячись на це зображення, методи та алгоритми поділяються на 3 категорії: Евристичні методи(Heuristic methods), Випадково вибіркові методи(Randomized Sampling methods) та Реактивний методи(Reactive methods).

−	[[Файл:3.1.png]	+	[[Файл:3.1.png]]

← Попередня версія		Версія за 14:31, 18 лютого 2018
Рядок 9:		Рядок 9:
	Декілька підходів використовуються для вирішення проблеми планування маршуту в динамічному середовищі,які зображені на малюнку 3.1. Дивлячись на це зображення, методи та алгоритми поділяються на 3 категорії: Евристичні методи(Heuristic methods), Випадково вибіркові методи(Randomized Sampling methods) та Реактивний методи(Reactive methods).		Декілька підходів використовуються для вирішення проблеми планування маршуту в динамічному середовищі,які зображені на малюнку 3.1. Дивлячись на це зображення, методи та алгоритми поділяються на 3 категорії: Евристичні методи(Heuristic methods), Випадково вибіркові методи(Randomized Sampling methods) та Реактивний методи(Reactive methods).

−	[[Файл:~~Example~~.~~jpg]~~]	+	[[Файл:3.1.png]