Alberth said:
It does? gScore seems to be the cost of the explored path to me.

Oh, you're right. Not sure why i got this wrong initially. Now it makes sense.

Alberth said:
What I don't know is if it ever happens that a better minimum real cost for a node ever occurs once you expanded the path from that node. It would need a path through that node with a shorter real cost, and thus a higher estimated cost than the path that reached that node you're expanding next. I guess it may happen if you have widely varying but always lower than real estimates but no idea what you need to ensure it never happens.

It's things like this why this stuff is difficult. I never trust myself to have thought on all special cases, and it's difficult to generate test data to clarify such doubts.

alvaro said:
In my particular implementation of the heuristic for this example, the true cost of moving to a neighbor is actually the same as what the heuristic returns, so I lazily used it.

I've noticed this one.

alvaro said:
it would be tricky to find it in the priority queue and update its cost. However, you can just add the node in the open list multiple times and make sure you don't process already closed nodes.

That's what i did for Dijkstra, with the ‘extracted’ bool vector.
I was using it for months before that, and only after that time i've noticed duplicates can happen, which caused my app to crash.
I did the fix with trial and error, not really understanding what i was doing. But duplicates went away, and it became faster as well, so i was happy. The resulting paths did not change.
But i was not sure this is guaranteed, or if some backtracking would be needed to do corrections. The Wikipedia articles also mentions an eventual need for a Fibonacci heap, or at least a requirement to update costs, which i did not.

This really seems the devilish detail here. It causes uncertainty, which needs to be resolved before making a fast real time implementation.

Alberth said: What I don't know is if it ever happens that a better minimum real cost for a node ever occurs once you expanded the path from that node. It would need a path through that node with a shorter real cost, and thus a higher estimated cost than the path that reached that node you're expanding next. I guess it may happen if you have widely varying but always lower than real estimates but no idea what you need to ensure it never happens.

JoeJ said: It's things like this why this stuff is difficult. I never trust myself to have thought on all special cases, and it's difficult to generate test data to clarify such doubts.

I tried getting the original paper, but it costs near 30 pound for 24 pages to get it, which seems a bit steep for seomthing from 1968 so I refrained from buying that. (Someone is making good money there!)

Also my brain spend background cpu cycles on this, and this morning it concluded “perhaps it can happen, but not at the destination”. The key to understanding is that the estimated costs are 0 at that spot. Higher or lower estimates become a non-issue at that position.

A longer explanation:

When you arrive at the destination you get an upperbound on the real length of the path. As that path may have increased its total cost (since it just replaced a bit of estimated costs by real costs), other paths with lower total cost may exist, and those will then be picked and extended first. A few of them may also arrive at the destination, and some of those may have a lower upperbound on the real length (due to different edge lengths in the last step as discussed before). Such better paths will get precedence over the path that arrived first then by the algorithm (to get extended further).

Now when you pick a path that is about to extend from the destination, you know that path is one of the paths with lowest total cost at that point in the exploration (the algorithm would have picked a cheaper path otherwise). That means that all other paths that still exist have equal or higher total cost. Since their total cost will not decrease (estimates are lower or equal to real costs), you know the lowest cost to the destination is the real cost of the path that you picked.

So, as long as you continue exploring paths with better total costs, and stop when you try to extend a path from the destination it should be fine, as far as I can see.

Makes sense.

But the example raised me another question: Can we do the ‘man in the middle’ optimization for A* too?

Using Dijkstra, we can grow paths from both the start and goal simultaneously, and stop as soon as they meet.
The savings are big. Assuming a dense graph on a plane, it's twice the area of a circle of half the radius vs. the area of a single circle of the full radius.

But i assume with A* this does not help but slows it down?

I have added the expected extra node visits from the destination with blue dots to the image. In total we would visit more nodes.

Responding to previous posts - no, a previously expanded node cannot get ‘cheaper’ once already expanded. This is why A* requires an underestimate - it means a node only ever gets more expensive as you resolve it. A* is actually quite a simple algorithm with very few edge cases - most of the problems creep in when people try to optimise it for their domain, which can lead to problems such as needing to revise scores for certain nodes (when the algorithm would, strictly speaking, use a different node).

