Навигация в закрытых помещениях – от идеи до рабочего прототипа

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

Что такое система позиционирования во внутренних помещениях?

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

Почему бы не использовать GPS?

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

Почему мы этим занимаемся

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

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

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

Необходимое оборудование

• iPhone с iOS 8.0 или выше. Желательно, чтобы в устройстве был установлен процессор движения (M7/M8).
• BLE-маячки. Это, возможно, самый дешевый вариант для Bluetooth-соединения с емкой батареей, средним радиусом работы (15 – 30 метров) и поддержкой конфигурации UDID/Major/Minor.

Современные подходы к решению проблем

• Триангуляция и трилатерация – два математических подхода, полагающихся на шкалы «угол» и «дистанция», соответственно. У них схожие принципы — поиск локуса точек пересечения, хорошая работоспособность в лабораторной среде (незначительный шум, предел видимости маячков и т. д.) и средние или неудовлетворительные результаты при работе в живой среде в связи с несколькими пересечениями или их отсутствием.
• Сетчатость — маячки расположены по сетчатому шаблону. В каждый момент времени ваше устройство будет находиться в зоне видимости ограниченного числа маяков, позволяя вам грубо определить своё местоположение.
• Продвинутые подходы к фильтрации (фильтры частиц и фильтры Калмана) – используют теорию вероятности и сложные математические модели чтобы снизить эффект от шума и настроить коэффициенты фильтрации при изменении местоположения, мощности сигнала и т. д.
• Гибридные системы – объединяют два или более подходов, описанных выше, чтобы свести к минимуму ошибки при определении местоположения, или для переключения между подходами в зависимости от внешних условий.

Основные проблемы

Многолучевое распространение и затухание сигнала. Системы навигации в закрытых помещениях, основанные на BLE, все полагаются на электромагнитные волны. Это может привести или к неверным показаниям с маячков, которые находятся далеко от пользователя, или к:

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

Некоторые технические детали текущей реализации

Первая проблема, с которой мы столкнулись, связана непосредственно с картой. «В чем проблема? — спросите вы. — MapKit позволяет использовать пользовательские элементы. Если и это не помогает — используйте OSM и MapBox». Да, всё так, но, если вы используете MapKit, в конечном итоге сталкиваетесь с массой препятствий:

• Элементы должны быть выровнены и подогнаны по размерам в соответствии с уже существующей сеткой создаваемой карты.
• План здания выполнен в плоскости, карты используют Меркаторову проекцию.

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

Второй (и главной) проблемой стал, конечно, поиск текущего местоположения. Мы протестировали и трилатерацию, и триангуляцию в двухмерном пространстве, но результаты были существенно подпорчены отсутствием Z-координат. После переключения на 3D (каждый маяк имеет координаты Vx, Vy, Vz), дела пошли лучше, но не настолько, насколько ожидалось.

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

Перспективы

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

• Обнаружение движения для осуществления адаптивной фильтрации, что позволит вносить изменения в алгоритм фильтрации на лету или настраивать ее коэффициенты.
• Более утонченное решение проблемы «исчезающих маячков» — введение уровня доверия показаниям маячка и его порогового значения, чтобы полагаться на «доверенные» маячки в каждой итерации.
• Более утонченный «геометрический фильтр» для направления движения и определения поворотов.
• Метаданные — график маршрутов и промежуточных пунктов («перекрестков», POI и т. д.).
• Опция «Привязать текущую позицию к сетке», как это делается в реальных картах и навигационных приложениях.
• Алгоритм маршрутизации для поиска (кратчайшего) пути.

Автор: Ярослав Воронцов, Senior iOS Developer.