<p>In real-world code, you almost never have to "scan the graph for changes."  Your graph only changes when you change it in the code, so you already know exactly when and where it can change!</p>

<p>One common way of implementing this is to have a <code>OnGraphChanged</code> <a href="https://stackoverflow.com/questions/2298242/callback-functions-in-c">callback</a> in your <code>Graph</code> class, which can be setup to call the <code>OnGraphChanged</code> method in your <code>PathFinder</code> class.  Then anywhere the graph changes in your <code>Graph</code> class, make sure the <code>OnGraphChanged</code> callback is called.</p>

CC BY-SA 3.0
2012-09-19T16:35:43.327Z
Thanks for the hint, that's what I thought after "playing around" with the Applet I gave the link to above. Using MatLab in my current implementation, callbacks aren't any option. I implemented it now by having a "true map" and a "known map" and letting the robot scan it's environment after every move. For now I just let it "scan" by checking all possible successors and comparing the true successor with the one in the known map and change the known map if needed.
EliteTUM
CC BY-SA 3.0
2012-09-19T17:33:24.687Z
@EliteTUM: Matlab supports callbacks.  See http://www.mathworks.com/help/matlab/ref/functions.html
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2012-09-19T20:37:24.210Z
Oh ok, didn't know about that. For now I tried implementing it manually without callback. Unfortunately, I somehow get wrong results not knowing why. Maybe someone might care looking over my code?

The errors must be somewhere in the functions  scanChangedEdgeCost() und myDStarSearch() (Lines 131-163), but not sure what I am calculating wrong or better to say how to calculate the updated matrices correctly.

See and Download Code at: http://snipt.org/vLgi8
EliteTUM
CC BY-SA 3.0
2012-09-19T23:00:16.643Z
@EliteTUM: This is exactly the case that unit-tests excel at :) Try writing some simple automated tests, and make sure the pathfinder returns the correct result in those cases.  I'd like to point out, however, since you're scanning the entire graph anyways at each step, you are completely negating the speed advantages D*Lite gives you - you might as well just do a brute-force *(breadth-first search/djikstra's)*, and it would probably be faster!
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2012-09-20T11:50:37.060Z
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
CC BY-SA 3.0
2012-09-20T23:52:32.183Z
Ok, so after some additional work and luckily finding another paper on D\* Lite (Title: Improved Fast Replanning
for Robot Navigation in Unknown Terrain) I got it all running as expected. In the previously mentioned papers one can find the Algorithm for "D\* Lite" and "D\* Lite (optimized version)". Until now I couldn't get the optimized version running (somehow the robot get's stuck because of wrong rhs-/g-values). In the new paper mentioned above, there is a so called Algorithm "D\* Lite Final Version". Its simplified and works like a charm for me! THX for the hints @ BlueRaja
EliteTUM
CC BY-SA 3.0
2012-09-19T14:48:40.453Z
2012-09-19T14:48:40.453Z
2017-05-23T12:40:09.333Z
BlueRaja - Danny Pflughoeft
<p>I currently try implementing the D* Lite Algorithm for path-planning (see also <a href="https://cstheory.stackexchange.com/questions/11855/how-do-the-state-of-the-art-pathfinding-algorithms-for-changing-graphs-d-d-l">here</a>) 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:
<a href="http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf" rel="nofollow noreferrer">Koening,S.;Likhachev,M. - D* Lite, 2002</a>
<a href="http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdf" rel="nofollow noreferrer">Koenig &amp; Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, June 2005</a></p>

<p>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).</p>

<p>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: </p>

<pre><code>{36”} Scan graph for changed edge costs;
{37”} if any edge costs changed
</code></pre>

<p>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.</p>

<p>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. </p>

<p>Thanks for any hint, advice and/or help!!!</p>

CC BY-SA 3.0
2012-09-19T11:34:24.347Z
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
<ds.algorithms><shortest-path>
Implementing D* Lite for Path-Planning - How detect Edge Cost Change?
EliteTUM
# Implementing D* Lite for Path-Planning - How detect Edge Cost Change?

(Asked by: username_0 on 2012-09-18)

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!!!

**Tags:** ds.algorithms, shortest-path
> **Comments:**
> **username_0**: 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)?  

---

## 1 answers

### Answer by username_1 on 2012-09-19. Score: 1 | Accepted answer

In real-world code, you almost never have to "scan the graph for changes." Your graph only changes when you change it in the code, so you already know exactly when and where it can change!

One common way of implementing this is to have a `OnGraphChanged` [callback](https://stackoverflow.com/questions/2298242/callback-functions-in-c) 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.

> **Comments:**
> **username_0**: Thanks for the hint, that's what I thought after "playing around" with the Applet I gave the link to above. Using MatLab in my current implementation, callbacks aren't any option. I implemented it now by having a "true map" and a "known map" and letting the robot scan it's environment after every move. For now I just let it "scan" by checking all possible successors and comparing the true successor with the one in the known map and change the known map if needed.  
> **username_1**: @EliteTUM: Matlab supports callbacks.  See http://www.mathworks.com/help/matlab/ref/functions.html  
> **username_0**: Oh ok, didn't know about that. For now I tried implementing it manually without callback. Unfortunately, I somehow get wrong results not knowing why. Maybe someone might care looking over my code?  The errors must be somewhere in the functions  scanChangedEdgeCost() und myDStarSearch() (Lines 131-163), but not sure what I am calculating wrong or better to say how to calculate the updated matrices correctly.  See and Download Code at: http://snipt.org/vLgi8  
> **username_1**: @EliteTUM: This is exactly the case that unit-tests excel at :) Try writing some simple automated tests, and make sure the pathfinder returns the correct result in those cases.  I'd like to point out, however, since you're scanning the entire graph anyways at each step, you are completely negating the speed advantages D*Lite gives you - you might as well just do a brute-force *(breadth-first search/djikstra's)*, and it would probably be faster!  
> **username_0**: 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.  
> **username_0**: Ok, so after some additional work and luckily finding another paper on D\* Lite (Title: Improved Fast Replanning for Robot Navigation in Unknown Terrain) I got it all running as expected. In the previously mentioned papers one can find the Algorithm for "D\* Lite" and "D\* Lite (optimized version)". Until now I couldn't get the optimized version running (somehow the robot get's stuck because of wrong rhs-/g-values). In the new paper mentioned above, there is a so called Algorithm "D\* Lite Final Version". Its simplified and works like a charm for me! THX for the hints @ BlueRaja  

---

