Система поиска и построения маршрутов внутри помещения с помощью путевых карточек

Аннотация

Кривошеев С.В., Алутин Е.А. Система поиска и построения маршрутов внутри помещения с помощью карточек путевых точек.Рассматриваются особенности реализации алгоритмов поиска и генерации траекторий движения внутри помещений на мобильной платформе Android, приведена структура системы, описаны структуры данных.

Введение

В современных сложных архитектурных объектах (аэропорты, вокзалы, торговые центры и т.д.) невозможно перемещаться без наличия специальных навигационных знаков и дополнительной информации, так как они предоставляют услуги, которыми люди пользуются не регулярно или вообще единожды для подобного типа здания. В связи с развитием современных вычислительных устройств, ростом их мобильности и достаточно высокой производительностью, такая задача, как реализация навигации внутри помещений имеет большое разнообразие путей решения, особенно с применением мобильных платформ.

В связи с ростом характеристик здания, таких как объём и сложность структуры, некоторые методы навигации уже не так эффективны, как раньше. Например, настенные планы теряют наглядность, если этаж здания имеет большую площадь и включает в себя большое количество помещений. Трудно взглянуть сразу на всѐ изображение и соотнести его с действительностью. Ситуация также может быть осложнена тем, что этажи могут иметь различную структуру. Тогда для каждого из них придѐтся составлять свой план, и объём информации, которой необходимо оперировать мысленно, возрастѐт до неприемлемых величин.

Особенности систем поиска и построения маршрутов внутри помещений

Современным решением задач навигации являются беспроводные технологии и мобильные платформы. Разработка таких систем и сервисов популярна в последние годы в IT-индустрии. Некоторые современные здания, например, аэропорты, торговые центры, склады имеют настолько сложную структуру и масштабы, чтобы чувствовать нехватку собственных навигационных инструментов. Кроме определения объекта в пространстве система навигации внутри помещений также занимается построением оптимальных маршрутов, отслеживанием популярных мест пользователей, отправлением push-уведомлений пользователям в зависимости от их местоположения и пр.

Системы позиционирования внутри помещений можно разделить на две категории, а именно сетевые системы позиционирования и системы позиционирования, не использующие сеть [1]. Основой сетевых систем позиционирования такие сетевые технологии, как Wi-Fi, Bluetooth, ультразвук и инфракрасные системы. Такие системы определяют положение пользователя как GPS, только внутри помещения. К системам, не использующим сеть можно отнести системы, основанные на технологиях RFID, QR-коды, NFS и пр. Такие системы не получают информацию о точном местонахождении пользователя, но на основе введенных им данных могут определить из какой контрольной точки в какую пользователь желает получить маршрут.

Существует другая классификация систем навигации – по относительным координатам и по ключевым точкам [1]. Позиционирование в относительных координатах предполагает наличие активных устройств (маяков) для позиционирования. А вот системы, использующие контрольные точки для навигации не требуют наличие активных устройств, что позволяет использовать такие системы в связке с пассивными устройствами (метками) или вовсе автономно.

На рисунке 1 изображена система навигации, использующая относительные координаты, то есть по площади здания расположены активные устройства (маяки), сообщающие навигационную информацию. Навигационный терминал пользователя получает информацию от маяков и вычисляет свое местоположение, система получает координаты пункта назначения и строит маршрут. Так как система знает местонахождение пользователя, пользователю не обязательно грубо следовать по маршруту, потому что в случае отклонения система сможет перестроить маршрут.

На рисунке 2 изображена система навигации, использующая ключевые точки. Такая система не требует активного оборудования, но и местоположение пользователя отслеживается только в ключевых точках. В данном случае местоположение пользователя задается в системе при помощи считывания RFID, NFC меток, QR-кода либо задается вручную самим пользователем. Система получает ключевую точку пункта назначения и строит маршрут, однако в отличие от системы с относительными координатами, в случае отклонения пользователю нужно будет считывать новую метку или задавать свое новое местоположение, чтобы система перестроила маршрут.

Алгоритмы поиска маршрутов

Для определения кратчайшего пути до заданной точки на местности необходимо еѐ формализованное представление. В качестве такового используется карта дорог, представляющая собой набор векторов с закреплѐнными за ними числовыми значениями. Значения эти могут иметь различный смысл: в простейшем случае, это просто расстояние, но чаще это более общий коэффициент, учитывающий и прочие факторы (например, состояние дорожного покрытия между двумя пунктами). В математике такое формализованное представление называется взвешенным графом. Для поиска кратчайшего пути во взвешенном графе существует несколько алгоритмов, наиболее классическим из них является алгоритм Дейкстры [2].

