Path Planning with CPD Heuristics

1 Introduction

There has been massive progress in quickly computing shortest paths for graphs with static edge-costs. Modern algorithms such as Contraction Hierarchies [Geisberger et al., 2008], Hub Labels [Abraham et al., 2012] and Compressed Path Databases [Botea, 2011; Botea and Harabor, 2013] use a combination of auxiliary data structures and fast query solving to improve the performance of reference algorithms such as Dijkstra search by several orders of magnitude. When edge costs are dynamic however fast path planning algorithms no longer guarantee optimality, and may fail altogether, due to invalid auxiliary data. When this happens the auxiliary data must be repaired or recomputed entirely from scratch. Problems with dynamic edge-costs are therefore more challenging than the static-cost case, and they appear in a number of important settings; e.g.:

• Routing in road networks, where travel times are adjusted due to congestion, construction and road closures [Delling and Wagner, 2007];
• Personalised routing, where edges have agent-dependent costs [Delling et al., 2011; Dibbelt et al., 2014; Funke and Storandt, 2015].
• Computer video games, where player interaction creates changes to the environment [Kring et al., 2010].

In this work we consider how to solve dynamic-cost path planning problems using Compressed Path Databases (CPDs): a preprocessing-intensive technique that finds static shortest paths without any state-space search. In dynamiccost settings CPD auxiliary data is invalidated and computed paths are no longer optimal. However, CPDs can still be used as heuristic functions to drive A* search and here they have several unique advantages. For example, each time a node is expanded we always have available a concrete and usually feasible plan to reach the target (i.e. the CPD path). Moreover, the static and dynamic costs of each CPD path provide strong upper and lower bounds that help A* to find the true optimal path sooner. Finally, when the upper and lower bounds coincide, A* can be immediately terminated, often well before it is necessary to expand the target.

We explore two possible applications of CPD heuristics. The first is optimal grid search, where we report convincing gains of up to several factors vs Landmarks [Goldberg and Harrelson, 2005], a popular but conventional preprocessingbased heuristic. We also consider CPD heuristics in Anytime A* and Anytime Weighted A* [Hansen and Zhou, 2007], a popular algorithm for settings where deliberation time is limited. Here we demonstrate even larger benefits.

2 Problem Setting

We study path planning problems in weighted graphs with dynamically changing edge costs. For input we require a graph G = (N, E) with nodes N and edges E ⊆ N × N. Associated with the graph is a non-negative function w : N ×N → R+, where w(m, n) is the weight of edge (m, n) ∈ E.

Each instance of the path planning problem is defined by a start node s and a target node t. Our task is to find a path in G from s to t where a path P is defined as a sequence of edges P = [(s = n1, n2), (n2, n3), . . . , (nk-1, nk = t)]. The cost of the path P given w, denoted c(P, w), is exactly:

We say that P is optimal if c(P,w) ≤ c(P ′ ,w) among all paths P ′ from s to t. We use [] to denote the empty sequence and ++ to denote sequence concatenation.

Context. In this work we focus on the path planning problem. That means we assume the start and target locations are fixed for the duration of each path planning episode (i.e. while solving a single instance) and we assume that any two subsequent path planning episodes are unrelated. We refer to the period of time, from the beginning of the first path planning episode to the end of the last episode, as the online phase. Consistent with typical road routing and computer game settings, we also assume that the graph is known a priori and that that it can be preprocessed during an offline phase. That means any offline investments in time, such as might be required to construct auxiliary data, do not need to be amortised online (i.e., the two phases are entirely divorced). From time to time during the online phase we allow edge costs to change as a result of some unknown exogenous event. We refer to such changes as perturbations and we assume they occur only between distinct path planning episodes. 1 The cost increases are always positive with respect to the original edge value, as observed at the time the graph is loaded. A related but different problem to ours, also involving dynamically changing edge costs, appears in the context of incremental search. Here planning, execution and sensing are interleaved and the map can change while an agent executes a path. Such settings are beyond our scope and we refer the interested reader to [Koenig et al., 2004] for an overview.

3 RelatedWork

Perhaps most similar to our work is ALT [Goldberg and Harrelson, 2005], a popular search technique that uses precomputed landmark heuristics to guide search in static and dynamic-cost graphs. ALT stores a precomputed set of distance labels: for every node in the graph to and from a selected set of landmark nodes. These distances are exploited to derive admissible lower-bounds on the true distance between any pair of graph nodes. For example, let L be the set of landmark nodes and a and b any pair of nodes in the graph. Then, h(a, b) = argmax{ |d(a, l) - d(b, l)| } s.t. l ∈ L.

