Hindsight Map Relabeling for Learned Local Navigation Planners

Robots that navigate with a learned local controller keep hitting the same problem. The controller is trained on expert demonstrations, drifts into situations the expert never visited, and has no idea how to recover. The fix that works best today, NavOL, has a perfect simulator map answer "what should you have done here?" at every state the robot visits. That map does not exist on a real robot. The main alternative, reinforcement learning, avoids the oracle but throws away its experience after each update, so it needs enormous numbers of simulated rollouts. We propose a third route. After every episode, the robot rebuilds the map from its own sensor logs and runs an ordinary global path planner on that map in hindsight. The planner then labels each visited state, including the drifted ones, with the recovery trajectory it would have taken. These labels depend only on the state and the map, not on which version of the policy produced the rollout, so every episode ever collected, in simulation or on hardware, stays useful as training data.

The same mechanism turns an old design tension into a single tunable quantity. The tension is between global foresight, which avoids dead ends, and local reactivity, which is fast but myopic. We can control how much of the hindsight map the labeling planner is allowed to see: only what the robot had observed by time $t$, or also what it observed up to $k$ seconds later. Small $k$ gives labels that are myopic but reachable from what the robot could perceive. Large $k$ gives labels with more foresight, but they encode information the robot never saw, which is a well-known way for imitation to fail. We expect an intermediate $k$ to work best, and measuring that curve is the scientific core of the proposal.

Core Claim

A non-privileged, retrospective global planner is a sufficient recovery expert for correcting the drift that builds up when a path-conditioned local planner imitates demonstrations. Here "path-conditioned" means a learned controller that receives a few waypoints of a coarse global route as input. Because the labels come from the robot's own reconstructed map, training is fully off-policy without importance weights: data from any past policy is reused by aggregation rather than reweighting. We claim this matches most of the gain of privileged online imitation, and exceeds on-policy and off-policy reinforcement learning at equal environment steps. We further claim that the lookahead $k$ given to the relabeling planner has an interior optimum that depends on how much of the environment is hidden from the robot's sensors.

Formally, let $\mathcal{D}$ be every logged tuple $(o_t, W_t)$, where $o_t$ is the robot's depth observation and $W_t$ is the global waypoint sequence its onboard planner supplied at time $t$. Let $M_{t+k}$ be the occupancy map reconstructed from sensor data up to time $t+k$. Let $a^*_k(s_t)$ be the local trajectory chunk, parameterized as a B-spline (a smooth curve defined by a few control points), extracted from a global plan on $M_{t+k}$ starting at the robot's logged pose. Training minimizes

$$ L(\theta) = \mathbb{E}_{(o_t, W_t) \sim \mathcal{D}}\big[\, c_t \,\ell\big(\pi_\theta(o_t, W_t),\, a^*_k(s_t)\big)\big], $$

where $\ell$ is the local planner's imitation loss and $c_t \in [0,1]$ is a confidence weight. The weight $c_t$ is set by the fraction of the labeled chunk that crosses map cells actually observed rather than assumed free. Because $\mathcal{D}$ grows by aggregation, this is DAgger (dataset aggregation, Ross et al.) with a reconstructed rather than a human or privileged expert.

Relation to Prior Work

The closest work is NavOL. It trains a diffusion-transformer local planner with an online DAgger loop in IsaacLab, querying a planner on the ground-truth navigation mesh at drifted states. It reaches 69.0% mean success rate on its out-of-domain benchmark against 37.7% for NavDP, using 16 GPU-days. NavOL motivates us, since it shows recovery labels are what matter. It also constrains us, since its oracle is exactly what we remove. Our labels come from the robot's own partial, noisy map, after the fact, and can therefore be computed on real-robot logs.

Two lines of work avoid oracles by other means. Action chunking and data augmentation proves that executing short open-loop action sequences and injecting noise while demonstrations are collected can match DAgger. That result assumes smooth dynamics and smooth experts, which obstacle boundaries break. IGS-BC/CMILe makes imitation cost independent of horizon under a stability condition, but it needs known dynamics. We borrow the chunking insight in the form of B-spline outputs, following SanD-Planner, which reached 90.1% cluttered and 72.0% indoor success on InternNav from 500 demonstrations. SanD-Planner's geometric critic cannot learn from the robot's own mistakes; hindsight relabeling supplies that missing loop.

The learned hybrid planners Path-conditioned RL and G2RL give us the conditioning interface: attention over 15 waypoints, and rewarding goal progress rather than rigid tracking. Both train with on-policy reinforcement learning across hundreds of parallel environments. Deep local trajectory replanning uses the same three-tier stack but trains only by offline behavioral cloning, and drops from 98% success in a known foyer to 84% in an unseen one. That drop is the drift we target.

On the sample-efficiency side, RT-PG and Off-Policy PPO reuse old trajectories by correcting importance weights, and have been shown only on MuJoCo. Off-Policy PPO reached Walker2d target return in about 220k steps against 750k for PPO. We see them as the strongest competitors rather than components. Our bet is that when a cheap geometric expert exists, reweighting is unnecessary, because supervised labels are indifferent to the policy that generated the data.

Research Program