Существуют также следующие алгоритмы [3]: алгоритм поиска в ширину, алгоритм Дейкстры, алгоритм А*, алгоритм Jump Point Search.

Широкое распространение при практической реализации получила модификация алгоритма Дейкстры – алгоритм А* [4]. Суть алгоритма проста: в качестве следующего пункта (вершина графа) выбирается тот, который имеет наименьшую оценку: сумма пройденного расстояния и предположительного расстояния до конечного пункта. Последнее принимается как расстояние до пункта по прямой, причѐм это специфика именно данной системы навигации. Сам алгоритм А* не указывает, какой именно метод предположительной оценки должен использоваться. Чтобы A* был оптимален, выбранная эвристическая функция h(v) должна быть допустимой эвристической функцией. Говорят, что эвристическая оценка h(v) допустима, если для любой вершины v значение h(v) меньше или равно весу кратчайшего пути от v до цели. Допустимая оценка является оптимистичной, потому что она предполагает, что стоимость решения меньше, чем оно есть на самом деле.

Поведение алгоритма сильно зависит от того, какая эвристика используется. В свою очередь, выбор эвристики зависит от постановки задачи. Часто А* используется для моделирования перемещения по поверхности, покрытой координатной сеткой[5].

Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние:

Расстояние Чебышева применяется, когда к четырем направлениям добавляются диагонали:

Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:

Где v.x и v.y – координаты текущей вершины, а goal.x и goal.y – координаты конечной вершины.

Также стоит обратить внимание на то, как соотносятся f(v) и h(v). Если они измеряются в разных величинах (например, g(v) — это расстояние в километрах, а h(v) — оценка времени пути в часах) А* может выдать некорректный результат.

Структура системы поиска и построения маршрутов внутри помещений

Рассмотрим систему, которая предназначена для поиска и построения маршрутов между кабинетами внутри учебного корпуса навигации пользователей по построенным маршрутам с помощью карточек путевых точек

Для реализации задач системы необходимо наличие следующих блоков: ввод начальных данных, система поиска пути, система обработки маршрута (рисунок 3). Ввод начальных данных, а именно начальная и конечная точки для поиска и построения маршрута между ними. Система поиска пути будет в соответствии с алгоритмом находить кратчайший маршрут между точками, указанными в начальных данных. Система обработки маршрута необходима для конвертации списка вершин графа в путевые точки, которые будут понятны человеку

Структурная схема включает в себя следующие элементы:

• Стартовое окно – окно с информацией о приложении и кнопкой запуска системы;
• Окно выбора местонахождения – окно со списком, элементами которого являются аудитории помещения, для выбора текущего местонахождения пользователя;
• Окно выбора пункта назначения – окно со списком, элементами которого являются аудитории помещения, для выбора конечной точки маршрута;
• Система поиска пути – специальный алгоритм, для обработки графа навигации;
• Система анализа маршрута – специальный алгоритм, для обработки полученного маршрута в путевые точки;
• Окно отображения маршрута пользователю – окно с карточками, которые визуализируют путевые точки

Разрабатываемая система навигации основана на контрольных точках, поэтому пользователь вручную вводит текущее местоположение и пункт назначения. После запуска системы пользователю отображается окно выбора текущего местоположения, где пользователь может указать свое местоположение, чтобы система имела информацию о том, откуда начинать построение маршрута.

Следующим окном является окно выбора пункта назначения, данное окно содержит список кабинетов, куда возможно построить маршрут, после выбора пункта назначения система имеет полный набор информации для старта работы основных алгоритмов.

После получения стартовой и конечной точки маршрута в работу вступает система поиска пути. Данная система содержит в себе алгоритмы поиска пути по графу, которым и представлено расположение кабинетов внутри здания. Результатом работы системы является список вершин, которые находятся между стартовой и конечной точкой, именуемый маршрутом.

Так как граф содержит большое количество промежуточных вершин, которые используются для более детального представления графа, полученный системой поиска пути маршрут нужно проанализировать и преобразовать к удобному для восприятия человека виду. С данной задачей справляется система анализа маршрута, которая преобразовывает сырой маршрут в список контрольных точек, по которым система будет направлять пользователя.

Заключительным этапом работы системы является окно отображения маршрута пользователю. В данном окне отображается список контрольных точек, полученный в результате работы системы анализа маршрута. Список контрольных точек отображается в виде карточек, смахивая которые пользователь перемещается к следующему или предыдущему элементам списка.

Подсистема поиска маршрута

Самой главной составляющей системы навигации является система поиска пути. Система поиска пути занимается определением оптимального маршрута между двумя точками

