The setting is shortest-path search between arbitrary start and goal states in a weighted graph. A differential heuristic (DH) precomputes distances from every state to a set of pivot states and uses those distances as a memory-based heuristic during search. The paper assumes that a domain already provides a base heuristic, such as octile distance on grids or air distance on road maps. The supplied excerpt does not establish every theoretical detail or every numerical result from the full paper.
The main contribution is a compression method that stores only a portion of the distances in a regular DH while retaining enough information for effective search. Unlike a regular DH, whose memory budget fixes the number of pivots when all state-to-pivot distances are stored, a CDH can use an arbitrary number of pivots and distribute only selected distances among states. Missing distances are handled using upper and lower bounds on distances from the goal to pivots, together with bidirectional pathmax. The paper also shows that a CDH can be built directly, without first constructing and storing the much larger uncompressed table.
Given an input graph and a memory budget, preprocessing first determines the number of pivots empirically and places them with the Avoid strategy. For every pivot, the method selects a subset of states that will retain a distance to that pivot; each selected state stores the pivot’s position in its local distance array. A breadth-first search from each pivot then computes distances only for the selected states and writes them into those positions. For each search instance, the method computes bounds on distances from the goal to pivots using the Bounding procedure, constructs the CDH heuristic, and runs A* to obtain an optimal path. Because different states can use different pivot subsets, the heuristic can be inconsistent, so the experiments use BPMX(1), which propagates values only between an expanded node and its immediate children.
The evaluation covers three real-world domains: eight-connected Dragon Age: Origins game maps, North American road maps, and a two-dimensional robotic-arm domain. Octile distance is used as the base heuristic for the grid maps, air distance is used for road maps, and the robotic-arm state is defined by the angles between adjacent segments. The comparisons include the base heuristic and a regular DH, and vary memory, the number of pivots, the Bounding parameter, and solution length while measuring search time. The supplied material does not provide the complete instance counts, all averages, repetition conditions, or exact values for every comparison.
CDH’s principal advantage is that a fixed memory budget can represent a richer diversity of pivots by distributing pivot distances across states, rather than applying a small set of pivots uniformly to every state. This makes DH-style information available even when the memory needed for a regular DH, or even the memory needed to store the input graph, is unavailable. The trade-off is that state-dependent pivot subsets can make the heuristic inconsistent, requiring BPMX and additional search-time handling. Performance also depends on pivot placement, distance distribution, the number of pivots, the Bounding setting, graph structure, and cache behavior. The authors identify more sophisticated distance distribution and pivot prioritization as future work.
Memory-based heuristics precompute values during a preprocessing phase and reuse them through lookup tables during search. Pattern databases are a prominent example, but they are commonly associated with implicit exponential domains where useful abstractions are available. Differential heuristics provide a simple and effective table-based heuristic for explicit state spaces by using distances to pivots. Earlier work on compressing pattern databases motivates the broader idea that selectively retained information can preserve useful heuristic strength with less memory.
A regular DH stores the distance from every state to every pivot, requiring information proportional to the number of states times the number of pivots. When memory is severely restricted, especially below the memory needed to represent the domain, a regular DH may be unusable. Merely reducing the number of pivots can reduce the diversity and strength of the heuristic. The problem is therefore to retain useful distance information while allowing the table to fit an arbitrary, possibly very small, memory budget.
For a state a and pivot p, the CDH stores d(a,p) only when that state-pivot pair is selected. Unstored distances are replaced or bounded using information about the goal-to-pivot distances and the values preserved by the compressed table. The resulting heuristic remains admissible according to the supplied evidence, so A* returns an optimal path. The paper also discusses omitting explicit pivot identities from a storage design, which can cut that part of the memory overhead in half and allow distances to more pivots, although the excerpt does not fully specify that variant.
The reported domains include the DAO ost100d map, North American road maps, and robotic arms with three or four segments. The three-arm and four-arm domains are described as having approximately 134 million and 69 billion states, respectively. The experiments study the effect of pivot count on search time, tune the Bounding parameter, compare several memory levels, and examine improvement as the optimal path becomes longer. Room maps and Delaunay graphs were also tested to confirm trends, but their detailed results are not included in the supplied evidence.
The paper’s conclusion reports several-fold time improvements of CDH over a regular DH when the memory budget is moderate, meaning it is not large enough to make the regular DH nearly perfect. When the available memory is smaller than the memory needed to store the input graph, the regular DH is described as inapplicable while CDH still achieves a several-fold improvement over the domain’s base heuristic. On the DAO map and the San Francisco Bay Area road map, the improvement over the base heuristic generally increased with the number of hops in the optimal solution, although deviations were attributed to cache effects. The excerpt does not give the exact improvement factors or their statistical significance.
CDH compresses a differential-heuristic table by retaining only selected state-to-pivot distances while preserving enough information for effective optimal search. It can be tuned to any memory size, including one smaller than the size of the state space, and can be constructed without materializing the complete uncompressed DH. Experiments across three real-world domains report advantages over both the regular DH and the corresponding base heuristics. The authors further suggest that the underlying ideas may apply to other table-based distance heuristics.
The supplied excerpt omits the complete formulas, the detailed definition of the Bounding procedure, the full pivot-placement and distance-distribution algorithms, and the complete experimental tables. Exact performance for each memory budget, map, and instance set therefore cannot be reconstructed from the evidence provided here. Results are likely sensitive to pivot placement, the distribution or hashing method, cache effects, the base heuristic, and graph structure. BPMX(1) addresses inconsistency in the reported experiments, but the excerpt does not establish the cost of alternative propagation depths or the scope of comparisons with other search configurations.
The work provides a way to use precomputed heuristic information in explicit state spaces where conventional differential heuristics do not fit in memory. This is especially relevant to game maps and very large robotic configuration spaces, but the design principle is broader: memory can be spent on pivot diversity and selective coverage rather than on a uniform complete table. For memory-limited optimal search, this exposes a useful trade-off between table size, heuristic strength, and search effort.
The paper is a good fit for readers studying explicit-state A*, differential heuristics, heuristic compression, and memory-bounded shortest-path search. It is also relevant to MAPF and MAPD researchers interested in reusable distance heuristics for large grids, road networks, or robot configuration spaces. Readers who need implementation-level details or exact reproducible measurements should consult the full paper, because the supplied excerpt does not establish all of them.