Модифікація та дослідження алгоритму пошуку шляху в динамічному середовищі на основі випадкових дерев
Вантажиться...
Дата
2019-12
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Метою роботи був аналiз та модифiкацiя алгоритму планування шляху
на основi випадкових дерев. Об’єктом дослiдження був процесс планування
шляху в динамiчних середовищах. Предметом дослiдження були алгоритми
планування шляху в динамiчних середовищах на основi випадкових дерев.
В результатi виконання роботи було дослiджено iснуючi алгоритми
пошуку шляху в режимi реального часу. Серед дослiдженних алгоритмiв за
основу було обрано алгоритм на основi випадкових дерев.
Для обраного алгоритму RT-RRT* запропоновано модифiкацiю, що
замiнює алгоритм розширення дерева та алгоритм iндексацiї дерева. Новий
алгоритм розширення дерева базується на побудовi областi видимостi
навколо вершин дерева та генерацiї точок всерединi цiєї областi. Це
забезпечує те, що будь-яка згенерована точка всерединi областi видимостi
може бути гарантовано приєднана принаймi до тих вершин, навколо яких
будувалась область видимостi. Модифiкацiя алгоритму iндексацiї дерева
пропонує замiнити grid-based iндексацiю на використання KD-дерев.
Порiвняно складнiсть обох алгоритмiв та наведено доведення
ймовiрнiсної повноти, що виконується для цих алгоритмiв. Для модифiкацiї
алгоритму показано, що швидкiсть збiжностi алгоритму є бiльшою нiж для
оригiнального алгоритму, вiдносно кiлькостi iтерацiй, завдяки
запропонованим модифiкацiям.
Опис
Ключові слова
планування шляху, випадковi дерева, трасування променiв, path planning, random trees, ray casting
Бібліографічний опис
Смірнов, А. О. Модифікація та дослідження алгоритму пошуку шляху в динамічному середовищі на основі випадкових дерев : магістерська дис. : 113 Прикладана математика / Смірнов Антон Олександрович. - Київ, 2019. - 54 с.