We survey recent advances in algorithms for route planning in transportation networks. For
road networks, we show that one can compute driving directions in milliseconds or less even …

We present a versatile and scalable algorithm for computing exact distances on real-world
networks with tens of millions of arcs in real time. Unlike existing approaches, preprocessing …

We present a new preprocessing algorithm for embedding the nodes of a given edge-
weighted undirected graph into a Euclidean space. The Euclidean distance between any …

Cost-optimal planning is a variant of a general planning problem, where all actions have
non-negative costs, and the solution is a valid plan that minimizes the sum of the costs of all …

Abstract Jump Point Search (JPS) is a well known symmetry-breaking algorithm that can
substantially improve performance for grid-based optimal pathfinding. When the input grid is …

Abstraction and refinement is a common approach used in games to improve the speed of
pathfinding by planning in an abstract space and then refining abstract paths to traversable …

Grid pathfinding, an old AI problem, is central for the development of navigation systems for
autonomous agents. A surprising fact about the vast literature on this problem is that very …

Abstract Compressed Path Databases (CPDs) are a leading technique for optimal
pathfinding in graphs with static edge costs. In this work we investigate CPDs as admissible …

Search speed, quality of resulting paths and the cost of pre-processing are the principle
evaluation metrics of a pathfinding algorithm. In this paper, a new algorithm for grid-based …

We introduce a novel preprocessing-based algorithm to solve the problem of determining
the first arc of a shortest path in sparse graphs. Our algorithm achieves query running times …