Several variations of this idea appear in the literature with a summary and unifying treatment given in [Sturtevant et al., 2009]. One attractive property of landmarks is that the estimates are robust [Delling and Wagner, 2007] and remain admissible as long as edge-costs never drop below their initial (i.e. unperturbed) values. More landmarks produce more accurate estimates but since each landmark requires 2×|N| distance labels the memory overhead grows quickly prohibitive. A related issue is the growing online cost to evaluate many landmarks and to find their maximum. For these reasons the number of landmarks is usually limited to a small set.

A variety of other methods exists in the literature, originally developed for static routing in road networks, but which can be adapted to the dynamic case. Contraction Hierarchies (CH) [Geisberger et al., 2008] is a fast, optimal and broadly representative example; another is Dynamic Highway Node Routing [Schultes and Sanders, 2007]. In the event of edgecost changes CH auxiliary data can be repaired [Geisberger et al., 2012] but the cost of this operation can dominate running time, unless updates are small or infrequent.

1 Equivalently, we consider only periodic (cf. real-time) updates.

Another way to improve on reference algorithms in dynamic road networks is to compute a metric independent auxiliary data structure and then customise this data with a user-specified metric function. Two examples of this idea are CCH [Dibbelt et al., 2014] and CRP [Delling et al., 2011]. The main drawback is the customisation overhead. Even a highly engineered implementation running on 12 parallel cores [Delling et al., 2017] requires ≈ 1 second per customisation plus the cost of computing a shortest distance and extracting a corresponding shortest path; i.e. depending on the problem, and the frequency of customisation calls, it could well be faster to simply run the reference algorithm. Two recent and related methods, PCH and PRP [Funke and Storandt, 2015], can significantly improve customisation performance but they require that metrics be available in advance.

4 Compressed Path Databases

We now review some key aspects of CPDs. Our descriptions are based on SRC [Strasser et al., 2015], a leading variant in this algorithmic family. In simple words, a CPD is a data structure that stores optimal moves: from any node s on a graph towards any other node t. More formally, a "move" from s towards t is the first edge of a path from s to t. An optimal move is the first move of an optimal path. 2

Building a CPD. It is an offline procedure that requires a number of iterations, one for each node in the graph. Each iteration is a complete Dijkstra search from a given source node s. With only slight modification, the Dijkstra algorithm produces a so-called first-move table T(s). In a first-move table (see Figure 1 for an example) all graph nodes t are assigned a label that identifies which of the edges leaving s appear on a shortest path towards t. The first-move table is then compressed, which concludes the iteration at hand. Being independent each Dijkstra search can be run in parallel, with a speed-up linear in the number of available processors.

Compression. It reduces the size of a first-move table using run-length encoding. For example, suppose the nodes in Figure 1 are ordered from left to right and from the top to the bottom. A string of symbols such as W; W; W; (W, E) can then be more compactly represented as 1W (i.e., a solid block of Ws starting at position 1). Observe how we are free to choose any symbol from a non-singleton list such as (W,E). Furthermore, obstacle nodes and the origin node s can be treated as wildcards, i.e. compatible with any run [Salvetti et al., 2017]. The effectiveness of RLE compression depends strongly on the the way nodes are ordered (i.e. we want to choose a good ordering that produces few runs across all source nodes). The problem is intractable in general but good heuristics exist. We use the DFS ordering from [Strasser et al., 2015].

2 We use the terms "move" and "edge" interchangeably.

Path Extraction. It is an online procedure which depends on CPDs to find optimal shortest paths. We denote as CPD(s,t) a function which returns the first move from s on an optimal shortest path to t. This function requires only a simple binary search through the compressed string of symbols for s. Once the first move is known we apply it directly and call the function again, recursively and until the target is reached.

5 Searching with CPDHeuristics

The principal idea we explore in this paper is the use of CPD as a lower bound heuristic for path planning. Under the perturbation scenario we consider, the cost of the shortest path recorded in the CPD using original weights w is a lower bound on the actual shortest path in the graph using new weights w′ . Clearly since w′ (s, t) ≥ w(s, t) for all (s, t) ∈ E we have that c(P, w′ ) ≥ c(P, w) for all paths P in G. Hence the CPD defines an admissible heuristic for A* search.

Furthermore, since the path P recorded in the CPD can be quickly recovered, we can calculate its cost c(P,w′ ) using the new weights w′ . This allows us to track an incumbent solution which is the shortest such path we have found. Given that we have an upper bound on the solution, and the f costs of nodes represent a lower bound of the solution we can then adjust the A* algorithm to return a bounded suboptimal path whose cost is not more than ϵ times the shortest path, where ϵ ≥ 1. This may allow us to explore much less of the graph than if we demand to find an optimal path.

