payasr's comments

Those seem a little outdated, there has been a ton of work since then :) A bit more updated reference is https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf is great!

There are also Prof. Hannah Bast's lectures (https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)

Camille Fournier gave an interesting talk on this a few years ago... I think it's worth a watch. https://www.youtube.com/watch?v=sc8sc-ELMhA

I enjoyed reading that, thank you!

I know of SOTA and SPOTAR.. thanks! :)

HD is independent of r. And it's not the minimal set of vertices that must be visited.. it is the smallest set of which at least one must be visited. Another good explanation of HD is in section 1.3 of the skeleton dimension paper (https://arxiv.org/pdf/1609.00512.pdf).

Also, there's some recent work on similar metrics, if you are interested. Do check out (https://arxiv.org/abs/1609.00512) and Sabine Storandt's work on how route planning algorithms behave as graphs scale (https://aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/1774...)

There are some excellent ready-to-use libraries too, if you don't want to code everything yourself. Please see the following gist for a list: https://gist.github.com/PayasR/bc46af938195a827e42006c3f5544...

Thanks Steve!

Sure! That is a classic paper, I didn't know there was a video too. Let me try:

Highway Dimension- Say we are given a bidirectional graph G and a radius r. Now take a vertex v, and find the set of all shortest paths from v of length > r and <= 4r. Let us call this set P(v, r). Iterate for all vertices in the graph and real radii, and obtain similar sets. Then, highway dimension is the size of the smallest set (H) of vertices such that all sets collected in the previous step have at least one vertex in H.

Why is this useful- Empirically, we know that road networks have small highway dimensions. This is interesting because it implies that there are only a handful of vertices from which you can take the shortest paths to all the vertices in the network. Intuitively, it makes sense too. If you want to travel long distances, it's best to take the highway as early as possible, and travel along it for as long as you can, then descend to the local roads as you reach closer to the destination.

Highway dimension basically gives us a theoretical way of capturing the inherent 'hierarchy' of the road network edges and explains why Contraction Hierarchies works so well on road networks (as opposed to random graphs, where CH can be easily beaten). HTH!

The freedom to think abstractly and not in terms of everything-is-on-fire-all-the-time is absolutely the best thing about being a graduate student :)

I've been thinking about writing a blog series on route planning algorithms if there is enough interest.. let me know if anyone wants it lol?

There's a _lot_ of work on hierarchical route planning in games. I don't mean to put down the developers or anything, and I'm so glad all of this works, but there are plenty of ideas in the academic-world that I think developers should know more about.

Botea, Adi, Martin Müller, and Jonathan Schaeffer. 2004. “Near Optimal Hierarchical Path-Finding.” In Journal of Game Development. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.....

Rahmani, Vahid, and Nuria Pelechano. 2017. “Improvements to Hierarchical Pathfinding for Navigation Meshes.” In Proceedings of the Tenth International Conference on Motion in Games, 8:1–8:6. MIG ’17. New York, NY, USA: ACM.

Toll, Wouter van, Roy Triesscheijn, Marcelo Kallmann, Ramon Oliva, Nuria Pelechano, Julien Pettré, and Roland Geraerts. 2016. “A Comparative Study of Navigation Meshes.” In Proceedings of the 9th International Conference on Motion in Games, 91–100. ACM.

And route planning in graphs (with static edge weights) has been studied to death.

https://arxiv.org/pdf/1504.05140.pdf

The coloring is correct, but the chrome extension 'undoes' the equations rendered on the mathjax-enabled pages. In other words, without the beelinereader extension I can see the equations, with it I see only the latex source code. You should be able to check this on any Springer article.

I have been playing around with the reader, and it doesn't seem to play well with mathjax-enabled pages.. Is it a known issue?