title: Implementing D* Lite for Path-Planning - How detect Edge Cost Change?
body: <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>