Does this A-Star heuristic already exist?

Question

I've been thinking about the A* algorithm recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's based on a distance-estimating heuristic you provide to it. The heuristic you provide must be able to tell the program, for any given position: 'This position is at least this far away from the destination'. The most simple heuristic being to use Pythagoras's theorem to get the distance "as the crow flies" between said point and a destination.

Now, the thing that interested me is that A* efficiency is tied to the preciseness of your 'getMinDistance' function. If it returns a value too low, the algorithm takes longer. If it returns a value too high, A* may return a non-optimal path. If it always returns 0, you have Dijkstra's algorithm. (also the heuristic must be monotonic, read the wikipedia articles for more details)

---

The heuristic I thought about goes like this:

• Using any method of your choosing, split the graph into regions. Designate a node of each region as the region's center (ideally, its centroid). The graph traversal distance between any node and its region's center should be trivially computable (or cached).

• Store the exact graph traversal distance between the centers of every single region. If you have N regions, you should end up with N² distances.

• For any two points A and B, and their respective region's centers Ra and Rb, the graph traversal distance AB is superior or equal to RaRb - (RaA+RbB)

The smaller the regions are, the closer this heuristic gets to the actual traversal distance AB.

---

My questions are:

• Is this algorithm actually admissible? I have no idea how to formally prove it.

• How efficient is this heuristic? My guess would be "Very if you have a lot of small groups, because A* only examines nodes within the groups that include the optimal path", but again, I'm not sure it's true and I don't know how to prove it.

• Was this idea ever published before? If so, what is it called and where can I read about it?

• In the same vein, are there video games which are known to use this heuristic?

Answer 1

This idea is called True Distance Heuristics and as you suspected, it can be very efficient.

True Distance Heuristics

True Distance Heuristics (as well as "Pattern Database") is a technique that utilizes the memory to help with the search. The general idea is "let us pre-compute a few important accurate distances, to save a lot of time during the search". This is also sometimes referred to as "Memory Based Heuristics".

Each technique has different memory requirements and require a different heuristic function (that, of course, may utilize the original heuristic function). Also, some of course might be more beneficial in specific domains.

Differential

This technique suggests to choose k "pivot" states and store the shortest path from every state to each pivot

Canonical

This consists of 2 different data-sets:

Primary data: choose k pivot states and calculate all pairs shortest path among all of these k states. Secondary data: From every node (out of all possible nodes), store distance to the closest canonical node.

Others

There are many other memory based techniques that uses this concept. Many prove themselves to be very beneficial, for a relatively small price to pay (in terms of space).

Food For Thought

As you suspected, these techniques can have admissible heuristics. Since it seems that you are interested in this field, I'll let you figure out the right heuristic functions on your on. I'll give you a hint that the formal proof uses simple math. Feel free to ask for these functions in the comments, and I'll answer.

I strongly suggest to draw these out in a simple drawing, it will make everything very clear.