30

Eu estou trabalhando em uma solução que envolve determinar a rota de menor esforço entre dois pontos de um prédio. (Imagine estudantes em seu primeiro dia de universidade, e que precisam saber onde fica e como chegar a uma dada sala de aula em um prédio, ou como ir da sala atual para a próxima aula.)

Basicamente eu tenho uma estrutura cartesiana onde cada andar está mapeado. Eu também tenho indicadores de pontos de acesso (portas, rampas para deficientes, escadarias) e os pontos onde estes pontos se conectam (Escadaria do Térreo se conecta com escadaria do 2º andar em X48 Y4, por exemplo), mais ou menos como a imagem abaixo:

inserir a descrição da imagem aqui

Onde ciano indica uma escadaria, e azul-estranho elevadores, entre outros marcadores não exibidos.

(Para os daltônicos, minhas sinceras desculpas e algumas informações adicionais: as escadarias estão localizadas na parte superior direita dos mapas; os elevadores, próximos ao centro.)

Eu comecei meu código baseado em uma variante do algoritmo de Dijkstra chamado A-Estrela (A*), que é basicamente o problema do caminho mais curto com algumas otimizações. (Curiosidade: Vários jogos implementam variantes do A* para determinar a rota de personagens em um mapa.)

inserir a descrição da imagem aqui

A* é perfeito para determinar rotas em um mesmo andar, porém eu tenho que levar em consideração os vários andares, cada um com um layout diferente.

Pergunta

Existe alguma maneira mais apropriada para solucionar este problema?

Ou, de forma mais clara (obrigado bfavaretto),

Dado o fator adicional de N andares, existe algum algoritmo que seja mais indicado do que o A*?

Disclaimer:
Imagem isométrica original de DougIllustrations.com.

10
  • 3
    até tentaria te ajudar ... mas para um daltônico esse esquema de cores não esta ajudando
    – Otto
    Commented 12/09/2014 às 20:43
  • 1
    Eu colocaria +2 nessa questão se pudesse. Commented 12/09/2014 às 20:58
  • 1
    @Otto desculpe! Adicionei um parágrafo especialmente pra você. =)
    – OnoSendai
    Commented 12/09/2014 às 21:03
  • 1
    @bfavaretto Eu acho que um formato mais claro da pergunta seria "Dado o fator adicional de N andares, existe algum algoritmo que seja mais indicado do que o A*?" Um outro ponto é performance (N usuários calculando suas rotas ao mesmo tempo), mas eu não quero saturar a pergunta com outras 3984 associadas...
    – OnoSendai
    Commented 12/09/2014 às 21:06
  • 2
    Ok, agora entendi. Me parece que você precisa de algo como um A*, só que em 3D. Como não é minha especialidade, deixo apenas um link que achei agora no Google: roy-t.nl/index.php/2011/09/24/…
    – bfavaretto
    Commented 12/09/2014 às 21:12

3 Respostas 3

11

De uma forma bem simples, conectar os andares por uma aresta, criando uma espécie de grafo tridimensional me parece a solução mais adequada.

O algoritmo, no entanto, deve ser customizado conforme certas condições. Por exemplo, a configuração para deficientes iria colocar um custo infinito nas escadas e demais vias sem acessibilidade para que estas nunca fossem selecionadas.

A questão de evitar elevadores em horários de picos poderia ser outra configuração a cargo do usuário. Já uma opção de "andar no máximo X andares" seria um pouco mais trabalhosa, exigindo armazenar um estado adicional para cada rota.

E para a coisa funcionar bem na prática, seria ideal ter métricas de tempo média de espera dos elevadores em cada horário.

A ideia geral é que os pesos de cada aresta, isto é, de andar cada trecho, teria que baseado numa função dinâmica que considerasse as configurações do usuário e também informações de tráfego daquele trecho.

Porém, dependendo da quantidade de nós e da carga de uso do sistema, isto pode ser pouco eficiente. Neste caso, seria possível definir rotas subótimas, por exemplo, pré-calculando para cada andar a menor distância entre um determinado ponto e a escada ou elevador mais próximo, juntando então essa informação para selecionar uma global.

Enfim, essas são algumas ideias. Elas não respondem de forma conclusiva ou matemática a questão (e são grandes demais para comentários), mas espero que possam gerar novas ideias que incrementem sua solução atual.

