Conceptio › Archive › Stack Exchange
Stack Exchange open access CC BY-SA

How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

BlueRaja - Danny Pflughoeft · 2012
Stack Exchange · Datasets · License: CC BY-SA · 2012
Open Source ↗
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.
Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

This document is indexed with metadata only: full text is not available in the archive for this record. Open the official source ↗

Related documents

Record · ID 787511
Retrieved via Conceptio: every document is proof-bundled with source, license, and retrieval metadata.
Bring this data into your agent: Connect via MCP or API · 20 free credits to start · no card required
Read the Docs → · View CLI source on GitHub · Conceptio Open Knowledge Archive