# A pathfinding algorithm for graphs in which arc weights can change over time

So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction.

Here's the situation, I have a weighted undirected graph of nodes and arcs. I have an implementation that uses A* for pathfinding on this graph. However, I now have a situation where the weights (cost) of each arc can change over time. That is at each step in the A* pathfinding algorithm the weights of the entire graph can change.

So I'm trying to see if there is an existing algorithm or alteration of A*-like algorithm that handles changing weights well. If anyone has any keywords I should be looking into I'd appreciate any pointers you can provide.

Look at pathfinding algorithms in the context of robotic navigation. In many such applications, the observed world is modeled as a graph. Naturally, the environment changes meaning the graph evolves as well.

For a start, have a look at D* Lite in the work of Koenig & Likhachev. This is a rather standard work in the area, and you'll find plenty of more work regarding replanning by looking at papers that reference it.

• Thanks for your reply! I've had a quick look at D* and D* Lite, but from what I understand those are best for when the actual shape of the graph changes i.e. arcs are added and deleted. In my case the shape of the graph is constant, it is only the weights of the arcs that change not what they connect.
– Jack
Commented Mar 6, 2020 at 19:22
• I didn't already know of D*, hence I looked into it from your answer. Please correct me if I'm wrong but from what I read D* is for use when the edges used in an existing route are no longer available. As stated in my question my arcs weight's change over time and at each step in the pathfinding algorithm
– Jack
Commented Mar 6, 2020 at 20:38
• @Jack OK, I see. Here's one hit from the list of papers that reference [1]. It claims to work well when edge costs are increased or decreased.
– Juho
Commented Mar 6, 2020 at 20:49