# Implementing D* Lite for Path-Planning - How detect Edge Cost Change?

I currently try implementing the D* Lite Algorithm for path-planning (see also here) to get a grasp on it. I found two implementations on the web, both for C/C++, but somehow couldn't entirely follow the ideas since they seem to differ more than expected from the pseudo code in the whitepapers. I especially use the following two papers: Koening,S.;Likhachev,M. - D* Lite, 2002 Koenig & Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, June 2005

I tried implementing the optimized version of D* Lite from the first whitepaper (p.5,Fig.4) and for "debugging" I use the example as shown and explained in the second whitepaper (p.6,Fig.6 and Fig.7). All work is done in MatLab (easier for exchanging code with others).

So far I got the code running to find the initial shortest path by running computeShortestPath() once. But now I am stuck at lines {36''} and {37''} of the pseudo-code:

{36”} Scan graph for changed edge costs;
{37”} if any edge costs changed


How do I detect those changes? I somehow don't seem to have a grasp on how this is being detected? In my implementation so far, I mainly used 3 matrices. One matrix of same size as the grid map containing all rhs-values. One matrix of same size containing similarly all g-values. And one matrix with variable row count for the priority queue with the first two columns being the priority keys and the third and fourth row being the x- and y-coordinates.

Comparing my results, I get the same result for the first run of computeShortestPath() in Step5 as seen in the second whitepaper, p.6 Fig.6. Moving the robot one step also isn't that a problem. But I really have no clue how the next step of scanning for changed edge costs should be implemented.

Thanks for any hint, advice and/or help!!!

• While searching answers for the same question on 'Lifelong Planning A*' (LPA*) I found this Applet here: homepages.dcc.ufmg.br/~lhrios/applet_d_lite/index.html Playing around with it brought me to the idea: Does 'scanning for changed costs' mean just to locally compare the possible Successor Nodes with the ones in the known map (which can differ from the real map if we find a new, unknown obstacle)? – EliteTUM Sep 19 '12 at 11:34

One common way of implementing this is to have a OnGraphChanged callback in your Graph class, which can be setup to call the OnGraphChanged method in your PathFinder class. Then anywhere the graph changes in your Graph class, make sure the OnGraphChanged callback is called.
• Actually, I only scan the successor nodes of the current Node my robot moved to (this happens in scanChangedEdgeCost(...) ). AND ONLY if a difference between the so far known map and the true map within those successor nodes is detected, I replan. For now, I just want to implement the functionality. Later on I will try to move to an automated replaning - as you suggested - using callbacks. Actually, I've done quite a lot of unit testing allready. But looks like I'll have to re-read the papers on D*-Lite. – EliteTUM Sep 20 '12 at 11:50