Основой алгоритма поиска пути является исследование вершин графа, передвигаясь по смежным вершинам от начальной заданной вершины до конечной заданной вершины. Для нахождения самого короткого маршрута за наименьшее количество времени алгоритм поиска пути использует еще и предсказания. Предсказания это результат некоторой эвристической функции, в нашем случае предсказанием будет являться расстояние по прямой от вершины, которая анализируется, до конечной. Такие предсказания помогают алгоритму быстро передвигаться по вершинам графа в сторону конечной вершины, минуя анализ остальных смежных вершин. Для реализации алгоритма поиска пути с предсказаниями вершины графа должны хранить относительные координаты, чтобы между каждыми двумя точками можно было вычислить расстояние по прямой.

В результате работы алгоритма создается список вершин от конечной вершины до начальной вершины, который и является найденным путем. Полученный список необходимо инвертировать, чтобы порядок следования вершин был от начальной вершины до конечной вершины. Результирующий список вершин передается в систему анализа маршрута.

Подсистема анализа маршрута

Граф, моделирующий структуру помещений внутри зданий, может иметь большое количество технических вершин, которые нужны для большей детализации маршрутов, но такие вершины не нужно выводить пользователю. Таким образом, полученный от системы поиска пути граф необходимо проанализировать и преобразовать в понятный пользователю формат.

Существует несколько видов технических вершин, такие как фрагменты коридоров, лестницы, пролеты лестниц. Данные типы вершин нужно анализировать по-разному, поэтому в системе навигации выделена система анализа маршрута.

При построении маршрута в его состав может входить большое количество фрагментов коридоров, особенно это будет заметно при построении маршрута между кабинетами в разных частях здания или на разных этажах. Нет необходимости отображать пользователю каждый фрагмент коридора, поэтому весь отрезок маршрута, который состоит только из вершин такого типа, собирается в одну путевую карточку, а расстояние всех вершин отрезка суммируется.

Лестницы представляют собой непростую структуру, поэтому их тоже необходимо анализировать и вывести пользователю корректную информацию о том, сколько этажей ему нужно пройти и в каком направлении, а именно подняться или спуститься. На графе лестницы представляют собой некую структуру из типовых вершин, а именно из вершины самой лестницы и лестничного пролета. Данная структура принята неспроста, вершины лестниц позволяют легко отследить отрезок вершин маршрута, где начинается и заканчивается перемещение по лестнице, а вершины лестничных пролетов позволяют легко отследить, сколько этажей потребуется пройти на данном отрезке.

Построение графа помещений

Граф помещений здания является главным и, по сути, единственным источником данных для системы поиска пути. Для выбранного нами в предыдущем разделе алгоритма поиска пути граф должен обладать определенными свойствами, а именно для любой вершины в графе значение эвристической оценки должно быть меньше или равно весу кратчайшего пути. Данное условие обеспечивает оптимистичную эвристическую оценку, так как она предполагает, что стоимость решения поиска пути меньше, чем оно есть на самом деле.

Для построения графа вершины графа должны иметь следующую информацию:

• Наименование вершины;
• Идентификатор вершины;
• Эвристическая дистанция от входа;
• Эвристическая высота от входа.

В рассматриваемой системе объектом навигации выступает здание учебного корпуса. Для большей наглядности, граф для навигации спроецирован на план здания (рисунок 4). На графе отчетливо видно вершины, отвечающие за кабинеты, специальные вершины, отвечающие за коридор, а также вершины лестниц. Для соединения этажей служат лестничные пролеты. Однако это не отменяет того, что подобный граф можно спроектировать для многих зданий, ведь сам граф не привязан к конкретному плану, как приведено на рисунке 5.

Пострение графа помещений

Для функционирования системы поиска и построения маршрутов необходим набор структур данных.

Одной из таких структур является помещение здания. Данная структура нуждается в нескольких реализациях. Во-первых, для модулей ввода начальных данных нужен список помещений, а именно список структур со следующими полями: наименование помещения, идентификатор помещения и тип помещения.

Так как в списке будет разделение помещений по типу, то данная информация должна присутствовать в структуре данных. Однако для помещения как вершины графа навигации, данные о типе помещения не нужны, в данной реализации необходимы поля для эффективной работы алгоритмов системы поиска пути. Поэтому данная реализация структуры данных должна включать следующие поля: идентификатор помещения, наименование помещения, список смежных вершин и эвристические координаты.

Также данная реализация структуры данных должна иметь поля, необходимые для корректной работы алгоритмов системы поиска пути, а именно: стоимость пути, значение эвристической функции и идентификатор родительской вершины.

