Hacker News Reader

Comment by gugagore | Hacker News Reader

This is not quite right.

A* and Contraction hierarchies (and other graph pre-processing techniques) make the same assumptions on what data is available at planning time.

The difference is whether you expect to make multiple shortest-path queries on the same graph, or not. If you will make several queries on the same graph (e.g. turn-by-turn navigation), then it makes sense to spend time to process the graph to make queries more efficient.

If you'll make a single query, because your graph is changing dynamically, then pre-processing doesn't help.

But A* still needs to have access to the whole graph at plan time. You might be thinking of D* and algorithms for that class of problems.

View on HN

Ah, so in your example we're using the term "turn-by-turn navigation" in the textbook accurate version of the term (actually evaluates each turn as you go in case something has changed or the driver missed the turn, etc) to contrast it with a series of turn by turn directions given on a single query prior to the trip (like printing off directions before you leave).

So, to get even more specific with contraction hierarchies, google maps has a feature where you can avoid highways, and/or avoid tolls, and/or avoid ferries.

So in this scenario google has likely done "customization contraction hierarchies" as described here https://dl.acm.org/citation.cfm?doid=2886843

Therefor to answer the original question of this thread, is a* is superseded by contraction hierarchies, the short answer is yes if you have even the slightest amount of time to preprocess a graph (If i'm understanding gugagore and reference material correctly).

However, the answer is no in a more arcane/toy/hypothetical context. In an example of something like a randomly generated massive pac man vs ai ms pac man game where one of the two can can win if he/she reaches a single randomly generated exit first, contraction hierarchies don't really help/apply over a-star. The randomly generated map sort of implies we don't even want to give the computer time to preprocess the map, ultimately its human a-star-ish vs ai a* in real time, while trying to avoid ghosts. Otherwise we could simply give the preprocessed shortest path to ai ms pacman upfront, and tell the ghosts to avoid ai ms pac man. This would seem very similar to the player, but would be far less insightful for someone trying to learn and understand a* vs contraction hierarchies and pathfinding in general.

To be clear, "turn-by-turn navigation" was an example of a query that happens on a fairly static graph: the road network. If the driver misses the turn, that just triggers another query on a static graph. I was not talking about needing to incorporate changes in connectivity, or in edge weights (due to e.g. road closures, or traffic updates).

Regarding "if you have even the slightest amount of time", no I don't think that's accurate. It's a trade-off between "offline" and "online" computation (sorry those words are so loaded, but they are often used in research on planning algorithms).

You could conceivably solve the All-Pairs Shortest Path for the road network offline, and then when you received a query online, you would be able to answer "immediately" by look-up table.

You could do nothing offline, and just run A* when you get a query. You won't be leveraging anything from the fact that the road network is fairly static.

Those are two endpoints of the trade-off spectrum, and approaches like contraction hierarchy lie in between.

Saying "contraction hierarchies supersedes A*" is kind of like saying "database indexing supersedes grep". If you're only going to grep a document once, it is not worth it to build an index. An index usually only helps if you will do multiple queries on the data.

Reply on news.ycombinator.com