Learning to Beat Biased Route Demonstrations on Weighted Terrain

Most learned path planners assume that every free cell of a map costs the same to cross, so a route is good simply if it is short and avoids walls. Real ground vehicles cross road, grass, mud and sand at very different costs. The best route on such a map is a sequence of deliberate bends at terrain borders, much as light bends when it enters water. People are poor at finding these routes: in a controlled study, 11 of 12 participants failed to find least-cost paths and reached a median efficiency of only 71%, mostly because they made one turn where two were needed. A policy trained by copying demonstrations, called imitation learning or behavioral cloning, copies this bias exactly. The usual fixes for weak demonstrators were built for robot arms, board games, or traveling-salesman tours, and nobody has tested them where the flaw is geometric and appears in nearly every demonstration.

We propose to learn a cost-to-go field from biased demonstrations whose slope is tied to a learned, spatially varying terrain cost. The field gives a goal-conditioned estimate of the remaining cost from each location, and a physics constraint called the Eikonal equation forces its slope at every point to equal the local cost of crossing. A policy that follows such a field bends at terrain borders by construction, so it can produce the two-turn routes the demonstrators never showed. The bet is that this structure lets an offline learner exceed its demonstrators on weighted maps. We also want to know whether it does better than the obvious alternative of learning a costmap and running a classical planner on it, and we treat that alternative as the main threat.

Core Claim

On weighted terrain, the performance ceiling of imitation has a specific form: demonstrations put almost no probability on the extra turn at a terrain border. Methods that only reweight or rerank demonstrated behavior therefore cannot get past it. The method we propose does three things together. It learns a value function from logged demonstrations using temporal-difference updates, which estimate long-run cost by bootstrapping from the next state's estimate. It learns a per-cell cost head from the step costs logged along those demonstrations. It ties the two with an Eikonal residual whose right-hand side is the learned cost, not the constant 1 used in all prior Eikonal value learners. We claim three outcomes. The method should exceed the demonstrators' path cost. It should recover border bending that is quantitatively consistent with Snell's law. Where the cost predictor must extrapolate, it should match or beat learn-cost-then-plan, because value learning stays anchored to states the data covers while a planner exploits errors in the predicted costmap.

What Exists and What Is Missing

Three bodies of work supply pieces of this.

On the pathfinding side, Optimal Pathfinding on Weighted Grid Maps shows that optimal paths across cost borders refract according to Snell's law. Its JPSW search solves weighted grids exactly when the costs are known. We use JPSW as the optimality oracle and as the planner inside our strongest baseline. How Does It Feel? Self-Supervised Costmap Learning for Off-Road Vehicle Traversability learns continuous costs from vibration measured by an inertial sensor, then hands them to a classical planner. Our cost head follows its recipe, and its learn-then-plan pipeline is the competitor we must beat.

On the value-learning side, Physics-informed Value Learner for Offline Goal-Conditioned Reinforcement Learning and Goal Reaching with Eikonal-Constrained Hierarchical Quasimetric Reinforcement Learning add an Eikonal penalty to offline goal-reaching value learning. This raised Antmaze-Giant success from 7% to 79% and humanoidmaze-giant-stitch from about 3% to about 69%. Both fix the speed at 1 everywhere, so their value functions measure geometric distance. On weighted terrain that is the wrong quantity. These papers supply our core technique and motivate the gap. Generalizable Motion Planning via Operator Learning fits Eikonal value fields by supervised regression onto Fast Marching Method solutions. It also assumes uniform cost, names weighted costs as open, and only mimics an optimal oracle. Our setting removes the oracle.

On the ceiling side, several methods are designed to surpass weak demonstrators. Discriminator-Weighted Offline Imitation Learning from Suboptimal Demonstrations filters out non-expert transitions. Beyond Imitation: Self-Improving Robot Policies via Off-Policy Q-Planning reranks candidate actions sampled from a frozen cloned policy. CADO fine-tunes on true solution cost, after showing that resemblance to expert labels barely predicts cost ($R^2 = 0.076$). Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes shows that value learning stitches together fragments of suboptimal trajectories. All of these were validated on manipulation, Atari, or graphs. Planning Routes Across Economic Terrains constrains our design: it shows the human error is systematic rather than zero-mean noise. That is exactly what filtering methods assume away. MAPF-GPT shows that cloning scales on grid pathfinding, but only with uniform costs and a near-optimal teacher.

Research Program

The learner receives an offline dataset of trajectories. Each trajectory comes with terrain observations $o(s)$ at each location $s$, a goal $g$, and the realized cost logged at each step. On real data this logged cost is vibration bandpower; on synthetic maps it is the true cell cost times the distance travelled. The learner never sees a costmap.

We train a goal-conditioned cost-to-go $V_\theta(s,g)$ and a cost head $c_\phi(o(s))$, which predicts cost per unit length, by minimizing

$$ \mathcal{L}(\theta,\phi) = \mathcal{L}_{\text{TD}}(\theta) + \lambda\, \mathbb{E}_{s,g}\big[(\|\nabla_s V_\theta(s,g)\| - c_\phi(o(s)))^2\big] + \mu\, \mathcal{L}_{\text{cost}}(\phi). $$

Here $\mathcal{L}_{\text{TD}}$ is a goal-conditioned temporal-difference loss on logged step costs. We use expectile-style updates as in the hierarchical value learners cited above, which keep the value anchored to data-supported actions. $\mathcal{L}_{\text{cost}}$ regresses $c_\phi$ onto logged step costs, and $\lambda$ and $\mu$ are weights. The middle term is the Eikonal equation with speed $1/c_\phi$. It replaces the constant 1 in Eik-HIQL, and it is the term that makes border bending possible.

