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][1]
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. [1]: https://i.sstatic.net/MhpV2.gif