Навигатор для пешеходов

    image

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

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

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


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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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


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

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

    image

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

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

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

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


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

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

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

    image

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

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

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

    image

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

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

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

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

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


    Что ещё


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

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

    Вибро

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

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


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

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

    Комментарии 40

      0

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


      Я пока нигде не видел функции «предложить новый маршрут». Т.е. пользователь включает этот режим и едет (указав машину — легковая, газель, фура) или идет. Раз он это смог, значит там и другие смогут.

        +11

        Сесть на трактор, указать фуру, проехать сквозь болото, собирать дань с засевших, пользуясь наличием трактора и безысходностью застрявших

          0

          Сто тысяч раз да! Именно такие тропинки я регулярно наблюдаю на картах OSM. Все тропинки для пешеходов нужно считать весьма условными: сегодня есть, а завтра нет. Прошёл дождь и там уже гигантская лужа. Сошёл снег и там оказалось болото. Ну и банально ктото ставит главный символ Росии — забор.

            0
            смех смехом, но решали обратную проблему. частные жилые дома в пригороде Казани, узкий вечно нечищенный проезд между двумя улицами (все местные ездят на машинах с просветом от 20см)
            и внезапно в нем ПОСТОЯННО стали застревать таксисты, массово просто. на вопрос откуда ты тут взялся — «Навигатор завел»

            открыл приложения известной компании, перешел в режим народных карт, а этот дворовой проезд указан как городская дорога(!), вернул статус проезда с не афальтовым покрытием, за одно пофиксил все таки же проезды в округе…
            и через какое то время таксисты пропали
            0
            Есть опен-стрит мап, в которой всё это есть, и регулярно обновляется. Остается только распарсить. А насчет предложений маршрута это действительно проблема, ибо некоторые маршруты в последних обновлениях только расстраивают.
              0

              Разве лицензия допускает так делать? Так-то и в Народных картах Яндекса постоянно обновления.

                0
                OSM позволяет делать со своими данными всё что угодно. Надо только разместить ссылку или где-то упомянуть об источнике.
                Но 2gis по наблюдениям стал реже пользоваться данными OSM. У них есть свой штат сотрудников которые обходят и помечают пешие маршруты.
                  0
                  Я как-то наоборот видел сотрудников только в первые годы существования 2гис, потом по слухам что-то всё окуклилось. Не знаю как на самом деле
                0
                в которой всё это есть, и регулярно обновляется

                К сожалению не так часто как хотелось бы.
                Вы можете помочь проекту во время прогулок с помощью StreetComplete. Эта программа заполняет данные OSM в игровой форме, в виде квестов. Все очень просто, понятно и не занимает много времени.
              0

              Люди, когда будет Крым?

                +2

                Очень была бы полезна версия для Android Wear и подобных часов. Еще во времена Samsung Gear S (Here Maps) мне очень понравилось: просто сказал часам адрес и дальше в наушник получаешь голосовые команды а на часах стрелка куда идти.

                  0
                  Here же не делся никуда. По крайней мере, на iOS.
                  +1
                  В навигации важна линейка масштаба. Увидим ли мы её когда-нибудь?
                    +1
                    А чтобы в дороге не было скучно, иногда строит путь с «русской рулеткой», предлагая перебегать дорогу в четыре полосы (а шире в городе нет), вместо построения маршрута до ближайшей «зебры».
                    UPD. на дороге в 4 полосы ошибочно видит «зебру», но на двухполосную всё же предлагает перебежать.
                      +1
                      Такая ошибка с переходом широкой дороги в неположенном месте действительно была в одной из прошлых версий алгоритма пешей маршрутизации, но с 1 февраля она должна быть исправлена: если заметит подобные места вновь, то можете выбрать «Сообщить об ошибке» в боковом меню приложения и мы постараемся разобраться
                      +2

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

                        0
                        Опробовал вчера на актуальной версии 2GIS. В общем мой вердикт: пока пользоваться невозможно. Видно, что алгоритм был перенесен с автомобильного навигатора и адаптация пока недостаточная.
                        Если бы заранее на карте не посмотрел маршрут, то так и не понял бы, куда меня ведут голосовые подсказки. Во-первых точности GPS явно не хватало: мне предлагали повернуть там, где до поворота еще было довольно далеко. Во-вторых, подсказки плохо адаптированы под пешеходов. Например что значит «после светофора держитесь правее», если после светофора тротуар и получаются два пути — либо налево и по тротуару, либо направо и по тротуару.
                          0
                          ganzmavag, спасибо за фидбек!
                          По поводу точности — да, есть такая специфика GPS (особенно при высокой застройке), поэтому предупреждаем за 30 метров до поворота (исходя из идеи, что лучше предупредить заранее, чем пропустить поворот)
                          По поводу подсказок — маневр «держитесь правее» хоть и звучит как в автомобильном, но логика его озвучки отличается для пешеходного навигатора — он должен озвучиваться когда поворот действительно находится примерно посередине между «прямо» и «направо»
                          Чтобы улучшить конкретные места нам бы очень помогла ссылка на конкретный пеший маршрут, где вы столкнулись с неожиданным поведением — можно просто скинуть ссылку на этот маршрут на 2gis.ru
                        +4

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


                        Хорошо бы иметь ещё и отдельную навигацию для велосипедов.


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

                          +1
                          Спасибо! Про велосипедные особенности вы достаточно точно подметили, именно их мы бы хотели учесть в будущем, но пока сроков пообещать, к сожалению, не могу
                          +1
                          Учитывается ли криминогенность района и освещенность улиц?

                            0
                            Криминогенность района достаточно субъективная характеристика и она сейчас не учитывается, но освещенность улиц в целом учитывается — один из предлагаемых маршрутов мы стараемся строить по основным улицам без заходов во дворы: именно такие улицы в основном являются освещенными
                            +4
                            Честно говоря, для меня turn by turn в пешеходном варианте выглядит странной идеей. Для меня самый естественный сценарий — это, условно говоря, выйти из метро, глянуть буквально 5 секунд на карту, чтобы понять как идти и дальше может быть пару раз в пути сверяться, правильно ли я иду. А ещё примерно в одном месте часто бывает много каких-нибудь переулков, арок во двор, мелких дорожек и т.п., поэтому в инструкции типа «поверните направо» бывает сложно понять, на какое именно право из десяти возможных.

                            Как пешеходу мне сильно не хватает двух вещей в разных приложениях карт:
                            1) Возможность построить маршрут, но продолжить пользоваться картами как обычно. Я хочу, например, в незнакомом городе зайти в магазин, а по дороге поискать, где бы взять кофе с собой. Когда я строю маршрут до магазина, я больше не могу найти кофе. Это бесит. Просто нарисуйте магазин и подсветите путь до него, не надо переводить приложение в другую модальность. Очень сильно мешает то, что ходьба по маршруту — это какой-то отдельный режим в другой вселенной, который вырубает большую часть функциональности карт. Может быть, это логично, когда ты едешь на машине, но ходьба пешком — это гораздо более гибкий режим, чем просто перемещение между строго заданными точками. Мне кажется, лучшая аналогия маршрута с пешеходной точки зрения — это как маркером на бумажной карте сделать пометку, а не как забить координаты в навигационную панель космического корабля.

                            2) Возможность построить маршрут «на попозже». Например, я заказал что-то в магазине с самовывозом, посмотрел, где он находится с утра, а поеду туда вечером. Хочется этот маршрут прямо с утра и зафиксировать на карте, чтобы вечером выйти из метро и сразу увидеть, куда мне нужно, стоит ли бежать вон на тот автобус который сейчас подъедет и т.п. В целом, это продолжение пункта 1 в том плане, что навигация для пешехода не должна быть особенным режимом, дайте мне одновременно построить хоть десять маршрутов из разных мест в разные другие места и подсматривать на них по мере надобности.
                              +1
                              Megakazbek, спасибо за фидбек!
                              Действительно примерно половина нашей аудитории поступает как и вы — строит пешеходный маршрут, оценивает время в пути и препятствия на маршруте и не запуская turn-by-turn режим ведения сворачивают приложение
                              Но есть и вторая половина аудитории — которая действительно запускает режим ведения и сейчас вынуждена довольно часто доставать телефон из кармана, чтобы не пропустить нужные повороты — именно для них мы и добавили режим ведения по маршруту, чтобы уменьшить необходимость просмотра телефона (но, тем не менее, действительно есть сложные места, где нужно будет все равно взглянуть на карту)

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

                                  0
                                  В Android приложение можете с помощью долго удержания на нужных местах на карте выбрать пункт из меню «Добавить промежуточную точку» — в таком случае пеший маршрут пройдет через выбранные точки. В iOS этой возможности пока нет, но тоже планируем добавить
                              +1
                              Спасибо за 2гис, самое полезное приложение в телефоне из бесплатных
                                +1
                                давно пользуюсь, спасибо за такого шикарного помощника
                                  0
                                  Давно хотел задать вопрос о построении маршрутов. Возможно, правильнее будет написать в поддержку, — напишите, пожалуйста, если это актуальный вопрос. Нередко можно встретить маршруты городского общественного транспорта, когда в одном направлении (из А в Б) транспорт движется по одной улице, а в обратном (из Б в А) по другой, соседней улице. Из того что я вижу возле своего дома, 2ГИС мне показывает, как минимум один известный маршрут, исключительно по одной из улиц для обоих направлений, что только сбивает с толку. (Нижний Новгород, т83)
                                    0
                                    2ГИС умеет показывать такие маршруты, где прямое и обратное направление проходит по разным улицам, на примере маршрута т83 в Нижнем Новгороде вижу, что в целом многие части маршрута проходят по разным улицам:
                                    2gis.ru/n_novgorod/route/2674617869140166?m=43.910011%2C56.264981%2F15.81

                                    Если где-то все-таки есть ошибка, то можете нажать «Нашли ошибку в данных?» и мы исправим маршрут
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      0
                                      Да, это было бы классно! Думаем об этом
                                      0
                                      Сделайте оценку предложенного маршрута, два раза в Сочи строился пеший маршрут, по которому пешком пройти невозможно.
                                        0
                                        Да, хотим сделать более прозрачный механизм обратной связи о построенном маршруте — особенно это важно в таких сложных для пешехода городах как Сочи, где есть сильные уклоны и множество лестниц
                                        0
                                        Почему 2GIS не хочет делать нормальной озвучки названий дорог?
                                        Типа: поверните направо на Пушкинскую улицу.
                                          0
                                          Для этого нужен механизм text-to-speech генерации инструкций — сейчас такой возможности у нас нет, но думаем о ней в будущем
                                          0
                                          По-моему, пешеходный навигатор с непрерывным ведением полезен разве что для слабовидящих. Когда вы объясняете дорогу обычному человеку, вы не прописываете каждый поворот — это действительно огромная (и бессмысленная) трата ресурсов. Вы скажете, например, так: «Видишь здание с надписью „что-то-там“ на крыше — держи направление на него. Но имей ввиду что примерно на 1/3 пути будет стройплощадка, которую лучше обойти слева.» Вот и навигатор должен указывать только примерное направление.

                                          И хоть это оффтоп, не могу не отбомбить по автомобильным навигаторам.
                                          Штуки полезные, но далеко не идеальные. До сих пор ни один из бесплатных навигаторов (2GIS, OSM, Yandex) не умеет строить маршруты с минимизацией левых поворотов или максимально длинными прямыми участками. Часто ведут какими-то закоулками, по плохим дорогам. А уж голосовые подсказки… Например, «Поверните налево, затем поверните налево» — означает разворот. Съезды с колец не умеют нормально считать — «Покиньте кольцо на первом съезде» может значить что угодно — на кольцах нужно смотреть на схему, а не слушать. Забывают предупредить о направлении движения перед развилками с плавно расходящимися дорогами. И тому подобное, пилить и пилить ещё…
                                            0
                                            Если озвучка пешеходных маневров покажется лишней, то всегда можно выключить её в один клик с помощью иконки с динамиком на экране пешего навигатора

                                            А по поводу автомобильного навигатора — прямо сейчас мы вкладываем силы в улучшение озвучки маневров, например озвучку тех самых развилок: в ближайшие месяцы качество должно улучшиться
                                            0
                                            Иногда инструкция вида «На ближайшем пешеходном переходе поверните налево,
                                            а сразу после перехода поверните направо» может быть не понятна с первого раза. Так как кажется, что тебе надо повернуть налево, когда ты уже находишься на пешеходном переходе. Возможно было бы лучше что-то вроде «перейдите улицу по ближайшему пешеходному переходу, а сразу после перехода поверните направо»?
                                              –1

                                              После продажи Сберу всё стало хуже: начиная от заигрывания с цветом станций метро в Москве и заканчивая предложениямт навигатора обойти площадь по дальней стороне 2 раза через дорогу, когда прямо перед глазами прямой путь

                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                              Самое читаемое