Search code examples
a-starrobotics

path planning -> ways from goal to initial state?


the problem: is it true that finding a path from goal to start point is much more efficient than finding a path from start to goal? if this is true,can some one help me out and explain why?

my opinion: it shouldn't be different because finding a way from goal to start is just like renaming goal to start and start to goal.


Solution

  • The answer to your question all depends on the path finding algorithm you use.

    One of the most well know path finding algorithms, A-Star (or A*), is commonly used in a reverse sense. It all has to do with the heuristics. Since we usually use proximity as the heuristic for the algorithm we can get stuck in obstacles. These obstacles might however be easier to face the other way around. A great explanation with examples can be found here. Just for clarity: if there is no certain knowledge of obstacles, then there is no predictable difference between forwards and backwards path finding by A*.

    Another reason why you might want to reverse the pathfinding is if you have multiple actors trying to reach the same goal. Instead of having to execute A*, or another path finding algorithm, for every actor you can combine them into a single executing of a graph explorational path finding algorithm. For example, a variation on Dijkstra's algorithm could find all the shortest distances to all actors in one graph exploration.