[Talk-br] A importância de não quebrar a hierarquia das vias dentro de cidades.

Fernando Trebien fernando.trebien em gmail.com
Domingo Julho 20 18:17:06 UTC 2014


"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.trebien em 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.carvalho em 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.trebien em 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.carvalho em gmail.com>:
>>> >
>>> >
>>> >
>>> > Em 19 de julho de 2014 22:29, Fernando Trebien
>>> > <fernando.trebien em 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.carvalho em 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.trebien em 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.carvalho em 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.trebien em 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.carvalho em 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 em openstreetmap.org
>>> >> >> >> > https://lists.openstreetmap.org/listinfo/talk-br
>>> >> >> >> >
>>> >> >> >>
>>> >> >> >>
>>> >> >> >>
>>> >> >> >> --
>>> >> >> >> Fernando Trebien
>>> >> >> >> +55 (51) 9962-5409
>>> >> >> >>
>>> >> >> >> "Nullius in verba."
>>> >> >> >>
>>> >> >> >> _______________________________________________
>>> >> >> >> Talk-br mailing list
>>> >> >> >> Talk-br em openstreetmap.org
>>> >> >> >> https://lists.openstreetmap.org/listinfo/talk-br
>>> >> >> >
>>> >> >> >
>>> >> >> >
>>> >> >> > _______________________________________________
>>> >> >> > Talk-br mailing list
>>> >> >> > Talk-br em openstreetmap.org
>>> >> >> > https://lists.openstreetmap.org/listinfo/talk-br
>>> >> >> >
>>> >> >>
>>> >> >>
>>> >> >>
>>> >> >> --
>>> >> >> Fernando Trebien
>>> >> >> +55 (51) 9962-5409
>>> >> >>
>>> >> >> "Nullius in verba."
>>> >> >>
>>> >> >> _______________________________________________
>>> >> >> Talk-br mailing list
>>> >> >> Talk-br em openstreetmap.org
>>> >> >> https://lists.openstreetmap.org/listinfo/talk-br
>>> >> >
>>> >> >
>>> >> >
>>> >> > _______________________________________________
>>> >> > Talk-br mailing list
>>> >> > Talk-br em openstreetmap.org
>>> >> > https://lists.openstreetmap.org/listinfo/talk-br
>>> >> >
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> Fernando Trebien
>>> >> +55 (51) 9962-5409
>>> >>
>>> >> "Nullius in verba."
>>> >>
>>> >> _______________________________________________
>>> >> Talk-br mailing list
>>> >> Talk-br em openstreetmap.org
>>> >> https://lists.openstreetmap.org/listinfo/talk-br
>>> >
>>> >
>>> >
>>> > _______________________________________________
>>> > Talk-br mailing list
>>> > Talk-br em openstreetmap.org
>>> > https://lists.openstreetmap.org/listinfo/talk-br
>>> >
>>>
>>>
>>>
>>> --
>>> Fernando Trebien
>>> +55 (51) 9962-5409
>>>
>>> "Nullius in verba."
>>>
>>> _______________________________________________
>>> Talk-br mailing list
>>> Talk-br em openstreetmap.org
>>> https://lists.openstreetmap.org/listinfo/talk-br
>>
>>
>>
>> _______________________________________________
>> Talk-br mailing list
>> Talk-br em 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."



Mais detalhes sobre a lista de discussão Talk-br