<p>There's a big caveat when using D*, D*-Lite, or any of the incremental algorithms in this category (and it's worth noting that this caveat is seldom mentioned in the literature). These types of algorithms use a reversed search. That is, they compute costs outwards from the goal node, like a ripple spreading outwards. When the costs of edges change (e.g. you add or remove a wall in your example) they all have various efficient strategies for only updating the subset of the explored (a.k.a. 'visited') nodes that is affected by the changes.</p>

<p>The big caveat is that the location of these changes with respect to the goal location makes an enormous difference to the efficiency of the algorithms. I showed in various papers and my thesis that it's entirely possible for the worst case performance of any of these incremental algorithms to be <em>worse</em> than throwing away all the information and starting afresh with something non-incremental like plain old A*.</p>

<p>When the changed cost information is close to the perimeter of the expanding search front (the 'visited' region), few paths have to change, and the incremental updates are fast. A pertinent example is a mobile robot with sensors attached to its body. The sensors only see the world near the robot, and hence the changes are in this region. This region is the starting point of the search, not the goal, and so everything works out well and the algorithms are very efficient at updating the optimum path to correct for the changes.</p>

<p>When the changed cost information is close to the goal of the search (or your scenario sees the goal change locations, not just the start), these algorithms suffer catastrophic slowdown. In this scenario, almost all the saved information needs to be updated, because the changed region is so close to the goal that almost all pre-calculated paths pass through the changes and must be re-evaluated. Due to the overhead of storing extra information and calculations to do incremental updates, a re-evaluation on this scale is slower than a fresh start.</p>

<p>Since your example scenario appears to let the user move any wall they desire, you will suffer this problem if you use D*, D*-Lite, LPA*, etc. The time-performance of your algorithm will be variable, dependent upon user input. In general, "this is a bad thing"... </p>

<p>As an example, Alonzo Kelly's group at CMU had a fantastic program called PerceptOR which tried to combine ground robots with aerial robots, all sharing perception information in real-time. When they tried to use a helicopter to provide real-time cost updates to the planning system of a ground vehicle, they hit upon this problem because the helicopter could fly ahead of the ground vehicle, seeing cost changes closer to the goal, and thus slowing down their algorithms. Did they discuss this interesting observation? No. In the end, the best they managed was to have the helicopter fly directly overhead of the ground vehicle - making it the world's most expensive sensor mast. Sure, I'm being petty. But it's a big problem that no one wants to talk about - and they should, because it can totally ruin your ability to use these algorithms if your scenario has these properties.</p>

<p>There are only a handful of papers that discuss this, mostly by me. Of papers written by the authors or students of the authors of the original papers listed in this question, I can think of only one that actually mentions this problem. Likhachev and Ferguson suggest trying to estimate the scale of updates required, and flushing the stored information if the incremental update is estimated to take longer than a fresh start. This is a pretty sensible workaround, but there are others too. My PhD generalizes a similar approach across a broad range of computational problems and is getting beyond the scope of this question, however you may find the references useful since it has a thorough overview of most of these algorithms and more. See <a href="http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364">http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364</a> for details.</p>

CC BY-SA 3.0
2013-02-24T01:44:36.550Z
Thank you for adding these details :) In my application, the wall gets moved towards the beginning just as often as towards the end.  I implemented BFS, A\*, and LPA\*; A\* was actually slightly slower than BFS *(my spaces tend to be confined, so A\* only searches slightly fewer nodes than BFS; meanwhile BFS only needs a queue, which can be implemented to be faster than a priority-queue can)*, but using LPA\* averaged to be over twice as fast.
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2013-02-23T23:11:05.363Z
2013-02-23T23:11:05.363Z
Schwolop
<p>The main idea is to use an incremental algorithm, that is able to take advantage of the previous calculations when the initial calculated route gets blocked. This is often investigated in the context of robots, navigation and planning.</p>

<p><a href="http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdf">Koenig &amp; Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, June 2005</a> introduces D* Lite. It seems safe to say that D* is outdated in a sense that D* Lite is always as fast as D*. In addition, D* is complex, hard to understand, analyze and extend. Figure 9 gives the pseudocode for D* Lite, and Table 1 shows experimental results with D* Lite compared to BFS, Backward A*, Forward A*, DynamicSWSF-P and D*.</p>

