Модифікація та дослідження алгоритму пошуку шляху в динамічному середовищі на основі випадкових дерев

Скорочена інформація про документ
dc.contributor.advisorОлійник, Андрій Станіславович
dc.contributor.authorСмірнов, Антон Олександрович
dc.date.accessioned2019-12-26T13:08:05Z
dc.date.available2019-12-26T13:08:05Z
dc.date.issued2019-12
dc.description.abstractenThe point of this work was analysis and modification of path-planning algorithm based on random trees. Object of the research was process of path-planning in dynamic environments. Subject of the research was path-planning algorithm in dynamic environments based on random trees. As a result, path-planning algorithms in dynamic environments were studied. Among studied algorithms, one was selected as a base algorithm which is based on random trees. For the selected algorithm RT-RRT* modification was suggested, that replaces expansion and tree-indexing algorithms. New expansion algorithm is based on building a visibility region around vertices of the tree and generating new points inside this region. This guarantess, that any samples point inside visibility region can be connected at least to those vertices around which visibility region was built. Modification of the tree-indexing algorithm suggest replacing grid-based indexing with KD-trees. Compares both algorithms and presented a proof of their probabilistic completeness. For the modification was shown that convergence speed is higher than that of the original algorithm, in terms of number of iterations, due to the described modifications.uk
dc.description.abstractruЦелью работы был анализ и модификация алгоритма планирования пути на основе случайных деревьев. Объектом исследования был процесс планирования пути в динамичесской среде. Предметом исследования были алгоритмы планирования пути в динамичесской среде на основе случайных деревьев. В результате выполнения работы было исследовано существующие алгоритмы поиска пути в режиме реального времени. Среди исследованых алгоритмов в качестве основного был обран алгоритм на основе случайных деревьев. Для выбранного алгоритма RT-RRT* предложено модификацию, которая заменяет алгоритм расширения дерева и алгоритм индексации дерева. Новый алгоритм расширения дерева базируется на построении области видимости вокруг вершин дерева и генерации точек внутри этой области. Это гарантирует, что любая сгенерированная точка внутри области видимости гарантированно может быть присоединена хотя бы к тем вершинам, вокруг которых строилась область видимости. Модификация алгоритма индексации дерева предлагает заменить grid-based индексацию на использование KD-деревьев. Проведено сравнение обоих алгоритмов и представленно доказательство вероятностной полноты, которое выполняется для этих алгоритмов. Для модификации алгоритма показано, что скорость сходимости алгоритма больше чем для оригинального алгоритма, относительно количества итераций, благодаря предложенным модификациям.uk
dc.description.abstractukМетою роботи був анал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
dc.format.page54 с.uk
dc.identifier.citationСмірнов, А. О. Модифікація та дослідження алгоритму пошуку шляху в динамічному середовищі на основі випадкових дерев : магістерська дис. : 113 Прикладана математика / Смірнов Антон Олександрович. - Київ, 2019. - 54 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/30578
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectпланування шляхуuk
dc.subjectвипадковi дереваuk
dc.subjectтрасування променiвuk
dc.subjectpath planninguk
dc.subjectrandom treesuk
dc.subjectray castinguk
dc.subject.udc681.3.06:519.248.681uk
dc.titleМодифікація та дослідження алгоритму пошуку шляху в динамічному середовищі на основі випадкових деревuk
dc.typeMaster Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Smirnov_magistr.pdf
Розмір:
3.57 MB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.06 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (ММЗІ)
Магістерські роботи