Спросить
Войти
Информатика и системы управления
УДК 51-7
В.В. Фурсов, С.Г. Самохвалова
АНАЛИЗ АЛГОРИТМОВ ПОИСКА ПУТИ ДЛЯ РАЗЛИЧНЫХ ЗАДАЧ И ИХ ИСПОЛЬЗОВАНИЕ В МОБИЛЬНОМ ПРИЛОЖЕНИИ
В статье проводится анализ существующих алгоритмов поиска пути для разных типов задач, история их создания и модификации. Реализация и тестирование алгоритмов на мобильном устройстве.
ANALYSIS PATHFINDING ALGORITHMS FOR VARIOUS PROBLEMS AND THEIR USE IN MOBILE APPLICATIONS
The existing pathfinding algorithms for different types of tasks and history of creation and modification, implementation and testing the algorithms on a mobile device are analyzed in this paper.
Сетки
Правильные сетки
> 2D квадратная сетка
Неправильные сетки
Граф видимости
Введение
Поиск пути является основой для применения в области GPS [1], видеоиграх [2], робототехнике [3], логистике и моделировании толпы [4]. Поиск пути может быть реализован также в статических, динамических и в средах реального времени. В течение последних двух десятилетий удалось повысить точность и эффективность методов поиска путей, но задача по-прежнему привлекает большое внимание исследователей. В настоящее время наиболее важными являются высокая производительность и реалистичные пути для пользователей.
Рассмотрим подробнее представленные на конференции [5] отношения между различными типами топологий местности (рис. 1).
Рис. 1. Топология местности.
Методы на основе сетки
Сетка состоит из вершин или точек, которые соединены ребрами и представляют собой граф. В большинстве алгоритмов поиска пути производительность навигации - это основной атрибут представления графа. Фундаментальной концепцией являются два популярных подхода, основанных на правильных и неправильных сетках.
Сетка навигации
Путевые точки
Правильные сетки
Правильные сетки - один из самых известных типов графов, их широко используют. В 2Б- и ЭБ-средах регулярные сетки описывают мозаику правильных многоугольников (т.е. равносторонних и равноугольных полигонов). Шестиугольники, квадраты и треугольники являются единственными правильными многоугольниками, которые могут быть использованы как непрерывная мозаика в 2Б (рис. 2, а, б, в) и кубические решетки в ЭБ (рис. 2, г).
) г) в)
Рис. 2. Правильные сетки: а - квадратные сетки с тремя препятствиями; б - гексагональные сетки с тремя препятствиями; в - триангуляционные сетки с тремя препятствиями; г - кубическая решетка
без препятствий.
Квадратные сетки - одни из наиболее популярных графов в компьютерных играх и навигации по карте, а также многочисленные алгоритмы были предложены для решения задачи поиска пути для этого типа сеток (рис. 2, а). Д. Харабор и А. Грастен [6] предложили алгоритм «прыжковых точек» (jump point search) с одним агентом для решения общей задачи в играх и навигации - хорошо известной «единичной стоимости сетки в статической среде». Jump point search в 10 раз быстрее, чем алгоритм «А*», и имеет небольшие накладные расходы на память. Исследователи оценивали свою работу на основе стандартного набора карт для поиска пути, предложенного Н.Р. Стертевант [7].
Харабор и Грастен [8] улучшили алгоритм «прыжковых точек» (jump point search), используя три стратегии: во-первых, они рассматривали узлы как базовые блоки операций, а затем применили систему предварительной обработки в автономном режиме, третья стратегия представляет собой усовершенствованный набор действующих правил обрезки деревьев. Полученные алгоритмы сравнивались с методом Ураса.
В отношении изменяющихся графов в присутствии «динамических препятствий» К. Андерсон [9] представил отличное дополнение эвристики для поиска с единственным агентом на 4-направленной квадратной сетке. Этот метод эффективно сокращает время поиска в неявных графах, единственный его недостаток - он реализован с алгоритмом «А*», излишне расширющего число узлов во время поиска.
Для мультиагентной задачи Х. Джин и др. [10] использовали алгоритм «А*» в XNA-игре, чтобы решить проблему поиска пути. Они использовали алгоритм «А*» для обработки динамических препятствий с 2Б-квадратной картой сетки, несмотря на 3Б-реализацию. Недостаток их работы - то, что «А*» не всегда является оптимальным для статических карт сетки.
Ю. Бьорнссон и др. [11] показали, что гексагональные сетки (рис. 2,б) имеют много свойств квадратных сеток. Кроме того, у шестиугольных сеток меньшее время поиска и потребление памяти, чем у сложных сеток графов, построенных из квадратов. П.Ж. Кихано и Л. Гарридо [12] использовали 6 алгоритмов гексагональной сетки для моделирования разведки робота. Они доказали, что алгоритмы на гексагональных сетках превосходят квадратные сетки для одно- и мультиагентных задач.
М.Ф. Осман и др. [13] обсудили проблемы, с которыми сталкиваются исследователи, использующие алгоритмы поиска пути в робототехнике. Одна из главных проблем в мобильной робототехнике - избегание реальных объектов. Алгоритм D* был применен к методам моделирования 2Б-карты с помощью квадратной плитки, шестиугольников и усовершенствованных шестиугольников. Результаты показывают, что усовершенствованные шестиугольники дают лучшие пути, но требуют больше времени для поиска в больших картах. Приемлемые результаты достигаются для малых и средних карт. Алгоритмы поиска пути были реализованы в основном на квадратных сетках, а муль-тиагентная задача на шестиугольной сетке еще не была исследована в динамических средах или в средах реального времени.
Треугольные сетки (рис. 2, в) используются не так широко, как квадратные и гексагональные, но у них есть некоторые хорошие свойства. Д. Димайном и М. Буро [14] был предложен способ, который уменьшает затраты на поиск с использованием ограничений триангуляции Делоне. Изменяя размеры объектов, авторы исследовали влияние окружающей среды на движение во время навигационной задачи. При использовании их алгоритмов TA* и TRA* обнаружено, что они безупречно работают на больших картах.
Наги [15] получил новую систему координат, состоящую из двух гексагональных и треугольных сеток графов. Эта новая сетка может применяться в различных областях, - например, таких как компьютерная графика и обработка изображений. Считается, что новую топологию можно использована с детерминированными методами поиска пути - такими как А* и его варианты.
ЗБ-кубическая сетка (рис. 2, г)
В отличие от сеточных графов, рассмотренных выше, кубическая решетка (рис. 2, г) является привычным графом для 3D-среды. Кылыч и Ялчин использовали простой алгоритм для вычисления движения трех типов волн в 3D-среде и применили его, чтобы решить проблему поиска пути для робота. Позже авторы улучшили алгоритм для среды 3D. В предложенной модели робот имеет всего 6 соседних клеток, которые могут быть использованы для навигации. Это явный недостаток данной модели, число соседних клеток должно быть увеличено, чтобы включать все 26 соседних ячеек для улучшения получившегося пути. Не так давно А. Нэш и С. Кениг [16] опубликовали отличную статью под названием «Any-Angle Path Planning». Они ввели три различных алгоритма - А*, Theta* и Ленивая Theta* - для квадратных, шестигранных, треугольных и кубических сеток. Цель этих алгоритмов - нахождение плавного реального пути для любой топологии местности, без учета размера агента или формы препятствий. На основании наблюдаемой производительности они определили кратчайшие пути, а не самый короткий путь на сетке. К сожалению, алгоритм «Any-Angle Path Planning» потребляет больше времени, чем обычные алгоритмы поиска пути.
Неправильные сетки
Аномальные сетки используются во многих задачах и областях.
а) б) в)
Рис. 3. Неправильные сетки: а - граф видимости; б - сеточная система навигации с треугольной сеткой; в - 3D пути сглаживания.
Граф видимости (рис. 3, а)
Граф видимости считается фундаментальной структурой в различных областях геометрической теории графов и в вычислительной геометрии, его привлекают к изучению различных задач. Граф видимости недавно был использован при вычислении евклидовых кратчайших путей при наличии препятствий [17].
Чтобы решить проблему с одним агентом, М. Надэан-Тахан и Т. Манзури-Шалмани [18] предложили новый генетический алгоритм для поиска эффективного пути через ряд расширяющихся препятствий. Кроме того, они использовали стратегию ускорения скорости сходимости путем создания подходящей начальной популяции. Авторы применили общую вычислительную геометрию на основе подхода суммы Минковского, а не на основе методов ячеек - таких, как сетки. Этот метод показал, что он быстрее, чем другие подходы вычислительной геометрии, но производит неоптимальные решения.
Сетка навигации (рис. 3, б)
Как показано на рис. 3, б, проходимые участки карты представляют собой навигационную сетку. Эта сетка может быть представлена разными способами, - например, с помощью треугольников или многоугольников. Ведь сеточные графы и графы видимости очень похожи, но в практическом плане графы видимости являются более сложными, чем сеточные. Чаще всего сетки графов применяются в видеоиграх.
Сислак и др. представили алгоритм, вдохновленный А*. Их алгоритм АА* (Accelerated А*) позволяет планировать траекторию полета на основе задачи поиска пути с единственным агентом. Алгоритм АА* был использован в динамичной среде для моделирования движения самолета. Основные его преимущества - способность рассматривать самолет ненулевого размера и планировать путь для направленного вектора вверх от горизонтальной плоскости.
С целью мультиагентного поиска пути Кападия и др. предложили структуру режима реального времени для мультиагентной навигации, которая использует несколько неоднородных проблемных областей в больших, сложных и динамических виртуальных средах.
Путевые точки (рис. 3, в)
Путевые точки широко используются в компьютерных играх и робототехнике. Нидерберг и др. предложили алгоритм на основе A* для поиска пути в статических местностях с полигональными препятствиями. Алгоритм генерирует путь в соответствии с минимальным числом точек пути, но характеризуется длительным временем вычислений и значительными накладными расходами памяти.
Фергюсон и Стентз разработали алгоритм Field D* c интерполяцией на основе планирования и описали алгоритм перепланировки для генерации малозатратных путей через однородные и неоднородные сетки. Есть два недостатка в поиске пути на основе сетки: во-первых, планирование на основе сетки имеет ограниченную способность в нахождении оптимального пути, потому что путь должен проходить через соседние точки; во-вторых, требования к памяти на основе планирования пути часто неприемлемо высоки.
Использование алгоритма поиска пути для навигации по зданию в мобильном приложении
После проведенного исследования алгоритмов и модификаций было решено протестировать их производительность на мобильном устройстве. Для этого было написано соответствующее программное обеспечение с использованием кроссплатформенного фреймворка Xamarin. Для теста использовалась карта, созданная по плану третьего этажа главного корпуса АмГУ (рис. 4).
п 1 ■ т ■ ■ ч - нч н к
■ Л 41
Рис. 4. Частичный вид карты третьего этажа главного корпуса АмГУ.
Для поиска пути по зданию было решено использовать в качестве карты правильную 2D-квадратную сетку как наиболее подходящую для текущей задачи.
Тестирование
При тестировании учитывались такие параметры как количество итераций, время расчета пути. Все замеры воспроизведились на устройстве iPhone 5 с двухъядерным процессором на 1,3 ГГц и оперативной памятью в 1 Гигабайт.
Результаты тестов
Время расчёта пути в секундах
Рис. 5. Замеры для неоптимизированной карты.
Таблица 1
Замеры для неоптимизированной карты
Алгоритм Время, сек. Количество итераций
A* 00.7810493 686
BiA* 01.0409421 927
Jump point search 00.1341923 182
Breadth first search 109.2012067 11203
Время расчёта пути в секундах
Рис 6. Замеры для оптимизированной карты.
Замеры для оптимизированной карты
Таблица 2
Алгоритм Время, сек. Количество итераций
A* 00.1639223 356
BiA* 00.1349399 351
Jump point search 00.0982483 178
Breadth first search 00.1947753 583
Заключение
В результате проведенного анализа были изучены различные алгоритмы поиска путей для разных типов задач. В итоге лучшим алгоритмом для поиска путей на правильной 2D-квадратной сетке, на мобильном устройстве, с минимальным временем расчета пути стал алгоритм «прыжковых точек» (jump point search), который в используется для создании навигационного мобильного приложения. Разработанное мобильное приложение поможет гостям и студентам в навигации внутри зданий университета.
