Хабрахабр

[Перевод] Переосмысление GPS: Разработка системы позиционирования нового поколения в Uber

image

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

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

Для преодоления этой проблем, мы разработали апгрейд для программного обеспечения GPS на Android, что существенно улучшило точность определяемой позиции в городском окружении посредством клиент-серверной архитектуры, которая использует 3D карты и проводит сложные вероятностные вычисления на GPS данных доступных через Android GNSS API. GPS работает хорошо под ясным небом, но его приближение позиции может быть дико неточным (с погрешностью в 50 метров и более) там где точность нужна нам больше всего: в густо населённых и застроенных высотками городских районах, там где расположено множество наших пользователей.

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

Наше приближенное местоположение оказалось очень близко к настоящему пути пассажиру, а GPS показал значительные отклонения. image
Изображение 1: GIF выше показывает сравнение стандартного GPS (красный) против нашего улучшенного приближения позиции (синий) для подбора из Uber HQ в Сан Франциско.

Немного бэкграунда GPS/GNSS

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

(Большинство смартфонов в наши дни, так же могут получать сигнал похожих Русских спутников "ГЛОНАСС".) Эти спутники посылают радиочастотные сигналы которые GPS приемники, как находящиеся в смартфонах, могут фиксировать. GPS это сеть из более чем 30 спутников управляемых правительством США, находящихся на орбите земли на высоте около 20 тысяч километров. Важно, что эти спутники оповещают о времени, когда они запустят эти сигналы.

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

На практике, приёмник GPS обрабатывает сигналы от значительно большего числа спутников (до 20 GPS и ГЛОНАСС спутников видимых в открытом поле), и получение большего, чем минимальное, число уравнений предоставляет дополнительную устойчивость к шуму, преградам и т.д. Если мы проигнорируем отклонение часов, мы интуитивно можем интерпретировать приближение локации, произведённого GPS приёмником, пересечением сфер с центром на спутниках и радиусом каждой сферы заданной псевдодистанцией. Некоторые другие запускаемые навигационные спутниковые системы Galileo, управляемый Европейским Союзом, IRNSS в Индии и BeiDou, управляемый Китаем. В дополнении к GPS и ГЛОНАСС, некоторые новые/будущие приёмники могут/смогут обрабатывать сигналы от других спутниковых систем. (Мы будем использовать этот термин далее.) Более общий термин GNSS (глобальная навигационная спутниковая система) охватывает эти системы.

image
Изображение 2: В этой упрощённой интерпретации вычислений приёмника GPS, сферы пересекаются в центре известных местоположений спутников.

Почему GNSS локация неточна в городской среде

Этот механизм хорошо работает на открытой местности, но в городской среде он работает плохо, как показано на изображении 3, ниже: Очень сильное утверждение находится за позиционированием основанном на GNSS, то что приёмник имеет линию прямой видимости до каждого спутника, чью псевдодистанцию он вычисляет.

image
Изображение 3: Ограничение прямой видимости и сильное отражение может вызвать большие погрешности GPS.

Существенная неточность (положительное смещение) в псевдодистанции получающаяся из этого явления может вести к погрешностям в приближении положения, которые могут достигать 50 или более метров в городских каньонах. Здания очень часто ограничивают прямой обзор спутников, так что приёмник обрабатывает сигналы соотвествующие отражению от других зданий. Большинство из нас, кто передвигался пешком, или на машине, или заказывал Uber в больших городах испытывал эти проблемы на себе.

Сила сигналов спутников к спасению

Как? Наш подход к увеличению точности определения локации создаёт особенность из каждого ограничения GNSS сигнала, которое создаёт проблемы для стандартных приёмников. Если мы сопоставим информацию о «силе сигнала» с 3D картами, тогда мы сможем получить очень ценную информацию о позиции. Для Android телефонов, LocationManager API предоставляет не только приблизительное положение телефона, но и показатель сигнал-к-шуму (SNR) для каждого видимого GNSS спутника. Изображение 4, ниже, показывает упрощённую версию того, как SNR спутников и 3D карты могут быть использованы для предположения на какой стороне улицы мы находимся:

image
Изображение 4: Сила сигнала спутников, в сочетании с 3D картами, предоставляет очень ценную информацию о местоположении.

Спецификатор «возможно» критичен здесь: даже если приёмник находится в теневой зоне, сильно отражённые сигналы, всё ещё могут достигнуть его, и даже если он находится в чистой местности, полученный сигнал может быть слаб (из-за разрушительной интерференции между LOS и отражёнными путями, явление относящееся к многопутевому затуханию). Погружаясь в детали, наш подход основан на помещение следующего предположения в математические рамки: если SNR для спутника низок, тогда путь линии прямой видимости возможно ограничен или затенён; если SNR высок, тогда LOS (линия прямой видимости) возможно чиста. Это добавляет неопределённость в процесс. Так же в большинстве случаем, 3D карта не до конца точна, и определённо не передаёт случайные ограничения большими двигающимися объектами не отражёнными на карте, как грузовики.

