Дослідження інкрементальних евристичних алгоритмів пошуку шляху (D* Lite)

Abstract

Бакалаврська кваліфікаційна робота виконана студенткою групи КН-413 Огорілко Вікторією Олегівною. Тема «Дослідження інкрементальних евристичних алгоритмів пошуку шляху (D* Lite)». Робота направлена на здобуття ступеня бакалавр за спеціальністю 122 «Комп’ютерні науки». Мета цієї дипломної роботи полягає в дослідженні алгоритмів інкрементального евристичного пошуку на прикладі реалізації алгоритму D* Lite для пересування робота у заданому просторі з динамічною зміною можливих перешкод. Об’єктом дослідження є процес пошуку шляху для роботизованих систем. Предметом дослідження є алгоритм D* Lite та його візуалізація для задачі пошуку оптимального шляху переміщення в заданому просторі з урахуванням стану середовища. В результаті виконання цієї дипломної роботи було розроблено інтерактивну візуалізацію для зображення роботи алгоритму D* Lite. The Bachelor's qualification work was carried out by a student of the KN-413 group, Ohorilko Viktoriia Olehivna. The topic is "Research of Incremental Heuristic Pathfinding Algorithms (D* Lite)". The work is aimed at obtaining a bachelor's degree in specialty 122 "Computer Science". The purpose of this thesis is to study incremental heuristic search algorithms using the example of the D* Lite algorithm implementation for moving a robot in a given space with a dynamic change of possible obstacles. The object of study is the process of pathfinding for robotic systems. The subject of the study is the D* Lite algorithm and its visualization for the task of finding the optimal path in a given space, taking into account the state of the environment. As a result of this thesis, an interactive visualization was developed for displaying the work of the D* Lite algorithm.