<p>I do not know the newer algorithms you list (Anytime D*, Field D*, LEARCH). Very recently I saw a robot that used D* Lite for planning in an environment with random walkers in it. In this sense, I don't think D* Lite is outdated by no means. For your practical problem, I guess there's no harm in trying the usual engineering way: take some approach, and if it doesn't fit your needs, try something else (more complex). </p>

CC BY-SA 3.0
2012-06-28T08:14:35.620Z
2012-06-28T08:14:35.620Z
Juho
<p>I'd like add something about rapidly-exploring randomized trees, or RRTs. The basic idea has good discussion all over the internet, but it's probably safe to start with the links off the Wikipedia page and with Kuffner and LaValle's original papers on the topic.</p>

<p>The most important feature of RRTs is that they can deal with real-valued spaces of <em>extremely</em> high dimension without choking. They can handle dynamics, are not optimal but are probabilistically complete (guaranteed to succeed if possible as computation time goes to infinity), and are capable of handling moving targets. There are some extensions that let them work in non-static spaces, the best of which looks to be the Multipartite RRT work that I've linked below.</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree" rel="nofollow">http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree</a></li>
<li><a href="http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf" rel="nofollow">http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf</a></li>
</ul>

CC BY-SA 3.0
2013-02-24T05:27:58.997Z
2013-02-24T05:27:58.997Z
Saul Reynolds-Haertle
<p>Data structures called <strong><em>distance oracles</em></strong> handle such problems. However, most research results are for <em>static</em> graphs only.</p>

<p>If the graphs are grids (and thus planar), some <em>dynamic</em> data structures exist (unclear whether the constants are small enough for the application in question):</p>

<p><strong>Exact shortest paths:</strong></p>

<p>Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)</p>

<p><strong>Approximate shortest paths:</strong></p>

<p>Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)</p>

<p>Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218</p>

CC BY-SA 3.0
2013-02-24T01:47:30.423Z
Sorry, but if they only work on static graphs, then what do you mean by "they handle such problems?"  The problem asked is *specifically* about non-static graphs.
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2013-03-18T04:30:49.957Z
let me change the emphasis: 
*most* results are for static graphs only. *some* dynamic data structures exist. followed by a list of those dynamic data structures.
Christian Sommer
CC BY-SA 3.0
2013-02-24T01:45:36.567Z
2013-02-24T01:45:36.567Z
Christian Sommer
<p>In school I dabbled with <a href="https://en.wikipedia.org/wiki/Ant_colony_optimization" rel="nofollow">ant colony optimization</a>. In some texts it was touted as a solution for continuously changing graphs, routing networks, etc. It's not an engineered solution, but an adaptation from how ants navigate around obstacles by spreading pheromones to mark good and bad paths. I have no idea if it works for your problem, but i think it's an interesting point of view.</p>

CC BY-SA 3.0
2013-02-24T09:06:10.147Z
2013-02-25T18:29:49.167Z
2013-02-25T18:29:49.167Z
silversplinter
<p>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 <em>(or add your own answer, and I will accept it instead!)</em>.</p>

<p>Links to each paper can be found in the question-post, above.</p>

