I am currently working on an indoor routing project for a multilevel building.For this, I want to find a shortest path over multiple level (or 'floors'). I have read some papers on A* in such an environment and I think I understand why it is needed to first let the algorithm calculate the shortest path to the next structure to overcome the vertical movement. As an example, consider two level of which the source node is on the first floor and the destination on the second. First the algorithm should calculate the path to the closest elevator in the first floor. However, I only THINK that I have understood it, but I cannot find any proof of it if I'm really correct. Maybe one of you could have a short look at the following image. This image shows the case where I think A* would not find a path as the vertical movement structure (e.g. the elevator, which would be here the grey nodes) is not set as a destination. A* would 'heat in the wrong direction' and ignore the nodes which actually would lead to the destination. Here, in the image, it ignores the outgreyed nodes which are representing the elevator. Is this a correct example for the difficulty you face when applying A* on a multilevel network?

enter image description here

I understand, that the used heuristic (here Euclidean distance) would lead the algorithm to, roughly spoken, 'search in the wrong space' in which it cannot find the destination node. Further, the heuristic prevents to search in other locations, like a barrier.

  • Don't think about your network in 3D space, just mathematically as distances. The algorithm has no idea that the destination is above a node on the 1st floor. If your network is complete, A* will always find a path between destination and source. – RomaH May 17 '18 at 14:20
  • I don't think that the algorithm cares about if the destination is above the floor, this is just an example. The example I have given is a case special for 3D (or 2.5D), of which I cannot think an analogue example for in 2D. What I understand, is, that the heuristic does not enhance performance in comparison to Dijkstra in this case,as the heuristic here is 'misleading'. – i.i.k. May 18 '18 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.