Dual-Speed Learned Heuristics for Search in Changing Environments

A learned heuristic is a neural network that tells a search algorithm such as A how far each state is from the goal. When it is good, the search goes almost straight to the goal. When it is wrong, the search wanders through a huge number of dead-end states. Learned heuristics beat hand-written ones by large margins on hard maps, but they are trained once, on one kind of environment. A robot or planner that meets a stream of different environments (concave traps, then forests, then mazes, then traps again) has to keep retraining the network, and ordinary retraining makes the network forget what it knew before. We propose to keep two copies of the learned heuristic, following the brain-inspired "complementary learning systems" idea. One copy adapts quickly to the current environment. The other is a slowly averaged copy that holds what was learned across all past environments. Both are run as separate guides inside multi-heuristic A, a search algorithm that alternates between several heuristics while one simple, provably safe heuristic keeps the solution-quality guarantee.

The reason to care is that forgetting costs far more in search than in classification. A few points of lost accuracy on a classifier is mild. A few points of lost ranking quality in a heuristic can push a search back toward brute force. Limited Discrepancy Search degrades to plain depth-first search once its guiding heuristic loses discriminative power (Limited Discrepancy Search), and Monte Carlo tree search gives only marginal gains in Chinese Chess without a strong evaluator (Tree Search Algorithms For Chinese Chess). The proposal therefore has two parts. The first measures how forgetting in a learned heuristic turns into extra node expansions. The second tests whether a fast/slow pair, run under a safe anchor, recovers most of the search efficiency that sequential training loses.

Core Claim

We make two claims. First, when a learned heuristic is trained on environments one after another, the extra nodes expanded on earlier environments grow much faster than its regression loss or local ranking error on those environments. Loss curves therefore understate forgetting, and the proposal needs its own search-based forgetting metric.

Second, a pair of heuristics recovers most of this lost efficiency: a fast "working" network plus a slow exponential-moving-average (EMA) copy of its weights, in the style of CLS-ER. The pair runs as two inadmissible queues in multi-heuristic A*. An inadmissible heuristic is one that may overestimate the distance to goal. Under the same compute and memory budget, the pair should beat a single network trained with experience replay, and it should do so without giving up the bounded-suboptimality guarantee supplied by a classical admissible anchor (a heuristic that never overestimates).

An obvious version of this idea is to make the slow network the admissible anchor. The candidate gaps in our source material suggest exactly that. We reject it deliberately: an averaged neural network is not admissible, so that design would silently void the guarantee. In our design the guarantee comes only from the classical anchor. The learning systems affect only how fast the search finds a solution.

Relation to Prior Work

Three papers supply the search side. SAIL (Learning Heuristic Search via Imitation) trains one neural heuristic by imitating a planner that can see the whole map. It cuts node expansions by orders of magnitude relative to Euclidean distance and relative to multi-heuristic A over Bug Trap, Forest and Maze maps. SAIL trains and tests within a single distribution; we reuse its features, its oracle and its maps but present the map families as a sequence. A-MHA (A-MHA: Anytime Multi-Heuristic A) combines one consistent anchor with several hand-built inadmissible heuristics. That construction supplies our guarantee. Its heuristics are fixed formulas, whereas ours are learned and change over time. The difference method (Dynamic Improvements of Heuristic Evaluations during Search) corrects a heuristic within one search using errors observed on the frontier. It is a within-instance memory that is discarded at the end of each search. We treat it as a complementary baseline, not a competitor, because our memory persists across instances.

Three papers supply the memory side. CLS-ER (Learning Fast, Learning Slow) keeps a working model, fast and slow EMA copies, and a replay buffer. It picks replay targets from whichever copy is more confident, and it more than doubles DER++ on Split-Tiny-ImageNet with a 200-sample buffer (23.47% vs 10.96%). We port its fast/slow averaging and target selection from classification to heuristic regression. Continual-MAML (Online Fast Adaptation and Knowledge Accumulation) detects task shifts from spikes in loss. We borrow the idea of using a surprise signal, but compute it from disagreement between the fast and slow heuristics. Adaptive Online Planning (Adaptive Online Planning for Continual Lifelong Learning) plans longer when a value ensemble is uncertain, in continuous control. It motivates using disagreement to allocate search effort, and we move that idea into discrete A*.

One paper constrains the design. Forgetting and Imbalance in Robot Lifelong Learning with Off-policy Data shows that keeping all past data still fails, because value estimates on unvisited actions are extrapolated badly. Our targets come from oracle distances on stored states, not from bootstrapped values, which avoids that failure. We still test whether the slow copy stays calibrated on regions of old maps that were never replayed.

The closest existing combination of the two directions is Trajectory-Aware Heuristic Learning for Combinatorial Search. It uses an EMA teacher to stabilize label smoothing for a Rubik's Cube heuristic. That teacher only generates training targets on one fixed puzzle. It is not a persistent memory across changing domains, and it does not guide search.

Research Program

