3 ms·

The next big advance after A* is something called [contraction hierarchies](https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/w

The next big advance after A* is something called [contraction hierarchies](https://en.m.wikipedia.org/wiki/Contraction_hierarchies https://en.m.wikipedia.org/wiki/Contraction_hierarchies) I’d love to see a “part 2” of this resource or similar that explains those in this kind of Laymans terms. There were some white papers but then I suspect the big tech companies started to guard this research a little more closely once its potential to give a commercial edge became apparent.

amitp 3y ago
There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction hierarchies, subgoals, bidirectional A*, hierarchical search, all-pairs compression, moving obstacles, group movement, coordinated movement, landmarks, labeling algorithms, transit nodes, arc flags, cluster distances, vertex separators, reach, highway hiearchies, etc. Differential heuristics are my favorite for "bang for the buck", as they are fairly low effort (maybe <20 lines of code) for good speedup (3-5X on my game map tests [1]). There's lots of research papers out there, especially for road maps. I tried keeping track of them all and gave up :-( But you might find these two papers useful: * https://arxiv.org/pdf/1504.05140.pdf https://arxiv.org/pdf/1504.05140.pdf * https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.pdf https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p... [1] https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen...
- payasr 3y ago
  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 https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf 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/EfficientRoutePlanningSS2012 https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)
1letterunixname 3y ago
See also Time-Dependent Contraction Hierarchies (2008) [pdf] https://algo2.iti.kit.edu/documents/routeplanning/tch_alenex09.pdf https://algo2.iti.kit.edu/documents/routeplanning/tch_alenex... Oh the fun of cobbling heuristic algorithms to work in the real-world where precise algorithms are big-O too slow.

amitp 3y ago

There are lots of variants of A* that depend on what you can assume about your graph, whether you can preprocess, how often the graph changes, etc. Contraction hierarchies, subgoals, bidirectional A*, hierarchical search, all-pairs compression, moving obstacles, group movement, coordinated movement, landmarks, labeling algorithms, transit nodes, arc flags, cluster distances, vertex separators, reach, highway hiearchies, etc. Differential heuristics are my favorite for "bang for the buck", as they are fairly low effort (maybe <20 lines of code) for good speedup (3-5X on my game map tests [1]). There's lots of research papers out there, especially for road maps. I tried keeping track of them all and gave up :-( But you might find these two papers useful: * https://arxiv.org/pdf/1504.05140.pdf https://arxiv.org/pdf/1504.05140.pdf * https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.pdf https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.p... [1] https://www.redblobgames.com/pathfinding/heuristics/differential.html https://www.redblobgames.com/pathfinding/heuristics/differen...

payasr 3y ago
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 https://arxiv.org/pdf/1504.05140.pdf, and http://www.sommer.jp/spq-survey.pdf 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/EfficientRoutePlanningSS2012 https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...) and her talk at ICAPS (https://www.youtube.com/watch?v=B3wKfJAVRkg https://www.youtube.com/watch?v=B3wKfJAVRkg), both excellent :)

1letterunixname 3y ago

See also Time-Dependent Contraction Hierarchies (2008) [pdf] https://algo2.iti.kit.edu/documents/routeplanning/tch_alenex09.pdf https://algo2.iti.kit.edu/documents/routeplanning/tch_alenex... Oh the fun of cobbling heuristic algorithms to work in the real-world where precise algorithms are big-O too slow.