0
$\begingroup$

A* needs a consistent heuristic to work on a graph.

So I'm not sure if the heuristic of a straight line (bird flight) can be used.

For example: the costs to travel to a neighbors node is always positive.

              GOAL

 --------------------
 |                  |
 |      START       |
 |                  |    where to stripes are obstacles.

Am I correct that this the proposed heuristic isn't consistent here as it has to travel away from the goal first?

Is there a good heuristic for this kind of situation? Or should I keep it with Dijkstra a forget about A*?

$\endgroup$
0
$\begingroup$

Three points here:

  1. A$^*$ does not require consistency of the heuristic function (for this, I refer to the definition provided by Klaus Draeger, which is perfect). Instead, A$^*$ requires admissibility of the heuristic function ($h(n)\leq h^*(n), \forall n$ where $h^*(n)$ is the optimal cost to reach the goal from a particular node $n$) or, in plain words, that it never overestimates the effort to reach the goal.
  2. As a matter of fact, it has been proven that inconsistencies (while preserving admissibility) can be very beneficial. There are a number of papers on this issue but let me please refer the one which summarizes the most important findings: Ariel Felner, Uzi Zahavi, Robert Holte, Jonathan Schaeffer, Nathan Sturtevant, Zhifu Zhang. Inconsistent Heuristics in Theory and Practice. Let me put their main finding in this way: if a heuristic $h(n)$ is inconsistent but it preserves admissibility then there are points where by exceeding the cost of an edge (again, I am referring here to Klaus Draeger's definition) either the starting vertex or the ending vertex are better informed than the other. The authors then revise an old idea: the Pathmax propagation rule and show that it can be greatly enhanced in undirected state spaces resulting in the Bidirectional Pathmax propagation rule (BPMX).
  3. Regarding your specific case, the euclidean distance or aerial distance however is both admissible and consistent so you should not bother about these issues ---it does not even matter if the optimal solution consists of moving away first from the goal to approach later, let A$^*$ prove that for you.

Concluding: I would try the euclidean distance between the current location and the goal location to guide A$^*$ to find optimal solutions in your domain. However, if you ever find out an inconsistent heuristic that serves this purpose to do not be afraid at all and just apply BPMX (which is a couple of lines of code, no more than that).

Hope this helps,

$\endgroup$
0
$\begingroup$

There is nothing wrong with the heuristic function you suggest. Note what the consistency condition actually says: If you have nodes $n_1,n_2$, and the cost of traveling from $n_1$ to $n_2$ is $c$, then the heuristic values need to satisfy a triangle condition: $h(n_1)$ must not be more than $h(n_2)+c$. It is ok for $h$ to underestimate the distance from a node, as it does for your start node (though obviously, the performance of the algorithm can suffer in this case).

$\endgroup$

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.