В продолжение дискуссии вокруг статьи о методе повышения точности позиционирования, разработанном в Uber, мне хотелось бы поделиться о проводимых в своей небольшой компании исследованиях и рассказать о технологии, с помощью которой мы пытаемся решить аналогичную задачу. Сразу отмечу, что здесь не будет никаких математических выкладок и глубоких технических подробностей, все пояснения постараюсь сделать максимально доступным языком. Если стало интересно узнать, а причем здесь собственно трамваи, то прошу под кат.
Итак, думаю ни у кого не возникнет проблем представить, что нас всех окружает несчётное множество мобильных устройств — смартфонов, планшетных компьютеров, GPS-трекеров, автомобильных навигаторов и даже бортовых компьютеров в автомобилях. Как правило, в
такие устройства встроены приёмники глобальных спутниковых навигационных систем (GPS, ГЛОНАСС, Baidu). Эти приемники являются достаточно бюджетными и, в отличие от дорогого профессионального оборудования, не поддерживают работу в дифференциальном режиме, в котором они могли бы принимать коррекционную поправку и определять, таким образом, местоположение устройства с сантиметровой точностью. Точность определения координат, к сожалению, пока оставляет желать лучшего.
Но прежде чем перейти к сути нашей технологии давайте напомним себе о причинах возникновения ошибок в позиционировании. В реальных условиях на точность определения координат устройства влияет множество факторов. Однако, все источники возникновения погрешностей вычисления можно разделить на следующие группы по их происхождению:
А теперь, прошу обратить внимание на ключевой момент, являющийся по своей сути теоретическим обоснованием описанного далее метода — первые три группы источников ошибок являются общими (то есть, коррелированными) для устройств, находящихся в одно и тоже время на относительной близком расстоянии друг от друга. Только лишь ошибки, связанные с внутренним шумом устройства и многолучевым распространением сигнала, являются индивидуальными. Кстати, именно эта идея лежит в основе работы дифференциальных подсистем. В областях так называемой пространственно-временной корреляции погрешностей, параметры ошибок, вычисленные в произвольной точке, можно использовать в течение времени корреляции для коррекции измерений в других точках области.
Чтобы было более понятно, что является единой пространственно-временной областью, а что нет, приведу примеры. Потребители, находящиеся одномоментно в Москве на Ленинградском проспекте и шоссе Энтузиастов, будут находится в такой единой области — навигационное поле, то есть состав и расположение спутников на небосводе, и состояние ионосферы и тропосферы над ними будут примерно одинаковыми, так как расстояние между ними будет существенно меньше расстояния до спутников и размеров неоднородностей в ионосфере. В свою очередь, потребители из Москвы и Казани будут располагаться в разных пространственно-временных областях, так как ошибки позиционирования будут зависеть от разных участков тропосферы и ионосферы. И даже если вы находитесь в одном месте, но делаете измерения с интервалом времени в 1 или 2 часа, ваши измерения будут соответствовать различным областям, так как за это время происходят изменения не только в ионосфере и тропосфере, но и изменяется само навигационное поле. Отмечу, что для различных вариантов дифференциальных подсистем типичные пространственные размеры таких областей составляют от нескольких единиц до сотен километров.
После краткого рассмотрения теоретического обоснования метода, перейдем к описанию гипотезы, относительно того, как множество «простых» устройств, находящихся в единой пространственно-временной области, могут помочь повысить точность позиционирования каждого из них.
Возьмем два трамвая (пусть будут, условно, 43 и 56 маршрутов) с установленными на них приёмниками спутниковых навигационных систем. Пусть трамвай 43 в данный момент времени движется с юга на север, а трамвай 56 — с запада на восток. В одно и тоже время или с некоторой небольшой разницей во времени приходит отметка с координатами о текущем местоположении трамваев. Но, так как дифференциальные подсистемы в их устройствах не используются, то точность определения не достаточно высокая для точного позиционирования — отметки, скорее всего, в обоих случаях будут располагаться вне трамвайных рельс.
Но мы то знаем, что приёмники находятся на трамваях, на реальное положение в пространстве которых накладываются физические ограничения. По сути, вариативность положения трамваев, определяется расположением рельс — реальное положение трамвая маршрута 43 находится западнее отметки с наблюдением, а трамвая 56, в свою очередь — южнее. А теперь давайте представим себе удачное стечение обстоятельств, что в процедуре вычисления местоположения в обоих случаях использовались одни и те же навигационные спутники (так называемое рабочее созвездие). А для упрощения примем, что точность определения была одинаковой — радиусы изображенных окружностей совпадают. Давайте мысленно совместим эти окружности в одну и найдем виртуальную точку на пересечении двух путей. Именно эта точка и будет являться потенциальным кандидатом на роль искомой — векторы коррекции от точек наблюдения до реального положения трамваев в этом случае будут одинаковыми.
Применяя этот коррекционный вектор к отметкам, мы легко вычисляем положение обоих трамваев с большей точностью относительно первоначальной. Конечно, останутся погрешности измерений, связанные с отражением радиосигналов или ошибкой приёмников.
А теперь давайте возьмём не два трамвая, а десятки, сотни тысяч и даже миллионы. И не просто трамваи, а всевозможные автотранспортные средства, колесящие по нашим дорогам с навигаторами и ЭРА-ГЛОНАСС устройствами на борту. И здесь следующая мысль, которую мне хотелось бы донести такая: автомобиль на дороге — это на 95% трамвай. В том смысле, что все автомобили в совокупности не перемещаются по дорогам хаотично. Если внимательно посмотреть на поток машин на прямом участке дороги, можно заметить, что большую часть времени они едут по полосам, словно привязанные к невидимым рельсам. Лишь малую долю времени занимают перестроения, обгоны и другие манёвры. Кроме этого, в отличие от пешехода, реальное расположение автотранспортного средства ограничено относительно небольшой областью пространства — проезжими частями, суммарная площадь которых в крупных городах не превышает 1-5% от общей территории. Двигающийся со скоростью более 20-30 километров в час автомобиль не может неожиданно оказаться вне проезжей части (на тротуаре, газоне или в открытом поле и т. д.) и продолжать там своё движение с той же или более высокой скоростью. А на дороге с разделительным ограждением вероятность выезда на встречную полосу пренебрежительна мала.
Таким образом, можно предположить, что зафиксированные с использованием спутниковых навигационных систем координаты автотранспортных средств вне «разрешённых» областей, то есть противоречащие существующим элементам дорожной инфраструктуры, являются хорошим информационным сигналом при вычислении поправки, корректирующей эти измерения в сторону реального расположения объектов. При этом, не все наблюдения будут полезны. Например, отметка от автомобиля, движущегося в средней полосе по МКАД, несёт в себе крайне мало информации, так как все потенциальные точки в радиусе 5-6 метров являются вполне допустимыми (автомобиль реально может ехать в соседних полосах или перестраиваться из ряда в ряд). С другой стороны, отметка от автомобиля на однополосной лесной дороге даст гораздо больше информации.
Более наглядно понять суть метода можно с помощью обычной бумажной крупномасштабной карты и прозрачной бумаги. Мысленно положите прозрачку на карту и нанесите отметки от автотранспортных средств так, чтобы они соответствовали полученным наблюдениям. Чем больше отметок, тем лучше. Затем необходимо двигать прозрачку влево-вправо и вверх-вниз на разные значения смещений так, чтобы максимальное количество точек попало в «свои» участки дорог (не были на встречной полосе, обочине и т.д.). Решая таким образом оптимизационную задачу, мы и находим наиболее вероятное реальное расположение этих автомобилей, попутно выявляя потенциальных нарушителей из числа тех, чьи отметки после такой кропотливой работы попали в «запрещенные» для них области.
Именно в этом и заключается суть нашей метода — с помощью компьютерных вычислений, без применения дополнительного дорогостоящего оборудования, проанализировать большое количество наблюдений из одной пространственно-временной области, выделить из каждого наблюдения кусочек необходимой информации, сопоставив отметку с «картой» и вычислить общую коррекционную поправку, которую можно использовать для всех устройств из данной области.
Для вычисления общих коррекционных поправок необходимо использовать максимально подробную цифровую разметку как можно большего количества участков улично-дорожной сети, с помощью которой можно более точно локализовать реальное положение потребителей. Причём не только самих водителей автотранспортных средств, но и «безлошадных» пешеходов, включая, конечно же, потенциальных клиентов такси. Устройства пешеходов, безусловно, должны исключаться из анализа и вычисления коррекционных поправок, но вычисленные поправки могут быть применены к ним на равных с автомобилистами основаниях.
А что же такое цифровая разметка? Мы сами определяем её как математическую модель, которая описывает реальное расположение некоторых элементов дорожной инфраструктуры в пространстве с точностью, необходимой и достаточной для решения разного рода навигационных задач. К таким элементам дорожной инфраструктуры относятся бордюры, разделительный полосы, дорожная разметка, трамвайные рельсы и т.п. Упрощенно говоря, цифровая разметка должна по координатам (широте и долготе) говорить, чему соответствует данная точка и насколько она удалена от других элементов дороги. Например, насколько близко находится точка к бордюру, не принадлежит ли она встречной полосе или пешеходному тротуару и т.д.
Кажется, что чем точнее удастся создать цифровую разметку, тем точнее можно делать предсказания. К сожалению, создание точной цифровой разметки является крайне сложной и дорогой задачей. Однако, ее наличие является важным и для развития беспилотного транспорта, поэтому её появление рано или поздно, надеюсь, станет неизбежным. В рамках создания описанной выше технологии мы изучаем и исследуем подходы, основанные на тех же принципах кооперативности наблюдений и направленные на решение данной проблемы, но это уже немного другая история…
Итак, думаю ни у кого не возникнет проблем представить, что нас всех окружает несчётное множество мобильных устройств — смартфонов, планшетных компьютеров, GPS-трекеров, автомобильных навигаторов и даже бортовых компьютеров в автомобилях. Как правило, в
такие устройства встроены приёмники глобальных спутниковых навигационных систем (GPS, ГЛОНАСС, Baidu). Эти приемники являются достаточно бюджетными и, в отличие от дорогого профессионального оборудования, не поддерживают работу в дифференциальном режиме, в котором они могли бы принимать коррекционную поправку и определять, таким образом, местоположение устройства с сантиметровой точностью. Точность определения координат, к сожалению, пока оставляет желать лучшего.
Но прежде чем перейти к сути нашей технологии давайте напомним себе о причинах возникновения ошибок в позиционировании. В реальных условиях на точность определения координат устройства влияет множество факторов. Однако, все источники возникновения погрешностей вычисления можно разделить на следующие группы по их происхождению:
- Вносимые контрольно-измерительным комплексом. Сюда входят ошибки из-за незначительного несоответствия шкал времени навигационных спутников и погрешности, обусловленные неточностью расчёта их местоположений относительно реальных орбит на момент излучения радиосигнала всем потребителям.
- Вносимые оборудованием самих навигационных спутников.
- Возникающие на пути распространения радиосигналов. Основной источник здесь — рефракция радиосигналов в тропосфере и ионосфере Земли, обусловленная существующими в них неоднородностями, которые вносят дополнительные задержки распространения сигнала.
- Вносимые приёмником потребителя (внутренний «шум» устройства).
- Многолучевость при распространении сигнала (отражение от поверхности Земли и окружающих зданий).
А теперь, прошу обратить внимание на ключевой момент, являющийся по своей сути теоретическим обоснованием описанного далее метода — первые три группы источников ошибок являются общими (то есть, коррелированными) для устройств, находящихся в одно и тоже время на относительной близком расстоянии друг от друга. Только лишь ошибки, связанные с внутренним шумом устройства и многолучевым распространением сигнала, являются индивидуальными. Кстати, именно эта идея лежит в основе работы дифференциальных подсистем. В областях так называемой пространственно-временной корреляции погрешностей, параметры ошибок, вычисленные в произвольной точке, можно использовать в течение времени корреляции для коррекции измерений в других точках области.
Чтобы было более понятно, что является единой пространственно-временной областью, а что нет, приведу примеры. Потребители, находящиеся одномоментно в Москве на Ленинградском проспекте и шоссе Энтузиастов, будут находится в такой единой области — навигационное поле, то есть состав и расположение спутников на небосводе, и состояние ионосферы и тропосферы над ними будут примерно одинаковыми, так как расстояние между ними будет существенно меньше расстояния до спутников и размеров неоднородностей в ионосфере. В свою очередь, потребители из Москвы и Казани будут располагаться в разных пространственно-временных областях, так как ошибки позиционирования будут зависеть от разных участков тропосферы и ионосферы. И даже если вы находитесь в одном месте, но делаете измерения с интервалом времени в 1 или 2 часа, ваши измерения будут соответствовать различным областям, так как за это время происходят изменения не только в ионосфере и тропосфере, но и изменяется само навигационное поле. Отмечу, что для различных вариантов дифференциальных подсистем типичные пространственные размеры таких областей составляют от нескольких единиц до сотен километров.
После краткого рассмотрения теоретического обоснования метода, перейдем к описанию гипотезы, относительно того, как множество «простых» устройств, находящихся в единой пространственно-временной области, могут помочь повысить точность позиционирования каждого из них.
Возьмем два трамвая (пусть будут, условно, 43 и 56 маршрутов) с установленными на них приёмниками спутниковых навигационных систем. Пусть трамвай 43 в данный момент времени движется с юга на север, а трамвай 56 — с запада на восток. В одно и тоже время или с некоторой небольшой разницей во времени приходит отметка с координатами о текущем местоположении трамваев. Но, так как дифференциальные подсистемы в их устройствах не используются, то точность определения не достаточно высокая для точного позиционирования — отметки, скорее всего, в обоих случаях будут располагаться вне трамвайных рельс.
Но мы то знаем, что приёмники находятся на трамваях, на реальное положение в пространстве которых накладываются физические ограничения. По сути, вариативность положения трамваев, определяется расположением рельс — реальное положение трамвая маршрута 43 находится западнее отметки с наблюдением, а трамвая 56, в свою очередь — южнее. А теперь давайте представим себе удачное стечение обстоятельств, что в процедуре вычисления местоположения в обоих случаях использовались одни и те же навигационные спутники (так называемое рабочее созвездие). А для упрощения примем, что точность определения была одинаковой — радиусы изображенных окружностей совпадают. Давайте мысленно совместим эти окружности в одну и найдем виртуальную точку на пересечении двух путей. Именно эта точка и будет являться потенциальным кандидатом на роль искомой — векторы коррекции от точек наблюдения до реального положения трамваев в этом случае будут одинаковыми.
Применяя этот коррекционный вектор к отметкам, мы легко вычисляем положение обоих трамваев с большей точностью относительно первоначальной. Конечно, останутся погрешности измерений, связанные с отражением радиосигналов или ошибкой приёмников.
А теперь давайте возьмём не два трамвая, а десятки, сотни тысяч и даже миллионы. И не просто трамваи, а всевозможные автотранспортные средства, колесящие по нашим дорогам с навигаторами и ЭРА-ГЛОНАСС устройствами на борту. И здесь следующая мысль, которую мне хотелось бы донести такая: автомобиль на дороге — это на 95% трамвай. В том смысле, что все автомобили в совокупности не перемещаются по дорогам хаотично. Если внимательно посмотреть на поток машин на прямом участке дороги, можно заметить, что большую часть времени они едут по полосам, словно привязанные к невидимым рельсам. Лишь малую долю времени занимают перестроения, обгоны и другие манёвры. Кроме этого, в отличие от пешехода, реальное расположение автотранспортного средства ограничено относительно небольшой областью пространства — проезжими частями, суммарная площадь которых в крупных городах не превышает 1-5% от общей территории. Двигающийся со скоростью более 20-30 километров в час автомобиль не может неожиданно оказаться вне проезжей части (на тротуаре, газоне или в открытом поле и т. д.) и продолжать там своё движение с той же или более высокой скоростью. А на дороге с разделительным ограждением вероятность выезда на встречную полосу пренебрежительна мала.
Таким образом, можно предположить, что зафиксированные с использованием спутниковых навигационных систем координаты автотранспортных средств вне «разрешённых» областей, то есть противоречащие существующим элементам дорожной инфраструктуры, являются хорошим информационным сигналом при вычислении поправки, корректирующей эти измерения в сторону реального расположения объектов. При этом, не все наблюдения будут полезны. Например, отметка от автомобиля, движущегося в средней полосе по МКАД, несёт в себе крайне мало информации, так как все потенциальные точки в радиусе 5-6 метров являются вполне допустимыми (автомобиль реально может ехать в соседних полосах или перестраиваться из ряда в ряд). С другой стороны, отметка от автомобиля на однополосной лесной дороге даст гораздо больше информации.
Более наглядно понять суть метода можно с помощью обычной бумажной крупномасштабной карты и прозрачной бумаги. Мысленно положите прозрачку на карту и нанесите отметки от автотранспортных средств так, чтобы они соответствовали полученным наблюдениям. Чем больше отметок, тем лучше. Затем необходимо двигать прозрачку влево-вправо и вверх-вниз на разные значения смещений так, чтобы максимальное количество точек попало в «свои» участки дорог (не были на встречной полосе, обочине и т.д.). Решая таким образом оптимизационную задачу, мы и находим наиболее вероятное реальное расположение этих автомобилей, попутно выявляя потенциальных нарушителей из числа тех, чьи отметки после такой кропотливой работы попали в «запрещенные» для них области.
Именно в этом и заключается суть нашей метода — с помощью компьютерных вычислений, без применения дополнительного дорогостоящего оборудования, проанализировать большое количество наблюдений из одной пространственно-временной области, выделить из каждого наблюдения кусочек необходимой информации, сопоставив отметку с «картой» и вычислить общую коррекционную поправку, которую можно использовать для всех устройств из данной области.
Для вычисления общих коррекционных поправок необходимо использовать максимально подробную цифровую разметку как можно большего количества участков улично-дорожной сети, с помощью которой можно более точно локализовать реальное положение потребителей. Причём не только самих водителей автотранспортных средств, но и «безлошадных» пешеходов, включая, конечно же, потенциальных клиентов такси. Устройства пешеходов, безусловно, должны исключаться из анализа и вычисления коррекционных поправок, но вычисленные поправки могут быть применены к ним на равных с автомобилистами основаниях.
А что же такое цифровая разметка? Мы сами определяем её как математическую модель, которая описывает реальное расположение некоторых элементов дорожной инфраструктуры в пространстве с точностью, необходимой и достаточной для решения разного рода навигационных задач. К таким элементам дорожной инфраструктуры относятся бордюры, разделительный полосы, дорожная разметка, трамвайные рельсы и т.п. Упрощенно говоря, цифровая разметка должна по координатам (широте и долготе) говорить, чему соответствует данная точка и насколько она удалена от других элементов дороги. Например, насколько близко находится точка к бордюру, не принадлежит ли она встречной полосе или пешеходному тротуару и т.д.
Кажется, что чем точнее удастся создать цифровую разметку, тем точнее можно делать предсказания. К сожалению, создание точной цифровой разметки является крайне сложной и дорогой задачей. Однако, ее наличие является важным и для развития беспилотного транспорта, поэтому её появление рано или поздно, надеюсь, станет неизбежным. В рамках создания описанной выше технологии мы изучаем и исследуем подходы, основанные на тех же принципах кооперативности наблюдений и направленные на решение данной проблемы, но это уже немного другая история…