---
abstract: 'Quickly determining shortest paths in networks is an important ingredient for many routing applications. While Dijkstra’s algorithm can be used to solve these problems, it is too slow for many practical problems. A\* is an extension to Dijkstra’s algorithm. It uses a potential function to estimate the distance of each node to the target. By adding these estimates to the queue keys, the search is directed towards the target. The quality of this potential determines the performance of A\*. We introduce a novel way to efficiently calculate perfect potentials for extended problem settings where a lower bound graph is available. For example, in the case of routing with live traffic, this could be the free flow graph.'
author:
- Ben Strasser
- Tim Zeitz
title: 'A\* with Perfect Potentials'
---

Introduction {#sec:intro}
============

Fast routing in huge street networks has seen a lot of research [@bdgmpsww-rptn-16]. For static, time- and user-invariant networks a lot of techniques exist. They work in two phases. The first phase is called preprocessing phase and is a slow index-construction. In this phase the road graph and the edge weights are known. In the second phase, called query phase, minimum weight paths are computed. The query phase has access to the precomputed index and is very fast.

One of the most successful ones are Contraction Hierarchies (CH) [@gssv-erlrn-12]. Contraction Hierarchies exploit inherent hierarchies in the shortest-path structure of road networks. Using CHs, Queries can be answered on the order of only a millisecond. However, CHs can not always be easily extended to more complicated problem settings. While such extensions exist [@dsw-cch-15; @bgsv-mtdtt-13], they often require substantial engineering effort.

On the other hand, goal directed speed-up techniques based on A\* are usually slower but more flexible. The performance of these approaches depends on the quality of the potential functions used for the A\* search. In this paper, we propose an algorithm which utilizes Contraction Hierarchies to efficiently calculate perfect (best possible) potentials. This allows us to retain the flexibility of A\* based approaches but use much more effective potentials than previously possible.

#### Related Work {#related-work .unnumbered}

A plethora of of research exists in the area of efficient routing in road networks [@bdgmpsww-rptn-16]. Here, we focus on the algorithms directly relevant to this work.

At the core is the algorithm of Dijkstra [@d-ntpcg-59]. This algorithm explores the graph visiting nodes ordered by increasing distance from a source node $s$. For each node $v$, a tentative distance $d_s(v)$ is maintained, which is initially set to $\infty$. In each iteration the node $u$ with the smallest remaining distance $d_s(u)$ is extracted from a priority queue and settled. For outgoing edge $(u,v)$ of $u$ the algorithms checks if $d_s(u) + w(u,v) < d_s(v)$. If so, the distance and the queue position of $v$ is updated. This process is denoted as edge relaxation. Once the target node $t$ is settled, the shortest path and distance between $s$ and $t$ is known.

A\* [@hnr-afbhd-68] extends Dijkstra’s algorithm by changing the order in which nodes are visited. Nodes in the direction of $t$ should be visited earlier. This is achieved through a potential function $p$ estimating the distance to $t$. The priority queue is ordered by $d_s(u) + p(u)$.

ALT [@gh-cspas-05] is an A\* based technique which precomputes shortest distances between a small set of landmark nodes and all other nodes during preprocessing. For the query, potentials are calculated using the triangle inequality for shortest distances and the precomputed distances. This achieves decent speed-ups and can be used in other problem settings. However, the performance is not competitive to hierarchical approaches.

Contraction Hierarchies [@gssv-erlrn-12] are a popular hierarchical speed-up technique. During preprocessing, all nodes are ranked by some measure of importance. Nodes which lie on many shortest paths are important. Then, nodes are contracted iteratively by increasing rank. To contract a node $v$ means removing it form the graph, but preserving shortest distances among all other nodes. This is achieved by inserting shortcut edges between the neighbors of $v$ which have the length of the path over $v$. The query is a bidirectional Dijkstra starting from $s$ and $t$ where only edges to higher ranked nodes are relaxed.

PHAST [@dgnw-phast-13] is an algorithm for one-to-many queries based on Contraction Hierarchies. The preprocessing phase remains the same. The query begins with a forward upward search from $s$. The backward search now needs to determine distances to *all* nodes. To achieve this, PHAST relaxes all edges $(u,v)$ in the backward graph where $rank(u) > rank(v)$ ordered descending by $rank(v)$. Having processed all edges, distances to all nodes are known. PHAST achieves good running times by heavily exploiting memory locality: Nodes and edges are reordered such that relaxing all downward edges is just a linear sweep over the edge array.

Perfect Potentials {#sec:algo}
==================

Our new algorithm is at its core a combination of A\* and PHAST. We take the preprocessing from CHs and PHAST and apply it to a lower bound graph. The query is an A\* variant. It uses exact distances on the lower bound graph as potentials and obtains these through a lazy PHAST-like approach.

The input of the preprocessing phase is a graph and lower-bound weights $w_{\ell}$. Denote by $d_{\ell}(x,y)$ the minimum weight $xy$-path distance with respect to $w_{\ell}$. How exactly this lower bound graph is obtained depends on the problem setting. In the case of routing with life traffic it may be the free flow travel time. In the case of time-dependent routing it may be the lower bound of each travel time function. The preprocessing phase consists of computing a CH of the graph with lower-bound weights.

The input to the query phase is a source $s$ and a target $t$ node and weights $w_u$. These weights $w_u$ must not be smaller than the lower-bound weights $w_{\ell}$, i.e., $w_{\ell}(e) < w_u(e)$ for all edges $e$. The weights may be time-dependent travel time predictions, incorporate live traffic or user specific preferences. Analogous to $d_{\ell}(x,y)$, $d_u(x,y)$ is the minimum-weight phase according to $w_u$. We obtain $d_u(x,y)$ through an A\* search with respect to $d_u$ from $s$ to $t$. The distance $d_{\ell}(x,t)$ from a node $x$ to $t$ is used as potential.

Our core contribution consist in the way $d_{\ell}(x,t)$ is efficiently computed. For this, we use a PHAST variant. Before starting the A\* search, we explore all nodes backward-reachable from $t$ in the CH. We store the computed distances in the array $B$. We then execute the A\* search. Potentials are computed recursively, on-the-fly, with memoization as depicted in Algorithm \[algo:pot\]. If a potential is unknown, it is computed by recursively computing the potentials of all higher nodes in the CH backward search graph. These potentials are then increased by the distance in the CH backwards search graph. The potential of a node $x$ is the minimum over all these values and the distance found in the CH forward search.

Conclusion {#sec:conclusion}
==========

We introduce a novel way to compute potentials for A\*. The potentials are calculated utilizing a CH on a lower bound graph and perfect with regards to that lower bound graph. With these potentials we can speed up A\* search for extended route planning problems like route planning with live traffic, time-dependent travel time predictions or user preferences.
