How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ? A lot of pathfinding algorithms have been developed in recent years which can calculate the best path in response to graph changes much faster than A* - what are they, and how do they differ?  Are they for different situations, or do some obsolete others?



These are the ones I've been able to find so far:


D* (1994)
Focused D* (1995)
DynamicSWSF-FP (1996)
LPA (1997)
LPA*/Incremental A* (2001)
D* Lite (2002)
SetA* (2002)
HPA* (2004)
Anytime D* (2005)
PRA* (2005)
Field D* (2007)
Theta* (2007)
HAA* (2008)
GAA* (2008)
LEARCH (2009)
BDDD* (2009 - I cannot access this paper :|)
Incremental Phi* (2009)
GFRA* (2010)
MTD*-Lite (2010)
Tree-AA* (2011)


I'm not sure which of these apply to my specific problem - I'll read them all if necessary, but it would save me a lot of time if someone could write up a summary.



My specific problem:  I have a grid with a start, a finish, and some walls.  I'm currently using A* to find the best path from the start to the finish.



The user will then move one wall, and I have to recalculate the entire path again.  The "move-wall/recalculate-path" step happens many times in a row, so I'm looking for an algorithm that will be able to quickly recalculate the best path without having to run a full iteration of A*.

Though, I am not necessarily looking for an alteration to A* - it could be a completely separate algorithm.
So, I skimmed through the papers, and this is what I gleamed.  If there is anyone more knowledgable in the subject-matter, please correct me if I'm wrong (or add your own answer, and I will accept it instead!).

Links to each paper can be found in the question-post, above.


Simple recalculations

D* (aka Dynamic A*) (1994):  On the initial run, D* runs very similarly to A*, finding the best path from start to finish very quickly.  However, as the unit moves from start to finish, if the graph changes, D* is able to very quickly recalculate the best path from that unit's position to the finish, much faster than simply running A* from that unit's position again.  D*, however, has a reputation for being extremely complex, and has been completely obsoleted by the much simpler D*-Lite.
Focused D* (1995):  An improvement to D* to make it faster/"more realtime."  I can't find any comparisons to D*-Lite, but given that this is older and D*-Lite is talked about a lot more, I assume that D*-Lite is somehow better.
DynamicSWSF-FP (1996): Stores the distance from every node to the finish-node.  Has a large initial setup to calculate all the distances.  After changes to the graph, it's able to update only the nodes whose distances have changed.  Unrelated to both A* and D*.  Useful when you want to find the distance from multiple nodes to the finish after each change; otherwise, LPA* or D*-Lite are typically more useful.
LPA*/Incremental A* (2001):  LPA* (Lifelong Planning A*), also known as Incremental A* (and sometimes, confusingly, as "LPA," though it has no relation to the other algorithm named LPA) is a combination of DynamicSWSF-FP and A*.  On the first run, it is exactly the same as A*.  After minor changes to the graph, however, subsequent searches from the same start/finish pair are able to use the information from previous runs to drastically reduce the number of nodes which need to be examined, compared to A*.  This is exactly my problem, so it sounds like LPA* will be my best fit.  LPA* differs from D* in that it always finds the best path from the same start to the same finish; it is not used when the start point is moving (such as units moving along the initial best path).  However...
D*-Lite (2002):  This algorithm uses LPA* to mimic D*; that is, it uses LPA* to find the new best path for a unit as it moves along the initial best path and the graph changes.  D*-Lite is considered much simpler than D*, and since it always runs at least as fast as D*, it has completely obsoleted D*.  Thus, there is never any reason to use D*; use D*-Lite instead.

Any-angle movement

Field D* (2007):  A variant of D*-Lite which does not constrain movement to a grid; that is, the best path can have the unit moving along any angle, not just 45- (or 90-)degrees between grid-points.  Was used by NASA to pathfind for the Mars rovers.
Theta* (2007): A variant of A* that gives better (shorter) paths than Field D*.  However, because it is based on A* rather than D*-Lite, it does not have the fast-replanning capabilities that Field D* does.  See also.
Incremental Phi* (2009): The best of both worlds.  A version of Theta* that is incremental (aka allows fast-replanning)

Moving Target Points

GAA* (2008): GAA* (Generalized Adaptive A*) is a variant of A* that handles moving target points.  It's a generalization of an even earlier algorithm called "Moving Target Adaptive A*"
GRFA* (2010): GFRA* (Generalized Fringe-Retrieving A*) appears (?) to be a generalization of GAA* to arbitrary graphs (ie. not restricted to 2D) using techniques from another algorithm called FRA*.
MTD*-Lite (2010): MTD*-Lite (Moving Target D*-Lite) is "an extension of D* Lite that uses the principle behind Generalized Fringe-Retrieving A*" to do fast-replanning moving-target searches.
Tree-AA* (2011): (???) Appears to be an algorithm for searching unknown terrain, but is based on Adaptive A*, like all other algorithms in this section, so I put it here.  Not sure how it compares to the others in this section.

Fast/Sub-optimal

Anytime D* (2005):  This is an "Anytime" variant of D*-Lite, done by combining D*-Lite with an algorithm called Anytime Repairing A*.  An "Anytime" algorithm is one which can run under any time constraints - it will find a very suboptimal path very quickly to begin with, then improve upon that path the more time it is given.
HPA* (2004): HPA* (Hierarchical Path-Finding A*) is for path-finding a large number of units on a large graph, such as in RTS (real-time strategy) video games.  They will all have different starting locations, and potentially different ending locations.  HPA* breaks the graph into a hierarchy in order to quickly find "near-optimal" paths for all these units much more quickly than running A* on each of them individually.  See also
PRA* (2005): From what I understand, PRA* (Partial Refinement A*) solves the same problem as HPA*, but in a different way.  They both have "similar performance characteristics."
HAA* (2008): HAA* (Hierarchical Annotated A*) is a generalization of HPA* that allows for restricted traversal of some units over some terrains (ex. a small pathway that some units can walk through but larger ones can't; or a hole that only flying units can cross; etc.)

Other/Unknown

LPA (1997): LPA (Loop-free path-finding algorithm) appears to be a routing-algorithm only marginally related to the problems the other algorithms here solve.  I only mention it because this paper is confusingly (and incorrectly) referenced on several places on the Internet as the paper introducing LPA*, which it is not.
LEARCH (2009):  LEARCH is a combination of machine-learning algorithms, used to teach robots how to find near-optimal paths on their own.  The authors suggest combining LEARCH with Field D* for better results.
BDDD* (2009): ??? I cannot access the paper.
SetA* (2002): ??? This is, apparently, a variant of A* that searches over the "binary decision diagram" (BDD) model of the graph?  They claim that it runs "several orders of magnitude faster than A*" in some cases.  However, if I'm understanding correctly, those cases are when each node on the graph has many edges?



Given all this, it appears that LPA* is the best fit for my problem.