[Talk-br] Necessidade de intermediação

Domingo Julho 5 15:16:48 UTC 2015

Eu não trabalho com isso mas já estudei o assunto a fundo. Mudei de área
quando vi que essa já estava muito avançada.

O que geralmente se faz é calcular o grafo dual do mapa geográfico: linhas
viram nós e pontos de conexão entre elas viram linhas entre esses nós. Uma
restrição de conversão se torna a exclusão de uma ou mais das linhas
resultantes de um cruzamento. Os nós contém os pesos (tempo, ou velocidade
e distância) de trafegar pela linha. O algoritmo então simplesmente explora
essa estrutura de dados até chegar no destino. Conforme explora, vai
somando os tempos. Quando encontrar a sequência que minimiza o tempo total,
termina. Como o grafo geralmente é imenso, usam-se heurísticas para
desconsiderar alguns caminhos. É aí que os algoritmos começam a dar
resultados diferentes para os mesmos dados.

Eu dei uma olhada por altos no projeto do mkgmap pra ver se poderia ajudar,
mas achei confusa a sua organização. O projeto não tem um líder e "evolui"
com contribuições eventuais. Também acho seu escopo limitado aos usuários
de Garmin (eu não tenho um Garmin), e o meu interesse são sistemas open
source que cheguem ao grande público. O OSRM é o contrário de tudo isso:
algoritmo estado-da-arte, código muito bem escrito, comunidade organizada e
responsiva, e utilizável pelo mundo todo sem precisar de ferramentas pagas.

As dificuldades relatadas até aqui me fazem supor que o Mapfactor Navigator
usa um algoritmo similar ao Garmin. É grátis e tem pra celular. E a
comunidade do Mapfactor, embora pequena, me parece maior e mais organizada
que a do mkgmap. Talvez o pessoal queira dar uma olhada no aplicativo.
On 5 Jul 2015 11:17, "Aun Johnsen" <lists em gimnechiske.org> wrote:

