Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU

2020/01/01 by Maximilian Reischl, Christian Knauer, Michael Guthe · 1 voice
Computer Science · #Robotic Path Planning Algorithms

paper · doi:10.2312/pg.20201228

openalex publication_date 2020/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

We present a new approach for path finding in weighted graphs using pre-computed minimal distance fields. By selecting the most promising minimal distance field at any given node and switching between them, our algorithm tries to find the shortest path. As we show, this approach scales very well for different topologies, hardware and graph sizes and has a mean length error below 1% while using reasonable amounts of memory. By keeping a simple structure and minimal backtracking, we are able to use the same approach on the massively parallel GPU, reducing the run time even further.

Discussions

• Anyone have access to "Using Landmarks for Near-Optimal Pathfinding on the CPU and GPU" (doi.org/10.2312/pg.2...)? I'd love to give it a read [bsky, 1 points, 2 comments]

Related

• On the quick search for the shortest paths in an unweighted dynamic graph by its projections in brief
• The FastMap Algorithm for Shortest Path Computations
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• Computing Shortest Paths Using A*, Landmarks, and Polygon Inequalities (Abstract)
• Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling