[Routing] A-Star meet-in-the-middle

[Jon Bright]

Hi Marcus,

Marcus Wolschon wrote:
> 
> you are using the heuristic to find a total ordering. Why should
> a linear factor make any difference here? As far as I can see
> the ordering resulting would be completely identical.

You're using the heuristic *and the distance travelled* to do the 
ordering.  Nic's suggesting applying a linear factor only to the 
heuristic.  A* works with an optimistic heuristic, giving the minimum 
cost from the current node to the destination node.  The factor makes it 
slightly less optimistic, leading to routes towards the target being 
preferred over potentially shorter routes which initially move away from 
the target.  An example:

/-----------------------------------------\
|                                         |
|                                         |
\-----S-\      C/-----\    /---\    /-----T
A       |       |     |    |   |    |
         |       |     |    |   |    |
         |       |     |    |   |    |
        B\_______/     \____/   \____/

Starting at S, the algorithm proceeds to A and B.  Assume the distance 
travelled between S and A and between S and B is 10.  Assume the 
distance between B and C is 35.  Assume the distance over the "top loop" 
between A and T is 110.  Assume the straight-line distance between A and 
T is 100, the straight-line distance between B and T is 90 and the 
straight-line distance between C and T is 80.

After travelling to A and B, the algorithm has:

route_a = 10+100 = 110
route_b = 10+90 = 100

It therefore explores route_b first and reaches C.  It then has:

route_a = 10+100 = 110
route_b = (10+35)+80 = 125

It therefore explores route_a.  Assuming there are no more fork nodes 
between A and T, it reaches T and has

route_a = (10+110)+0 = 120
route_b = (10+35)+80 = 125

At this point, the algorithm terminates, having found the shortest 
route.  The distance that route_b has already travelled plus the 
*shorted possible distance* that it would have to travel in order to 
reach T is longer than the distance of route_a.

Nic's modification recognises that in real road networks, there's rarely 
an exact straight line between two points.  His hope was that adding 10% 
to the straight-line distance still represents the minimum distance but 
leads to routes away from the target being rejected more quickly.

> Would it break anything to even use sqr(dx)+sqr(dy) instead of
> sqrt(sqr(dx)+sqr(dy)) ?

Yes.  The heuristic would no longer give the minimum distance.  If you 
don't see the problem, imagine the example above rotated by 45 degrees. 
    The straight-line distance between A and T is still 100. 
dx=dy~=70.71.  Instead of getting 100 back from the heuristic, though, 
you get 10000 - and the algorithm will continue exploring route_b.

Summary:

  - The heuristic must always be shorter than or equal to the shortest 
actual path to the target for A* to find an optimal route.
  - The closer the heuristic is to reality, the quicker A* will be.
  - If the heuristic isn't shorter, the quality of the routes produced 
will progressively degrade.

--
Jon