Algorithm 1 is a modification of A* as follows. For simplicity, we store with each node n in the open list a (current) shortest path p[n] from s to n; in practice this is stored by back pointers. We keep track of a shortest incumbent path I and its cost u (an upper bound on the cost of the shortest possible path). The incumbent I is stored as a node mwhich encodes the concatenation of the current path from s to m with the CPD path from m to t.

When we select a node n from the open set (line 6), if it is the target we have found an optimal path and we return it (line 7). If ϵ times the f value is not less than u, then the incumbent path I is no worse than factor ϵ from optimal, and we return the incumbent (line 8) (function SP-CPD(I, t) returns the path recorded by the CPD from I to t). Note that the algorithm will always terminate early if it expands a node n, where wCPD(n,t) indicates that h = h′ . In this case, when n was added to open it also became the incumbent I and set u = f [n] = g[n] + h, and hence the test on line 8 succeeds.

Otherwise we investigate the neighbours m of n where the path from s to m via n is shorter than any previously found path. We call wCPD(m,t) which returns the cost h = c(P, w) according to w of the path P recorded in the CPD from m to t, as well as the cost h′ = c(P, w′ ) according to w′ . We update the f cost of m using the original cost h of this path (line 16).

Algorithm 1: CPD-Search(w,w′ , s, t, ϵ): Variant of Weighted A* with a CPD heuristic. Parameters s and t indicate the start and target, w′ encodes actual edge-costs while w encodes weights used by the CPD. This algorithm guarantees solutions are ϵ-optimal.

1 closed ← ∅; open← {s} 2 for n ∈ N do g[n] ←∞; 3 g[s] ← 0; f[s] ← 0; p[s] ← [] 4 u ←∞; I ← s 5 while open ̸= ∅ do 6 n← argmin{f[n′ ] | n′ ∈ open} 7 if n = t then return p[n] ; 8 if ϵf [n] ≥ u then return p[I] ++SP-CPD(I, t) ; 9 open ← open - {n} 10 closed ← closed ∪ {n} 11 for (n, m) ∈ E, m ̸∈ closed do 12 if g[n] +w′ (n,m) < g[m] then 13 p[m] ← p[n] ++ [(n, m)] 14 g[m] ← g[n] + w′ (n, m) 15 〈h, h′ 〉 ← wCPD(m, t) 16 f [m] ← g[m] + h 17 if u > g[m] +h′ then 18 u ← g[m] + h′ ; I ← m 19 open ← open ∪ {m} 20 return ⊥ ▶ No solution

Algorithm 2: wCPD(s,t): Retrieving the original (using w) and new (using w′ ) cost of the shortest path (according to w) for an (s, t) pair.

• 1 if s = t then return (0,0);

2 if co[s] <∞ then return 〈co[s], cn[s]〉; 3 (s,m) ←CPD(s, t) 4 〈h, h′ 〉 ←wCPD(m, t) 5 co[s] ← h+w(s,m) 6 cn[s] ← h′ +w′ (s,m) 7 return 〈co[s], cn[s]〉

We also check if the cost to m followed by P, using the current weights w′ is shorter than any previous path (line 17). If so we update the upper bound u and the incumbent I.

Algorithm 2 simply returns the cost of the CPD path from s to t both using the original weights w and the new weights w′ . The path can always be reconstructed using the CPD itself. The pseudo-code use co[s] and cn[s] to cache the cost of the shortest path from s to t using original weights w, and the cost of the same path, not necessarily shortest for these weights, using weights w′ . We assume the cache is initialised to ∞ for each new CPD-Search call.

Note that because of caching of calls to wCPD, the CPD is only called for any node m for current target t at most once. Hence the CPD heuristic is amortised O(1) cost to compute.

Proposition 1. Let P be the path returned by CPD-Search(s, t,w,w′ , ϵ) then c(P,w′ ) ≤ ϵc(S,w′ ) for all paths S in G from s to t.

Proof. Since the CPD heuristic is admissible, we know that f[n] is no greater than the cost of the shortest path from s to t via n. When the node n in open with minimum f [n] is such that ϵf[n] ≥ u, where u is the cost of the incumbent, then we have that no path from s to t via n can cost less than u.

6 Anytime Search

When deliberation time is limited, an optimal algorithm such as A* may not find a path in time, even with the help of sophisticated heuristics. Bounded suboptimal or bounded cost algorithms are better suited for such settings but still depend on the user to fix an acceptable quality threshold a priori. On the one hand, if the user bound is too loose the quality of the first solution may not be very good. On the other hand, if the user bound is too tight, the algorithmmay not finish in time.

