Many recent robots that follow spoken instructions without a prebuilt map use two layers. A large vision-language model looks at camera images a few times per second and issues short commands like "turn right 30 degrees, move forward 75 cm." A small, fast controller, trained in simulation with randomized physics so it transfers to hardware unchanged, turns those commands into motor actions. The fast controller executes each command as if it were exact. In practice the commands are late, because the big model is slow. They are biased, because a single camera cannot reliably judge metric distance. And they go stale as the robot moves or the scene changes. Small errors pile up, and the systems are known to fail when an early command is wrong and nothing downstream notices.
We propose to treat each high-level command as a forecast instead of an order. The forecast is delayed and noisy, and it can be checked against the robot's own odometry and corrected online. A thin middle layer would sit between the slow planner and the frozen low-level policy. It re-anchors every command to the moment the planner's image was taken. It learns, during a single episode, the planner's systematic distance and heading bias from the planner's own self-inconsistency. It then tracks the corrected commands with a short-horizon predictive controller. To evaluate the layer we borrow dynamic regret from online control, meaning the extra cumulative cost compared with a clairvoyant controller that knew the whole future. This turns "the hierarchy drifts" into a quantity we can measure, decompose, and predict.
Core Claim
Dynamic-regret theory for predictive control says what should hurt a slow-planner/fast-controller system and by how much. MPC (model predictive control, which re-optimizes a short future trajectory at every step) has dynamic regret that splits into two parts: a horizon-truncation term that shrinks exponentially with the lookahead length, and a prediction-error term in which errors farther into the future are discounted exponentially (On the Regret Analysis of Online LQR Control with Predictions). Separately, when a controller tracks a moving reference, its regret grows linearly with the reference's total path length (Karapetyan et al.). When the underlying system keeps changing, regret is bounded below by the total variation of those changes (Minasyan et al.).
Our working hypothesis puts these forms together for the planner-controller interface:
$$ \mathrm{Regret}_T \;\lesssim\; C_1 \sum_{t=1}^{T} \lVert g_{t+1}-g_t\rVert \;+\; C_2 \sum_{t=1}^{T}\sum_{k=d}^{W} \rho^{k}\,\lVert \hat g_{t+k\mid t}-g^{\star}_{t+k}\rVert \;+\; C_3\,\rho^{W-d}T. $$
The symbols are as follows. $g_t$ is the reference waypoint the fast layer is tracking at step $t$, expressed in a fixed odometry frame. $\hat g_{t+k\mid t}$ is the planner-derived forecast of the waypoint $k$ steps ahead. $g^{\star}$ is the waypoint a clairvoyant planner would have chosen. $d$ is the planner latency in control steps, $W$ is the controller's lookahead, $\rho<1$ is the contraction rate of the closed-loop tracker, and the $C_i$ are constants that depend on the tracker.
Each term implies something about design. The first term is the path length of the reference. It blows up if commands are re-expressed in the robot's moving body frame, or if the planner flips intent often. The second term grows linearly in $T$ whenever the planner has a persistent bias, such as a monocular scale error. Removing that bias online makes the term sublinear. The third term is the price of latency: it eats directly into the useful lookahead.
The claim we will test is this. If the hierarchy is built so that all three terms are controlled, through frame anchoring, online bias correction, and latency-aware lookahead, then cumulative suboptimality grows sublinearly in episode length on long mapless navigation tasks. A standard open-loop hierarchy grows linearly. The difference should appear as higher success, and specifically as recovery from early errors, under shifts that the simulation randomization never covered.
What Exists and What Does Not
The closest systems fall into two camps that do not touch each other.
On the hierarchy side, NaVILA pairs a vision-language-action model that emits mid-level language commands with an RL locomotion policy trained in Isaac Sim. It transfers zero-shot to real quadrupeds and humanoids without a map, but its authors note it cannot recover once an early wrong turn is made. PixNav has an LLM/VLM planner pick a single target pixel and a Transformer skill drive toward it, assuming that pixel stays valid. HiRT and FARE formalize slow-reasoning/fast-acting splits. These papers motivate our work: all of them pass the planner output to the fast layer open-loop. None of them estimates or corrects the planner's error at runtime, and none measures how that error accumulates.
On the theory side, ProDR.control reaches optimal dynamic regret for non-stationary LQR (the linear-quadratic regulator, the textbook linear control problem). Lin et al. bound regret for constrained nonlinear MPC in terms of per-step prediction error. Both assume clean states and well-defined quadratic costs, with no perception in the loop. These papers supply our method: the regret decomposition and the exp-concave online-regression tools.
The single closest paper is Adaptive Legged Locomotion via Online Learning for MPC. It learns residual body dynamics online at 200 Hz with random Fourier features and online gradient descent, feeds them into a 0.6 s MPC, and proves sublinear dynamic regret. It reports a 67% tracking improvement over nominal MPC on slopes under an 8g lateral force. Our proposal differs in where the online learner sits and what it learns. Zhou et al. correct the robot's physics given a known geometric command. We keep the physics layer as a frozen domain-randomized policy and correct the planner's forecast of where to go, which is the error source that mapless monocular hierarchies actually suffer from. Their system also has no vision, no semantic planner, and no sim-to-real randomization.
Two papers constrain our design. Minasyan et al. show that when the target itself changes a lot, no controller can achieve sublinear regret. A planner that changes its mind every query is therefore a hard floor, and the system has to limit intent switching rather than hope tracking hides it. Sim-to-Real: Learning Agile Locomotion finds that compact, low-dimensional inputs transfer best. That argues for leaving the randomized low-level policy untouched and putting all adaptation in a small, analyzable layer.
Research Program
We will build a middle layer of four parts and keep both the planner and the low-level policy frozen.
The first part is frame anchoring. Every planner output, whether a NaVILA-style metric command or a PixNav-style pixel turned into a bearing ray, is timestamped with the capture time of its input image. It is then converted into a waypoint in the odometry frame, using the pose the robot had at that moment rather than the pose it has when the answer arrives. This removes the latency-induced error from the first and second terms of the bound. It also stops waypoints from shifting every time the robot moves.
The second part is online forecast correction. The planner repeatedly reports distances and bearings to the same intended target. Between two reports, legged or wheel odometry measures how far the robot actually moved toward that target, so differences between successive reports can be regressed against odometry displacement. This yields an online least-squares problem for a small set of parameters: a scale factor, a heading offset, and optionally a few features of image content such as estimated corridor width. Squared loss is exp-concave, so we can use the strongly adaptive online regression methods underlying ProDR.control. Their low regret on every time interval matters here, because the bias changes when the robot enters a new room or the camera height changes.
The third part is a latency-aware tracker. A planar MPC runs at 50 Hz and outputs body-velocity commands to the frozen locomotion policy. Its effective lookahead is set to the planner latency plus a margin, and forecast steps are weighted by a trust factor that decays with forecast age. This follows the exponential discounting in Zhang et al..
The fourth part is an intent-commitment rule. A new high-level intent replaces the current one only when it disagrees beyond a threshold for two consecutive queries. This directly bounds reference path length, at the cost of some staleness, and we will sweep the threshold to map out that tradeoff.
The analysis has a deliberately narrow scope. We will identify the closed-loop behavior of the domain-randomized locomotion policy as a stable linear tracker of body-velocity commands, and estimate $\rho$ from step responses in simulation. For that model we will prove the displayed bound under the stated assumptions. We will not claim guarantees for the neural planner. The planner enters the analysis only as a forecast sequence whose errors we measure. Recursive feasibility under obstacles, which Lin et al. leave open, stays open here as well. We handle obstacles with a soft-constraint MPC and report constraint violations.
Baselines
The naive reference point is the hierarchy as published: planner commands go straight to the domain-randomized locomotion policy, executed in the robot's current body frame, with no latency compensation and no correction. It uses the same planner weights, the same low-level policy, and the same scenes as every other condition. Beating it is the minimum bar. On its own it would show only that open-loop execution is wasteful.
The strongest existing method on our main benchmark is NaVILA, run as the authors describe it on VLN-CE-Isaac. The file reports its gains only in relative or real-world terms: a 17% success-rate improvement over prior methods on the VLN-CE benchmarks and an 88% real-world success rate on complex instructions. No reported result was found on Lacuna for NaVILA's absolute success rate on VLN-CE-Isaac, so we will reproduce it under our compute and seeds and compare against our reproduced number. Our layer is added to NaVILA itself, which makes the comparison planner-matched and policy-matched. Beating NaVILA means a statistically significant success-rate gain on the shifted test conditions described below, with no loss on the unshifted standard split.
For object navigation, the strongest comparison is PixNav on HM3D. It reports a 37.9% success rate under ObjectNav Challenge 2022 rules on 20 unseen validation scenes, against 25.5% for the RGB-only ZSON and 39.2% for the map-based ESC. Here our layer converts PixNav's pixel goals into anchored bearing waypoints, and the forecast corrector estimates range along the ray. The bar is to close the gap to map-based ESC without adding a map.
The strongest competitor for the online-learning part is a residual-dynamics adapter in the style of Zhou et al., placed under the planner. It learns online how commanded velocity maps to realized velocity, but it does not correct the planner. It gets the same 200 Hz update budget and the same random-feature dimension as our corrector. This baseline separates "correct the body" from "correct the forecast." We expect it to win under payload and friction shifts and to lose under camera-scale shifts. Combining the two should beat both.
Three ablations isolate our ingredients. One removes frame anchoring. One removes forecast correction, keeping anchoring and the tracker. One removes the commitment rule. Each ablation predicts which term of the bound should grow, and therefore which failure mode should reappear.
Why not just…?
Why not just domain-randomize the interface, training the low-level policy with random command delays, noise, and scale errors? This is the most serious alternative, and we will run it. We retrain the locomotion policy in Isaac Sim with command latency, Gaussian command noise, and per-episode scale bias drawn from the same ranges our shifts use, with the same training budget as the original policy. Randomization makes a policy robust on average over biases it cannot see, and the evidence from Tan et al. is that broader randomization buys robustness at the cost of conservative, slower behavior. A policy acting on a single command cannot tell a 75 cm command that is truly 75 cm from one that is really 50 cm, because nothing in its input identifies the bias. Our corrector identifies the bias from planner self-inconsistency over time. If interface randomization matches our success rate and regret under persistent bias, our central claim is wrong and we will say so. We expect it to cut variance without removing the linear regret growth.
Why not just query the planner more often? Faster replanning shrinks latency $d$, but it does not remove systematic bias, and it increases intent switching, which inflates the first term of the bound. Quantization helps only modestly: NaVILA reports 40% faster inference from W4A16 quantization, nowhere near closing the gap to control rates. We will sweep planner query rate from the native rate up to the fastest the simulator allows, with and without our layer. If high query rates alone flatten regret growth, the correction component is unnecessary.
Why not just build a local metric map with onboard SLAM and run classical MPC? That gives up the mapless constraint, and the evidence available here does not favor it in crowds. Arena-Bench reports that classical planners including MPC struggled in 10-pedestrian scenes, and Zeus shows a mapless stack running at 26 Hz on a CPU alone. We do use odometry, a few seconds of local pose history, which goes stale far more slowly than a map. We will include a depth-plus-local-occupancy MPC baseline on Arena-Bench to make this comparison explicit rather than assumed.
Why not just fine-tune the planner on more data so it stops being biased? Fine-tuning can reduce average bias, but the shifts we target occur at deployment: a different camera height on a humanoid, a new room's scale, a payload that lowers the body. These are exactly the cases where NaVILA's cross-embodiment transfer has no reported number. Our tests use biases absent from any training data, which a fixed fine-tuned model cannot anticipate.
Proposed Experiments
The main testbed is VLN-CE-Isaac with NaVILA's planner and locomotion policy, plus HM3D ObjectNav with PixNav. Each benchmark is run in its standard form and in a shifted form. The shifts are camera-height changes that bias monocular distance by ±20–40%, mid-episode payload and friction changes, an embodiment swap from quadruped to humanoid that keeps the quadruped-trained planner, and Pedsim crowds imported from Arena-Bench. We report success rate, success weighted by path length, collisions, and the rate of recovery after the first planner error that misses its target by more than one meter.
Dynamic regret is computed against a privileged hindsight oracle. The oracle is a planner given the full scene mesh and the goal, tracked by the same MPC, and is used only for evaluation. Its cost combines path length, time, and obstacle-margin violations. We also log the three terms of the bound separately: reference path length, discounted forecast error, and latency-truncated lookahead.
Three checks decide the outcome. First, extend episode length by chaining instructions and fit the log-log slope of cumulative regret against duration. The prediction is a slope near one for the open-loop hierarchy and clearly below one with our layer, only under the bias shifts. Second, under injected scale bias, our layer must beat both the interface-randomized policy and the residual-dynamics adapter, and its advantage must disappear when the bias is set to zero. That pattern shows the gain comes from correcting the forecast and not from extra control effort. Third, the ablations must each bring back the predicted failure. Removing anchoring should inflate reference path length, removing correction should restore linear regret under bias, and removing commitment should increase intent switches and degrade performance in the crowd scenes. As a final, smaller check, we will deploy the layer zero-shot on a real quadruped running NaVILA's released policy where available. Only the online parameters adapt, and we compare early-error recovery on a fixed set of instruction routes, with and without the layer.
References
- On the Regret Analysis of Online LQR Control with Predictions
- Online Linear Quadratic Tracking With Regret Guarantees
- Online Control of Unknown Time-Varying Dynamical Systems
- NaVILA: Legged Robot Vision-Language-Action Model for Navigation
- Bridging Zero-shot Object Navigation and Foundation Models through Pixel-Guided Navigation Skill
- HiRT: Enhancing Robotic Control with Hierarchical Robot Transformers
- FARE: Fast-Slow Agentic Robotic Exploration
- Optimal Dynamic Regret in LQR Control
- Bounded-Regret MPC via Perturbation Analysis: Prediction Error, Constraints, and Nonlinearity
- Adaptive Legged Locomotion via Online Learning for Model Predictive Control
- Sim-to-Real: Learning Agile Locomotion For Quadruped Robots
- Habitat-Matterport 3D Dataset (HM3D): 1000 Large-scale 3D Environments for Embodied AI
- Arena-Bench: A Benchmarking Suite for Obstacle Avoidance Approaches in Highly Dynamic Environments
- Building a Winning Self-Driving Car in Six Months