Научный семинар «Разработка интеллектуального алгоритма поиска пути на основе алгоритмов A* и Navmesh»
18 ноября в 15:00 по московскому времени
На факультете физико-математических и естественных наук пройдет семинар кафедры информационных технологий РУДН «Разработка интеллектуального алгоритма поиска пути на основе алгоритмов A* и Navmesh».
В докладе будет рассмотрена работа классического алгоритма поиска пути A*, а также производный от него алгоритм Navmesh. Особое внимание уделяется присущим таким алгоритмом недостатками, в том числе нереалистичному отображению поведения агентов при моделировании движения людей.
Базовый алгоритм Navmesh основан на представлении моделируемой среды в виде сетки, разбитой на выпуклые многоугольники. Для построения такой сетки применяются алгоритмы триангуляции от двух множества точек — точки границ среды и точки внутренних препятствий. Отдельные многоугольники объединяются в граф, с указанием соседства и расстояний между ними. Далее задача поиска пути разбивается на две тривиальные задачи: поиск пути по графу алгоритмом А*; и поиск пути внутри многоугольника проведением прямой линии.
В целях более адекватного, т.е. соответствующего реальности, моделирования поведения агентов разрабатывается гибридный алгоритм поиска пути, основанный на алгоритме Navmesh, но при этом учитывающий психофизиологические особенности поведения людей. Моделируемые агенты наделяются набором целей, с различным приоритетом, расположенных в моделируемой среде. Расположение целей, а также точная конфигурация среды изначально не известны агенту, и представляются ему в процессе моделирования.
Рассматриваются дальнейшая перспектива создания гибридного алгоритма, преимущества и недостатки его использования.
Мамонов Антон Алексеевич — аспирант кафедры информационных технологий РУДН.