<sub>**Disclaimer**: Esta não é uma resposta per ser, 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.</sub>

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