<ul>
<li><strong>Simple recalculations</strong>
<ul>
<li><strong>D*</strong> <em>(aka <strong>Dynamic A*</strong>)</em> (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.</li>
<li><strong>Focused D*</strong> (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.</li>
<li><strong>DynamicSWSF-FP</strong> (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.</li>
<li><strong>LPA*/Incremental A*</strong> (2001):  LPA* <em>(Lifelong Planning A*)</em>, also known as Incremental A* <em>(and sometimes, confusingly, as "LPA," though it has no relation to the other algorithm named LPA)</em> 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 <em>(such as units moving along the initial best path)</em>.  However...</li>
<li><strong>D*-Lite</strong> (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 <em>at least</em> as fast as D*, it has completely obsoleted D*.  Thus, there is never any reason to use D*; use D*-Lite instead.</li>
</ul></li>
<li><strong>Any-angle movement</strong>
<ul>
<li><strong>Field D*</strong> (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.</li>
<li><strong>Theta*</strong> (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.  <a href="http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/">See also</a>.</li>
<li><strong>Incremental Phi*</strong> (2009): The best of both worlds.  A version of Theta* that is incremental <em>(aka allows fast-replanning)</em></li>
</ul></li>
<li><strong>Moving Target Points</strong>
<ul>
<li><strong>GAA*</strong> (2008): GAA* <em>(Generalized Adaptive A*)</em> is a variant of A* that handles moving target points.  It's a generalization of an even earlier algorithm called "Moving Target Adaptive A*"</li>
<li><strong>GRFA*</strong> (2010): GFRA* <em>(Generalized Fringe-Retrieving A*)</em> appears (?) to be a generalization of GAA* to arbitrary graphs <em>(ie. not restricted to 2D)</em> using techniques from another algorithm called FRA*.</li>
<li><strong>MTD*-Lite</strong> (2010): MTD*-Lite <em>(Moving Target D*-Lite)</em> is "an extension of D* Lite that uses the principle behind Generalized Fringe-Retrieving A*" to do fast-replanning moving-target searches.</li>
<li><strong>Tree-AA*</strong> (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.</li>
</ul></li>
<li><strong>Fast/Sub-optimal</strong>
<ul>
<li><strong>Anytime D*</strong> (2005):  This is an <em>"Anytime"</em> variant of D*-Lite, done by combining D*-Lite with an algorithm called <em>Anytime Repairing A*</em>.  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.</li>
<li><strong>HPA*</strong> (2004): HPA* <em>(Hierarchical Path-Finding A*)</em> is for path-finding a large number of units on a large graph, such as in RTS <em>(real-time strategy)</em> 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 <em>"near-optimal"</em> paths for all these units much more quickly than running A* on each of them individually.  <a href="http://aigamedev.com/open/article/clearance-based-pathfinding/">See also</a></li>
<li><strong>PRA*</strong> (2005): From what I understand, PRA* <em>(Partial Refinement A*)</em> solves the same problem as HPA*, but in a different way.  They both have <em>"similar performance characteristics."</em></li>
<li><strong>HAA*</strong> (2008): HAA* <em>(Hierarchical Annotated A*)</em> 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.)</li>
</ul></li>
<li><strong>Other/Unknown</strong>
<ul>
<li><strong>LPA</strong> (1997): LPA <em>(Loop-free path-finding algorithm)</em> appears to be a <a href="http://en.wikipedia.org/wiki/Routing_algorithm">routing-algorithm</a> 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.</li>
<li><strong>LEARCH</strong> (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.</li>
<li><strong>BDDD*</strong> (2009): ??? I cannot access the paper.</li>
<li><strong>SetA*</strong> (2002): ??? This is, apparently, a variant of A* that searches over the <em>"binary decision diagram"</em> (BDD) model of the graph?  They claim that it runs <em>"several orders of magnitude faster than A*"</em> in some cases.  However, if I'm understanding correctly, those cases are when each node on the graph has many edges?</li>
</ul></li>
</ul>

<p>Given all this, it appears that <strong>LPA*</strong> is the best fit for my problem.</p>

CC BY-SA 3.0
2013-12-08T08:36:14.570Z
I know this is old, but I think it's worth noting a small flaw in your description of Field D*. Regular D* isn't constrained to "a grid", it's constrained to a discrete graph. The point the paper makes is that in order to make A*, D* etc work you have to discretize a continuous space into chunks, which limits the angles you can move at. Field D* eliminates that constraint and allows you treat successor states in a continuous, rather than discrete manner (more or less, trickery is involved). It simply uses a 2D grid as an example, D*/A* etc are by no means constrained to a grid.
Linear
CC BY-SA 3.0
2013-12-08T08:47:42.237Z
I should mention that Field D* is limited to a grid, though the paper mentions that they did work on a 3D version. This is due to the interpolation it uses. It still stands that A* and D* work on graphs with arbitrary numbers of successor states, Field D* is just an improvement for scenarios where D* uses grid-based planning.
Linear
CC BY-SA 3.0
2013-06-08T17:57:15.500Z
Well.. I also found [this paper by @lhrios](http://homepages.dcc.ufmg.br/~lhrios/publications/classes.pdf) which compares some of the algorithms.
mg007
CC BY-SA 3.0
2015-05-07T12:33:26.043Z
An important difference between Field D* and Theta*/Incremental Phi*, is that Field D* can have unique weights for each square, whereas Theta* and Incremental Phi* are limited to having the same weight for all squares that can be visited. Hence, Incremental Phi* is not superior to Field D*.
HelloGoodbye
CC BY-SA 3.0
2015-05-07T12:49:18.463Z
@Jsor: Here is a 3D version of Field D*: [3D Field D - JPL Robotics](http://www-robotics.jpl.nasa.gov/publications/Joseph_Carsten/fdstar3d.pdf)
HelloGoodbye
CC BY-SA 3.0
2017-10-28T20:33:08.823Z
@BlueRaja: The mention of a grid shocked me. Which ones *are* restricted to grids? I thought these were general graph algorithms...
user541686
CC BY-SA 3.0
2017-11-01T13:39:55.927Z
@Mehrdad Some of these are restricted to grids because they rely on the fact that grids have known predecessors and successors, are typically bidirectional, and have known geometric characteristics.  Field D* is restricted to grids because the whole point of that algorithm is to linearly interpolate where the robot should go in order to provide smoother movement.
Krupip
CC BY-SA 3.0
2012-06-28T16:20:58.257Z
2012-07-13T21:05:48.473Z
2012-07-13T21:05:48.473Z
BlueRaja - Danny Pflughoeft
<p>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?</p>
<hr />
<p>These are the ones I've been able to find so far:</p>
<ul>
<li><a href="https://web.archive.org/web/20181222193824/http://www.frc.ri.cmu.edu:80/%7Eaxs/doc/icra94.pdf" rel="nofollow noreferrer">D*</a> (1994)</li>
<li><a href="https://web.archive.org/web/20181222193830/http://www.frc.ri.cmu.edu:80/%7Eaxs/doc/ijcai95.pdf" rel="nofollow noreferrer">Focused D*</a> (1995)</li>
<li><a href="https://web.archive.org/web/20210929205756/https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7926&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">DynamicSWSF-FP</a> (1996)</li>
<li><a href="https://web.archive.org/web/20160429171742/https://ccrg.soe.ucsc.edu/publications/shree.ton.pdf" rel="nofollow noreferrer">LPA</a> (1997)</li>
<li><a href="http://idm-lab.org/bib/abstracts/papers/nips2001.pdf" rel="nofollow noreferrer">LPA*/Incremental A*</a> (2001)</li>
<li><a href="http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf" rel="nofollow noreferrer">D* Lite</a> (2002)</li>
<li><a href="https://www.cs.cmu.edu/%7Emmv/papers/02aaai-rune.pdf" rel="nofollow noreferrer">SetA*</a> (2002)</li>
<li><a href="https://web.archive.org/web/20210509203909/http://abotea.rsise.anu.edu.au/data/hpastar.pdf" rel="nofollow noreferrer">HPA*</a> (2004)</li>
<li><a href="https://www.cs.cmu.edu/%7Eggordon/likhachev-etal.anytime-dstar.pdf" rel="nofollow noreferrer">Anytime D*</a> (2005)</li>
<li><a href="https://www.societyofrobots.com/robottheory/Partial_Pathfinding_Using_Map_Abstraction_and_Refinement.pdf" rel="nofollow noreferrer">PRA*</a> (2005)</li>
<li><a href="http://robots.stanford.edu/isrr-papers/final/final-23.pdf" rel="nofollow noreferrer">Field D*</a> (2007)</li>
<li><a href="http://idm-lab.org/bib/abstracts/papers/jair10b.pdf" rel="nofollow noreferrer">Theta*</a> (2007)</li>
<li><a href="https://harablog.files.wordpress.com/2009/01/haa.pdf" rel="nofollow noreferrer">HAA*</a> (2008)</li>
<li><a href="https://www.aamas-conference.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0026.pdf" rel="nofollow noreferrer">GAA*</a> (2008)</li>
<li><a href="http://www.springerlink.com/content/b8m2765x57155226/?p=9286afb6eee64ea5b896fbc2c85353e8&amp;pi=24" rel="nofollow noreferrer">LEARCH</a> (2009)</li>
<li><a href="https://doi.org/10.1007/978-3-642-02270-8_28" rel="nofollow noreferrer">BDDD*</a> (2009 - I cannot access this paper :|)</li>
<li><a href="http://idm-lab.org/bib/abstracts/papers/ijcai09d.pdf" rel="nofollow noreferrer">Incremental Phi*</a> (2009)</li>
<li><a href="https://web.archive.org/web/20170829204504/http://www-scf.usc.edu/%7Exiaoxuns/GFRAstar.pdf" rel="nofollow noreferrer">GFRA*</a> (2010)</li>
<li><a href="http://idm-lab.org/bib/abstracts/papers/aamas10a.pdf" rel="nofollow noreferrer">MTD*-Lite</a> (2010)</li>
<li><a href="https://www.ifaamas.org/Proceedings/aamas2011/papers/A1_B44.pdf" rel="nofollow noreferrer">Tree-AA*</a> (2011)</li>
</ul>
<p>I'm not sure which of these apply to my specific problem - I'll read them all if necessary, but it would save me <strong>a lot</strong> of time if someone could write up a summary.</p>
<hr />
<p>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.</p>
<p><img src="https://i.sstatic.net/fbO4P.png" alt="Image2" /></p>
<p>The user will then <strong>move one wall</strong>, and I have to recalculate the entire path again.  The <em>&quot;move-wall/recalculate-path&quot;</em> 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*.</p>
<p>Though, I am not necessarily looking for an alteration to A* - it could be a completely separate algorithm.</p>

CC BY-SA 3.0
2012-06-27T22:52:22.220Z
Have you taken a look at D*? It's an incremental algorithm, and if I remember correctly, should handle a situation exactly like this. I once saw a robot that used it for pathfinding where there were random walkers in the environment.
Juho
CC BY-SA 3.0
2012-06-27T23:03:48.997Z
@mrm: Somehow, in my last hour of googling, I had no come across that algorithm.  I'll look into it - thanks for pushing me in the right direction!
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2012-06-27T23:35:23.323Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
CC BY-SA 3.0
2012-06-28T04:38:30.123Z
@Kaveh: Why isn't asking for an overview of the state-of-the-art in dynamic pathfinding algorithms "research-level?" Field-D* is less than 5 years old, and LEARCH is less than 3..
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2012-06-28T05:20:21.173Z
I'm not sure why this isn't an appropriate question for this forum. this is by no means a settled and old topic
Suresh Venkat
CC BY-SA 3.0
2012-06-28T05:44:58.597Z
@BlueRaja, I don't see what you ask in your comment in the post. What you asked is "Are there any known (grid-) graph pathfinding algorithms which don't require a complete recalculation when a small change to the graph is made?" and that doesn't look like a research-level question in TCS. I would suggest that you incorporate your comment into the question if that is what you want to ask. Same applies to "Which (if any) of these apply to my problem?".
Kaveh
CC BY-SA 3.0
2012-06-28T05:50:56.903Z
I hope this clarifies my comment [above](http://cstheory.stackexchange.com/questions/11855/pathfinding-recalculating-shortest-path-after-small-change-in-a-dynamic-grid-l#comment32489_11855). The edit "Do the newer ones outdate the older ones, or are there times where the older ones are still applicable?" is asking for comparison of several algorithms and doesn't seem a good question at all unless you clarify that you are looking for survey on the topic, but that didn't seem to be what you were asking, you want a survey with respect to your specific problem (which is unlikely to exist).
Kaveh
CC BY-SA 3.0
2012-06-28T08:00:36.120Z
@BlueRaja-DannyPflughoeft I also think this is a good, research-level question. I'll add an answer based on my comment, and expand it a little bit.
Juho
CC BY-SA 3.0
2013-02-24T06:56:27.197Z
Out of curiosity, does anyone know why this question suddenly shot up in popularity 8 months after it was asked, getting 20+ more upvotes and 3 new answers?
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2013-02-24T11:55:47.560Z
@BlueRaja-DannyPflughoeft Got linked on reddit.
U2EF1
CC BY-SA 3.0
2013-02-25T21:06:09.597Z
@U2EF1: Could you please post a link here to that thread?
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2013-02-25T21:26:55.300Z
http://i.reddit.com/r/programming/comments/194aae/how_do_the_stateoftheart_pathfinding_algorithms/
Sasho Nikolov
<ds.algorithms><shortest-path>
How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?
BlueRaja - Danny Pflughoeft
# How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

(Asked by: username_0 on 2012-06-27)

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\*](https://web.archive.org/web/20181222193824/http://www.frc.ri.cmu.edu:80/%7Eaxs/doc/icra94.pdf) (1994)
* [Focused D\*](https://web.archive.org/web/20181222193830/http://www.frc.ri.cmu.edu:80/%7Eaxs/doc/ijcai95.pdf) (1995)
* [DynamicSWSF-FP](https://web.archive.org/web/20210929205756/https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7926&rep=rep1&type=pdf) (1996)
* [LPA](https://web.archive.org/web/20160429171742/https://ccrg.soe.ucsc.edu/publications/shree.ton.pdf) (1997)
* [LPA\*/Incremental A\*](http://idm-lab.org/bib/abstracts/papers/nips2001.pdf) (2001)
* [D\* Lite](http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf) (2002)
* [SetA\*](https://www.cs.cmu.edu/%7Emmv/papers/02aaai-rune.pdf) (2002)
* [HPA\*](https://web.archive.org/web/20210509203909/http://abotea.rsise.anu.edu.au/data/hpastar.pdf) (2004)
* [Anytime D\*](https://www.cs.cmu.edu/%7Eggordon/likhachev-etal.anytime-dstar.pdf) (2005)
* [PRA\*](https://www.societyofrobots.com/robottheory/Partial_Pathfinding_Using_Map_Abstraction_and_Refinement.pdf) (2005)
* [Field D\*](http://robots.stanford.edu/isrr-papers/final/final-23.pdf) (2007)
* [Theta\*](http://idm-lab.org/bib/abstracts/papers/jair10b.pdf) (2007)
* [HAA\*](https://harablog.files.wordpress.com/2009/01/haa.pdf) (2008)
* [GAA\*](https://www.aamas-conference.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0026.pdf) (2008)
* [LEARCH](http://www.springerlink.com/content/b8m2765x57155226/?p=9286afb6eee64ea5b896fbc2c85353e8&pi=24) (2009)
* [BDDD\*](https://doi.org/10.1007/978-3-642-02270-8_28) (2009 - I cannot access this paper :|)
* [Incremental Phi\*](http://idm-lab.org/bib/abstracts/papers/ijcai09d.pdf) (2009)
* [GFRA\*](https://web.archive.org/web/20170829204504/http://www-scf.usc.edu/%7Exiaoxuns/GFRAstar.pdf) (2010)
* [MTD\*-Lite](http://idm-lab.org/bib/abstracts/papers/aamas10a.pdf) (2010)
* [Tree-AA\*](https://www.ifaamas.org/Proceedings/aamas2011/papers/A1_B44.pdf) (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.

![Image2](https://i.sstatic.net/fbO4P.png)

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.

**Tags:** ds.algorithms, shortest-path

> **Comments:**
> **username_1**: Have you taken a look at D*? It's an incremental algorithm, and if I remember correctly, should handle a situation exactly like this. I once saw a robot that used it for pathfinding where there were random walkers in the environment.  
> **username_0**: @mrm: Somehow, in my last hour of googling, I had no come across that algorithm.  I'll look into it - thanks for pushing me in the right direction!  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  
> **username_0**: @username_2: Why isn't asking for an overview of the state-of-the-art in dynamic pathfinding algorithms "research-level?" Field-D* is less than 5 years old, and LEARCH is less than 3..  
> **username_3**: I'm not sure why this isn't an appropriate question for this forum. this is by no means a settled and old topic  
> **username_2**: @BlueRaja, I don't see what you ask in your comment in the post. What you asked is "Are there any known (grid-) graph pathfinding algorithms which don't require a complete recalculation when a small change to the graph is made?" and that doesn't look like a research-level question in TCS. I would suggest that you incorporate your comment into the question if that is what you want to ask. Same applies to "Which (if any) of these apply to my problem?".  
> **username_2**: I hope this clarifies my comment [above](http://cstheory.stackexchange.com/questions/11855/pathfinding-recalculating-shortest-path-after-small-change-in-a-dynamic-grid-l#comment32489_11855). The edit "Do the newer ones outdate the older ones, or are there times where the older ones are still applicable?" is asking for comparison of several algorithms and doesn't seem a good question at all unless you clarify that you are looking for survey on the topic, but that didn't seem to be what you were asking, you want a survey with respect to your specific problem (which is unlikely to exist).  
> **username_1**: @BlueRaja-DannyPflughoeft I also think this is a good, research-level question. I'll add an answer based on my comment, and expand it a little bit.  
> **username_0**: Out of curiosity, does anyone know why this question suddenly shot up in popularity 8 months after it was asked, getting 20+ more upvotes and 3 new answers?  
> **username_4**: @BlueRaja-DannyPflughoeft Got linked on reddit.  
> **username_0**: @username_4: Could you please post a link here to that thread?  
> **username_5**: http://i.reddit.com/r/programming/comments/194aae/how_do_the_stateoftheart_pathfinding_algorithms/  

---

## 6 answers

### Answer by username_0 on 2012-06-28. Score: 87 | Accepted answer

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](http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/).
  + **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](http://aigamedev.com/open/article/clearance-based-pathfinding/)
  + **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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_11**: Well.. I also found [this paper by @lhrios](http://homepages.dcc.ufmg.br/~lhrios/publications/classes.pdf) which compares some of the algorithms.  
> **username_10**: I know this is old, but I think it's worth noting a small flaw in your description of Field D*. Regular D* isn't constrained to "a grid", it's constrained to a discrete graph. The point the paper makes is that in order to make A*, D* etc work you have to discretize a continuous space into chunks, which limits the angles you can move at. Field D* eliminates that constraint and allows you treat successor states in a continuous, rather than discrete manner (more or less, trickery is involved). It simply uses a 2D grid as an example, D*/A* etc are by no means constrained to a grid.  
> **username_10**: I should mention that Field D* is limited to a grid, though the paper mentions that they did work on a 3D version. This is due to the interpolation it uses. It still stands that A* and D* work on graphs with arbitrary numbers of successor states, Field D* is just an improvement for scenarios where D* uses grid-based planning.  
> **username_12**: An important difference between Field D* and Theta*/Incremental Phi*, is that Field D* can have unique weights for each square, whereas Theta* and Incremental Phi* are limited to having the same weight for all squares that can be visited. Hence, Incremental Phi* is not superior to Field D*.  
> **username_12**: @Jsor: Here is a 3D version of Field D*: [3D Field D - JPL Robotics](http://www-robotics.jpl.nasa.gov/publications/Joseph_Carsten/fdstar3d.pdf)  
> **username_13**: @BlueRaja: The mention of a grid shocked me. Which ones *are* restricted to grids? I thought these were general graph algorithms...  
> **username_14**: @Mehrdad Some of these are restricted to grids because they rely on the fact that grids have known predecessors and successors, are typically bidirectional, and have known geometric characteristics.  Field D* is restricted to grids because the whole point of that algorithm is to linearly interpolate where the robot should go in order to provide smoother movement.  

---

### Answer by username_6 on 2013-02-23. Score: 17

There's a big caveat when using D\*, D\*-Lite, or any of the incremental algorithms in this category (and it's worth noting that this caveat is seldom mentioned in the literature). These types of algorithms use a reversed search. That is, they compute costs outwards from the goal node, like a ripple spreading outwards. When the costs of edges change (e.g. you add or remove a wall in your example) they all have various efficient strategies for only updating the subset of the explored (a.k.a. 'visited') nodes that is affected by the changes.

The big caveat is that the location of these changes with respect to the goal location makes an enormous difference to the efficiency of the algorithms. I showed in various papers and my thesis that it's entirely possible for the worst case performance of any of these incremental algorithms to be *worse* than throwing away all the information and starting afresh with something non-incremental like plain old A\*.

When the changed cost information is close to the perimeter of the expanding search front (the 'visited' region), few paths have to change, and the incremental updates are fast. A pertinent example is a mobile robot with sensors attached to its body. The sensors only see the world near the robot, and hence the changes are in this region. This region is the starting point of the search, not the goal, and so everything works out well and the algorithms are very efficient at updating the optimum path to correct for the changes.

When the changed cost information is close to the goal of the search (or your scenario sees the goal change locations, not just the start), these algorithms suffer catastrophic slowdown. In this scenario, almost all the saved information needs to be updated, because the changed region is so close to the goal that almost all pre-calculated paths pass through the changes and must be re-evaluated. Due to the overhead of storing extra information and calculations to do incremental updates, a re-evaluation on this scale is slower than a fresh start.

Since your example scenario appears to let the user move any wall they desire, you will suffer this problem if you use D\*, D\*-Lite, LPA\*, etc. The time-performance of your algorithm will be variable, dependent upon user input. In general, "this is a bad thing"...

As an example, Alonzo Kelly's group at CMU had a fantastic program called PerceptOR which tried to combine ground robots with aerial robots, all sharing perception information in real-time. When they tried to use a helicopter to provide real-time cost updates to the planning system of a ground vehicle, they hit upon this problem because the helicopter could fly ahead of the ground vehicle, seeing cost changes closer to the goal, and thus slowing down their algorithms. Did they discuss this interesting observation? No. In the end, the best they managed was to have the helicopter fly directly overhead of the ground vehicle - making it the world's most expensive sensor mast. Sure, I'm being petty. But it's a big problem that no one wants to talk about - and they should, because it can totally ruin your ability to use these algorithms if your scenario has these properties.

There are only a handful of papers that discuss this, mostly by me. Of papers written by the authors or students of the authors of the original papers listed in this question, I can think of only one that actually mentions this problem. Likhachev and Ferguson suggest trying to estimate the scale of updates required, and flushing the stored information if the incremental update is estimated to take longer than a fresh start. This is a pretty sensible workaround, but there are others too. My PhD generalizes a similar approach across a broad range of computational problems and is getting beyond the scope of this question, however you may find the references useful since it has a thorough overview of most of these algorithms and more. See <http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364> for details.

> **Comments:**
> **username_0**: Thank you for adding these details :) In my application, the wall gets moved towards the beginning just as often as towards the end.  I implemented BFS, A\*, and LPA\*; A\* was actually slightly slower than BFS *(my spaces tend to be confined, so A\* only searches slightly fewer nodes than BFS; meanwhile BFS only needs a queue, which can be implemented to be faster than a priority-queue can)*, but using LPA\* averaged to be over twice as fast.  

---

### Answer by username_1 on 2012-06-28. Score: 9

The main idea is to use an incremental algorithm, that is able to take advantage of the previous calculations when the initial calculated route gets blocked. This is often investigated in the context of robots, navigation and planning.

[Koenig & Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, June 2005](http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdf) introduces D\* Lite. It seems safe to say that D\* is outdated in a sense that D\* Lite is always as fast as D\*. In addition, D\* is complex, hard to understand, analyze and extend. Figure 9 gives the pseudocode for D\* Lite, and Table 1 shows experimental results with D\* Lite compared to BFS, Backward A\*, Forward A\*, DynamicSWSF-P and D\*.

I do not know the newer algorithms you list (Anytime D\*, Field D\*, LEARCH). Very recently I saw a robot that used D\* Lite for planning in an environment with random walkers in it. In this sense, I don't think D\* Lite is outdated by no means. For your practical problem, I guess there's no harm in trying the usual engineering way: take some approach, and if it doesn't fit your needs, try something else (more complex).


---

### Answer by username_7 on 2013-02-24. Score: 4

I'd like add something about rapidly-exploring randomized trees, or RRTs. The basic idea has good discussion all over the internet, but it's probably safe to start with the links off the Wikipedia page and with Kuffner and LaValle's original papers on the topic.

The most important feature of RRTs is that they can deal with real-valued spaces of *extremely* high dimension without choking. They can handle dynamics, are not optimal but are probabilistically complete (guaranteed to succeed if possible as computation time goes to infinity), and are capable of handling moving targets. There are some extensions that let them work in non-static spaces, the best of which looks to be the Multipartite RRT work that I've linked below.

* <http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree>
* <http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf>


---

### Answer by username_8 on 2013-02-24. Score: 0

Data structures called ***distance oracles*** handle such problems. However, most research results are for *static* graphs only.

If the graphs are grids (and thus planar), some *dynamic* data structures exist (unclear whether the constants are small enough for the application in question):

**Exact shortest paths:**

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

**Approximate shortest paths:**

Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218

> **Comments:**
> **username_0**: Sorry, but if they only work on static graphs, then what do you mean by "they handle such problems?"  The problem asked is *specifically* about non-static graphs.  
> **username_8**: let me change the emphasis:  *most* results are for static graphs only. *some* dynamic data structures exist. followed by a list of those dynamic data structures.  

---

### Answer by username_9 on 2013-02-24. Score: 0

In school I dabbled with [ant colony optimization](https://en.wikipedia.org/wiki/Ant_colony_optimization). In some texts it was touted as a solution for continuously changing graphs, routing networks, etc. It's not an engineered solution, but an adaptation from how ants navigate around obstacles by spreading pheromones to mark good and bad paths. I have no idea if it works for your problem, but i think it's an interesting point of view.


---