Такие поля как стоимость вершины и значение эвристической функции будут использованы в расчетах системы поиска пути, для нахождения самого короткого маршрута между точками, указанными в начальных данных системы навигации. Идентификатор родительской вершины необходим для выделения, найденного системой поиска пути, маршрута.

Выбранный алгоритм в качестве алгоритма поиска пути, для выполнения своей задачи использует эвристическую функцию, а это значит, что для корректной работы алгоритма необходима не только информация о расстоянии между вершинами графа, но и эвристические координаты для каждой вершины графа.

Для полноценной реализации графа, как структуры данных, помимо вершин графа необходимо наличие еще и ребер графа. Ребра графа должны нести информацию о взаимосвязях между вершинами, а значит должны иметь следующие поля: идентификатор ребра, идентификаторы вершин, которые соединяет ребро и расстояние между вершинами.

Интерфейс системы поиска и построения маршрутов внутри помещений

Разработанная система представляет собой мобильное приложение для операционной системы Android. При запуске приложения на экране появляется стартовый экран (рисунок 6), на котором находится кнопка запуска системы навигации и информация о системе навигации, а также краткое руководство пользователя.

Окно выбора текущего местоположения пользователя (рисунок 6) выполнено в форме диалога, текст «Где вы находитесь?» в самом начале призывет к выбору вариантов из списка. Ниже находится список возможных местоположений, так как система основана на ключевых точках – этот список фиксирован. Список выполнен в виде двух колонок, пункты списка помечены цветом в зависимости от типа элемента – типа аудитории или помещения. Так как не все элементы списка помещаются на окне устройства список имеет функцию скроллинга – содержимое списка может перемещаться в вертикальном направлении.

При нажатии на любой элемент списка появляется окно выбора конечной точки маршрута (рисунок 6). Данное окно имеет схожую компоновку – надпись и список локаций. Окно также выполнено в форме диалога, за исключение того, что предыдущее окно необходимо для ввода текущего местоположения пользователя, а в этом окне пользователь выбирает в какую локацию ему необходимо построить маршрут.

После выполнения всех действий по вводу начальных данных и работы системы навигации на экране появляется окно отображения маршрута, которое состоит из рабочей области, на которой отображаются карточки путевых точек (рисунок 7). Перемещение по путевым карточкам выполняется с помощью свайпа – управляющего жеста, при котором палец кладут на экран и проводят в каком-либо направлении. Данный метод управления отлично подходит для устройств с сенсорным экраном.

Для перемещения на следующую путевую карточку нужно сделать свайп влево. В процессе свайпа текущая путевая карточка перемещается вместе с пальцем пользователя, а из-под текущей карточки появляется следующая путевая карточка. После того как пользователь убирает палец от сенсорного экрана анимация перемещения карточек плавно завершается и следующая путевая карточка занимает место текущей путевой карточки. Если необходимо вернутся на предыдущую путевую карточку, то следует сделать свайп вправо, тогда текущая путевая карточка начнет перемещение вслед за пальцем пользователя, а с левой стороны рабочей области из-под текущей карточки начнет появляться предыдущая путевая карточка. Данный процесс завершается аналогично переходу на следующую путевую карточку

Если необходимо построить маршрут к другому кабинету или помещению, то нужно нажать на устройстве кнопку «назад», осуществится переход на окно выбора конечной точки маршрута. Если же текущее местоположение пользователя изменилось, то, находясь в окне выбора конечной точки маршрута, необходимо нажать на устройстве кнопку «назад», тогда произойдет переход на окно выбора текущего местоположения. После ввода необходимых начальных данных система навигации построит новый маршрут.

Заключение

Рассмотренная система поиска и построения маршрутов внутри помещений позволяет минимизировать объем одновременно отображаемой навигационной информации и обеспечивает удобство работы пользователю.

Список использованной литературы

1. NFC Internal: An Indoor Navigation System [Электронный ресурс] / Busra Ozdenizci, Vedat Coskun, Kerem Ok // The National Center for Biotechnology Information. 2015. 27 марта. – Режим доступа: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4431189/ - Загл. с экрана.
2. Алгоритм Дейкстры нахождения кратчайшего пути [Электронный ресурс]. – Режим доступа: https://prog-cpp.ru/deikstra/
3. Tproger: Алгоритмы поиска пути в графе [Электронный ресурс]. 2016. 27 июля. – Режим доступа: https://tproger.ru/articles/pathfindings/
4.Шлыков А.А., Абрамова О.Ф. Исследование проблемы навигации внутри современных зданий со сложной архитектурой // Современная техника и технологии. 2014. № 2 [Электронный ресурс]. – Режим доступа: http://technology.snauka.ru/2014/02/3085
5. Алгоритм А* [Электронный ресурс]. – Режим доступа: https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_A*