Anytime algorithms are a class of related methods which seek to find a first solution quickly and then continue searching, improving the incumbent until time runs out. Current state-of-the-art methods of this type include Anytime Weighted A* (AWA*) [Hansen and Zhou, 2007] and Anytime Repairing A* [Likhachev et al., 2008]; both of them can be seen as variants of bounded-suboptimal search: i.e. they seek in the available time a suboptimal solution with the tightest possible suboptimality bound. A different and also stateof-the-art method is Anytime Non-parametric A*, sometimes called Anytime Potential Search [Stern et al., 2014]. This method can be seen as a variant of bounded-cost search: i.e it seeks in the available time a suboptimal solution with cost less than the smallest possible cost limit C.

We can modify Algorithm 1 to be anytime by simply outputting a new incumbent when discovered (line 18). We can similarly extend an anytime search such as AWA* by simply using the CPD heuristic and making use of any incumbents it finds, we call this Anytime Weighted CPD-Search. The CPD heuristic offers considerable advantages for anytime search. We discuss several of them that hold for both bounded-cost and bounded-suboptimal settings.

Fast feasible plans. When available time is small, any solution at all can be acceptable. In this case anytime search can stop at the first expanded node where the CPD path is feasible. Often this node is the start node.

Strong lower-bounds. Bounded search algorithms typically proceed in best-first fashion and are guided by specialised heuristics that need to accurately estimate the costto-go. As a general rule, stronger lower-bounds lead to more efficient search. Because CPD heuristics are derived from concrete paths, the cost estimates account for topological features of the map such as obstacles.

Strong upper-bounds. In bounded search each new incumbent solution improves the upper-bound u and provides an opportunity to prune the search: any node n with f(n) ≥ u need never be expanded or generated since it cannot possibly yield a better path. CPD heuristics provide upper and lower bounds at each node, which means we can update u sooner.

Early termination. Also valuable for anytime algorithms.

7 Experiments

We evaluate CPD-Search in two online settings: optimal search and anytime search. In both experiments we use grid benchmarks drawn from Sturtevant's well known repository at http://movingai.com. Each benchmark comprises a set of grid maps and each map is associated with a set of instances (start-target pairs). They are as follows:

DAO: Drawn from the game DRAGON AGE: ORIGINS, this benchmark is representative of uniform-cost game maps.

WC3: Drawn from the game WARCRAFT III, this is benchmark is representative of weighted-cost game maps. Each map features several types of terrains to which we assign costs as follows: Ground 1.0, Trees 1.5, Shallow water 2.0, Water 2.5. When traversing from one tile to another we weight the base move cost (1 or √2 respectively) by the average terrain cost of the origin and destination tile.

MAZES: This classic benchmark consists of automatically generated labyrinths of size 512 × 512. Each map is uniform cost and features corridors of fixed width k ∈ {1, 2, 4, 8, 16, 32}. Mazes are especially challenging for search algorithms using distance-based heuristics.

ROOMS: This synthetic benchmark features uniform-cost maps with square rooms of size k × k, k ∈ {8, 16, 32, 64} and which are randomly connected by entrances of width 1. Room maps are designed to force the expansion of seemingly promising nodes that cannot appear on any optimal path.

In our online experiments we allow grid map traversal costs to change between different instances. We model these changes using one of two perturbation policies. They are:

AREA: This policy is meant to simulate a traffic problem, where some node is the location of the "problem" and edges around it are penalised with decreasing multiple less as their hop distance grows from the "problem". For each query of a path from a node s to a target node t that we perform in the experiment, a node n on the CPD path P from s to t is randomly chosen. We increase the weight of all edges in the graph within radius r of node n by an amount that decays as the distance from n increases. We use a radius r = 15 and a weight multiplication of w′ (e) = w(e) × (3e- x2 45 + 1) where x is the number of hops from node n to edge e. This Gaussian-like distribution is illustrated in Figure 2.

RANDOM: This policy involves a randomly selected subset of edges E′ ⊆ E s.t. |E′ |/|E| = 0.1 whose weights we multiply by a factor of 3.

We undertake empirical comparisons between CPDSearch and ALT [Goldberg and Harrelson, 2005], a pathfinding algorithm that combines of A* search with the preprocessing-based heuristic known as Landmarks. We implement ALT with different numbers of landmark nodes, up to diminishing returns: 6, 12 and 18. Our test machine is a i78700 machine with 16GB memory. All codes are in C++ and available from https://bitbucket.org/koldar/astar-early-stop/.

7.1 Experiment 1: (Offline) Preprocessing