> Fernando,
>
> Se eu entendo esse certa o graf de roteamento, alias o produto do
> algoritmo, não ha informação geográfico mas tem linhas que representa
> tempo e distancia entre nos que representando locações fisico, um no
> pode ser um ponto onde 2 vias cruzam, mas pode também ser a rotatório
> completo, ou ate um trevo complicado como um ponto so. Um ponto pode
> ser um referencia da rota (vira a esquerda no BR-101), ou um ponto do
> penalidade (espera 2 segundos no semáforo). Esses linhas e pontos e
> abstratos, e não direitamente retirado do mapa física.
>
> Se voce trabalho com isso, talvez voce posso ajudar identificar os
> objetos que pode/deve dar penalidade de roteamento?
>
> On 7/5/15, Fernando Trebien <fernando.trebien em gmail.com> wrote:
> > Aí você que entra na minha área de expertise como se soubesse mais. Sou
> > mestre em computação, li várias versões desses algoritmos.
> >
> > O nó a que me refiro é o do grafo de roteamento. Não é o nó do mapa (com
> > coordenadas e tal). O nó do grafo de roteamento sequer tem coordenadas,
> > possui apenas propriedades abstratas como o tempo para atravessar uma
> linha
> > de uma ponta à outra, e a referência a essa linha daí sim no mapa
> > geográfico.
> > On 5 Jul 2015 05:44, "Marcio - Thundercel" <thundercel em gpsinfo.com.br>
> > wrote:
> >
> >> Uma coisa é o esperado de acordo com a teoria e outra o observado na
> >> pratica em exaustivos testes.
> >>
> >>  A criação do nó em si não interfere, a princípio, com o algoritmo.
> >>> Será um nó a mais a ser visitado enquanto o grafo é explorado pelo
> >>> algoritmo de roteamento.
> >>>
> >>
> >> O algoritmo, dentre outros, trata os nós e é por eles que ele traça a
> >> rota.
> >>
> >> Já fizemos inúmeros testes de roteamento e identificamos que o
> >> roteamento,
> >> entre duas vias iguais, ele opta pela que tem menos nós.
> >>
> >> Faça o teste chegando em um nó onde se abrem duas vias e que se fecham
> lá
> >> na frente, como um losango.
> >> Divida um segmento de reta de uma das vias inserindo um nó nela.
> >> Identificará que o roteamento se dá pela via que não tem o nó inserido.
> >> Foi assim que nos testes constatamos a influência de partições de via em
> >> um roteamento.
> >>
> >> -----Mensagem Original----- From: Fernando Trebien
> >> Sent: Sunday, July 5, 2015 4:52 AM
> >> To: OpenStreetMap no Brasil
> >> Subject: Re: [Talk-br] Necessidade de intermediação
> >>
> >> 2015-07-05 1:40 GMT-03:00 Marcio - Thundercel
> >> <thundercel em gpsinfo.com.br>:
> >>
> >>> Por outro lado lembro que classificação de vias e de velocidades
> >>> interferem
> >>> no roteamento e, infelizmente, não dominamos ainda o algoritmo garmin.
> O
> >>> que
> >>> sabemos sobre ele advém de exaustivos testes realizados.
> >>> Não estamos debatendo tempo e sim roteamento e tudo que interfere nele.
> >>> Como bem deve saber você o roteamento leva em consideração, além de
> >>> outros,
> >>> a quantidade de nós empregados para unir os segmentos de reta na
> >>> retratação
> >>> da via.
> >>> Ao se reduzir a velocidade de um trecho de via o editor é obrigado a
> >>> dividir
> >>> a via de forma a poder no trecho dividido estabelecer a velocidade.
> Isso
> >>> por
> >>> si só já afeta o calculo de rota por aquele trecho.
> >>>
> >>
> >> Afeta, mas muito pouco, pelo menos na minha compreensão de algoritmos
> >> de roteamento.
> >>
> >> O que acontece é que ele cria um novo nó no grafo de roteamento para
> >> representar o trecho. O nó contem o tempo total para percorrer o
> >> trecho, calculado dividindo distância por velocidade. (há variações em
> >> que o nó contem ambas velocidade e distância e o cálculo do tempo é
> >> feito durante o processamento, mas elas são matematicamente
> >> equivalentes)
> >>
> >> A criação do nó em si não interfere, a princípio, com o algoritmo.
> >> Será um nó a mais a ser visitado enquanto o grafo é explorado pelo
> >> algoritmo de roteamento.
> >>
> >> O que acontece é que algoritmos diferentes usam heurísticas
> >> diferentes. Algumas dessas heurísticas decidem "descartar" alguns nós
> >> que eles "acham" que têm pouca chance de conduzir à melhor rota.
> >> "Heurística" é um método matematicamente impreciso para chegar a uma
> >> solução sub-ótima mais rapidamente. Se é impreciso, há heurísticas
> >> melhores e piores. Uma heurística comum é visitar primeiro os nós
> >> relativos às vias de maior classificação. Nesse caso, como a
> >> classificação não foi alterada, o nó seria visitado mesmo tendo uma
> >> velocidade mais baixa. Mas o Garmin pode usar alguma outra heurística
> >> que eu desconheço.
> >>
> >> Outro insight: explorar o gráfico requer somar esses tempos, trecho
> >> por trecho. São milhares de operação de soma. Se o programa não for
> >> bem construído, ele pode acumular erros numéricos ao somar milhares de
> >> números. O OSRM me parece particularmente sensível a esses erros. O
> >> Garmin geralmente opera num hardware limitado e talvez também seja
> >> sensível (tratar desses erros numéricos requer usar mais memória).
> >>
> >> Mais um insight: classificação interfere com esses algoritmos "mais
> >> simples" que usam "heurísticas". A classificação das vias não
> >> interfere em nada com o algoritmo A* (a-estrela) puro, nem com o
> >> algoritmo do OSRM. Por isso, classificações não devem ser alteradas
> >> com vistas ao roteamento. No entanto, um bom método de classificação
> >> serve bem a praticamente qualquer algoritmo de roteamento, não por ser
> >> o objetivo da classificação, mas por ser efeito colateral dela.
> >>
> >> Se, numa rota com vários quilômetros, a escolha de uma alternativa ou
> >> outra depender de um trecho tão curto quanto o mencionado, é bem
> >> provável que alguma dessas características esteja inteferindo no
> >> resultado. Mas os mapeadores do OSM não podem fazer nada, e talvez nem
> >> os desenvolvedores da aplicação sem ter que reescrevê-la por completo
> >> para resolver algum problema mais profundo.
> >>
> >> O que os roteadores prometem não é encontrar a melhor rota, mas uma
> >> rota sub-ótima. Quanto mais longa a distância, maior o efeito desses
> >> dois fatores (erro numérico e qualidade da heurística). Até mesmo o
> >> Waze às vezes faz bobagem na tentativa de encontrar a melhor rota.
> >>
> >> --
> >> 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
> >>
> >
>
> _______________________________________________
> 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/20150705/783636b8/attachment.html>