1
  • 1
    Excelentes pontos, eu já incorporei alguns à lista de 'coisas que DEFINITIVAMENTE precisamos ter'. =)
    – OnoSendai
    Commented 13/09/2014 às 21:31
9

Disclaimer: Esta não é uma resposta per se, apenas uma compilação das respostas/possibilidades até o momento. Imagino que o resultado final venha a ser uma combinação das sugestões apresentadas.

A* 3D (@bfavaretto)

Uma implementação possível deste algoritmo mapearia os pontos de contato entre os andares, implementado as 'lajes' como descrito por @bacco. A altura de cada camada pode ser definida como 1, já que não usaremos jetpacks, evitando assim o cálculo de custo horizontal.

inserir a descrição da imagem aqui

Na imagem, vermelho indicaria elevadores e azul, escadarias; verde, as paredes (objetos intransponíveis) e branco o espaço navegacional. (Espero que esta combinação de cores seja válida para daltônicos!)

D* / D* Lite (@Cigano)

Esta é bem interessante por permitir cálculos de custo composto de tempo. Algumas situações possíveis:

  • O ponto a ser alcançado é em um andar superior. O custo inicial de elevador é 10, +2 por andar. O custo de escadarias é 5 inicialmente, mas é adicionado 10 a cada andar a ser percorrido (+15, +25, etc.) Subir 1 andar pelas escadas pode ser melhor do que esperar pelo elevador, mas não é o caso se você precisar subir 10.
  • O ponto a ser alcançado é em um andar inferior. Custo de elevador: 10 +2 por andar. Custo de escadarias: 5 +3 por andar (Não é tão cansativo descer uma escada, mas toma tempo.)

Otimizações (@utluiz)

Várias sugestões boas aqui, algumas não relacionadas diretamente à pergunta porém podem ajudar a criar uma solução bem melhor.

  • A informação sobre a presença de alguma deficiência física nos usuários cadastrados está presente, e a otimização de rota eliminando escadarias é possível. Uma configuração similar pode ser oferecida a usuários públicos via seleção na interface.

  • É possível utilizar OpenCV para analizar ruído em imagens das câmeras que observam os elevadores, entradas e escadarias e traçar um histograma por horário. O resultado poderia ser um multiplicador de custo.

  • Uma possibilidade de otimização deste algoritmo é definir zonas dentro de cada andar que possuem apenas uma possibilidade de rota de saída, e manter um cache com custos para pontos pré-determinados comuns (pontos de acesso, etc.) Isso pouparia um pouco do workload.

2
  • 1
    Acho que isso ficaria melhor na sua própria pergunta, pois se surgirem mais respostas, essa aqui via ficar perdida.
    – ptkato
    Commented 13/09/2014 às 21:49
  • @Patrick Isso não iria contra a prerrogativa de 'não responder no corpo da pergunta'? Afinal, se não houver uma 'resposta definitiva', eu marcarei esta como resultado final - uma compilação de todos os pontos válidos mencionados pelos participantes.
    – OnoSendai
    Commented 13/09/2014 às 22:17
8

A* é o que é normalmente usado, mas existe uma família de algoritmos chamada D* que considera que o cálculo pode variar de etapa pra etapa, mas esse seria interessante se o caminho não fosse constante, como acredito que é o caso da sua realidade.

Há ainda uma versão mais simples de ser implementada chamada D* Lite, que é bem diferente do D* original.

4
  • Na verdade D* pode ser uma boa opção se eu considerar que elevadores têm um 'custo' padrão menor do que escadas, mas que pode variar dependendo do horário - 'Vale a pena esperar pelo elevador na hora do almoço, ou é melhor descer dois lances de escadaria?' Mas esta é uma questão posterior.
    – OnoSendai
    Commented 12/09/2014 às 21:10
  • 1
    Também. Na verdade você me fez desenterrar algum conhecimento das aulas de Teoria dos Grafos que tive há uns 8 anos atrás. Commented 12/09/2014 às 21:11
  • 1
    Eu encontrei uma implementação D*, vou dar uma olhada e ver como posso aplicar. Link - idm-lab.org/project-a.html
    – OnoSendai
    Commented 12/09/2014 às 21:20
  • 1
    Update: Até o presente me parece que o D* Lite possui um custo melhor, já que não há a necessidade de recalcular o custo do caminho até alcançarmos um dos pontos de acesso.
    – OnoSendai
    Commented 13/09/2014 às 21:30

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .