2

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

Community
  • 1
  • 1
EliteTUM
  • 705
  • 2
  • 8
  • 21
  • While searching answers for the same question on 'Lifelong Planning A*' (LPA*) I found this Applet here: http://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:31
  • Please don't cross-post: http://cstheory.stackexchange.com/questions/12647/implementing-d-lite-for-path-planning-how-detect-edge-cost-change – BlueRaja - Danny Pflughoeft Sep 19 '12 at 17:34

1 Answers1

1

The following was pointed out to me by someone else:

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

I personally implemented it by using a "true map" and a "known map" and after every move letting the robot check/scan all next possible successors and comparing them on the true map and the known map.

EliteTUM
  • 705
  • 2
  • 8
  • 21