Construímos trilhas para caminhadas ao longo de caminhos, através de portões e com a possibilidade de pegar um atalho pelo pátio desde abril de 2017. Mais recentemente, adicionamos um navegador completo para pedestres ao 2GIS - com um modo curva a curva e dublagem de pontos importantes na rota.
Debaixo do corte está uma história de como queríamos resolver esse problema rapidamente, contando com expertise em navegação para carros, e como resultado, criamos novos cenários, lutamos pelo tamanho das bases e aprendemos a dar as instruções corretas .
Novos cenários
Planejamos lidar com o problema “em algumas semanas” alterando ligeiramente a lógica das manobras do carro. Para os primeiros testes, fizemos uma montagem com a dublagem de manobras a pé, "enrolada" nos algoritmos de navegação automotiva. O resultado foi incrível.
Planejei uma rota de casa e coloquei meu telefone no bolso. Focado apenas na orientação por voz. Quando percebi que estava começando a vagar inutilmente, e os comandos de voz apenas me afastavam do ponto final, decidi reconstruir a rota. Quando o problema se repetiu pela oitava vez, ficou claro que tínhamos muito trabalho pela frente.
As instruções de voz são baseadas no cenário de seu uso. O modelo de cenário padrão é exatamente como um pedestre se aproxima de um cruzamento, quão rápido ele se move e para onde ele irá mais tarde. As instruções automotivas não funcionaram, pois as condições de sua reprodução são muito diferentes das dos pedestres. É banal - a velocidade de um pedestre é várias vezes menor, e isso afeta o momento de dublagem da manobra.
Ao mesmo tempo, é importante levar em consideração as nuances: travessias de pedestres, semáforos, portões, escadas, travessias de solo e subterrâneas, pois as informações sobre esses objetos ajudam o pedestre a se orientar mais rapidamente.
Recolhemos e descrevemos novos cenários práticos e formulámos novas regras para que, ao nos aproximarmos de uma passagem subterrânea, digamos “Desça para a passagem subterrânea”, e não apenas “Atravesse a estrada”.
Algoritmo antigo
A qualidade do roteamento depende diretamente da completude dos dados usados para construir a rota: conhecimento básico do gráfico rodoviário, a localização das bordas e seus atributos adicionais.
A integridade dos dados é obtida em duas etapas: primeiro, coletamos as informações e, em seguida, as aprimoramos usando algoritmos de pré-cálculo.
Com base nas informações básicas, os algoritmos podem enriquecer o conhecimento sobre o gráfico com atributos adicionais, por exemplo, instruções do carro.
Portanto, para rotas de carros, geramos antecipadamente todas as opções possíveis para dirigir em um cruzamento e, para cada opção, calculamos a instrução necessária e adicionamos atributos a ela. Esta abordagem tem uma série de vantagens:
Verificabilidade
Mesmo no estágio de pré-cálculo, você pode implementar vários algoritmos para verificar casos comuns. Calculado corretamente, as instruções verificadas não serão mais alteradas. Isso torna possível verificar a exatidão das instruções recebidas antes de entregarmos os dados e algoritmos ao usuário.
Atualizando dados
Os dados no aplicativo 2GIS são atualizados separadamente do próprio aplicativo. E nós os lançamos com mais frequência do que mudanças nos algoritmos de nossas bibliotecas para telefones celulares - isso torna possível corrigir ou adicionar instruções sem esperar pelo lançamento do aplicativo.
Eficiência do algoritmo de pré-geração
O algoritmo para emitir instruções ao longo da rota na verdade se resume a comparar as instruções já no banco de dados para todas as arestas que compõem a rota e emiti-las para o usuário. Usando o algoritmo, isso é muito mais fácil e rápido do que analisar possíveis situações em tempo de execução e gerar instruções a partir delas.
Mas há duas grandes desvantagens - essa abordagem força você a alocar recursos adicionais para armazenar novas informações e cria uma dependência na atualização de pacotes de dados. Se os dados não forem atualizados ou não estiverem lá, o usuário não terá acesso ao recurso, mesmo que tenha um algoritmo.
Novo algoritmo
Ainda na fase de criação do primeiro protótipo, vimos que devido às instruções de pedestres, o tamanho da base local usada para encontrar rotas foi crescendo. Em média, o pacote de roteamento cresceu 20% - valor inaceitável, pois levará a um aumento no tamanho dos bancos de dados offline nos telefones de nosso público.
Em comparação com os cruzamentos de automóveis, as faixas de pedestres permitem muito mais opções de passagem. Um cruzamento padrão tem 56 opções de caminhada, dependendo da posição dos pontos inicial (8 lados do cruzamento) e final (7 lados). E em cada versão - até três manobras de pedestres.
E os próprios cruzamentos de pedestres, devido a toda variedade de caminhos de pedestres e seus cruzamentos no gráfico, são muitas vezes mais do que os de automóveis. Levando em consideração que percebemos crescimento apenas na fase inicial de acerto das instruções e ainda havia muitos casos não resolvidos, a tendência foi assustadora.
Por causa disso, abandonamos a ideia de pré-calcular as instruções para pedestres e movemos a lógica de sua geração para o tempo de execução. Se houver Internet, as instruções são calculadas em nossos servidores, e se não houver Internet ou a resposta do servidor não atingiu o tempo limite, então no aplicativo móvel. Na verdade, reescrevemos o algoritmo do zero.
Tornamo-nos menos dependentes da versão dos dados. E em combinação com o fato de que a maioria dos scripts são construídos através de nosso servidor online, tornou-se possível refinar rapidamente o algoritmo para todos os usuários de uma vez.
Novas instruções
Repito que as passarelas de pedestres em cruzamentos são muito mais variáveis em comparação com as de automóveis.
Cada cruzamento é uma oportunidade para mudar o percurso.
Na fase de elaboração das instruções, nos deparamos com o problema da sua apresentação compacta, inequívoca e oportuna. O asterisco para a tarefa foi adicionado pelo fato de o telefone poder estar no bolso, e o usuário não ver a linha guia e as setas. Você só pode se concentrar na orientação por voz. Além disso, um pedestre, ao contrário de um carro, pode facilmente virar em quase qualquer ângulo em uma área muito estreita. E é importante explicar a uma pessoa com a maior precisão possível como e onde exatamente atravessar a rua, virar ou descer.
No início, dei uma volta e anotei os erros. Às vezes, eu passava pelos cruzamentos várias dezenas de vezes para entender quais seriam as opções. Em seguida, fizeram um emulador, no qual lançaram um pedestre virtual, e ouviram o que lhe era falado e em que momento.
Verificamos a dublagem de caminhos na floresta, estradas de pátio, cruzamentos em cruzamentos largos, passagens de pedestres não regulamentadas e regulamentadas com semáforos.
A experiência prática recolhida foi analisada, discutida, dividida em grupos de melhorias, unidas por soluções comuns. Para cada um deles, cenários algorítmicos foram inventados.
Nesse estágio, percebeu-se que as instruções de um componente, como as de automóveis, não eram suficientes - em percursos pedestres, duas instruções separadas eram tão próximas que, devido ao GPS impreciso, poderiam soar fora do tempo e confundir uma pessoa.
Fizemos instruções de voz composta para nos orientar antes da transição, em que direção nos mover depois dela.
Do ponto de vista do usuário, tal instrução não difere da usual para automóveis. Portanto, a frase "Vire à esquerda e depois vire à direita após 100 metros" para um carro é duas instruções de um componente
“Vire à esquerda” + “após 100 metros, vire à direita”. E para os pedestres, a frase para atravessar a rua “Vire à esquerda na faixa de pedestres e depois vire à direita” é completamente uma instrução.
Na verdade, essas instruções são conjuntos de quaisquer instruções elementares de giro, mas na forma de uma única instrução falada. Essa abordagem tornou possível aumentar significativamente o conteúdo da informação e a conveniência da manutenção em segundo plano. Especialmente ao cruzar cruzamentos não triviais.
Na faixa de pedestres mais próxima, vire à esquerda
e , imediatamente após a passagem, vire à direita
O que mais
"Ajustando" o geo-posicionamento
As rotas de pedestres geralmente incluem passagens relativamente rasas - as bordas do gráfico. E em condições urbanas, quando o sinal é instável e / ou blindado por arranha-céus, erros de posicionamento podem interferir no cálculo correto das instruções e orientações ao longo do percurso. Para não lançar acidentalmente o ponto atual para o outro lado da rua, "afinamos" ligeiramente o algoritmo - levamos em consideração as nuances do erro e ajustamos o algoritmo para traçar a rota de até 30 metros.
Vibro
A orientação por voz é a solução quando o telefone está no seu bolso. Mas para evitar a situação em que a voz não será ouvida em uma cidade barulhenta, adicionamos a vibração, que é acionada em conjunto com a dublagem antes da manobra desejada. O padrão de vibração em si era diferente do usual durante a comunicação em um mensageiro.
O que aconteceu
Como resultado, a primeira versão pública do navegador para pedestres levou cerca de seis meses. Agora está disponível na versão 2GIS para iOS e Android.
Fizemos um excelente trabalho, mas nós próprios sabemos que perdemos opções complicadas. Envie pelo aplicativo mobile os casos que mostramos e verbalizamos incorretamente - cada um será considerado e levado em consideração no algoritmo.