Олійник, Андрій СтаніславовичСмірнов, Антон Олександрович2019-12-262019-12-262019-12Смірнов, А. О. Модифікація та дослідження алгоритму пошуку шляху в динамічному середовищі на основі випадкових дерев : магістерська дис. : 113 Прикладана математика / Смірнов Антон Олександрович. - Київ, 2019. - 54 с.https://ela.kpi.ua/handle/123456789/30578Метою роботи був анал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ям.ukпланування шляхувипадковi дереватрасування променiвpath planningrandom treesray castingMaster Thesis54 с.681.3.06:519.248.681