In Table 1 we give the time and space overheads needed to compute and store auxiliary data for CPD and Landmark heuristics (the latter with 12 nodes; results for 6 and 18 nodes are similar). Clearly CPD costs are substantially larger than landmarks but certainly not prohibitive. We make two observations: (i) we can easily store CPDs in main memory which is important for efficient online performance (we discuss performance in the next sections); (ii) since we assume the map is known a priori, the preprocessing overhead does not need to be amortised online. We compute auxiliary data once and we re-use it to speed up all subsequent queries.

7.2 Experiment 2: (Online) Optimal Grid Search

In this experiment we apply to each instance from every benchmark the AREA perturbation policy. Once the graph is perturbed, we solve the modified instance to optimality with both CPD-Search and ALT. The graph is then reset.

We begin with Figure 3 which makes a detailed CPU-time comparison on three selected maps from games and mazes. Each curve is a cactus-plot that represents one algorithm with times being independently sorted from smallest to largest; i.e. we show the entire distribution of results and the xaxis represents specific instance-quantiles. Notice from the figure that when landmarks provide accurate distance estimates, such as on the map hrt201n, the advantage of CPDSearch is small. The Landmark heuristic is known to be a one-dimensional estimator [Rayner et al., 2011]: i.e. each landmark can be thought of as the origin of a one-dimensional Euclidean space in which all other nodes are placed according to their recorded distance from the origin. The maps dustwallowkeys and maze512-1-4 are more complicated environments where one-dimensional embeddings are insufficient to provide accurate estimates between any pair of states. In these cases we see a strong advantage for CPDSearch. Table 2 gives a more comprehensive report with summary statistics for CPU time and node expansions across all benchmarks. We observe that CPD-Search strongly outperforms ALT and often by several factors.

7.3 Experiment 3: (Online) Anytime Search

In time-constrained applications (e.g., computer video games) even fast algorithms may still require too much time to compute an optimal path. This motivates us to consider CPD-Search as an anytime algorithm. We compare its performance against Anytime Weighted A* with Landmark heuristics and we develop a related variant, Anytime Weighted CPD-Search. Both weighted algorithms use the suboptimality bound ϵ = 2, as in [Hansen and Zhou, 2007]. We test performance on the map hrt201n with RANDOM perturbations. As we saw in the previous section, on this map CPD heuristics have only a small benefit over Landmarks. This concentrates the comparison on the anytime advantages of CPD-Search, rather than on the advantages that come from the CPD heuristic being more accurate.

In Figure 4 (left) we report normalised solution costs at various time cutoffs. We observe strong improvements for CPD-Search. For example, at 0.03ms AWA* with Landmarks has almost no incumbent solutions while both CPD methods have incumbents for at least 25% of instances. By 0.3ms AWA* with Landmarks has incumbents for <50% of instances while CPD methods have incumbents for >75%. More interesting is the comparison between anytime CPDSearch and its use in AWA*. Clearly Anytime Weighted CPD-Search is slightly better at generating good solutions early. However by 1ms CPD-Search has a better median value and is only slightly worse for max and mean. By 4ms CPD-Search has proven optimality for all instances and is finished. Neither AWA* variant reaches this point, even by 10ms. These results clearly shows that CPD-Search is a competitive anytime algorithm, even without modification.

In Figure 4 (right) we report performance for optimal CPD-Search and optimal A* with Landmarks [12]. Notice that median values are only 1ms and 1.5ms respectively; i.e., the only anytime behaviour that is interesting is before that. The plot also reinforces the benefit of CPD-Search over Landmarks, this time with RANDOM cost perturbations.

8 Conclusions

Compressed Path Databases (CPDs) are a family of ultra-fast pathfinding algorithms which eliminate the need for runtime search in static-cost maps. In this work we propose CPDs as heuristic functions for dynamic settings where costs can only increase. We describe a new algorithm, CPD-Search, which is the combination CPD heuristics with A*. In a first experiment we use standard grid benchmarks to show that CPD-Search strongly outperforms ALT [Goldberg and Harrelson, 2005], a well known and state-of-the-art method. In a second experiment we consider CPD-Search as an anytime algorithm. Here we find that it generates good solutions earlier and optimal solutions faster than even dedicated methods such as Anytime Weighted A* [Hansen and Zhou, 2007].

Our results are based on SRC [Strasser et al., 2015], a leading CPD solver from the 2014 Grid-based Path Planning Competition. Since 2014 several works extend SRC by improving its compression strength [Salvetti et al., 2017], its running time [Salvetti et al., 2018] or both [Chiari et al., 2019]. These techniques can be easily combined with CPDSearch to further improve current results.