CODEWITHSUNDEEP
algorithmdistancepath-findingshortest-patha-star
Zik
Zik

Reputation: 1576

Shortest path A* f(n) = g(n) + h(n)

When you use A*, it chooses the best node which is the closest to the goal right? ( using f(n) = g(n) + h(n)) ( using Manhattan distance for h(n) )

But what if there are walls between the start and goal. I can't explain it in words but I'll show a picture.


(source: uploadir.com)

If A* chooses the node that is closest to the goal, why is the path not the one encircled in red? But the one encircled in green. I really don't understand A* especially when there are impassable cells/tiles/nodes/etc. (walls). Also, you can see this picture I made like in this video http://www.youtube.com/watch?v=DINCL5cd_w0 (Path Finding Algorithms (A*, Dijkstra, Bi-Directional BFS)) at 1:20

Upvotes: 2

Views: 6471

Answers (2)

Chris
Chris

Reputation: 8170

A* also considers the length of the current path as well as the distance to the goal. All possible paths are expanded, but with a priority on those which are:

  1. Closest to the goal
  2. Shortest

The path cost, f(n) is equal to the cost at the previous step, g(n), plus a factor based on distance to the goal, h(n). So for every extra grid space the path goes through, the cost of the path increases. This will effectively create a balance between short paths, and paths which move directly to the goal.

So by the time your example paths have joined up again, it is the purple path which is shortest, and so that will be the path which is expanded first, and will eventually reach the goal first.

There is a Udacity course: Programming a Robotic Car which has a good section on the A* (and similar) algorithms.

Upvotes: 3

rlinden
rlinden

Reputation: 2041

As you stated, A* chooses the current best path base on f(n)=g(n)+h(n), where g(n) is the currently computed cost and h(n) an estimation of the remaining cost. Only the most promising node (the one with the smallest f(n)) at the moment will be expanded. Therefore, when the blue and purple paths diverge (let us call it point A), it goes straight towards the wall, because there h(n) is smaller and the whole f(n) becomes smaller.

Remember that h functions usually are relaxations of the problem - in your case, it probably is the straight distance to the goal. Hence, the whole f becomes smaller. Another path will be consider if the current f becomes bigger than the estimation made to the unpursued paths.

Therefore, the probable reason it does not go through the purple path is that the current value for f at every point in the blue path is always smaller than the one in the purple path.

That is very strange to me because your g is always increasing and there are many points in the blue path that are farther away from the goal than point A. Nevertheless, if you want to be sure, you should do some debugging and verifying each value of f, g and h at every unpursued point versus the current pusued path's values.

Upvotes: 2

Related Questions