6
$\begingroup$

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* over Dijkstra. To my understanding, Dijkstra gives a best path and D* works backwards from the end goal, but unlike A* it seems to do many calculations, so it doesn't seem as efficient.

$\endgroup$
  • $\begingroup$ Dijkstra is designed when the graph is known, from wikipedia, apparently D* is designed for unknown terrain? $\endgroup$ – Joe Mar 5 '14 at 7:25
  • 1
    $\begingroup$ i mean in order to calculate the path, you need to know something... so if its unknown terrain, you still need to scan it (i found out about D* in autonomous vehicle research), and then i imagine you get the nodes from the scan. either way if you dont know the terrain how do you start at the end $\endgroup$ – user-2147482637 Mar 5 '14 at 7:33
8
$\begingroup$

The main reason for choosing D* is that it is incremental. Basically, when your initial route gets blocked, an incremental search algorithm is able to take advantage of the previous calculations. Dijkstra doesn't do this; it needs to recompute everything from scratch. Such an incremental approach is often used in robotics, navigation, and planning.

This is the short answer. For much more, I think you would be interested in How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.