Вероятностное сопоставление теней с использованием трассировки лучей

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

Это делается для тысяч вероятных местоположений. image
Изображение 5: Трассировка лучей от одного возможного местоположения до каждого спутника для вероятностного сопоставления теней.

Как бы то ни было, как мы видим на Изображении 6 ниже, эта тепловая карта может быть очень сложна. Вероятностная поверхность или тепловая карта, от вероятностного сопоставления теней объединяет информацию от измерений SNR спутников. Для того чтобы сузить наше приближение позиции и избежать наводку на фантомов, мы должны соединить эту информацию с ещё большим её количеством.
image
Изображение 6. Она может иметь множество обособленных, сильно разделённых горячих точек (локальных максимумов) зачастую отвечающих заданной стороне улицы, но иногда и неправильным позициям (например фантомам). В приведённом выше примере, наше улучшенное приближение позиции (синий путь, чёрный эллипс с неопределённостью) следует за действительным путём (жёлтый путь), в то время как обычный GPS (красный путь, серый эллипс с неопределённостью) неточен. Тепловая карта позиций вычисленная с использованием сил сигнала спутников может иметь множество горячих точек.

Сочетание информации через частичный фильтр

Поскольку данная локация может быть весьма неточна, одноразовое мгновенное сочетание стандартного исправления GNSS с вероятностным теневым сопоставлением обычно ведёт к плохой производительности. Для Android телефонов, информация которую мы используем в дополнение к силе сигнала спутников, это обычно стандартное исправление позиции GNSS, но так же может быть и Android Fused позиция, которая может включать в себя основанное на Wi-Fi позиционирование. Затем мы используем предыдущие измерения и накладываем ограничения на изменения позиции со временем, используя модель адаптированную для приложения (например, пешеход против автомобиля). Для того чтобы получить преимущество от информации о силе сигналов спутников, мы доверяем GPS меньше в застроенных районах (серый эллипс неопределённости GPS на изображении 6 это обычная модель, которую мы используем, а чёрный эллипс неопределённости для улучшенного GPS это результат нашего алгоритма). Другими словами, мы предполагаем где находится телефон, используя тысячи возможных локаций (т.е., частицы). Мы достигаем этого с использованием частичного фильтра, который аппроксимирует вероятности распределения позиций приёмника в любой заданный момент времени набором взвешенных частиц.

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

Радиус неточности (белый круг) для улучшенного GPS основан на срезе набора частиц, и зачастую является более реалистичным измерением, чем малый радиус неточности (чёрный круг) обычно возвращаемым чистым GPS даже когда погрешности позиции велики. image
Изображение 7: Приближение местоположения полученное, как взвешенный центроид горячих точек, предоставленное частичным фильтром часто исправляет очень большие погрешности GPS.

От обработки сигнала к масштабному ПО

Сочетание частичного фильтра и трассировки лучей добавляет сложности к экосистеме бекенд серверов, с получением очень stateful сервисов.

image
Изображение 8: Улучшенная система GPS Uber состоит из сервиса частичного фильтра, сервиса управления 3D карт тайлами, сервиса менеджера, Uber HTTP API, и облачного хранилища и интегрируется с другими сервисами Uber.

Использование частичного фильтра требует уровня серверной афинности. В игре находится два типа состояния: состояние частичного фильтра для каждого пользователя и 3D карты, используемые для трассировки лучей, порегионно. Дополнительно, из-за большого размера 3D карт, каждый бекенд сервер может содержать некоторое малое количество 3D мира в оперативной памяти. Каждый новый запрос к нашему сервису должен быть направлен к тому же бекенд серверу для обработки, для того чтобы обновить правильный частичный фильтр.

Реализация бекенд системы для нашего решения потребовало создание слоя маршрутизации сессий, который берёт в расчёт 3D карту сервера. Поскольку каждый сервер может содержать только несколько квадратных километров данных карт, не все сервера способны обслужить всех пользователей. В дополнение к внутренним тестам и оценке производительности, мы так же запустили проверку на наших собственных Android устройствах, используя внутреннюю версию приложения Uber для водителей, что проиллюстрировано на Изображении 9, ниже:

image
Изображение 9: Сравнение красной/синей точки в нашей внутренней версии приложения для водителей, позволило работникам Uber проверить наше решение где угодно в мире.

Двигаясь вперёд

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

Danny, Andrew, и Upamanyu были частью оригинальной группы, которая вела это исследование в университете Калифорнии, Санта Барбара. Danny Iland, Andrew Irish, Upamanyu Madhow, & Brian Sandler являются членами Uber’s Sensing, Inference и Research team. Они присоединились к Uber в Июле 2016. После запуска этой работы в качестве стартапа, они продемонстрировали серверное частичное фильтрование для улучшения определения позиции в Сан Франциско, используя 3D карты созданные с использованием общедоступных данных с воздушного LiDAR.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть