1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.


[1] Koenig, Sven, and Maxim Likhachev. "Fast replanning for navigation in unknown terrain." IEEE Transactions on Robotics 21.3 (2005): 354-363.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jack Mar 6 at 19:22
  • $\begingroup$ 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 $\endgroup$ – Jack Mar 6 at 20:38
  • $\begingroup$ @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. $\endgroup$ – Juho Mar 6 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.