Как GPS навигатор находит кратчайший путь?

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

    Среди всех алгоритмов, отвечающих за работу спутниковых навигаторов, ярко выделяются два. Первый позволяет определить положение приемника по сигналам со спутников GPS, второй определяет кратчайший путь из точки А (в которой Вы находитесь) в точку Б (в которую Вы желаете попасть). Существуют и другие алгоритмы, определяющие в основном визуальное отображение маршрута, но первые два являются наиболее важными.

    Первоначально навигационная система GPS была введена ВВС США для определения местонахождения приемника с точностью до 15 м. После катастрофы гражданского авиалайнера KAL 007 Рональд Рейган (президент США, 1981-1989) пообещал сделать систему общедоступной при первой возможности.

    Такая возможность открылась в конце 1993 г, и общедоступный сигнал с преднамеренно введенными искажениями позволил позиционировать гражданские объекты с точностью до 100 м. Подобные ограничения на точность были сняты только в 2000 г.

     Алгоритм позиционирования довольно прост. На средней околоземной орбите находятся 30 спутников, передающих одинаковый сигнал. Сообщения состоят из трех основных частей: точного время передачи, точных данных орбиты спутника (эфемерид) и общесистемной информации. Устройство GPS принимает и анализирует передаваемые спутниками сообщения. Зная время отправки, навигатор определяет, как долго сигнал находился в пути и как далеко расположен спутник

   
    Определение местонахождения

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

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

    В случае с тремя случаями мы имеем область пересечения сферы и окружности, рассмотренной ранее. Геометрически такое пересечение может дать до двух точек.

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

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

    Если как часть навигационной системы рассматривать приемное устройство, расположенное в автомобиле, то оно может использовать в работе дополнительную информацию с автомобиля, такую как скорость, пройденный путь, ускорение и другие данные. Это существенно помогает в городах, где путь распространения сигналов со спутника перекрывается зданиями, а из-за плотной застройки на приемник приходим многократно отраженный от стен сигнал.

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

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

    Главным условием для работы такого алгоритма является наличие векторной карты. Векторная карта представляет собой набор объектов (в основном дорог), которые отображаются на дисплее навигатора. Благодаря этому можно учитывать ориентацию и положение машины в текущий момент времени.

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

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

    А теперь самое интересное. У нас есть две точки: начало и конец маршрута. Также у нас есть карта, представляющая собой большой массив векторов. Мы должны использовать его и рассчитать оптимальный маршрут.