"Acho razoável se basear na rota do OSRM pra elencar um ponto mais ou menos" > mais ou menos no meio
2014-07-20 15:16 GMT-03:00 Fernando Trebien <fernando.treb...@gmail.com>: > Uma sugestão para diminuir o espaço de busca: dividir para conquistar. > > Ao invés de calcular uma rota tão longa, tente calcular a rota até > metade do caminho, e depois da metade até o destino. (Não precisa ser > exatamente a metade, qualquer ponto mais ou menos no meio serve.) O > problema vai estar no trecho em que esse teste falhar. > > Daí você pega o trecho problemático e repete: testa a primeira metade > dele, depois a segunda metade. Cada vez que você repete você diminui o > espaço de busca. São 3000km, dividindo por 2 a cada vez você > provavelmente vai chegar à raiz exata do problema em menos de 20 > tentativas. > > Como saber onde fica a metade? Acho razoável se basear na rota do OSRM > pra elencar um ponto mais ou menos: http://osrm.at/8yC > > Um complicador é que pode ter mais de um problema ao longo de toda > essa rota. Se os dois trechos falharem, você vai ter que testar os > dois trechos separadamente, ao invés de eliminar um deles. E se forem > muitos os problemas, pode precisar de papel e caneta pra lembrar de > quais trechos você já testou. > > É bem provável que isso seja de fato um erro de classificação que > precisa ser corrigido no OSM - não com o objetivo específico de fazer > o Garmin funcionar, mas sim com o objetivo de deixar a classificação > correta. Sim, aplicações mais simples podem ser usadas (e normalmente > são uma forma excelente) para detectar problemas com os dados que não > interferem tanto com as aplicações mais modernas. E nesse caso > específico tanto a comunidade do OSM (agnóstica aos dispositivos) > quanto os usuários de Garmin saem ganhando. > > 2014-07-20 12:47 GMT-03:00 Paulo Carvalho <paulo.r.m.carva...@gmail.com>: >> Temos um exemplo de um mapa Garmin que não está calculando uma rota entre o >> extremo sul do Brasil e um ponto no Ceará. A rota é calculada normalmente >> no Mapsource (computador) mas não no GPS (dipositivo móvel). O problema é >> justamente localizar onde está a interrupção ou alternância de classificação >> de vias nos mais de 3000km da rota. >> >> >> Em 20 de julho de 2014 12:05, Fernando Trebien <fernando.treb...@gmail.com> >> escreveu: >> >>> Contraction hierarquies permite usar Dijkstra bidirecional + alguma >>> heurística otimista em ambientes com restrições de memória e >>> capacidade computacional sem remover qualquer via do cálculo. Isso tá >>> lá nos papers referenciados no final daquele artigo da Wikipédia que >>> você apontou. Era a isso que eu me referia ao julgar a inteligência do >>> algoritmo, e por ser um fato (o algoritmo foi publicado e nada >>> "impede" que seja implementado), não tem como ser arrogante. É uma >>> escolha simples (bem, não tão simples) que o desenvolvedor da >>> aplicação tem que fazer. E é uma escolha que é independente do mapa >>> (que, novamente, serve a vários propósitos, não só ao roteamento, não >>> só ao roteamento em ambientes com capacidades limitadas). >>> >>> "Mas interromper uma motorway com um trecho de residential vai quebrar >>> o roteamento em muitas aplicações." Pode dar um exemplo de aplicação e >>> local? >>> >>> Apesar de solicitar esse exemplo, não conheço nenhum caso em que uma >>> motorway/trunk precisaria ter um trecho classificado como >>> "residencial". Na pior das hipóteses, teria um trecho classificado >>> como terciária por estar não-pavimentada - mas acho que nem no Brasil >>> essa situação ocorre. Recentemente eu achei um exemplo em que uma >>> trunk se intercala com uma primária [1], mas isso também não deve >>> afetar esses sistemas que descartam vias a que você se refere. >>> >>> E claro, no caso particular, raro, e bizarro de uma classificação fiel >>> produzir uma situação assim, podemos pensar em discutir com a >>> comunidade sobre o que fazer. A idéia de não alternar demais a >>> classificação da via poderia ser aplicada ser for só um trecho curto >>> com características diferentes, e o motivo não seria só o roteamento. >>> >>> [1] http://www.openstreetmap.org/#map=12/-29.5385/-51.8998 >>> >>> 2014-07-20 10:47 GMT-03:00 Paulo Carvalho <paulo.r.m.carva...@gmail.com>: >>> > >>> > >>> > >>> > Em 19 de julho de 2014 22:29, Fernando Trebien >>> > <fernando.treb...@gmail.com> >>> > escreveu: >>> > >>> >> Sabendo que há trabalhos cientificos publicados descrevendo bons >>> >> algoritmos para esses ambientes e que não descartam quaisquer vias >>> >> (mesmo as de classe bem inferior), acho que não devemos fazer >>> >> adaptações no mapa em favor de algoritmos menos inteligentes. (Isso >>> >> seria mapear para a aplicação.) >>> > >>> > >>> > Menos inteligentes???? Desculpa, Fernando, esse seu comentário foi um >>> > tanto arrogante. Quando você tem restrição de recursos de hardware em >>> > dispositivos móveis você TEM que fazer otimização. Isso para mim é sinal >>> > de >>> > extrema inteligência. >>> > >>> > E só uma palavra sobre artigos científicos: poucas vezes tratam-se de >>> > ideias >>> > praticáveis. O algoritmo Dijkstra é um exemplo. Ninguém usa a forma tal >>> > como publicada pelo Dijkstra originalmente. A indústria sempre faz >>> > várias >>> > melhorias para o mundo real. Sei disso porque trabalho nos dois mundos >>> > e >>> > também porque estou escrevendo um artigo e não estou pensando em >>> > problemas >>> > de ordem prática. A teoria já dá trabalho suficiente. Isso não é >>> > pecado, é >>> > como o progresso funciona: cada especialista em sua área. >>> > >>> >> >>> >> >>> >> Mas, ao mesmo tempo, acho que são muito raros os casos em que >>> >> adaptações seriam necessárias para evitar problemas com esses >>> >> algoritmos que descartam vias. A menos que eles estejam descartando >>> >> até as vias primárias (arteriais urbanas), daí não tem como resolver >>> >> mesmo. >>> > >>> > >>> > Não são raros não. Você tem que pensar em para que a maioria dos >>> > usuários >>> > precisa de um mapa de ruas (Street Map): >>> > a) Encontrar um lugar (geocoding); >>> > b) Navegar até um lugar (roteamento); >>> > c) Quase sempre em trânsito, com dispositivos móveis. >>> > >>> > Se essas coisas não estão funcionando bem, elas procurarão alternativas >>> > e aí >>> > seu mapa será o mais puro do mundo mas vazio de propósito. Se queres >>> > que o >>> > mapa se torne popular, TEM que pensar nas questões de ordem prática. >>> > >>> > Acho que dá para conciliar os princípios do OSM com as questões >>> > práticas. >>> > Mas interromper uma motorway com um trecho de residential vai quebrar o >>> > roteamento em muitas aplicações. Não digo colocar tudo igual, mas não >>> > deixar as classes tão contrastantes conforme já exemplificado. >>> > >>> > []s >>> > >>> > Paulo >>> > >>> >> >>> >> >>> >> 2014-07-19 17:56 GMT-03:00 Paulo Carvalho >>> >> <paulo.r.m.carva...@gmail.com>: >>> >> > E qual sua opinião sobre o descarte de vias de baixa prioridade nos >>> >> > roteamentos de longa distância em ambientes com baixa memória e >>> >> > processamento mais lento? >>> >> > >>> >> > >>> >> > Em 19 de julho de 2014 12:58, Fernando Trebien >>> >> > <fernando.treb...@gmail.com> >>> >> > escreveu: >>> >> > >>> >> >> Li sim, há bastante tempo. Mas acho que estás confundindo as >>> >> >> hierarquias do OSM com a hierarquia de atalhos emergente que o >>> >> >> algoritmo de "contraction hierarchies" produz (que inclusive pode >>> >> >> ter >>> >> >> muito mais níveis do que os poucos que existem no OSM). Os atalhos >>> >> >> servem apenas para acelerar outro algoritmo de roteamento qualquer >>> >> >> (geralmente se adota uma variação do Dijkstra, e nesse caso as >>> >> >> heurísticas acabam preferindo usar os atalhos). E a hierarquia do >>> >> >> OSM >>> >> >> não se converte em atalhos automaticamente. A sequẽncia das coisas é >>> >> >> assim: >>> >> >> - cada arco original representa a ligação de duas interseções no >>> >> >> mapa >>> >> >> - o peso dos arcos originais é atribuído por velocidade X distância, >>> >> >> onde velocidade é uma estimativa feita de forma diferente por cada >>> >> >> aplicação (algumas usam a classificação da via, outras não) >>> >> >> - (contraction hierarchies) os arcos de atalho são gerados >>> >> >> eliminando >>> >> >> sequências de arcos cujo peso total é muito alto >>> >> >> - (contraction hierarchies) um grafo é formado combinando os arcos >>> >> >> originais com os atalhos >>> >> >> - um algoritmo de busca em grafos é aplicado sobre o grafo >>> >> >> resultante >>> >> >> (< ou seja, esse algoritmo vai usar tanto atalhos quanto arcos >>> >> >> originais, possivelmente se intercalando entre os dois) >>> >> >> >>> >> >> Por exemplo, se você tiver dois caminhos de A a B com quase a mesma >>> >> >> distância total, um deles é uma primária com velocidade de 10km/h, e >>> >> >> outro é uma terciária intercalada com trechos de living_street que, >>> >> >> na >>> >> >> média, fica em torno de 80km/h, vai ser a primária que vai ser >>> >> >> removida na geração dos atalhos e o segundo caminho (mais rápido, >>> >> >> embora envolva vias de classificação inferior) que vai virar um >>> >> >> atalho. O fato de ser primária, secundária, living street, não faz >>> >> >> diferença alguma a princípio - a menos que exista um programa antes >>> >> >> (como o mkgmap) que associa a classificação ao peso do arco (mais >>> >> >> especificamente à velocidade, já que a distância é exata sempre). O >>> >> >> OSRM, por exemplo, não associa quando a velocidade máxima é definida >>> >> >> (ou seja, o segundo caso pode acontecer). >>> >> >> >>> >> >> Enfim, isso é um detalhe, a classificação tem que estar bem feita >>> >> >> por >>> >> >> diversos motivos, mas (se formos pensar genericamente, para vários >>> >> >> sistemas) não se pode ignorar o mapeamento da velocidade máxima das >>> >> >> vias. >>> >> >> >>> >> >> 2014-07-19 12:10 GMT-03:00 Paulo Carvalho >>> >> >> <paulo.r.m.carva...@gmail.com>: >>> >> >> >> Pra esse algoritmo só importa a velocidade atribuída a cada >>> >> >> >> trecho >>> >> >> >> das >>> >> >> >> vias (e a atribuição pode não ter relação direta com aquilo que >>> >> >> >> foi >>> >> >> >> mapeado, só indireta). >>> >> >> > >>> >> >> > >>> >> >> > Não é bem assim. Na graduação se ensina o Djkstra que leva a >>> >> >> > maioria >>> >> >> > das >>> >> >> > pessoas focar apenas no custo de percurso. Mas uma aplicação real >>> >> >> > é >>> >> >> > mais >>> >> >> > complexa. O tamanho do grafo é um fator de extrema relevância. >>> >> >> > >>> >> >> > Acho que tu não leste o artigo sobre Hierarchy Contraction. >>> >> >> > Existe >>> >> >> > uma >>> >> >> > otimização que é feita nos dispositivos móveis. Enfim, vou >>> >> >> > resumir: >>> >> >> > para >>> >> >> > rotas de longa distância, em que analisar o grafo todo seria muito >>> >> >> > custoso >>> >> >> > tanto em termos de desempenho quanto de memória, é feito um >>> >> >> > descarte >>> >> >> > de >>> >> >> > vias >>> >> >> > de baixa hierarquia. As vias de menor hierarquia só passam a ser >>> >> >> > computadas >>> >> >> > nas proximidades dos pontos de origem e de destino. Por causa >>> >> >> > desse >>> >> >> > descarte, o cálculo de rotas longas pode falhar em smartphones, >>> >> >> > tablets >>> >> >> > e >>> >> >> > GPSs para mapas mal desenhados. >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > Em 19 de julho de 2014 11:56, Fernando Trebien >>> >> >> > <fernando.treb...@gmail.com> >>> >> >> > escreveu: >>> >> >> > >>> >> >> >> Só acrescentando uns detalhes. Um resumo da ópera: em alguns >>> >> >> >> sistemas, >>> >> >> >> a classificação pode ter um efeito no roteamento, mas >>> >> >> >> fundamentalmente >>> >> >> >> o mais importante é mapear as características da via (velocidade >>> >> >> >> máxima, superfície, etc.). >>> >> >> >> >>> >> >> >> Pra esse algoritmo só importa a velocidade atribuída a cada >>> >> >> >> trecho >>> >> >> >> das >>> >> >> >> vias (e a atribuição pode não ter relação direta com aquilo que >>> >> >> >> foi >>> >> >> >> mapeado, só indireta). Se não for mapeada a velocidade máxima das >>> >> >> >> vias, então a maioria dos roteadores tenta "adivinhar" a >>> >> >> >> velocidade >>> >> >> >> a >>> >> >> >> partir da classificação. Como exemplo, eis aqui [1] como o OSRM >>> >> >> >> faz >>> >> >> >> essa adivinhação (lembrando que é um serviço mais voltado às >>> >> >> >> características do trânsito na Europa). >>> >> >> >> >>> >> >> >> Então, sim, a classificação é importante para o roteamento caso >>> >> >> >> não >>> >> >> >> seja mapeada a velocidade máxima. Mas, fundamentalmente, o mais >>> >> >> >> importante para o roteamento é a velocidade atribuída à via. >>> >> >> >> Existem >>> >> >> >> casos em que uma primária urbana tem velocidade reduzida num >>> >> >> >> trecho >>> >> >> >> curto e isso faz diferença pro roteamento decidir mandar o >>> >> >> >> usuário >>> >> >> >> por >>> >> >> >> ali ou não. Só seria mapear para a aplicação se alguém mudasse a >>> >> >> >> classificação naquele trecho por causa da velocidade, para forçar >>> >> >> >> um >>> >> >> >> roteador a evitar o trecho. (Um problema é que muita gente faz >>> >> >> >> isso.) >>> >> >> >> >>> >> >> >> Especificamente para o Garmin/mkgmap, parece que ainda existe o >>> >> >> >> conceito de "classe de velocidade", que não é nem a classificação >>> >> >> >> da >>> >> >> >> via (que se reflete no desenho), nem a velocidade máxima (que >>> >> >> >> produz >>> >> >> >> os alertas de velocidade). Essa é uma velocidade estimada de >>> >> >> >> trânsito >>> >> >> >> que no mkgmap [2] pode ter regras até bem complexas de derivação >>> >> >> >> (nos >>> >> >> >> exemplos que eu vi por aí o pessoal estava derivando esse campo a >>> >> >> >> partir de uma combinação da classe da via e da velocidade >>> >> >> >> máxima). >>> >> >> >> Até >>> >> >> >> daria pra mapear no OSM uma velocidade "esperada" pra via (que >>> >> >> >> então >>> >> >> >> se traduziria diretamente nessa velocidade do Garmin), mas isso é >>> >> >> >> complicado de padronizar e por isso pode gerar divergências (e >>> >> >> >> guerras >>> >> >> >> de edição) e até pode acabar não sendo usado. [3] Algumas >>> >> >> >> abordagens >>> >> >> >> melhores são coletar a velocidade média [4] e monitorar o tráfego >>> >> >> >> [5]. >>> >> >> >> Com essas duas abordagens, a classificação se torna irrelevante >>> >> >> >> pro >>> >> >> >> roteamento (por exemplo, no caso de uma primária estar sempre >>> >> >> >> congestionada e uma secundária paralela estar sempre livre). >>> >> >> >> >>> >> >> >> [1] >>> >> >> >> >>> >> >> >> >>> >> >> >> https://github.com/DennisOSRM/Project-OSRM/blob/master/profiles/car.lua >>> >> >> >> [2] http://www.mkgmap.org.uk/doc/pdf/style-manual.pdf seção 4.6.5 >>> >> >> >> [3] >>> >> >> >> >>> >> >> >> >>> >> >> >> >>> >> >> >> http://wiki.openstreetmap.org/wiki/Talk:Proposed_features/traffic_speed#Practicality_of_Using_Info_in_Router >>> >> >> >> [4] http://wiki.openstreetmap.org/wiki/Average_speed_per_way >>> >> >> >> [5] >>> >> >> >> >>> >> >> >> >>> >> >> >> https://lists.openstreetmap.org/pipermail/talk/2012-August/063985.html >>> >> >> >> >>> >> >> >> 2014-07-15 8:30 GMT-03:00 Paulo Carvalho >>> >> >> >> <paulo.r.m.carva...@gmail.com>: >>> >> >> >> > Amigos, >>> >> >> >> > >>> >> >> >> > Para compreender a razão de não quebrar a hierarquia de >>> >> >> >> > vias >>> >> >> >> > nos >>> >> >> >> > pequenos trechos que rodovias passam por cidades, recomendo >>> >> >> >> > esta >>> >> >> >> > leitura: >>> >> >> >> > >>> >> >> >> > http://en.wikipedia.org/wiki/Contraction_hierarchies >>> >> >> >> > >>> >> >> >> > Aos que já estão com o argumento "isso é mapear para >>> >> >> >> > aplicação" >>> >> >> >> > na >>> >> >> >> > ponta >>> >> >> >> > da língua rogo um momento para parar e pensar: >>> >> >> >> > >>> >> >> >> > "For routing software to work well, the underlying map data >>> >> >> >> > must >>> >> >> >> > be >>> >> >> >> > of >>> >> >> >> > good >>> >> >> >> > quality. Essentially this means that ways that should be >>> >> >> >> > connected >>> >> >> >> > are >>> >> >> >> > in >>> >> >> >> > fact connected, one-way roads are tagged, turn restrictions are >>> >> >> >> > mapped, >>> >> >> >> > and >>> >> >> >> > so on. You should be familiar with the Map Features used, in >>> >> >> >> > particular >>> >> >> >> > see >>> >> >> >> > OSM tags for routing to understand the tags specific to >>> >> >> >> > routing." >>> >> >> >> > (grifo >>> >> >> >> > meu) >>> >> >> >> > >>> >> >> >> > Palavras da própria comunidade OSM. >>> >> >> >> > >>> >> >> >> > Fonte: http://wiki.openstreetmap.org/wiki/Routing >>> >> >> >> > >>> >> >> >> > [ ]s >>> >> >> >> > >>> >> >> >> > Paulo >>> >> >> >> > >>> >> >> >> > _______________________________________________ >>> >> >> >> > Talk-br mailing list >>> >> >> >> > Talk-br@openstreetmap.org >>> >> >> >> > https://lists.openstreetmap.org/listinfo/talk-br >>> >> >> >> > >>> >> >> >> >>> >> >> >> >>> >> >> >> >>> >> >> >> -- >>> >> >> >> Fernando Trebien >>> >> >> >> +55 (51) 9962-5409 >>> >> >> >> >>> >> >> >> "Nullius in verba." >>> >> >> >> >>> >> >> >> _______________________________________________ >>> >> >> >> Talk-br mailing list >>> >> >> >> Talk-br@openstreetmap.org >>> >> >> >> https://lists.openstreetmap.org/listinfo/talk-br >>> >> >> > >>> >> >> > >>> >> >> > >>> >> >> > _______________________________________________ >>> >> >> > Talk-br mailing list >>> >> >> > Talk-br@openstreetmap.org >>> >> >> > https://lists.openstreetmap.org/listinfo/talk-br >>> >> >> > >>> >> >> >>> >> >> >>> >> >> >>> >> >> -- >>> >> >> Fernando Trebien >>> >> >> +55 (51) 9962-5409 >>> >> >> >>> >> >> "Nullius in verba." >>> >> >> >>> >> >> _______________________________________________ >>> >> >> Talk-br mailing list >>> >> >> Talk-br@openstreetmap.org >>> >> >> https://lists.openstreetmap.org/listinfo/talk-br >>> >> > >>> >> > >>> >> > >>> >> > _______________________________________________ >>> >> > Talk-br mailing list >>> >> > Talk-br@openstreetmap.org >>> >> > https://lists.openstreetmap.org/listinfo/talk-br >>> >> > >>> >> >>> >> >>> >> >>> >> -- >>> >> Fernando Trebien >>> >> +55 (51) 9962-5409 >>> >> >>> >> "Nullius in verba." >>> >> >>> >> _______________________________________________ >>> >> Talk-br mailing list >>> >> Talk-br@openstreetmap.org >>> >> https://lists.openstreetmap.org/listinfo/talk-br >>> > >>> > >>> > >>> > _______________________________________________ >>> > Talk-br mailing list >>> > Talk-br@openstreetmap.org >>> > https://lists.openstreetmap.org/listinfo/talk-br >>> > >>> >>> >>> >>> -- >>> Fernando Trebien >>> +55 (51) 9962-5409 >>> >>> "Nullius in verba." >>> >>> _______________________________________________ >>> Talk-br mailing list >>> Talk-br@openstreetmap.org >>> https://lists.openstreetmap.org/listinfo/talk-br >> >> >> >> _______________________________________________ >> Talk-br mailing list >> Talk-br@openstreetmap.org >> https://lists.openstreetmap.org/listinfo/talk-br >> > > > > -- > Fernando Trebien > +55 (51) 9962-5409 > > "Nullius in verba." -- Fernando Trebien +55 (51) 9962-5409 "Nullius in verba." _______________________________________________ Talk-br mailing list Talk-br@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-br
