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

Paulo Carvalho paulo.r.m.carvalho em gmail.com
Domingo Julho 20 13:47:16 UTC 2014


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
>
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://lists.openstreetmap.org/pipermail/talk-br/attachments/20140720/61f61348/attachment-0001.html>


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