Preferences

ziaddotcom parent
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.


gugagore
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.

This item has no comments currently.