The environment stream is built from SAIL's 200×200 eight-connected grids. It cycles through the Bug Trap, Forest and Maze families twice, so we can measure both forgetting and recovery on revisits. A harder stream adds the Warehouse, Rooms and Game maps from the safe-interval path planning suite (Revisiting Bounded-Suboptimal Safe Interval Path Planning) and the Mazes, Random, Warehouse and Cities maps from POGEMA, used here only as single-agent maps.

The first study is diagnostic. We train one SAIL network sequentially and log three quantities on held-out maps of every past family after each stage: regression error, local neighbor-ranking accuracy (the search-free proxy used with CubeLocalRank), and median and 95th-percentile node expansions under greedy best-first search and weighted A*. The goal is an empirical curve linking ranking error to the growth in expansions. That curve decides whether proxy metrics are adequate for continual heuristic learning.

The second study is the method. The working network is trained with SAIL's mixed rollouts on the current family plus a reservoir replay buffer of states and their oracle cost-to-go. Two EMA copies are maintained, with decay rates $\alpha_f > \alpha_s$ (the fast copy moves quickly toward the working weights, the slow copy slowly). As in CLS-ER, the replay targets for the working network are taken from whichever copy has lower error on each buffered state.

At search time, multi-heuristic A runs three queues. The anchor is octile distance, a classical admissible heuristic, inflated by a weight $w_1$. The second queue is ordered by the fast copy and the third by the slow copy. Each inadmissible queue may expand a node only if its key is within $w_2$ times the anchor's minimum key. This keeps solution cost within $w_1 w_2$ of optimal, inherited from the MHA family. Instead of plain round-robin, the share of expansions given to the fast queue grows with the normalized disagreement $d = |h_f - h_s| / (h_s + 1)$ on the states just expanded. The reasoning is that high disagreement signals a new environment, where the fast copy is more likely to be right. Every result reports inference cost, and wall-clock time counts network evaluations, because node savings that do not pay for inference are not savings.

Baselines

The naive reference points are octile distance alone under weighted A and under MHA. These are the levels learning must beat, and they require no memory at all. Next is the difference method's Add variant (Dynamic Improvements of Heuristic Evaluations during Search) applied on top of octile distance. It tests whether within-instance correction alone closes the gap on these maps. It reports 70.7% of baseline A* nodes on 2000×2000 mazes, which is a modest reduction compared with learned heuristics.

The main competitor is a single SAIL network trained sequentially with the same reservoir replay buffer and the same total gradient steps, placed inside the same anchored MHA as one inadmissible queue. It is the strongest competitor because the anchor already guarantees correctness, so the only remaining question is whether the second learned memory buys speed. For fairness it gets two queues of the same network under different weights, so it matches our queue count, and it gets a tuning budget for learning rate and buffer mixing equal to what our method spends on its two decay rates. Neither SAIL nor any other paper in our source material reports continual-learning results for learned heuristics. We found no reported result on Lacuna for sequentially trained learned heuristics on SAIL's map families. The nearest published anchors are SAIL's own "orders of magnitude" fewer expansions within a single distribution, and A-MHA's final suboptimality of 3.3 on the 63-tile puzzle versus 25 for ARA*. Neither is directly comparable to our setting.

Two further baselines bracket the problem. The upper bound is joint retraining on all maps seen so far. A per-family model library selected by an oracle family label shows what perfect task identification would give. Two ablations isolate our ingredients. The first uses the slow copy only, which tests whether a slow average of weights is enough on its own. The second replaces the disagreement-based allocation with round-robin. Beating the single-network competitor means lower 95th-percentile expansions and wall-clock time on revisited families, averaged over seeds with confidence intervals that exclude zero, and no loss on the family currently being trained.

Why not just…?

Why not just rely on the anchor, since MHA* already survives a bad heuristic? This is the most serious threat. The anchor bounds solution cost, but a forgotten learned queue still spends a share of expansions on misleading nodes, and the anchor alone behaves like octile distance on bug traps. The single-network-with-replay baseline inside the same anchored search tests this directly. If the gap between it and our method is within noise, we will report that the anchor plus replay is sufficient, and the paper becomes a measurement study of heuristic forgetting.

Why not just keep one network per environment? A library works when environments are discrete, labeled and few. It fails under gradual drift and grows memory linearly with the number of environments. The oracle-labeled library baseline shows its best case. The unlabeled SIPP/POGEMA stream, where families blend, shows whether that best case can actually be reached.

Why not just retrain jointly on everything? It is the right upper bound, but its compute grows with the length of the stream. Evidence from classification that small buffers break single-model replay (DER++ at 10.96% vs CLS-ER at 23.47%) suggests the gap matters when memory is tight. We sweep buffer size to find where the dual copies stop helping.

Decisive Checks

The first check comes from the diagnostic study. If extra expansions track ranking error roughly linearly, the premise that search amplifies forgetting is wrong for these maps, and the method's motivation shrinks accordingly.

The second check is whether the dual-speed method beats the single-network replay baseline on revisited families at equal compute, measured in wall-clock time rather than node counts. We will also verify that every returned path stays within $w_1 w_2$ of optimal cost.

The third check is whether disagreement-based allocation beats round-robin right after a family switch. That result shows whether the fast/slow disagreement actually carries information about environment change, or only adds complexity.