Мы строим пешеходные маршруты по тропинкам, через калитки и с возможностью срезать через двор с апреля 2017 года. А совсем недавно мы добавили в 2ГИС полноценный навигатор для пешеходов — с режимом turn-by-turn и озвучкой важных точек на маршруте.

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

Новые сценарии

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

Я построил маршрут от дома и убрал телефон в карман. Ориентировался только на голосовое ведение. Когда понял, что начинаю бессмысленно блуждать, а голосовые подсказки лишь уводят меня в сторону от конечной точки, решил построить маршрут заново. Когда проблема повторилась в восьмой раз, стало понятно, что нам предстоит огромный пласт работ.

Голосовые инструкции опираются на сценарий их использования. Стандартный шаблон сценария — как именно пешеход подходит к перекрёстку, с какой скоростью двигается и куда пойдёт потом. Автомобильные инструкции не сработали, так как условия их воспроизведения слишком отличаются от пешеходных. Банально — скорость пешехода в разы меньше, и это влияет на момент озвучки манёвра.

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

Мы собрали и описали новые практические сценарии и сформулировали новые правила, чтобы при подходе к подземному переходу говорить «Спуститесь в подземный переход», а не просто «Перейдите дорогу».

Старый алгоритм

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

Полнота данных достигается в два этапа: сначала собираем информацию, а потом улучшаем её с помощью алгоритмов предрасчёта.

На основе базовой информации алгоритмы могут дообогащать знания о графе дополнительными атрибутами — например, автомобильными инструкциями.

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

Верифицируемость

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

Обновление данных

Данные в приложении 2ГИС обновляются отдельно от самого приложения. И их мы выпускаем чаще, чем изменения в алгоритмах наших библиотек для мобилок — это даёт возможность исправлять или добавлять инструкции, не дожидаясь релизов приложений.

Эффективность алгоритма предварительной генерации инструкций

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

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

Новый алгоритм

Ещё на этапе создания первого прототипа мы увидели, что из-за пешеходных инструкций растёт размер локальной базы, используемой для поиска маршрутов. В среднем пакет роутинга вырос на 20% — это недопустимо много, так как приведёт к увеличению размера офлайн-баз на телефонах нашей аудитории.

По сравнению с автомобильными перекрёстками пешеходные допускают намного больше вариантов прохода. Стандартный перекрёсток — это 56 вариантов прохода пешком в зависимости от положения начальной (8 сторон перекрестка) и конечной (7 сторон) точки. И в каждом варианте — до трёх пешеходных манёвров.



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

Из-за этого мы отказались от идеи предрасчёта пешеходных инструкций и перенесли логику их генерации в рантайм. Если есть интернет, то расчёт инструкций идёт на наших серверах, а если интернета нет или ответ сервера не уложился по таймауту, — то на мобильном приложении. Фактически мы заново переписали алгоритм.

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

Новые инструкции

Повторюсь, что пешеходные проходы через перекрёстки намного более вариативны по сравнению с автомобильными.


Каждый перекрёсток — возможность изменить маршрут

На этапе проработки инструкций мы столкнулись с проблемой их компактного, однозначного и своевременного представления. Звёздочку задаче добавляло то, что телефон может лежать в кармане, и пользователь не видит направляющую линию и стрелочки. Ориентироваться можно только на голосовое ведение. Кроме этого, пешеход в отличие от автомобиля может легко развернуться практически на любой угол на совсем узком участке. И важно объяснить человеку максимально точно, как и где именно переходить дорогу, поворачивать или спускаться.



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

Проверяли озвучку лесных тропинок, дворовых дорог, переходов через широкие перекрёстки, нерегулируемые и регулируемые пешеходные переходы со светофорами.

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



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

Мы сделали составные голосовые инструкции, чтобы ориентироваться ещё до начала перехода, в какую сторону двигаться после него.

С точки зрения пользователя, такая инструкция ничем не отличается от привычной автомобильной. Так, фраза «Поверните налево, затем через 100 метров поверните направо» для авто — это две однокомпонентных инструкции
«Поверните налево» + «через 100 метров поверните направо». А у пешеходов фраза для перехода через дорогу «Поверните налево на пешеходный переход, а затем поверните направо» — это полностью одна инструкция.

Фактически такие инструкции — связки любых элементарных инструкций поворота, но в виде единой озвучиваемой инструкции. Такой подход позволил существенно повысить информативность и удобство фонового ведения. Особенно при переходе нетривиальных перекрёстков.


На ближайшем пешеходном переходе поверните налево,
а сразу после перехода поверните направо

Что ещё

«Тюнинг» гео-позиционирования

Пешеходные маршруты часто включают в себя относительно мелкие проходы — рёбра графа. А в городских условиях, когда сигнал нестабильный и/или экранируется высотными объектами, погрешности позиционирования могут мешать правильно рассчитывать инструкции и вести по маршруту. Чтобы случайно не перекинуть текущую точку на другую сторону улицы, мы немного «подтюнили» алгоритм — учитываем нюансы погрешности и корректируем алгоритм притяжки к маршруту вплоть до 30 метров.

Вибро

Ведение голосом — решение, когда телефон лежит в кармане. Но чтобы избежать ситуацию, когда в шумном городе голос не будет слышно, мы добавили вибрацию, которая срабатывает вместе с озвучкой перед нужным манёвром. Сам вибрационный паттерн сделали отличающимся от привычного при сообщении в мессенджере.

Что получилось

В итоге на первую публичную версию навигатора для пешеходов у нас ушло примерно шесть месяцев. Сейчас он доступен в версии 2ГИС для iOS и Android.

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