Башкирский государственный педагогический университет им. М. Акмуллы
Автор статьи: Галеев Д.Р
Введение
Существуют различные системы для определения местоположения и построения маршрутов в пространстве. Однако большинство из них не могут быть использованы внутри зданий, главным образом из-за отсутствия свободного доступа к планам этажей. Эта проблема особенно актуальна для студентов начальных курсов, которым сложно ориентироваться в большом числе корпусов и аудиторий учебных заведений. Поэтому задача минимизации времени для построения кратчайшего маршрута к объектам внутри зданий является актуальной.
Алгоритмы моделирования маршрута
В данной статье был проведен анализ теоретических и практических разработок в области навигации, включая сравнительный анализ алгоритмов поиска маршрута и технологий геолокации. В таблице 1 приведен сравнительный анализ алгоритмов поиска кратчайшего маршрута, которые могут быть использованы для работы систем навигационных графов. Среди самых известных и популярных алгоритмов поиска пути можно выделить алгоритм Ли и алгоритм A* (A-STAR) [4]. Для поиска маршрутов 17 внутри здания, рекомендуется использовать алгоритм Ли, если пункт назначения меняется редко.
| Алгоритм | Назначение | Особенности |
| Беллмана-Форда [2] | Поиск кратчайшего пути во взвешенном графе | Допускает рёбра с отрицательным весом |
| Дейкстры [2;3] | Аналогично алгоритму Беллмана-Форда | Работа только с ребрами, имеющими положительный вес. Хорошо выполняется в графах с небольшим количеством вершин |
| A* (ASTAR) [2;3] | Находит кратчайшие пути от одной из вершин графа до всех остальных | Сравнение различных путей по эвристической функции, за счет этого достигает более высокой производительности, чем алгоритм Дейкстры |
| Ли [2;3] | Поиск пути на планарном графе. Находит путь между двумя вершинами графа, с минимальным количеством промежуточных вершин (ребер) | Начало и конец пути могут представляться более чем одной клеткой. Работает и по диагонали. |
| Джонсона [2] | Нахождение кратчайшего пути между всеми парами вершин взвешенного ориентированного графа | Данный алгоритм работает, если в графе содержатся ребра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом. |
| Флойда-Уоршелла [3]. | Для поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер | Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Требует больших вычислительных затрат на значительно разветвленном графе. |
В случае, когда пункт назначения часто меняется, предпочтительным является использование алгоритма A* (A-STAR), так как он является самым быстрым алгоритмом с относительно простой реализацией. Для соединения всех графов (уровней здания) в системе могут использоваться общие вершины, такие как лестницы [4].
Алгоритм A* (A-STAR) используется для нахождения кратчайшего пути между двумя вершинами графа. Он последовательно рассматривает все пути от начальной до конечной вершины, пока не находит минимальный. В отличие от других алгоритмов, A* учитывает всю пройденную длину пути (функция g(x)) при сравнении. Алгоритм исследует все смежные пути от начальной вершины и выбирает тот, который имеет наименьшее значение функции f(x)
(сумма значений g(x) и h(x), см. формулу (1): Алгоритм А*(ASTAR) – f(x)=g(x)+h(x) (1), где h(x) – эвристическая оценка пути).
На каждом шаге алгоритм также обрабатывает все оставшиеся пути к непосещенным вершинам графа, помещая их в приоритетную очередь по значению f(x). А* продолжает свою работу до тех пор, пока значение f(x) целевой вершины не станет меньше любого значения в очереди или пока все значения не будут просмотрены. Такой путь является искомым кратчайшим путем между двумя вершинами графа. В случае наличия нескольких решений, выбирается путь с наименьшей стоимостью. Чем меньше эвристическая функция h(x), тем больший приоритет имеет путь. Таким образом, достигается оптимальный маршрут [1, 2].
Технологии геолокации
Сейчас представлено множество технологий для определения местоположения устройств, перечисленных в таблице 2.
| Название | Краткое описание | Достоинства | Недостатки |
| GPS – Global Positioning System [2]. | Спутниковая система навигации, обеспечивающая измерение расстояния, времени и определяющая местоположение во всемирной системе координат WGS 84. | Бесплатное использование, глобальная доступность, стабильная работа на большинстве устройств | Большое потребление энергии, точность позиционирования составляет 2-4 метра, в помещениях сигнал со спутника часто пропадает |
| Galileo [2]. |
Европейская спутниковая система навигации |
Работает с системой GPS. Точность определения позиции 0.5-1 метр |
Низкая совместимость с современными навигационными приборами. Разрабатывалась не для гражданского применения
|
| ГЛОНАСС – Глобальная навигационная спутниковая система [2]. | Российская спутниковая система навигации. Вторая глобальная система навигации (после GPS). | Высокая точность в северном полушарии, хорошо дополняет GPS в работе | Точность определения координат не стабильна, в среднем 4-9 метров. В помещениях сигнал часто теряется |
| Bluetooth-маячки [4]. | Навигация относительно Bluetooth-маячков расположенных на небольшом расстоянии друг от друга. | Обладают высокой точностью 1-1.5 м | Требуют больших материальных затрат для покрытия большой площади, слабая проходимость сигнала через препятствия. Используют открытые протоколы. |
| WPS [2]. | Технология определении местоположения по силе сигнала от Wi-Fi роутеров | Высокая точность определения местоположения. В местах с плотной Wi-Fi сетью не требует дополнительного оборудования | Работает только с Android устройствами |
| Визуальные метки (QRкод) [4]. | QR-код – это особый вид штрих-кода, в котором с помощью пикселей зашифрован некоторый объем информации. | Недорогой вариант для обслуживания и установки внутри здания | Повышенные требования к освещенности и возможности камеры смартфона, невозможно отследить местоположение в реальном времени |
| Датчики мобильного устройства (акселерометр, магнитометр) [4] | Акселерометр – отслеживает изменение скорости движения устройства и повороты вокруг своей оси. Магнитометр – измеряет уровень магнитного поля | Определяют текущую скорость и направление движения, положение в пространстве | Значительно ограничивают возможных пользователей, поскольку не во все смартфонах есть эти датчики |
Эти системы могут работать как внутри, так и вне зданий. При выборе системы геолокации внутри помещений рекомендуется учитывать преимущества и недостатки каждой из них, а также масштабы здания и финансовые возможности. Одними из лучших систем являются Galileo, ГЛОНАСС и GPS, которые позволяют определить относительные координаты текущего местоположения человека для построения маршрута от одной точки к другой. Визуальные QRметки также являются отличным вариантом при ограниченном бюджете, позволяя идентифицировать начальное местоположение человека и построить маршрут к нужному объекту в здании.
Исследование алгоритмов и технологий для формирования маршрута приводят к выводу о целесообразности использования алгоритма A* (ASTAR), так как он является наиболее быстрым и относительно простым в реализации прикладных программных приложениях. Технология визуальных меток (QR-код) также представляет собой недорогую, простую в установке и обслуживании систему для определения начального местоположения студента в здании образовательного учреждения с множеством корпусов и этажей.
Список использованных источников
- Барабанов, В.Ф. Программная реализация поиска для множества объектов с областями различной проходимости / В.Ф. Барабанов, Н.И. Гребенникова, А.К. Донских, С.А. Коваленко. // Вестник воронежского государственного технического университета. – 2018. – № 5. – С. 33-41.
- Дубовик, Н.Н. Анализ методов пространственной навигации и трассировки маршрутов с линейными ограничениями / Н.Н. Дубовик, А.В. Лавров, О.А. Ногин, В.М. Туманов. // Международный научно-исследовательский журнал. – 2015. – № 11-2 (42). – С. 35-42.
- Изотова, Т.Ю. Обзор алгоритмов поиска кратчайшего пути в графе / Т.Ю. Изотова. // Новые информационные технологии в автоматизирован- ных системах. – 2016. – № 19. – С. 341-344.
- Охотниченко, А.В. Проектирование системы для навигации внутри здания со сложной иерархической структурой / А.В. Охотниченко, Ю.Б. Кухта. // Программные системы и вычислительные методы. – 2021.–№ 4. – С. 46-57.