Bidirectional search finds a shortest path by growing one search forward from the start and another backward from the goal. It can stop only once it has proven that no pair of nodes, one on each frontier, could still be joined by a cheaper path. A heuristic that estimates the distance between any two frontier nodes, called a front-to-front heuristic, makes this proof much tighter. In the 14-Pancake puzzle it cut the required expansions from roughly 23,000 to roughly 2,300. The cost is that every forward node has to be compared against every backward node, so wall-clock time grew from 0.1 seconds to 229 seconds (Comparing Front-to-Front and Front-to-End Heuristics in Bidirectional Search). The tighter bound is free in theory and ruinous in practice.
This note proposes removing the all-pairs comparison. For an important class of heuristics, the bound each forward node needs is a "distance transform": the cheapest backward-frontier cost plus estimated distance, taken over all backward nodes. Such a transform can be computed by a wave that starts at the backward frontier and spreads across the heuristic's own geometry. A spiking neural network computes this wave naturally. If each neuron fires once, at a time equal to its cost, then the first spike to reach a neuron gives the minimum. The network uses energy only where the wave actually travels, and when the frontiers change, only the affected region fires again. The question the proposal answers is how much of the 229-second penalty disappears from the decomposition alone, on any hardware, and how much more event-driven neuromorphic hardware saves in energy for each solved instance.
Core Claim
Write $g_F(u)$ for the cost from the start to forward-frontier node $u$, $g_B(v)$ for the cost from backward-frontier node $v$ to the goal, and $h(u,v)$ for an admissible front-to-front estimate. The per-node front-to-front bound is
$$ L(u) = g_F(u) + \min_{v \in Open_B} \big[\, g_B(v) + h(u,v) \,\big]. $$
The inner minimum, written $D(u)$, does not depend on $g_F$. When $h$ is the shortest-path distance in some sparse "heuristic graph", $D$ is exactly a shortest-path computation from many sources, with each $v$ seeded at cost $g_B(v)$. Octile distance on a grid with obstacles removed is one such case. That computation costs time linear in the size of the heuristic graph, not $|Open_F|\times|Open_B|$.
Differential heuristics are a second case. They take $h(u,v)=\max_p |d_p(u)-d_p(v)|$, where $d_p$ is the precomputed distance to pivot $p$. Swapping the max and the min gives
$$ \tilde D(u)=\max_p \min_v \big[g_B(v)+|d_p(u)-d_p(v)|\big] \le D(u), $$
so $\tilde D$ is still an admissible bound, only weaker. Each inner term is a one-dimensional transform along a single pivot's distance axis. The claim has two parts. First, this decomposition keeps most of the expansion savings of exact front-to-front pruning at front-to-end runtime cost. Second, a time-to-first-spike network, in which each neuron fires once at a time encoding its cost, computes $D$ or $\tilde D$ with energy proportional to the number of cells the wave changes. That makes it a natural incremental co-processor for this one search step.
Relation to Prior Work
The search theory motivates and constrains the design. Must-expand pairs (Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search) define what any optimal bidirectional search must resolve. Shaham et al. cast these pairs as a minimum vertex cover of a bipartite "must-expand graph" (The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search). NBS (Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions) expands both nodes of the pair with the smallest bound, which keeps it within twice the cover size. DVCBS (Enriching Non-Parametric Bidirectional Search Algorithms) tracks the cover dynamically and expands fewer nodes. Our module plugs into either algorithm unchanged: it only supplies tighter per-node bounds. Their termination rules and NBS's factor-of-two guarantee still hold, because every bound we produce stays admissible.
Siag et al. (Comparing Front-to-Front and Front-to-End Heuristics in Bidirectional Search) supply the problem and the tighter bound $lb^{FC2}$. They evaluate pairs explicitly. We replace that pairwise evaluation with a transform. We give up some tightness when we swap max and min for differential heuristics, and we restrict ourselves to heuristics that come from a graph.
The neuromorphic papers supply the hardware motivation and its cautions. SF-HMVC (Slack-Free Spiking Neural Network Formulation for Hypergraph Minimum Vertex Cover) solves vertex cover on Loihi 2 with one feedback neuron per edge and reports large energy savings over Gurobi. It works on fixed graphs, gives no guarantee of optimality, and is limited by the cost of reading results off the chip. Our module avoids all three problems. Its output is exact up to a quantisation step that rounds downward. It is updated as the frontiers move. It needs only one readout neuron to signal termination. Dietrich et al. (Threshold Adaptation in Spiking Networks Enables Shortest Path Finding and Place Disambiguation) find shortest paths with spike-timing races and global inhibition, on 10-node graphs, with no stopping condition. We borrow their first-spike-wins idea but use it to compute a bound, not to search. The stopping rule comes from must-expand-pair theory. Finally, the claim that dynamic energy scales with spike count (Tavanaei et al., Wu et al.) is the premise our energy accounting tests, not something we assume.
Research Program
The first component is algorithmic and hardware-agnostic. For grid pathfinding with octile distance, $D$ is a shortest-path computation from many sources on the obstacle-free 8-connected lattice. The obstacles must stay out of this lattice. Including them would turn the "heuristic" into the true distance and the module into a second search, which would blur the comparison. For road maps we use differential heuristics with $k$ pivots, giving $k$ sorted one-dimensional min-plus sweeps.
We implement incremental updates. When a backward node is expanded, its seed is removed and its children are added. Only the cells whose $D$ value changes are recomputed, using a decrease-key and increase-repair scheme in the style of dynamic shortest-path algorithms. Pruning uses $L(u)$ together with the existing front-to-end bounds, inside both NBS and DVCBS.
The second component is the spiking realisation. Each lattice cell, or each pivot-axis bin for differential heuristics, is a non-leaky integrate-and-fire neuron that fires once. Each heuristic edge is a synaptic delay equal to its quantised cost. Backward-frontier neurons are injected at time $g_B(v)$, so the first spike time at $u$ equals $D(u)$. We quantise costs by scaling and rounding delays down, for example the $\sqrt2$ diagonal, which keeps the bound admissible. We sweep the scale to measure how much tightness quantisation costs.
Termination runs on chip. Each forward neuron $u$ is gated by a deadline $C - g_F(u)$, where $C$ is the current best solution cost. One readout neuron fires if any gated neuron fires before its deadline. If the readout is silent through time $C$, the search may stop, matching the front-to-front stopping condition. This addresses both the missing stopping condition noted by Dietrich et al. and the readout overhead noted by Nguyen et al. Map capacity is a real constraint, since a single chip limits neuron count according to Nguyen et al. We therefore tile maps and report which instances fit. For instances that do not fit, we use a spike-accurate simulator with a spike-count energy model, and we calibrate that model against on-chip measurements on the instances that do fit.
Baselines
The naive reference point is front-to-end search with no pairwise reasoning: BAE* and NBS on CPU. These are the algorithms Siag et al. found to be within 5% to 10% of the theoretical cover size on road maps and Towers of Hanoi (Front-to-End Bidirectional Heuristic Search with Consistent Heuristics: Enumerating and Evaluating Algorithms and Bounds). They set the runtime floor, and on road maps they leave little room for any front-to-front method. They run with the same heuristics, the same instances, and single-threaded C++.
The strongest existing front-to-front method is the explicit pairwise $lb^{FC2}$ search of Siag et al. Its reported cost is 229 seconds of wall-clock time against 0.1 seconds for front-to-end on 14-Pancake (Comparing Front-to-Front and Front-to-End Heuristics in Bidirectional Search). For the 156 Dragon Age: Origins maps, no per-map node count or runtime was found on Lacuna, so we rerun that method ourselves. Our method beats it if it reaches at least 80% of its expansion reduction at no more than twice front-to-end wall-clock time.
The decisive competitor is the same transform computed incrementally on a CPU. This baseline isolates whether the spiking hardware adds anything beyond the algorithmic decomposition. A brute-force pairwise GPU implementation on an embedded GPU is a second hardware baseline, since GPUs are the obvious way to parallelise the quadratic scan. All hardware variants get the same instances and the same pruning logic, with tuning limited to the quantisation scale and tile size. Each is scored on energy per solved instance, measured with package energy counters on CPU and GPU and with on-chip power readings on the neuromorphic chip. The spiking module counts as beating the CPU transform only if its whole-system energy per instance is lower, including host communication, and not just its module energy.
Two ablations isolate the key ingredients. The first compares exact pairwise differential-heuristic bounds with the swapped $\tilde D$, which measures the tightness lost by exchanging max and min. The second compares incremental waves with from-scratch waves at every step, which measures how much event-driven locality actually contributes.
Why not just…?
Why not just offload DVCBS's vertex cover to a neuromorphic solver like SF-HMVC? This is the obvious combination, and we rejected it. The must-expand graph is bipartite, so its minimum vertex cover can be found exactly in polynomial time through maximum matching. Shaham et al. further show that grouping nodes by $g$-value reduces it to a weighted cover solvable in time linear in the number of distinct costs. A stochastic solver with no guarantee, built for NP-hard hypergraph cover, would replace an exact cheap computation with an approximate one. The DVCBS overhead is better addressed with incremental matching on CPU.
Why not just compute the transform on a CPU? This is the real threat. If incremental CPU transforms close most of the 229-second gap, the main contribution is algorithmic, and the hardware claim narrows to energy alone. Our baseline design measures exactly this. We will report the neuromorphic result as positive only if whole-system energy wins after communication is counted.
Why not just brute-force the pairs on a GPU? Parallelism reduces latency, but the work stays $|Open_F|\times|Open_B|$ per step. The energy evidence (75 times less energy per inference for Loihi than for a Jetson TX2 in Reinforcement co-Learning of Deep and Spiking Neural Networks for Energy-Efficient Mapless Navigation with Neuromorphic Hardware) comes from a different task, so we measure this comparison directly rather than cite it.
Why not just stay front-to-end? On road maps this may well be the right answer, since BAE* is already within 5% to 10% of the minimum. The value of front-to-front bounds lies where front-to-end leaves a large gap, which we expect on maze-like maps. There, Shaham et al. report a bimodal distribution of optimal meeting fractions, peaking near 0.2 and 0.8. We report results per domain rather than averaged.
Decisive Experiments
We run on the 156 Dragon Age: Origins maps with octile distance and on the road-map benchmark with differential heuristics. For each instance we measure expansions, the fraction of the theoretical minimum-cover size (computed offline), wall-clock time, and energy per solved instance. We also confirm on every instance that the returned path cost equals the optimum.
Three outcomes decide the proposal. First, the decomposition must retain most of the front-to-front expansion savings at near front-to-end runtime. If it does not, the bound is too loose and the idea fails. Second, measured spike counts per search step must track the number of changed cells, and must not scale with the pair count. Third, the spiking module must beat the incremental CPU transform in end-to-end energy on the instances that fit on chip, with the on-chip readout eliminating per-step polling. If the third check fails while the first two pass, the paper becomes a purely algorithmic result, and we will say so.
References
- Comparing Front-to-Front and Front-to-End Heuristics in Bidirectional Search
- Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search
- The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search
- Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
- Enriching Non-Parametric Bidirectional Search Algorithms
- Slack-Free Spiking Neural Network Formulation for Hypergraph Minimum Vertex Cover
- Threshold Adaptation in Spiking Networks Enables Shortest Path Finding and Place Disambiguation
- Deep learning in spiking neural networks
- Deep Spiking Neural Networks for Large Vocabulary Automatic Speech Recognition
- Front-to-End Bidirectional Heuristic Search with Consistent Heuristics: Enumerating and Evaluating Algorithms and Bounds
- Reinforcement co-Learning of Deep and Spiking Neural Networks for Energy-Efficient Mapless Navigation with Neuromorphic Hardware