Определение местоположения и навигация с использованием глобальной системы позиционирования (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.
Комментарии (78)
FreeNickname
21.04.2018 11:25+2Спасибо за статью. Но укажите, пожалуйста, ссылку на оригинал. Это абсолютно точно перевод, потому что ни один русскоязычный человек в здравом уме не напишет «Сила сигналов спутников к спасению» :) Если это компиляция нескольких статей с вашими авторскими доработками, то оформлять именно как перевод не нужно, но я был бы благодарен за ссылки на источники.
JustRoo
21.04.2018 11:30+3Под заголовком висит плашка перевода и ссылка на оригинал. Это старая проблема хабра, что если не знаешь, где их искать, не найдёшь.
FreeNickname
21.04.2018 11:49Ох. Спасибо! Давно не читал переводы. В курсе старой проблемы хабра, поэтому предварительно залез в футер, поглядел там, потом в хеадер, поглядел там в поисках старой иконки A->Z, или чего-то похожего, но не увидел. Вижу надпись «Перевод», но она так отдельно от всего, и особенно от, собственно, ссылки, что вообще является абсурдом, что даже сейчас, когда я знаю, где её искать, я и то секунды две шарю глазами по хеадеру статьи, пытаясь увидеть… Дичь)
GetJump, извините.
TimsTims
21.04.2018 13:15+1Давно не читал переводы
Значит, давно вы не читали Хабр)… Не считал, но довольно много статей — переводы. Хотя по-моему, в последние месяц-два количество переводов заметно снизилось.
GetJump
21.04.2018 13:03Я старался сделать текст более лёгким для восприятия русским человеком, но это сложно, если так же стараться донести некоторые исходные вещи.
Думаю если буду переводить в следующий раз, прибегну к пересказу.TrllServ
21.04.2018 15:48Я старался сделать текст более лёгким для восприятия русским человеком
Более привычно видеть LoF, чем LOF.
Ну или ЗПВ (зона прямой видимости).
«Тепловая карта» как-то неправильно. Температурная? Как на счёт вариантов «Зона покрытия»?GetJump
21.04.2018 18:01«Тепловая карта», как раз это распространённый термин. Вы про LOS (Line of Sight)?
Про ЗПВ согласен, но это больше характеризует именно зону, нежели прямую.
KirEv
21.04.2018 11:38сначала бы усовершенствовали позиционирование на открытой местности, потом в городе… до сих пор машину с полосы в полосу кидает )
интересно, какой на самом деле % из теории применен на практике.GetJump
21.04.2018 12:48Огромный, даже за популярным картографическим софтом стоит очень большой теоретический пласт, в том числе и современный.
Проблемы на открытой местности связаны, как раз с описанными в статье вещами, так и помимо этого, с слабыми приёмниками в большинстве мобильных устройств. Скажем, последние разработки в области GPS, показывают точность порядка 40 сантиметров, что уже весьма и весьма неплохо. А если в свою очередь использовать методики Sensor Fusion, что с точки зрения современной инфраструктуры позволяет существенно уточнять геопозицию.
New_iDimka
21.04.2018 12:49Добрый день.
А, что если разместить радиометки на всех точках пересечения плоскостей и тем самым дать электронным мозгам точную 3D картину нашего мира.
Всем беспилотным аппаратам и системам навигации станет намного легче, и не надо просчитывать сложные алгоритмы и тратить на это ресурсы.
Apache02
21.04.2018 15:14Ориентироваться по ближайшим BSSID не проще? В городах, по которым постоянно ездят машины со своим приложением, можно собирать статистику. Назначать рейтинг «стабильности» или «доверия» точкам.
GetJump
21.04.2018 18:03Внутри API Android, которое определяет геопозицию, есть функциональность, которая использует Wi-Fi для уточнения данных (Sensor Fusion) от GPS, помимо этого, если не изменяет память, там есть и возможность использования данных от базовых вышек.
Jef239
21.04.2018 15:50+4Отвратительный перевод технически плохо написанная рекламной статьи. В итоге -полное непонимание, что же предлагается.
Что касается перевода — от одного слова «псевдодистанция» — начинает тошнить. Реально используется термин "псевдодальность", причем псевдодальности по ГОСТ Р 52928-2010 бывают кодовые и фазовые. Для фазовых чащей говорят «псевдофаза.»
Остальные претензии — к низкому качеству самой статьи.
- Непонятно, о каких приемниках речь: L1, L1/L2, L1, L5. На L1 многолучевость может дать ошибку кодовых измерений на одном спутнике до 75 метров, на L2 или L5 — до 7.5 метров.
- Непонятно, о каких системах речь — о получающих поправки через интернет или о неполучающих. Для систем с поправками через инет важнее высокоточные эфемериды и ионосферная коррекция. И лишь после них идет влияние многолучевости. Поэтому невозможно оценить ни влияние на точность, ни экономический эффект.
- 50 метров — это суммарная ошибка псевдодальности одного спутника. Она дает точность порядка 3 метров КВО-50 координат.
- Если у спутника плохое отношение сигнал-шум, то он и так идет в решение с пониженным коэффициентом корреляции (или вообще исключается из решения). То есть метод из статьи — это лишь добавочная навигация по спутникам, не идущим в решение или идущим с пониженным коэффициентом корреляции.
- Предложенный метод может дать результаты для Нью-Йорка, но малополезен для Питера. Потому что в Питере — дожди. И капля воды на одной стороне антенны = даст тот же результат. А антенна внутри салона — бесполезна для таких измерений, ибо больше всего снижает S/N крыша автомобиля.
- Непонятны экономические затраты на создание модели в сравнении с затратами на переход на двухчастотные приемники. Особенно с учетом того, что broadcom собирается в этом году выпустить дешевые двухчастотные чипы с точностью 30 см КВО-50
GetJump
21.04.2018 17:53Отвратительный перевод технически плохо написанная рекламной статьи.
Пытался правильно расставить запятые, не получилось.
Что касается перевода — от одного слова «псевдодистанция» — начинает тошнить. Реально используется термин «псевдодальность», причем псевдодальности по ГОСТ Р 52928-2010 бывают кодовые и фазовые. Для фазовых чащей говорят «псевдофаза.»
Каюсь, никогда не изучал ГОСТЫ по данной тематике, да и не было потребности, а при подготовке статьи нашёл упоминание «псевдодистанция» в русскоязычной научной литературе, от чего и отталкивался.
Непонятно, о каких приемниках речь: L1, L1/L2, L1, L5. На L1 многолучевость может дать ошибку кодовых измерений на одном спутнике до 75 метров, на L2 или L5 — до 7.5 метров.
В статье практически с самого начала чётко ведётся речь о мобильных устройствах на платформе Android, в виду доступности API для взаимодействия с приёмником напрямую. По поводу конкретики не могу дать точного ответа, возможно вам стоит обратиться к авторам оригинальной статьи, но смею предположить что ответ будет разниться в зависимости от конкретного устройства.
Непонятно, о каких системах речь — о получающих поправки через интернет или о неполучающих. Для систем с поправками через инет важнее высокоточные эфемериды и ионосферная коррекция. И лишь после них идет влияние многолучевости. Поэтому невозможно оценить ни влияние на точность, ни экономический эффект.
Если я правильно вас понял, то вы ведёте речь о самом низком уровне, с которым как раз и взаимодействует система Android, и возможно прошивка самого приёмника. Я думаю здесь стоит обратиться к исходному коду Android, либо, как вариант к статьям посвященным реализации API на определённой версии Android.
50 метров — это суммарная ошибка псевдодальности одного спутника. Она дает точность порядка 3 метров КВО-50 координат.
Можете сослаться на подтверждённый источник в литературе? Смущает контекст: «суммарная ошибка» и «одного спутника».
Если у спутника плохое отношение сигнал-шум, то он и так идет в решение с пониженным коэффициентом корреляции (или вообще исключается из решения). То есть метод из статьи — это лишь добавочная навигация по спутникам, не идущим в решение или идущим с пониженным коэффициентом корреляции.
Как раз в статье утверждается, насколько я смог уловить, о том, что классический подход, в том числе и с пониженным коэффициентом работает плохо в условиях многоэтажек, а авторы предлагают подход с трёхмерными картами, которые увеличивают точность в этих условиях.
Предложенный метод может дать результаты для Нью-Йорка, но малополезен для Питера. Потому что в Питере — дожди. И капля воды на одной стороне антенны = даст тот же результат. А антенна внутри салона — бесполезна для таких измерений, ибо больше всего снижает S/N крыша автомобиля.
Это уже детали реализации, и в целом сторонняя проблема. Насчёт дождей, возможно, но есть мнение, что в данном случае большую ошибку внесёт именно облачность. Поправьте, если я не прав. Чаще всего, телефон монтируется на лобовое стекло, и приёмник имеет прямую видимость через него. Но да, по поводу крыши я с вами согласен.
Непонятны экономические затраты на создание модели в сравнении с затратами на переход на двухчастотные приемники. Особенно с учетом того, что broadcom собирается в этом году выпустить дешевые двухчастотные чипы с точностью 30 см КВО-50
Речь о покрытии существующих и новых пользователей приложения Uber и не только. Вы предлагаете отказаться от 100% существующих устройств и поддерживать только те, в которых будут установлены эти новые чипы Broadcom? Это не та область применения, где возможно взять и просто внедрить передовые хардварные решения. В массовый рынок, например телефонов, эти чипы будут приходить год — два, как это обычно и бывает.Jef239
21.04.2018 21:57при подготовке статьи нашёл упоминание «псевдодистанция» в русскоязычной научной литературе
Можно ссылочки? Если вы про статью от ААНИИ, то они под псевдодистанцией имеют ввиду расстояние между приемниками, измеренное при помощи GPS. Статья смешная, потому что люди использовали кодовые измерения вместо RTK из-за очень слабого знакомства с технологией. Но спасибо за наводку на возможного заказчика наших приборов.
но смею предположить что ответ будет разниться в зависимости от конкретного устройства.
Зря смеете. Андроиды — это дерьмовейшие чипы, только L1 без внешней коррекции. В лучшем случае — будет сырая псевдодальность и псведофаза. В худшем — только координаты.
Можете сослаться на подтверждённый источник в литературе? Смущает контекст: «суммарная ошибка» и «одного спутника»
Уже давал вам ссылку на вики с бюджетом ошибок, ссылка на пруф там есть. Если интересно подробнее — то скачиваете учебники по GPS и читаете. А что вас смущает? СКО суммарной ошибки псевдодальности считаются как корень из суммы квадратов СКО конкретных ошибок. КВО-99 — это 3 СКО. Так что из приведенных в Вики 13 метров СКО суммарной ошибки получается ± 40 метров КВО-99. Сейчас СКО ошибки бортовых эфемерид поменьше, чем в вики, зато у них в бюджете побольше СКО многолучевости. Кстати, margin of error — это КВО-99, то есть 3 СКО.
есть мнение, что в данном случае большую ошибку внесёт именно облачность. Поправьте, если я не прав.
Не правы. Облачность влияет слабо, ибо в тропофсере и так полно воды, из-за ненудевой влажности воздуха. Намного важнее длина пути через тропосферу — для спутников над головой это 10км, а а для спутников «сбоку» — больше. Так что даже в геодезии тропосферная модель считается на основе температуры и относительной влажности воздуха.
Чаще всего, телефон монтируется на лобовое стекло, и приёмник имеет прямую видимость через него.
Откуда же прямая видимость? Если монтировать на лобовое, то весь задний сегмент будет экранирован крышей. Мы, например, для высокоточки (5-7мм СКО) монтируем антенны прямо на крышу.
Старое видео с испытаний, антенки на крыше вполне видныpdima
22.04.2018 02:53Вы уверены что заменить смартфоны всем клиентам убера получится дешевле? Там же не тысяча машин а миллионы клиентов с смартфонами, которых необходимо найти и подобрать. Ну и не все согласятся поменять свой смартфон на смартфон с навигатором от убера.
Jef239
22.04.2018 03:23Менять смартфоны и так и так придется — нужные опции Android GNSS API пока поддерживает лишь пяток моделей.
Только это не для клиентов сделано. Клиент все равно выбирает точку на карте. Это для водительского навигатора важно — привести водителя в нужную точку. Ну и для автовождения, если они с какого-то перепугу решили его на андроиде сделать.
Nick_Shl
21.04.2018 17:43Никогда не испытывал проблем с GPS… пока не попал в Нью-Йорк. Но там кроме навигации ещё проблема с траффиком — 4 мили ехать час это занадто. Так что можно и по бумажной карте :)
iproger
22.04.2018 02:14Как-то слишком жестко. Чтобы избежать такого надо не брать такси в Манхеттене и из/в Бруклин. Все остальные дороги почти всегда зеленые или желтые.
Nick_Shl
24.04.2018 01:27Избежать такого было невозможно — ехали на машине по делам из другого штата. Всего ~1200 миль, конечный пункт — отель в Квинсе… но что бы туда добраться надо проехать Манхэттен. А приехали мы около 5 вечера в будний день. И вот когда хочется побыстрее вылезти из машины и размяться, такая подлянка с траффиком.
legrus
21.04.2018 22:10Подождите, люди что, не глядя на карту вызывают такси к точке, где их нашел убер? Там же специально можно точку встречи подвинуть куда удобно.
ProLimit
21.04.2018 23:11Видимо, точное позиционирование нужно не только для указания точки посадки. На нее могут быть завязаны многие функции сервиса. Навскидку: расчет стоимости поездки по расстоянию. Если у вас координата от GPS мечется в радиусе 50м, то очевидно вы точно не посчитаете пройденный путь. Также очевидно, что сервису хочется точно, знать где в каждый момент времени находится каждый таксист. Прокладка маршрута также часть системы и требует точного местоположения.
iproger
22.04.2018 02:16Видимо, не всегда. По опыту уже понял что надо ставить точку как можно дальше от зданий куда-нибудь на парковку. Водители просто отказываются понимать куда ехать даже им навигатор прямо показывает точку в 10 метрах.
unwrecker
22.04.2018 00:57Что только ни придумают лишь бы не встраивать инерциальную навигацию в телефоны...
Jef239
22.04.2018 01:03А что она, простите, даст? Нормальная БИНС, держащая 15 минут с СКО 1 метр стоит 200К рублей. А то, что есть в мобильниках — держит с нужной точностью всего пару минут.
kahi4
23.04.2018 21:20Не буду утверждать, но по наличию даже барометра, участвующего в навигации, в современных телефонах, могу предположить, что некая степень комплексирования используется, по крайней мере в iOS, но, как уже написал Jef239, МЭМС БИНС хватит разве что понять что вы куда-то там пошли, с примерной скоростью.
P.S. Интересно стало, какой уход у датчиков у современных телефонов, никто не тестировал?
TrllServ
24.04.2018 06:05Интересно стало, какой уход у датчиков у современных телефонов, никто не тестировал?
Уход?
Всмысле, отклонение или погрешность?
mSnus
22.04.2018 02:08При это только у Uber машина скачет по экрану, ездит по крышам домов и по воде… ни Yandex.Taxi, ни навигаторы на Google Maps, поверх которых построено приложение Uber, такую дичь себе не позволяют.
Ну и Яндекс научился справляться даже не то что с отраженными сигналами, но и с "кремлевскими глушилками", которые делали вид, что центр Москвы это аэропорт Внуково. Всегда очень точно показывает местоположение. Догоняй, Uber!)
iproger
22.04.2018 02:18Подтверждаю, скачет ещё как. Забавный был случай: отменил поездку и вызвал снова. Вызвался тот же водитель и сразу его позиция переместилась на несколько километров. Такое надо фиксить, конечно.
TimsTims
22.04.2018 02:18По статье сложилось впечатление, что на улицах ездят только uber, мобильники людям нужны для заказа такси, спутники GPS нужны только Uber'у. И навигацию на android тоже придумали uber.
И вместо того, чтобы спрашивать у пользователя, с какой стороны лучше подъехать, давайте лучше сделаем 3D-карты самого популярного города Сан-Франциско, будем перебирать варианты точек на кластере серверов, и подавать машину на 1 минуту быстрее.
vire
22.04.2018 02:22Я бы не сел в такую машину с предсказанием реальной позиции по теням зданий. Этот труд в продакшн не пойдет, я надеюсь.
Пора бы уже HD ГЛОНАСС. А там и hd карты подтянутся, а обновлять их будут автономные автомобили. Все упирается в точные координаты. Или нет?
Что необходимо чтобы у юзера на земле в любом утюге была точность 20 см?TrllServ
22.04.2018 06:12Что необходимо чтобы у юзера на земле в любом утюге была точность 20 см?
Проще тогда проще проставить радиомаяки на каждом здании выше 5 этажей, и научить приложения корректно их обрабатывать.
Хотя я с трудом понимаю для чего простому пользователю может понадобиться точность выше 1-2м.vire
22.04.2018 17:02Точность — это всегда хорошо! Подготовить инфраструктуру для автономных авто.
HD аннотированные карты с треками полос и перекрестков плюс глобальное позиционирование с сантиметровой точностью — разве не прелесть?
Не то что бы я не верю в силу нейронных сетей и лидаров всяких, но мне будет спокойнее, если электоводятел будет точно знать свои координаты и на карте тоже, а не мчать туда, куда он классифицировал как научили. Это как еще один слой данных, авто теперь железно знает где асфальт, какая полоса, а перекресток уже расчерчен — а-ля по рельсам.
TrllServ
23.04.2018 13:40Не то что бы я не верю в силу нейронных сетей и лидаров всяких, но мне будет спокойнее, если электоводятел будет точно знать свои координаты и на карте тоже, а не мчать туда, куда он классифицировал как научили
А я вот, что-то начинаю сомневаться.
Если электронный водятел, всего лишь такой же как человек, только быстрее и меньше устает, но всё так же может ошибиться из-за плохого нанесения разметки.
То я за прокладывание в асфальт спец.меток, просто у нас ведь разметки по полгода может не быть, то снег, то грязь, но не нанесли. Альтернативный вариант, так сказать.
mealse
22.04.2018 03:41ИМХО, довольно надуманная проблема и очень странное решение.
Всю статью можно свести — с помощью машинного обучения и какой-то там эвристики пытаемся увеличить точность. А как — ну технических деталей тут минимум. Как будут обучать все это дело вообще не понятно, ибо спутников много и они постоянно в разных частях неба, поэтому понять какое здание какую «тень» дает — очень проблематично. Для меня не понятно как будет реагировать зоопарк трубок на одну и ту же «тень».
По ВиФи гораздо проще обучиться — у них сигнал более стабильный для одной точки на местности. Собственно точность которую дает Гугл по ВиФи это подтверждает.
Развитие не стоит на месте, если 10 лет назад был фактически только GPS, то сейчас уже и Глонасс и Бейдоу работоспособны. Актутальные навигационные решения — мультисистемны.
Я в городах с небоскребами как Нью-Йорке не был, но в Мск проблем нет. Точность очень высокая, речь почти всегда идет о считанных метрах — ну это если трубка нормальная. Хотя все актуальное не смотря на уменьшение антенн дает очень хорошую точность. Я не про гарантированную какую-то, а реально получаемую.
ИТОГО: овчинка выделки не стоит, а решение вообще ИМХО вряд ли реализуемое.
ЗЫ: картинки с 4-мя сферами всегда улыбают… ну напишите просто — 4 неизвестных (время прибора + координаты в 3Д) — поэтому надо 4 уравнения для однозначного решения. 1 спутник — одно уравнение. А со сферами — бредово выглядит, когда их 4.awesomer
22.04.2018 17:16но в Мск проблем нет. Точность очень высокая, речь почти всегда идет о считанных метрах — ну это если трубка нормальная
А как именно вы определяете, что точность высокая?
mealse
23.04.2018 02:09Запускаю Яндекс карты и смотрю на ориентиры.
Не знаю как где, а в Мск на спутнике люди на карте видны — т.е. «понятно» с натяжкой а иногда и точно, что это человек — достаточно на людные места посмотреть. Поэтому по карте местоположение можно определить с метровой точностью. Тут накладывается конечно еще погрешность привязки карты — но если карта говорит, что я стою около зебры у края тротуара и я в реале стою около зебры у края тротуара — то я делаю вывод, что всего скорее точность идет на метр-два-три-четыре.
А вообще сам приемник может же точность выдавать всего скорее некую эвристическую.
Не знаю как оно делается, но очевидно, что если спутников больше чем четыре, то точного решения положения может и не быть. 4-ре уравнения, 4-ре неизвестных — все неплохо. А вот если уравнений 4+, то для реальных данных почти всегда будет обломс.
Скажем можно выбирать из N уравнений подмножества в 4 шт, решать их — получится множество решений. Усреднить и получить более вероятное положение, а по разбросу определить точность по 3 сигма какой-нить. Но это так… я к примеру сказал, как это может быть. Ошибка может быть систематическая какая-нибудь… например скорость света будет ниже или выше предполагаемой — тогда надо какие-нить WAAS, EGNOS использовать.
DrZlodberg
Вообще если добавить несколько предположений, то можно пойти другим путём.
1. человек не движется, пока ждёт такси
2. вызывает его с уровня земли
В этом случае можно попросить сделать пару снимков и ориентироваться просто по гугл-панорамам. Там покрытие сильно больше, чем у 3Д-карт, да и нагрузка даже при полном переборе некоторой окрестности будет сильно меньше (imho).
GetJump
Как раз у Uber несколько другая философия в этом плане, то есть человек может двигаться пока ждёт такси, поправьте если не прав.
Высота (например над уровнем моря) в подобном классе задач редко рассматривается.
А в целом, да, любое улучшение данных GPS основано на некоторых предположениях (например объект автомобиль движется только по дорогам общего пользования, или объект движется со скоростью не больше заданного и т.д.).
Подход Uber очень интересен с точки зрения универсальности.
kalininmr
с уровнем земли всё сложно.
особенно в некоторых городах.
DrZlodberg
В каком смысле?
kalininmr
взгляните, нарпимер, на Уфу.
прошел 50 метров и уже сильно другая высота.
а перепад 10-15 метров ступенькой — популярное архитектурное решение в любом современном городе.
DrZlodberg
Вы не поняли. Я предлагаю для уточнения положения использовать гугл-панорамы, которые сняты условно с уровня грунта (не всегда, но это не принципиально). Просто чем дальше, от траектории камеры, тем сложнее опознать место. Т.е. получаем грубое положение и по ближайшим снимкам уточняем его.
kalininmr
гуглпанорамы есть только для дорог, притом крупных.
а всякие дворы и прочее — нет
DrZlodberg
Тут с одной стороны да, с другой — их явно больше, чем 3Д моделей города. Ну и доснять их проще, чем построить модель. Хотя с дворами не получится скорее всего. Деревья будут всё портить. Правда они же будут и в их модели портить, т.к. отлично и очень неравномерно во времени забивают сигнал. Т.е. даже модель каждого дерева не поможет.
Henry7
Это поможет понять, человек находится на мосту или под мостом?
DrZlodberg
Вот тут как раз никаких проблем Картинка на и под мостом отличается так, что перепутать их невозможно. А вот gps их вряд-ли различит (не думаю, что навигаторы учитывают высоту)
TrllServ
На транспортной развязке фото в даль пересекающей дороги под и над будут отличаться не так уж и сильно.
Во многих телефонах даже достаточно старых есть датчики давления, точность правда, так себе. Но 5й этаж от грунта отличает.
DrZlodberg
1. Вообще и gps даёт высоту. Вопрос в том, используют ли её навигаторы. Судя по тому, что все карты обычно двухмерны — нет.
2. Надо постараться так встать именно под мостом, чтобы при этом в кадр не попали опоры или верхний настил. Разве что для узких мостов. Ну и картинка вдоль дороги не особо информативна в принципе, т.к. не даёт никакого представления собственно о близлежащих ориентирах. Это как объяснять где ты стоишь в стиле — «в 200 метрах от меня какое-то здание, но я туда не пойду».
3. Система же не самодостаточна, а опирается на те же датчики, что доступны и навигатору (т.е и этому тоже). Однако вопрос ещё в том, какова его точность при отсутствии информации об атмосферном давлении в данной точке в данный момент. Я не знаю, на сколько сильно оно гуляет по отношению к градиенту по высоте. Ну и мосты обычно сильно ниже, чем 5й этаж. Хотя бывают всякие…
kalininmr
по опыту использования даже неплохих навигаторов, могу сказать, что высоту они дают как то уж очень приблизительно.
Busla
Земля не круглая, а очень неправильной формы. Поэтому существуют национальные системы координат, а глобальная во-первых даёт одинаково плохую точность по всей планете, во вторых большинство систем вообще не учитывает высоту.
DrZlodberg
Посмотрите мой ответ на один комментарий выше. Мы сейчас о разных вещах говорим.
TrllServ
Не каждый день городах занимаются терраморфингом.
Можно один раз построить карту уровня земли для всего города, сильно повысив удобство и снизив затраты вычислительных ресурсов.
GetJump
Такие карты уже существуют (с разной степенью покрытия), но в целом, для весьма универсальных решений, высота как раз и не требуется.
awesomer
Страшно дорого.
DrZlodberg
Похоже я очень криво объяснил, но сам уровень нафиг не нужен. Просто у нас (у гугла) уже есть снимки с уровня поверхности (и не только). При сильном несовпадении высоты просто будет сложно сопоставить их с картинкой юзера.
areht
Я боюсь у пользователей будет ракурс сильно отличаться от гугломобиля. В центре может ещё и можно поиграть, а фотка типовой серой многоэтажки в 200 метров мало что даст
DrZlodberg
Если там нет ничего, кроме 1 дома в 200 метрах, то проблем с gps быть не должно. Тут речь о плотной застройке, где ориентиров должно быть много. И даже по условию погрешность навигации меньше, чем 200м. Отличие ракурсов как раз и даст информацию о его положении. Понятно, что он будет снимать с тротуара, а не с середины дороги.
areht
Ну вот вам плотная застройка, где ориентиров должно быть много. Для полноты эффекта, добавьте в текстуры снег.
DrZlodberg
Этот метод тут тоже не будет давать результатов, т.к. учесть переменное затухание в деревьях он не может. Ну и 3Д карты пятиэтажек вряд-ли скоро появятся.
А ориентиров на самом деле тут очень много. Любой человек, знакомый с этим местом моментально его узнает. Правда машине будет сложнее, особенно с сезонными изменениями.
С другой стороны ей потребуется не шерстить всю память, а перебрать только дворы в радиусе 50..100 метров от этой точки. Как минимум в таких пределах расположение разного типа деревьев (достаточно отличать тёмный ствол от светлого) и цвет балконов практически уникальны. Бонусом идёт малая вариативность снимков за счёт смены ракурса (если не снимать с газона тут особо некуда отойти).
На самом деле основная проблема тут будет ночью. Вот там всё очень сильно меняется. Если на крупных дорогах ориентиры более-менее опознаваемы и ночью, тут скорее всего будет нереально совершенно.
Ну и я не говорил, что метод универсален. Он лишь проще и текущее покрытие снимками больше. Понятно, что будут места, где от него толку не будет. Например китайские квадратно-гнездовые посёлки-клоны (которые и у нас встречаются уже довольно часто) или новостройки с длинными рядами одинаковых домов и полным отсутствием других ориентиров.
TrllServ
DrZlodberg
В таких домах обычно стекление балконов (например) достаточно индивидуально и образует относительно уникальный паттерн. Плюс кондёры, деревья, мусорки, лавочки, клумбы и многие другие мелкие ориентиры. Именно человек очень вряд-ли сможет перепутать. Но да, гарантированной уникальности, естественно нет. Тут, как уже писал, основная проблема будет лето/осень/зима, т.к. листва очень много места в кадре занимает.
areht
> Ну и я не говорил, что метод универсален.
Т.е. мы обсуждаем метод, который работает:
1) Днем
2) Летом
3) Не во дворах, спальных районах и промзонах
4) Если гугломобиль там проехал после последней покраски балконов
5) Если гугломобиль там вообще проехал
Ну, такое себе.
> достаточно отличать тёмный ствол от светлого
а «светлый» от «темного под солнышком, которое на него падает только при ветре 5м/с с 13:12 до 14:45».
DrZlodberg
Как на счёт наличия для таких мест 3Д карты города?
1 и 2 зависит от места.
3. промзоны (по крайней мере в наших краях) чертовски индивидуальны. Разве что найти длинную дорогу с глухим забором и без зданий по близости.
Очень сложно осветить дерево так, чтобы весь ствол был равномерно освещён. Ещё сложнее встать так, чтобы получить такой кадр. Контрпример — в приведённом методе один припаркованный рядом грузовик может дать такое переотражение, что никакой анализ не поможет. Ну вот нет на 3д-карте этого грузовика… Всегда можно найти условия, в которых метод не сработает. Любой метод.
Не панацея, да. Но на сколько он хуже предложенного в статье судить не берусь.
liddom
Мне кажется, при наличии достаточных вычислительных мощностей можно сделанные пользователями снимки учитывать для актуализации внешнего вида пространства. Т.е. если изменения происходят постепенно, а вызывают такси из этого места достаточно часто, проблемы у предложенного метода возникать не должно. А в перспективе можно и 3д модель по имеющимся фотографиям построить.
DrZlodberg
Это вряд-ли. Слишком отличается ракурс. И это бессмысленно т.к. панорамы сплошные, а тут будет мозайка одиночных снимков в разное время года/времени суток/погоды/трафика и т.д. которые не состыковать друг с другом никак.
liddom
А зачем им стыковать? Задача же в нахождении похожих, деталей, так? Найти похожие детали в снимках, сделанных примерно в одно и то же время, проще, чем при сравнении с Гугл партнерами сделанными год назад. Конечно, полноценную панораму из таких снимков не построить, но оно и не нужно. Снимки других пользователей вообще не нужно делать публично доступными, просто накапливать для внутреннего использования.
Ну а про 3д модели местности- мне кажется, это технически выполнимая задача. Сначала нейросетью выделить объекты на снимках, затем нейросетью же привести вид снимков к примерно одному времени года (была же где-то здесь статья про обработку снимков для превращения осени в лето). Потом составить примерную 3д модель из простейших геометрических форм, сопоставить со спутниковыми снимками. Ресурсоемко — да, требует разработки большого количество софта — да, технически возможно — тоже да.
liddom
*при сравнении с Гугл панорамами сделанными год назад.
Автозамена :(
DrZlodberg
Мелкие тут особо не нужны. Они как раз наоборот, будут мешать. Модель можно (в теории) более-мене составить и из обычной панорамы.
А в чём смысл сопоставления со спутником? Если мы сможем привязаться к панорамам, то координаты уже будут. Гугл же собирает и точные координаты каждой.
areht
> Как на счёт наличия для таких мест 3Д карты города?
На сколько я знаю, обрисовывают фото со спутника.
> грузовик может дать такое переотражение, что никакой анализ не поможет.
Если посмотреть на фото, то понятно, что грузовик даст искажения порядка своего размера. Метра 3.
DrZlodberg
С грузовиком пример неудачный по другой причине. Их система отслеживает перемещение человека и учтёт внезапный прыжок (та самая тепловая карта). Однако для статичного положения она и так может давать приличную погрешность (опять-таки см. карту)
areht
Ну по фото с самолёта, не суть. Главное можно без и объезда машиной каждого куста обойтись.
Погрешность измерения и метод компенсации — разные вещи. Грузовик не даёт приличной погрешности. Её можно ещё уменьшать, но ради грузовика не очень то и нужно.
В идеале, конечно, каждый грузовик с точностью до сантиметра обмерить, но для задачи «подать такси к нужному подъезду» это излишне. Всё равно есть замечатальные дома, где даже с лидаром моделировать отражения и видимость спутников замучаешься, так что точности в полметра ждать не приходится.
maksim_ms
Оба ваших пункта спорны:
1) иду по парку к дороге, вызываю такси.
2) сижу дома на 9 этаже вызываю такси, с учетом того как убер «быстро» едет смысла нет вызывать с уровня земли.
DrZlodberg
Так по этому они и допущения. Увы, в этих случаях толку будет 0. Но с 9м этажом и описываемый метод не справится, т.к. там тоже предполагается уровень грунта (на сколько я понял). 3Д модели парка у них тоже вряд-ли есть, так что и тут пролёт.