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

Question

The large network (of small world graph type) I wish to deal with is dynamic in nature, new nodes are added and subtracted frequently. Presumably using D* over A* would be a better way to detect paths in this dynamic environment?

How solid is D*? has it had any real world experience? like a cryptographic algorithm - is D* hardened by lots of peer review and testing? Would you use D* for this problem?

Answer 1

As I understand, the first time you run D* it finds the same path as A* with nearly the same runtime. However, when a node changes it's edge value or nodes are added A* recomputes ALL of the path while D* simply recomputes the inconsistent nodes the second time around rather than the whole thing.

Anthony Stentz's D* algorithm (original whitepaper here) has largely been deprecated by derivatives of his work. D* Lite and LPA* are the most commonly found and are much easier to code/implement.

As far as real world experience, Joseph Carsten and Art Rankin from NASA's Jet Propulsion Laboratory installed a version of Field D* using elements of D* Lite on the mars rovers "Spirit" and "Opportunity" (slideshow of rovers using D* here). In Feburary 2007 it was used to fully navigate the mars rover autonomously.

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

Apparently D* is really useful in the robotics domain because the robots on-board sensors are constantly re-evaluating edge values. That would make it pretty "battle tested" in my own opinion.

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

I'll end this answer by stating that I've never implemented D* before, only A*. Because of the significant increase in complexity I would say that D* (or D* Lite) should only be used in cases where there is a significant and frequent changes in the graph. You described your situation as being similar to that so I would say definately go for D* Lite. If NASA uses it you could safely bet it has been thoroughly investigated.