The system has three parts. The local planner is a path-conditioned depth policy that outputs an eight-control-point clamped cubic B-spline. It uses the waypoint attention encoder of Path-conditioned RL and the output head of SanD-Planner, and receives waypoints from an onboard A* planner running on the robot's live map. The relabeler replays each finished episode, rebuilds occupancy maps $M_{t+k}$ from logged depth and odometry, and plans from every logged pose, with a stride. It fits the first segment of each plan to B-spline control points and computes the confidence weight $c_t$. The training loop alternates rollouts with supervised updates on the ever-growing aggregate buffer. It starts from a small demonstration set of about 500 episodes, to match SanD-Planner's data scale.

Three questions structure the analysis. The first is how much of the privileged-oracle gain survives when the oracle is replaced by the robot's own hindsight map. We measure this as the success gap to NavOL at matched rollouts. The second is how the optimal $k$ shifts with how much of the environment is occluded; we vary sensor range and field of view. The argument for an interior optimum is that labels at $k=0$ cannot anticipate dead ends, while labels at large $k$ ask the policy to react to walls it has not seen. The third is whether the confidence weight is needed. If it is, planner mistakes on unobserved space poisoning the labels is a real failure mode. If it is not, the method is simpler than we assumed.

Baselines

The naive reference point is offline behavioral cloning of the same architecture on the 500 seed demonstrations, with no further data. This shows how much drift exists to be corrected. The classical reference is A* global planning with a DWA local planner (dynamic window approach, which scores candidate velocity commands by clearance and progress) on the same onboard map. For this baseline we tune the DWA cost weights with the same trial budget the learned methods receive. It matters because on BARN (Benchmark Autonomous Robot Navigation) a classical hierarchical planner completed 8/9 physical trials in 2022 while a PPO agent completed 2/9 (BARN 2022).

The strongest existing method with privileged access is NavOL itself, run on the same scenes with the same simulated sensor, the same architecture and the same rollout count. It reports 69.0% mean success rate on the NavOL benchmark. We treat it as an upper bound rather than a competitor. Success means recovering at least most of the gap between behavioral cloning and NavOL without the ground-truth navigation mesh.

The strongest non-privileged competitors are Path-conditioned RL trained with PPO, and the same policy trained with Off-Policy PPO and with RT-PG. All three get identical environment steps, identical GPU budget capped at NavOL's 16 GPU-days, and an equal hyperparameter-search budget, and they start from the same behavioral-cloning initialization so the comparison is not about pretraining. Path-conditioned RL reports a 7.02% gain in success weighted by path length (SPL) over a single-waypoint planner with optimal paths, and 0.83 success with degraded paths, on its Isaac Lab mazes. Beating these baselines means higher success and SPL at every step budget up to the cap, not only at the end.

Two ablations isolate the key ingredient. The first relabels with the live map only ($k=0$). The second skips relabeling and adds only the robot's own successful rollouts to the buffer, which is self-imitation. If the second matches the full method, the planner's recovery labels are not what helps.

Why not just…?

Why not just use NavOL's privileged oracle and transfer zero-shot, as NavOL already does? In simulation this will probably beat us, and we report it as a ceiling. The question is what happens when training must continue on hardware or in scenes with no ground-truth mesh, where NavOL has no expert at all. Our physical-log experiment tests exactly that regime, where the oracle cannot run.

Why not just behavioral cloning with noise injection and action chunking? The theory in action chunking and data augmentation requires Lipschitz dynamics and experts. Noise injected near centimeter clearances produces collisions rather than recovery demonstrations. BARN 2024 reports that behavioral cloning without a geometric safety layer failed in tight squeezes (BARN 2024). We run this baseline with the noise scale tuned per benchmark, so if it matches us the verdict is empirical.

Why not just reuse trajectories with RT-PG or Off-Policy PPO on a path-conditioned policy? This is the real threat, since both methods remove the waste of discarding data. Our argument is that importance weights over long visual navigation rollouts are exactly where RT-PG's divergence assumptions are weakest, whereas relabeling needs no weights. The equal-step learning curves settle this. We also run a hybrid that adds our relabeled loss to Off-Policy PPO, in case the two are complementary.

Why not just a well-tuned classical A*+DWA stack? It needs no data. However, it was outperformed by learned or hybrid systems in both BARN physical finals, and G2RL reports classical replanning at about 1.58 times optimal path cost against 1.12 for its learned planner. We still include it, tuned fairly.

Proposed Experiments

The main simulation study uses the NavOL benchmark: training on 50 3D-Front scenes and evaluating on 8 unseen layouts in IsaacLab. The ground-truth mesh is used only by the NavOL baseline and for scoring. Metrics are mean success rate, SPL and collision rate, plotted against environment steps. The long-range test uses the Isaac Lab maze benchmark of Path-conditioned RL (training on 30 m mazes, evaluating on 50 m mazes) with both optimal and degraded global paths. This probes whether hindsight labels teach escape from dead ends. The tight-clearance test uses the 300 BARN simulation worlds with the challenge score; the top 2022 simulation score was 0.2415, from DRL-VO. The $k$ sweep, from 0 to full episode, runs on all three benchmarks at three sensor ranges.

The decisive checks are these. First, if full-hindsight relabeling is best at every sensor range, information asymmetry does not matter, and the $k$ contribution collapses to plain hindsight relabeling. Second, if $k=0$ is best, hindsight adds nothing over a live-map expert. Third, if self-imitation matches the full method, the planner labels are unnecessary. Finally, we take a policy trained in simulation and continue training it on a legged or wheeled robot using only relabeled physical logs from a few hours of operation. We compare held-out real success against the frozen simulation policy. No oracle-based method can run this experiment at all.