[Перевод] Переосмысление GPS: Разработка системы позиционирования нового поколения в Uber
Определение местоположения и навигация с использованием глобальной системы позиционирования (GPS) глубоко проникли в нашу повседневную жизнь, и они в частности критичны для сервисов Uber. Для организации быстрых и эффективных подборов, нашим GPS технологиям необходимо знать положение сопоставленных пассажиров и водителей, а так же предоставлять навигационное руководство от текущего положения водителя к месту откуда нужно забрать пассажира, и затем до необходимого места назначения. Для наиболее плавной работы подобной системы, определение местоположения для пассажиров и водителей должно быть настолько точным насколько это возможно.
После запуска (буквально) GPS в 1973, мы стали понимать наш мир лучше, испытали экспоненциальный рост вычислительных мощностей доступных нам, и разработали мощные алгоритмы для моделирования неопределённостей из областей, как робототехника. Несмотря на то что наши жизни стали всё больше зависеть от GPS, фундаментальные основы, то есть как GPS работает, не сильно изменились, что приводит к существенным ограничениям производительности. По нашему мнению, настало время для переосмысления некоторых из начальных допущений, которые были верны в 1973, относительно того где и как мы используем GPS, соотвественно и вычислительная мощность и дополнительная информацию, которую мы можем использовать для улучшения результатов.
GPS работает хорошо под ясным небом, но его приближение позиции может быть дико неточным (с погрешностью в 50 метров и более) там где точность нужна нам больше всего: в густо населённых и застроенных высотками городских районах, там где расположено множество наших пользователей. Для преодоления этой проблем, мы разработали апгрейд для программного обеспечения GPS на Android, что существенно улучшило точность определяемой позиции в городском окружении посредством клиент-серверной архитектуры, которая использует 3D карты и проводит сложные вероятностные вычисления на GPS данных доступных через Android GNSS API.
В этой статье мы обсудим почему GPS может плохо справляться в городском окружении и подведём итог, как мы исправили это используя продвинутые алгоритмы обработки сигналов, развёрнутые в масштабе на нашей серверной инфраструктуре.
Изображение 1: GIF выше показывает сравнение стандартного GPS (красный) против нашего улучшенного приближения позиции (синий) для подбора из Uber HQ в Сан Франциско. Наше приближенное местоположение оказалось очень близко к настоящему пути пассажиру, а GPS показал значительные отклонения.
Немного бэкграунда GPS/GNSS
Перед подробным обсуждением нашего подхода, давайте кратко резюмируем то как работает GPS, для того чтобы понять почему он может быть неточным в многоэтажной городской среде.
GPS это сеть из более чем 30 спутников управляемых правительством США, находящихся на орбите земли на высоте около 20 тысяч километров. (Большинство смартфонов в наши дни, так же могут получать сигнал похожих Русских спутников «ГЛОНАСС».) Эти спутники посылают радиочастотные сигналы которые GPS приемники, как находящиеся в смартфонах, могут фиксировать. Важно, что эти спутники оповещают о времени, когда они запустят эти сигналы.
Для каждого спутника, чей сигнал обрабатывает приёмник, разница между временем получения и временем запуска (время полёта), умножается на скорость света, полученная величина называется псевдодистанцией. Если часы спутника и получателя синхронизированы, и сигнал перемещается по линии прямой видимости, тогда эта величина будет равна реальной дистанции до спутника. Однако, часы не синхронизированы, так что приёмнику необходимо решить уравнение из четырёх неизвестных, его собственные 3D координаты на сфере, и отклонение часов. Таким образом, нам необходимо минимум четыре спутника (четыре уравнения) для получения этих четырёх неизвестных.
Если мы проигнорируем отклонение часов, мы интуитивно можем интерпретировать приближение локации, произведённого GPS приёмником, пересечением сфер с центром на спутниках и радиусом каждой сферы заданной псевдодистанцией. На практике, приёмник GPS обрабатывает сигналы от значительно большего числа спутников (до 20 GPS и ГЛОНАСС спутников видимых в открытом поле), и получение большего, чем минимальное, число уравнений предоставляет дополнительную устойчивость к шуму, преградам и т.д. В дополнении к GPS и ГЛОНАСС, некоторые новые/будущие приёмники могут/смогут обрабатывать сигналы от других спутниковых систем. Некоторые другие запускаемые навигационные спутниковые системы Galileo, управляемый Европейским Союзом, IRNSS в Индии и BeiDou, управляемый Китаем. Более общий термин GNSS (глобальная навигационная спутниковая система) охватывает эти системы. (Мы будем использовать этот термин далее.)
Изображение 2: В этой упрощённой интерпретации вычислений приёмника GPS, сферы пересекаются в центре известных местоположений спутников.
Почему GNSS локация неточна в городской среде
Очень сильное утверждение находится за позиционированием основанном на GNSS, то что приёмник имеет линию прямой видимости до каждого спутника, чью псевдодистанцию он вычисляет. Этот механизм хорошо работает на открытой местности, но в городской среде он работает плохо, как показано на изображении 3, ниже:
Изображение 3: Ограничение прямой видимости и сильное отражение может вызвать большие погрешности GPS.
Здания очень часто ограничивают прямой обзор спутников, так что приёмник обрабатывает сигналы соотвествующие отражению от других зданий. Существенная неточность (положительное смещение) в псевдодистанции получающаяся из этого явления может вести к погрешностям в приближении положения, которые могут достигать 50 или более метров в городских каньонах. Большинство из нас, кто передвигался пешком, или на машине, или заказывал Uber в больших городах испытывал эти проблемы на себе.
Сила сигналов спутников к спасению
Наш подход к увеличению точности определения локации создаёт особенность из каждого ограничения GNSS сигнала, которое создаёт проблемы для стандартных приёмников. Как? Для Android телефонов, LocationManager API предоставляет не только приблизительное положение телефона, но и показатель сигнал-к-шуму (SNR) для каждого видимого GNSS спутника. Если мы сопоставим информацию о «силе сигнала» с 3D картами, тогда мы сможем получить очень ценную информацию о позиции. Изображение 4, ниже, показывает упрощённую версию того, как SNR спутников и 3D карты могут быть использованы для предположения на какой стороне улицы мы находимся:
Изображение 4: Сила сигнала спутников, в сочетании с 3D картами, предоставляет очень ценную информацию о местоположении.
Погружаясь в детали, наш подход основан на помещение следующего предположения в математические рамки: если SNR для спутника низок, тогда путь линии прямой видимости возможно ограничен или затенён; если SNR высок, тогда LOS (линия прямой видимости) возможно чиста. Спецификатор «возможно» критичен здесь: даже если приёмник находится в теневой зоне, сильно отражённые сигналы, всё ещё могут достигнуть его, и даже если он находится в чистой местности, полученный сигнал может быть слаб (из-за разрушительной интерференции между LOS и отражёнными путями, явление относящееся к многопутевому затуханию). Так же в большинстве случаем, 3D карта не до конца точна, и определённо не передаёт случайные ограничения большими двигающимися объектами не отражёнными на карте, как грузовики. Это добавляет неопределённость в процесс.
Вероятностное сопоставление теней с использованием трассировки лучей
Несмотря на то что интуитивное предположение, что сила сигнала спутников несёт в себе полезную информацию о местоположении звучит хорошо, оно должно быть конкретизировано с использованием вероятностных рамок. Для любого возможного положения приёмника, мы можем проверять заблокирован ли луч из этого положения до спутника на нашей 3D карте. Теперь, используя модель для распределения вероятности SNR под LOS и теневых условий, мы определяем наиболее вероятное значение SNR для этого спутника. Например, если положение затенено, тогда вероятность высокого SNR мала. Общая вероятность заданной позиции, основана на SNR спутников, это произведение вероятностей относящихся к разным спутникам. Делая это на сетке возможных положений, мы получаем вероятностную поверхность — или тепловую карту возможных положений приёмника, основанную только на силе сигнала спутников. Мы называем эту процедуру вероятностным сопоставлением теней.
Изображение 5: Трассировка лучей от одного возможного местоположения до каждого спутника для вероятностного сопоставления теней. Это делается для тысяч вероятных местоположений.
Вероятностная поверхность или тепловая карта, от вероятностного сопоставления теней объединяет информацию от измерений SNR спутников. Как бы то ни было, как мы видим на Изображении 6 ниже, эта тепловая карта может быть очень сложна. Она может иметь множество обособленных, сильно разделённых горячих точек (локальных максимумов) зачастую отвечающих заданной стороне улицы, но иногда и неправильным позициям (например фантомам). Для того чтобы сузить наше приближение позиции и избежать наводку на фантомов, мы должны соединить эту информацию с ещё большим её количеством.
Изображение 6. Тепловая карта позиций вычисленная с использованием сил сигнала спутников может иметь множество горячих точек. В приведённом выше примере, наше улучшенное приближение позиции (синий путь, чёрный эллипс с неопределённостью) следует за действительным путём (жёлтый путь), в то время как обычный GPS (красный путь, серый эллипс с неопределённостью) неточен.
Сочетание информации через частичный фильтр
Для Android телефонов, информация которую мы используем в дополнение к силе сигнала спутников, это обычно стандартное исправление позиции GNSS, но так же может быть и Android Fused позиция, которая может включать в себя основанное на Wi-Fi позиционирование. Поскольку данная локация может быть весьма неточна, одноразовое мгновенное сочетание стандартного исправления GNSS с вероятностным теневым сопоставлением обычно ведёт к плохой производительности. Для того чтобы получить преимущество от информации о силе сигналов спутников, мы доверяем GPS меньше в застроенных районах (серый эллипс неопределённости GPS на изображении 6 это обычная модель, которую мы используем, а чёрный эллипс неопределённости для улучшенного GPS это результат нашего алгоритма). Затем мы используем предыдущие измерения и накладываем ограничения на изменения позиции со временем, используя модель адаптированную для приложения (например, пешеход против автомобиля). Мы достигаем этого с использованием частичного фильтра, который аппроксимирует вероятности распределения позиций приёмника в любой заданный момент времени набором взвешенных частиц. Другими словами, мы предполагаем где находится телефон, используя тысячи возможных локаций (т.е., частицы).
Со временем, вероятностные веса и местоположения частиц прогрессирует на основе измерений и модели движения. Поскольку тепловая карта от вероятностного сопоставления теней имеет так много локальных максимумов и поскольку GNSS исправление может иметь такие большие выбросы, мы не можем использовать обычную технику, как фильтр Калмана или расширенный фильтр Калмана, который основывается на отслеженной вероятности распределения хорошо приближаемой Гауссовым распределением, имеющим форму колокольчика. Частичный фильтр позволяет нам приближать произвольное распределение, в обмен на бОльшую сложность, и здесь в игру вступает наша серверная архитектура.
Изображение 7: Приближение местоположения полученное, как взвешенный центроид горячих точек, предоставленное частичным фильтром часто исправляет очень большие погрешности GPS. Радиус неточности (белый круг) для улучшенного GPS основан на срезе набора частиц, и зачастую является более реалистичным измерением, чем малый радиус неточности (чёрный круг) обычно возвращаемым чистым GPS даже когда погрешности позиции велики.
От обработки сигнала к масштабному ПО
Сочетание частичного фильтра и трассировки лучей добавляет сложности к экосистеме бекенд серверов, с получением очень stateful сервисов.
Изображение 8: Улучшенная система GPS Uber состоит из сервиса частичного фильтра, сервиса управления 3D карт тайлами, сервиса менеджера, Uber HTTP API, и облачного хранилища и интегрируется с другими сервисами Uber.
В игре находится два типа состояния: состояние частичного фильтра для каждого пользователя и 3D карты, используемые для трассировки лучей, порегионно. Использование частичного фильтра требует уровня серверной афинности. Каждый новый запрос к нашему сервису должен быть направлен к тому же бекенд серверу для обработки, для того чтобы обновить правильный частичный фильтр. Дополнительно, из-за большого размера 3D карт, каждый бекенд сервер может содержать некоторое малое количество 3D мира в оперативной памяти.
Поскольку каждый сервер может содержать только несколько квадратных километров данных карт, не все сервера способны обслужить всех пользователей. Реализация бекенд системы для нашего решения потребовало создание слоя маршрутизации сессий, который берёт в расчёт 3D карту сервера. В дополнение к внутренним тестам и оценке производительности, мы так же запустили проверку на наших собственных Android устройствах, используя внутреннюю версию приложения Uber для водителей, что проиллюстрировано на Изображении 9, ниже:
Изображение 9: Сравнение красной/синей точки в нашей внутренней версии приложения для водителей, позволило работникам Uber проверить наше решение где угодно в мире.
Двигаясь вперёд
Точное определение положения пассажира и водителя является очень важным условием для исполнения миссии Uber для предоставления транспорта с такой же надёжностью, что и доставка воды везде и для всех. Для достижения нашей миссии, наши команды Sensing, Intelligence и Research работают над целым рядом подходов для улучшения определения позиции с креативным использованием сенсоров и вычислений на мобильных устройствах, в сочетании с вычислительной мощностью нашей серверной инфраструктуры. Сочетание продвинутой обработки сигналов, алгоритмов машинного обучения и ПО в масштабе имеет огромный потенциал, и мы всегда ищем талантливых и высокомотивированных личностей (инженеров ПО и алгоритмов, инженеров визуализации данных и инженеров машинного обучения), для присоединения к нам и помощи в реализации этого потенциала.
Danny Iland, Andrew Irish, Upamanyu Madhow, & Brian Sandler являются членами Uber«s Sensing, Inference и Research team. Danny, Andrew, и Upamanyu были частью оригинальной группы, которая вела это исследование в университете Калифорнии, Санта Барбара. После запуска этой работы в качестве стартапа, они продемонстрировали серверное частичное фильтрование для улучшения определения позиции в Сан Франциско, используя 3D карты созданные с использованием общедоступных данных с воздушного LiDAR. Они присоединились к Uber в Июле 2016.