And on the last post - 'man in the middle’ optimisation is called bidirectional search. It helps with Djikstra because in the general case it's an inefficient algorithm for finding single paths. A* is, however, optimal for finding single paths. Thus, bidirectional search is not going to help, and is probably just going to cause many bugs.

Kylotan said:
Responding to previous posts - no, a previously expanded node cannot get ‘cheaper’ once already expanded. This is why A* requires an underestimate - it means a node only ever gets more expensive as you resolve it.

I don't think this is true, the rules don't say anything about the relation between estimates.

           P (3 steps)
       /------------\              R (100 stps)
entry *              *-------------------- * exit
       \------------/ merge
           Q (2 steps)

As a counter-example, assume we want to compute a path from ‘entry’ to ‘exit’. At first there is a choice between paths P and Q. Then at ‘merge’, the path merges and continues to the ‘exit’.

Let's assume real cost of P = 3 steps, of Q = 2 steps, and of R = 100 steps. One step costs 10. Thus path PR real costs are 1030, while real costs QR are 1020. The estimate of the PR path is 1 for each step, while the estimate for the QR path is 9 for each step. Both estimates are below the real costs and thus proper underestimates.

Let's run the algorithm:

1. At the first iteration the ‘entry' point spawns both PR and QR paths. PR makes one step, and has 1 * 10 + 102 * 1 = 112 total cost, QR makes one step and has 1 * 10 + 101 * 9 = 919 total cost.

2. PR has lower total costs and makes the 2nd step, leading to 2 * 10 + 101 * 1 = 121 total cost.

3. PR has lower total costs and makes the 3rd step (arriving at 'merge'), leading to 3 * 10 + 100 * 1 = 130 total cost.

4. PR has lower total costs and makes the 4th step (leaving ‘merge’), leading to 4 * 10 + 99 * 1 = 139 total cost.

And there you have it, a the path gets expanded at ‘merge’, while much later in the process the QR path will also arrive and leave the ‘merge’ point (and eventually win the race).

I agree the example is totally constructed, but it complies with the constraints that were stated yet behaves differently.

JoeJ said:
Can we do the ‘man in the middle’ optimization for A* too?

As Kylotan already said, A* steers the search, so it doesn't wander of in totally wrong directions. The advantages are less big thus.

How useful it depends a lot on how good your estimates are I think. On a straight path and with estimates being equal to real costs, when both searches meet, you can compare real costs of one search with the estimate of the other search and if they are equal you're probably done I think (with the search in progress, as far as I can see the real costs are an upper-bound while estimates are a lower-bound). Otherwise (estimate of one search being lower than the real costs of the other search), I don't see a simple way to make a decision so you'd have to continue.

So if you have lousy estimates I don't expect you gain anything and instead double the amount of work.

Some of this is confusion over what ‘node’ and ‘expanded’ means. If you use a representation where the same node can be evaluated multiple times, then it can be possible to need to overwrite the old value with a new, cheaper route. This especially applies if you're implementing it in what I'll call a ‘graph painting’ style similar to Djikstra where every node has precisely 1 value and you're refining it over time.

But mostly the issue here is that the A* heuristic needs to not just be an underestimate but to be consistent, aka monotonic - in other words, if the heuristic esimates that A → C is 100 and a movement from A → B costs 10, the heuristic from B → C cannot ‘legally’ return a number over 110. It can't have a situation where it is returning either 100 for merge → exit in one situation and 900 for merge → exit in another situation, because this could potentially lead to a situation where the algorithm takes one step costing 10 but somehow making the heuristic from the next node go up by 800. The worst case for a step in A* is one that takes us directly away from the goal, so if we incur a cost of 10 going the wrong direction, the estimate to the goal can only ever get worse by 10 points as well. If you're using a system where the 2 different ways of reaching ‘merge’ are counted as the same node in the search, then the heuristic must always return the same value to get from merge → exit. Otherwise, you have 2 search nodes, by definition.

What this means in practice is that the ‘merge’ node can get into the open list when evaluated as a neighbour of P, but you will only ever expand it after you expand Q, because it's cost is the sum of a single consistent heuristic (which does not care whether it was expanded from P or Q) plus the cost to reach it (which is lower for Q).