A robot that plans by optimizing a short trajectory and then asks a learned value network "how good is the state where this trajectory ends?" gets a useful guarantee. The longer the planned trajectory, the less the value network's mistakes matter. Planning longer, however, takes longer to compute. While the robot computes, the world keeps moving. In a static room this delay is mostly harmless, because the robot can predict where it will itself be when the plan starts. In a crowd, the pedestrians also move during the computation, and their motion cannot be predicted exactly. A plan that was safe for the world as it looked when computation began can be unsafe by the time it is executed. The planning horizon therefore trades two errors against each other. Error from the learned value shrinks as the horizon grows. Error from acting on a stale picture of moving obstacles grows with the horizon, through compute time.
This note proposes to make that trade-off explicit, measure it, and exploit it. We will derive and empirically validate a loss bound that combines the value-error damping term from Plan Online, Learn Offline with a latency-drift term driven by obstacle forecast error. We will use the bound to pick the horizon at every control step from the measured solver time and the local crowd unpredictability. We will also fix a second, recursive failure mode that latency creates. When the planner's multi-step returns are used as training targets for the value network, targets computed from stale states teach the network values for states the robot never actually acted from. That corruption then feeds back into the next round of planning.
Core Claim
In value-terminated model predictive control (MPC, repeatedly solving a short trajectory optimization and executing its first action), the best horizon in dynamic environments is not "as long as compute allows." It is an interior optimum $H^*$ that shifts within an episode as crowd density and obstacle predictability change. Choosing $H$ per step according to the bound below should beat both a fixed hand-tuned horizon and latency compensation by forward prediction alone. The gain should be concentrated in dense, unpredictable crowds, and in static scenes the method should reduce to "use the longest affordable horizon."
The working form of the bound, which the project will derive rigorously, is
$$\mathrm{Loss}(H) \;\lesssim\; \frac{2\gamma^H \epsilon_V}{1-\gamma^H} \;+\; \frac{L\,\delta\big(\tau(H)\big)}{1-\gamma}.$$
Here $\gamma$ is the discount factor and $\epsilon_V$ is the value network's approximation error. The first term is POLO's result that terminal value error is suppressed geometrically in $H$. $L$ is a Lipschitz constant of the planner's action-value in the obstacle states. $\tau(H)$ is the measured solver latency at horizon $H$, roughly affine in $H$ for sampling planners, since rollout cost is linear in length. $\delta(\tau)$ is the forecast error of obstacle positions after $\tau$ seconds, which grows with $\tau$ at a rate set by how erratic nearby agents are. The ego-state part of the drift is removed by standard forward prediction, so only the obstacle part remains in $\delta$. Because $\delta$ is estimated online from a pedestrian predictor's residuals, and $\epsilon_V$ from ensemble disagreement as in POLO, the minimizer can be recomputed every step at negligible cost.
Relation to Prior Work
Two lines of work motivate this. Plan Online, Learn Offline proves the $\gamma^H$ damping of terminal value error and shows the horizon can be shortened as the value matures. It assumes a known, stationary simulator and zero compute delay, and we keep its damping term while adding the delay term. Deep Value Model Predictive Control embeds a critic in the running cost of nonlinear MPC and finds that longer horizons (2.2 s vs 1.5 s) make it robust to imperfect critics. Its walls are static, and its authors flag the computational burden and dynamic maps as open. Our prediction is that its "longer is better" finding reverses past some horizon once obstacles move and latency is charged.
Latency itself has been studied without planning. Handling Delay in Real-Time Reinforcement Learning pipelines network layers and adds history-augmented states and skip connections to act on stale observations. Its delay is a fixed constant, and it has no trajectory optimizer or moving obstacles. We borrow its history augmentation for the value network's input but treat latency as a quantity we control through $H$ and as a random variable with jitter.
Three works supply methods or constrain the design. Bootstrapped Model Predictive Control shows that value targets computed through learned models compound error, forcing a one-step target horizon. That constrains us to compute value targets from logged real transitions rather than model rollouts. Error Propagation for Approximate Policy and Value Iteration shows that errors in later iterations dominate and that loss scales with state-distribution mismatch. It motivates our delay-consistent targets, because stale-state targets are exactly a train/deploy distribution mismatch. Model-Based Offline Planning shows that test-time planning adapts zero-shot to new constraints where distilled policies cannot, and it reports planning at 40–100 Hz against over 360 Hz for a direct policy. Those numbers ground our latency model.
On the dynamic-environment side, three works handle crowds with fast optimization but no learned value bootstrapping. Collision-Free Robot Navigation in Crowded Environments using Learning based Convex MPC uses a policy to pick reference points inside a convex free region tracked by a quadratic program. Safe Hierarchical Navigation in Crowded Dynamic Uncertain Environments uses gap analysis, convex trajectory optimization, and a 0.68 ms safety filter, and reports multi-agent traps. Planning, Fast and Slow switches between fast and slow planners with reachability bounds but explicitly assumes static obstacles. The last is the closest in spirit, since it also chooses planning effort online. It switches between discrete planners based on tracking error in static maps, whereas we choose a continuous horizon based on value error and obstacle forecast drift in moving crowds.
Research Program
The system is a sampling-based MPC planner (MPPI, which scores thousands of noisy action sequences and averages them) with an ensemble value network as terminal cost. The obstacle forecast is a constant-velocity or learned pedestrian predictor whose residuals are tracked online. The planner runs on a fixed CPU budget, so latency is real and measured, not simulated as a constant. The first strand builds the loss bound properly. That means stating conditions on the obstacle forecast error and deriving $H^*$ as a function of $\epsilon_V$, $\gamma$, the latency slope, and the forecast growth rate, then checking the predicted $H^*$ against empirical sweeps.
The second strand is the online horizon selector. At each step, it takes the upper quantile of recent measured solver times to handle jitter, the current ensemble disagreement, and a local forecast-error estimate, and then selects $H$ by minimizing the bound. The third strand is delay-consistent value learning. The multi-step targets that POLO-style training uses are anchored to the state that actually held when the action was applied, $s_{t+\tau}$ as logged, rather than the state the planner saw, $s_t$. We will measure value error on held-out real transitions to show whether stale targets inflate $\epsilon_V$ over training iterations, and hence whether the recursion compounds.
Baselines
The naive reference is POLO-style value-terminated MPPI with the longest horizon that fits the control period, no latency awareness, and value targets from planner-time states. This is what one gets by moving existing hybrid methods into a crowd unchanged. It runs on identical compute, the same value network architecture, and the same training steps.
The strongest competitor on the specific question is fixed-horizon value-terminated MPPI with standard latency compensation. In that variant, the ego state is forward-predicted by the measured delay, obstacles are forward-predicted by the same forecaster our method uses, and $H$ is grid-searched per benchmark stage with the same tuning budget we spend on the selector's two constants. Beating it requires a statistically significant improvement in success rate on dense crowd stages at equal compute, over at least 1,000 scenarios per stage to match the protocol of prior Arena-Rosnav results.
The strongest published system on the shared benchmark is Learning based Convex MPC, which reports a 68.5% success rate on Arena-Rosnav Stage 7 dense crowds against 57.8% for TEB across 1,000 scenarios. We will rerun it from the same benchmark rather than copy its number, and treat exceeding its rerun success rate on Stage 7 as the headline target. H-DAGap reports 100% success with 20 agents and 97% with 50 in its own simulator. Because that setting differs, we will port it to our scenarios only if the code allows, and otherwise report it as not directly comparable. On CrowdNav, LM-SARL reports 100% success in the invisible setting, so we use CrowdNav mainly for time-to-goal and freezing rather than success.
Two ablations isolate the ingredients. The first keeps adaptive horizons but uses stale-state value targets. The second uses delay-consistent targets with a fixed tuned horizon.
Why not just…?
Why not just forward-predict the state by the measured delay and use the longest horizon you can afford? This is the most serious threat, and it is the strongest baseline above. Forward prediction removes the ego-state drift exactly, which is why a static-environment version of our bound says "longest affordable horizon" and our method should then tie. The open question is whether obstacle forecast error, which forward prediction cannot remove, grows fast enough with latency to create an interior optimum. The horizon sweep in the experiments answers this directly. If success rate is monotone in $H$ even in Stage 7 crowds, the claim fails and we will report that.
Why not just grid-search a single horizon per environment? If crowd density and predictability were uniform within an episode, a tuned constant would capture everything and the selector would add nothing. Arena-Rosnav's social-force pedestrians produce episodes that alternate between open space and bottlenecks, so we expect $H^*$ to vary within episodes. We test this by logging the selector's chosen $H$ and comparing against the per-stage tuned constant. If the tuned constant matches, the contribution narrows to the analysis and the delay-consistent targets, and we will say so.
Why not distill the planner into a fast policy and avoid latency altogether? Bootstrapped MPC makes distillation effective in static locomotion. Model-Based Offline Planning, however, finds that test-time planning is needed to adapt to changed constraints. We include a distilled student of our own planner, trained on the same data, and test it on crowd densities and speeds held out from training. There, the online planner should retain its advantage.
Why not rely on a decoupled planner plus a fast safety filter? A safety filter prevents collisions but cannot prevent traps or freezing that stem from the slow planner, which is the failure H-DAGap itself reports. We will add the same filter on top of every method, so collision rates are comparable. The comparison then turns on success rate, freezing rate, and filter intervention frequency.
Proposed Experiments
The primary testbeds are Arena-Rosnav Stages 5 and 7 from Arena-Bench, which provide 2D Flatland scenes with social-force pedestrians, and CrowdNav. Metrics are success rate, collision rate, time to goal, freezing rate, filter intervention rate, and measured control-loop latency including its jitter distribution.
The first decisive check is the horizon sweep. For fixed compute, we plot success against $H$ at several crowd densities and pedestrian speed noise levels, and compare the empirical argmax with the bound's predicted $H^*$. The claim requires an interior optimum that moves toward shorter horizons as crowds get denser or more erratic, and a monotone curve in empty scenes.
The second check is a latency-scaling experiment. We artificially slow the solver by constant factors and verify that the empirical $H^*$ shifts as the bound predicts.
The third check tests the recursive claim. We track the held-out value error across training iterations under stale versus delay-consistent targets. If stale targets feed a growing $\epsilon_V$, the gap should widen over training, consistent with the "later is greater" analysis of Farahmand et al.. A flat gap would mean latency corrupts planning but not learning.
The final comparison runs all baselines and ablations on 1,000 scenarios per stage at matched compute.
References
- Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control
- Deep Value Model Predictive Control
- Handling Delay in Real-Time Reinforcement Learning
- Bootstrapped Model Predictive Control
- Error Propagation for Approximate Policy and Value Iteration
- Model-Based Offline Planning
- Collision-Free Robot Navigation in Crowded Environments using Learning based Convex Model Predictive Control
- Safe Hierarchical Navigation in Crowded Dynamic Uncertain Environments
- Planning, Fast and Slow: A Framework for Adaptive Real-Time Safe Trajectory Planning
- Arena-Bench: A Benchmarking Suite for Obstacle Avoidance Approaches in Highly Dynamic Environments