The policy is built from the value field. It samples candidate moves from a cloned policy. It adds candidates obtained by following $-\nabla_s V_\theta$ for a short distance; these are directions the demonstrators never took. It then picks the candidate with the lowest predicted step cost plus remaining cost. The added candidates address the support limitation that the Q-Planning paper itself identifies.

We will analyze three things. The first is whether the learned field reproduces Snell's ratio at borders. The second is how much of the gain comes from stitching fragments versus refracting at borders. The third is where the learned cost head extrapolates badly, and whether the value function or the planner is hurt more there.

Baselines

Plain behavioral cloning. A cloned policy trained with cross-entropy on the same demonstrations, at the same parameter count as our value network. This is the do-nothing reference. Doing better than the demonstrators means beating this.

Learn-cost-then-plan. The same cost head $c_\phi$, trained on the same logged costs, then searched exactly with JPSW. This is the How Does It Feel pipeline with a stronger planner, and we expect it to be the strongest competitor. The only reported number on Lacuna for that pipeline uses a different metric: 57% fewer human interventions than occupancy-based navigation on real trails. We found no reported result on Lacuna for learn-cost-then-plan on weighted-terrain imitation benchmarks.

We will also run a pessimistic variant. It uses an ensemble of five cost heads and plans on the mean plus one standard deviation, with the penalty weight tuned on the same validation maps used to tune $\lambda$. If this pessimistic planner matches our method in path cost, our contribution shrinks to faster inference, and we will report it that way.

Discriminator reweighting (DWBC). Run on our datasets with the authors' training loop. Their reported result on D4RL is beating ORIL, BCND and DemoDICE on 27 of 36 tasks.

Q-Planning-style reranking. A value network trained on the same data, reranking 32 samples from the frozen cloned policy. Its reported gain is 40% to 90% on the real stack-cups task.

Eik-HIQL with uniform speed. The direct ancestor of our method, with $c_\phi \equiv 1$. Its reported result is 79% versus 7% on Antmaze-Giant.

Ablations isolating the key ingredient. Our full method is run three more ways: with $\lambda = 0$, which leaves pure value learning; with the true cost in place of $c_\phi$, which gives an upper bound on what the cost head could achieve; and without the gradient-following candidates. All learned methods get the same data, a 24-hour single-GPU training budget, and 20 hyperparameter trials each.

Beating a baseline means a lower mean ratio of path cost to the JPSW optimum on held-out maps, with non-overlapping 95% bootstrap intervals over 3 seeds.

Why not just…?

Why not just learn the costmap and run JPSW? When the cost head is accurate everywhere, this pipeline is exact, and our method can at best tie it. The two should differ where the cost head is extrapolating, for example on terrain types that look cheap but are absent from the demonstrations. There a planner deliberately routes into the cells it most underestimates, while expectile value learning stays near supported states. We test this directly with held-out "deceptive" terrain types. If the pessimistic ensemble planner closes the gap, we concede the cost advantage. What would remain is that a single forward pass replaces a per-query search, and the speed advantage of learned value fields reported by the operator-learning paper (10× over the Fast Marching Method) would be the relevant figure.

Why not just filter for the good demonstrations? In the human study, 11 of 12 participants failed to find least-cost paths, and 7 of 12 showed the one-turn bias. There is almost no clean positive set from which a discriminator could learn the second turn, so filtering can only choose among one-turn routes. Our datasets contain a controlled fraction of two-turn demonstrations, from 0% to 30%. If DWBC catches up once that fraction is non-trivial, the threat is real but confined to datasets that contain good examples.

Why not just rerank samples from the cloned policy? Reranking cannot choose a turn that the sampler never proposes. We will measure the cloned policy's probability mass on JPSW-optimal border crossings. Our prediction is that reranking gains are capped by that mass, while the gradient-following candidates are not.

Why not just use Eik-HIQL unchanged? With speed fixed at 1, its value function measures geometric distance. It will therefore prefer straight lines through expensive terrain, and the uniform-speed ablation measures exactly this cost.

Proposed Experiments

No weighted-terrain imitation benchmark appears on Lacuna, so we build one from the resources in the file.

The first tier reproduces the human study's field-and-desert layouts at 3× and 5× cost ratios. Demonstrators are synthetic: one-turn planners whose suboptimality is calibrated to the reported 71% median efficiency, mixed with noisy and fragmentary trajectories.

The second tier converts the weighted Stripes, Dragon Age and StarCraft maps used for JPSW, together with MovingAI city maps, into terrain-observation maps paired with logged step costs. Maps are split so that the test maps and some terrain types are unseen during training. JPSW provides exact optimal costs; it runs 4.5× to 8× faster than A* on the game maps.

The third tier is offline only, on TartanDrive and TartanDrive 2.0. Vibration-derived costs stand in for true costs, and we evaluate how well each method ranks held-out driven trajectory segments by realized cost. Since closed-loop rollouts are impossible on logged real driving, this tier tests whether learned costs and values transfer, not navigation itself.

The metrics are the ratio of path cost to the JPSW optimum, the fraction of trajectories that beat their own demonstrator, goal success, and wall-clock time per query.

Three checks would decide the question.

The first is the ceiling check. On tier one with 0% two-turn demonstrations, our method must reach a mean optimality ratio below the demonstrators' ratio. Cloning, DWBC and reranking should not reach it.

The second is the mechanism check. At border crossings, the measured ratio of sines of incoming and outgoing angles should track the cost ratio. With $\lambda = 0$ or with unit speed, it should not.

The third is the threat check. On held-out deceptive terrain, we compare our method against the pessimistic learn-cost-then-plan baseline, with prediction error of the cost head as the x-axis. The outcome decides whether this work contributes better routes, or only faster routes of equal cost.