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

Aun Johnsen lists em gimnechiske.org
Domingo Julho 20 16:03:47 UTC 2014


Eu poder testar no meu Nüvi, usando mapas do garmin.openstreetmap.nl

Aun Johnsen
Sent from my iPhone

> On 20. juli 2014, at 12:47, Paulo Carvalho <paulo.r.m.carvalho at gmail.com> wrote:
> 
> 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 at 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 at gmail.com>:
>> >
>> >
>> >
>> > Em 19 de julho de 2014 22:29, Fernando Trebien <fernando.trebien at 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 at 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 at 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 at 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 at 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 at 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 at openstreetmap.org
>> >> >> >> > https://lists.openstreetmap.org/listinfo/talk-br
>> >> >> >> >
>> >> >> >>
>> >> >> >>
>> >> >> >>
>> >> >> >> --
>> >> >> >> Fernando Trebien
>> >> >> >> +55 (51) 9962-5409
>> >> >> >>
>> >> >> >> "Nullius in verba."
>> >> >> >>
>> >> >> >> _______________________________________________
>> >> >> >> Talk-br mailing list
>> >> >> >> Talk-br at openstreetmap.org
>> >> >> >> https://lists.openstreetmap.org/listinfo/talk-br
>> >> >> >
>> >> >> >
>> >> >> >
>> >> >> > _______________________________________________
>> >> >> > Talk-br mailing list
>> >> >> > Talk-br at openstreetmap.org
>> >> >> > https://lists.openstreetmap.org/listinfo/talk-br
>> >> >> >
>> >> >>
>> >> >>
>> >> >>
>> >> >> --
>> >> >> Fernando Trebien
>> >> >> +55 (51) 9962-5409
>> >> >>
>> >> >> "Nullius in verba."
>> >> >>
>> >> >> _______________________________________________
>> >> >> Talk-br mailing list
>> >> >> Talk-br at openstreetmap.org
>> >> >> https://lists.openstreetmap.org/listinfo/talk-br
>> >> >
>> >> >
>> >> >
>> >> > _______________________________________________
>> >> > Talk-br mailing list
>> >> > Talk-br at openstreetmap.org
>> >> > https://lists.openstreetmap.org/listinfo/talk-br
>> >> >
>> >>
>> >>
>> >>
>> >> --
>> >> Fernando Trebien
>> >> +55 (51) 9962-5409
>> >>
>> >> "Nullius in verba."
>> >>
>> >> _______________________________________________
>> >> Talk-br mailing list
>> >> Talk-br at openstreetmap.org
>> >> https://lists.openstreetmap.org/listinfo/talk-br
>> >
>> >
>> >
>> > _______________________________________________
>> > Talk-br mailing list
>> > Talk-br at openstreetmap.org
>> > https://lists.openstreetmap.org/listinfo/talk-br
>> >
>> 
>> 
>> 
>> --
>> Fernando Trebien
>> +55 (51) 9962-5409
>> 
>> "Nullius in verba."
>> 
>> _______________________________________________
>> Talk-br mailing list
>> Talk-br at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/talk-br
> 
> _______________________________________________
> Talk-br mailing list
> Talk-br at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/talk-br
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/talk-br/attachments/20140720/12b2a513/attachment-0001.html>


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