Where can I find information on the D* or D* Lite pathfinding algorithm?

Question

There are links to some papers on D* here, but they're a bit too mathematical for me. Is there any information on D*/D* Lite more geared towards beginners?

Answer 1

Wikipedia has an article on the topic: http://en.wikipedia.org/wiki/D*

Also a D* Lite implementation in C is available from Sven Koenig's page: http://idm-lab.org/code/dstarlite.tar However I find the impenetrable math much easier to read than the C source code ;-)

Another implementation of D* Lite (in C++) is available here: http://code.google.com/p/dstarlite/

Answer 2

Having said that, why not add a few more papers, yes they have math as well :-) but I'll try to get some more recent stuff. People usually get better at explaining their own work as the time goes by, so the focus is on Stentz, Likhachev and Koenig

• Stentz,2007 - Field D* - claims to be better than D* Lite :-)
• Stentz,2010 - Imitation Lerning- mostly talk about combining Field D* and LEARCH
• Ratliff,2009 - LEARCH - also talks about combining with Field D* - yes a cyclic ref :-)
• Likhachev,2005 - Anytime D* - with Stentz as well
• Yanyan,2009 - BDD-Based Dynamic A*
• Koenig,2008 - Comparing real-time and incremental heuristic search

Answer 3

Well if pseudo code is hard for you (you don't have to read theorems and proofs - pseudo code is pretty straight forward if you know standard algorhitms) and you complain against published C and C++ code then I guess you'll need to go doing something else :-)

Seriously, don't expect that someone can teach you a top grade algorithm in a few web paragraphs. Take a pen and paper and write, draw and follow on paper what's going on. You may have to read something twice and google one or two references to get to know a few concepts around it, and there's no need to dig in the theorems and proofs at all - unless you hope to prove the author wrong that is :-))

Can't go forward without some more math - c'est la vie. Imagine that you asked someone to teach you what on earth is matrix inversion but you don't know what are vectors. No one could help you till you learned enough of the math context first.

Answer 4

D* Lite Explanation for the Layperson

D* starts with a crow-flies, idealistic path between Start and Goal; it handles obstacles only as and when it comes across them (usually by moving into an adjacent node). That is - D* Lite has no knowledge of any obstacles until it begins moving along that ideal path.

The holy grail with any pathfinding implementation is to make it quick while getting the shortest path, or at least a decent path (as well as handling [all your various special conditions here - for D* Lite this is dealing with an unknown map as a Mars Rover might do]).

So one of D* Lite's big challenges is adapting to obstacles cheaply as they are reached. Finding them is easy - you just check the node status of neighbours as you move. But how do we adapt the existing map's cost estimates without running through every node... which could be very costly?

LPA* uses a clever trick to adapt costs, a trick D* Lite has put to good use. The current node asks its neighbours: You know me best, do you think I'm being realistic about myself? Specifically, it asks this about its g value, which is the known cost of getting from the initial node to itself i.e. the current node. Neighbours look at their own g, look at where the current node is in relation to them, and then offer an estimate of what they think its cost should be. The minimum of these offers is set as the current node's rhs value which is then used to update its g value; when estimating, neighbours take into account the newly discovered obstacle(s) (or free spaces), such that when current updates g using rhs, it does so with the new obstacles (or free spaces) accounted for.

And once we have realistic g values across the board, of course, a new shortest path appears.

Answer 5

D* vs D* Lite: First of all, D*-Lite is considered much simpler than D*, and since it always runs at least as fast as D*, it has completely obsoleted D*. Thus, there is never any reason to use D*; use D*-Lite instead.

D* Lite vs A*: The D* Lite algorithm works by basically running A* search in reverse starting from the goal and attempting to work back to the start. The solver then gives out the current solution and waits for some kind of change in the weights or obstacles that it is presented with. As opposed to repeated A* search, the D* Lite algorithm avoids replanning from scratch and incrementally repair path keeping its modifications local around robot pose.

if you would like to really understand the algorithm. I suggest you start by reading through the pseudo code for A* and implement it. Try first to get the grip of how you put pick from and insert into the heap queue, and how the algorithm uses another heuristic as opposed to just regular Dijkstra algorithm, and why that allows the algorithm to explore less vertices as opposed to Dijkstra.

Once you feel you have a grip of how A* works (you should implement it as well), then I would suggest you take a look at Koenig, 2002 again. I suggest you start looking at the regular D*-Lite pseudo code first. Make sure you understand what every line of code.

concept of priority queue

• 'U' is your priority queue where you want to stack unexplored vertices.
• 'U' is has elements of (key, value) where key is you vertex and value is the result of the value = [k1, k2] = calculateKey saying what the priority of the key (meaning vertex) should be. Now your priority queue uses a.
• 'U.Top()' returns a vertex with the smallest priority of all vertices in priority queue U.
• 'U.TopKey()' returns the smallest priority of all vertices in prior.
• 'U.Pop' deletes the vertex with the smallest priority in priority queue U and returns the vertex.
• 'U.Insert()' inserts vertex into priority queue U with priority.
• 'U.Update()' changes the priority of vertex in priority queue U to.

Implementation

I have already implemented the Optimized D*-Lite algorithm once python (take a look at this thread here). I suggest you put the code and pseudo code side by side and read through. There is also instructions there to test the simulation if you would like that.

Answer 6

I came up with this
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf and this
http://www.cs.cmu.edu/~maxim/files/dlitemap_iros02.pdf http://www.cs.cmu.edu/~maxim/files/dlite_icra02.pdf - has 2 versions of D*

http://www.cs.cmu.edu/~maxim/files/dlite_tro05.pdf - polished up version of icra02

https://www.cs.cmu.edu/~maxim/files/rstar_aaai08.pdf - R* - randomization to reduce computation cost

http://www.cs.cmu.edu/~maxim/files/rstar_proofs34.pdf - modified R* http://www.cs.unh.edu/~ruml/papers/f-biased-socs-12.pdf - real time R* + PLRTA*

I hope those link will help you :)
Edit: After posting I noticed that the links I gave you were in the link you pointed out as well. Nevertheless I found those directly on Google. Anyway I've looked them up a bit and they don't seem to be that complicated. If you know A* well you should manage to understand D* as well.
From experience I can tell you that A* can be used for what you want as well.

Answer 7

Maxim Likhachev's CMU class notes are very informative. It contains an example of how to propagate the dynamics changes occurred on your graph. Also explains the idea of under-consistent which is very important to understand the algorithms. http://www.cs.cmu.edu/~maxim/classes/robotplanning_grad/lectures/execanytimeincsearch_16782_fall18.pdf