On Path Finding: A detailed description for the layman of the D * algorithm

Question

A large network (such as a small world) that I want to deal with is dynamic, new nodes are added and subtracted often. Presumably using D * over A * would be the best way to detect paths in this dynamic environment?

How hard is D *? Does he have any real world experience? as a cryptographic algorithm, - D * hardens with many expert reviews and tests? Would you use D * for this problem?

Answer 1

As I understand it, the first time D * starts, it finds the same path as A *, with almost the same runtime. However, when a node changes its edge value or nodes are added, A * will recompose the ALL path, and D * will simply reconfigure the inconsistent nodes a second time, not the whole thing.

The Anthony Stentz D * algorithm (source document here ) is pretty much out of date with derivatives of its work. D * Lite and LPA * are the most common and much easier to code / implement.

Regarding real-world experience, Joseph Carsten and Art Rankin of the NASA Jet Propulsion Laboratory installed the Field D * version using the D * Lite elements on the Spirit and Opportunity rovers (slide show of rovers using D * here ). In February 2007, it was used for autonomous navigation of the rover.

alt text http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg

Apparently, D * is really useful in the field of robotics, because the built-in robot sensors constantly overestimate the values ​​of the boundaries. That would make it a “battle tested” in my opinion.

Similarly, I found another technical paper that mentions the use of the D * Lite algorithm in Mobile Gaming.

I will end this answer by stating that I have never implemented D * before, only A *. Due to the significant increase in complexity, I would say that D * (or D * Lite) should be used only when significant and frequent changes occur on the chart. You described your position as similar to this, so I would say, of course, for D * Lite. If NASA uses it, you can safely bet that it has been thoroughly investigated.

Answer 2

I implemented the D * and A * algorithms. So, I advise you that if your card does not have dynamic obstacles, you should implement A *. Else, implement D *. Main reason: During the first search, D * calculates all nodes on the map, and then shows the shortest path, and A * calculates only a limited area around the targets and starting points on the map. Thus, it is much faster than D *. In a dynamic environment, D * is faster and more efficient than A *. Since the robot goes in the way if it detects a new obstacle, it updates only a few nodes around the unexpected obstacle. For now, A * will calculate everything again.