Replanning Horizon

The replanning horizon is the finite future time window, typically measured in seconds or minutes, over which a real-time planning engine recalculates and optimizes an agent's trajectory or task sequence. It represents a trade-off between computational feasibility and strategic foresight. A longer horizon allows for more globally optimal, proactive plans but requires more processing time. A shorter horizon enables faster, more reactive adjustments but may lead to myopic, sub-optimal decisions.

This is the fundamental engineering trade-off governed by the horizon length.

• Short Horizon (High Reactivity): Enables rapid re-planning in response to immediate obstacles or new high-priority tasks. Ideal for dense, highly dynamic environments but can cause oscillatory behavior or local minima where agents get stuck.
• Long Horizon (High Optimality): Provides greater foresight, allowing agents to anticipate bottlenecks, coordinate smooth interactions, and select globally efficient routes. This increases computational latency and may reduce responsiveness to sudden changes.

The length of the replanning horizon is a primary driver of computational cost. Search-based planners (e.g., A*, Lattice Planners) and optimization-based methods (e.g., Model Predictive Control) see an exponential or polynomial increase in state-space size with horizon extension. Engineers must balance horizon length against the real-time constraint—the plan must be computed within the agent's control cycle (often <100ms). Techniques like warm-starting with the previous plan and using incremental algorithms (e.g., D Lite*) help manage this cost.

The horizon works in concert with replanning triggers to define the system's operational cadence.

• A trigger (e.g., new obstacle, task change) initiates a replanning cycle.
• The horizon defines the scope of that new plan. For example, a minor obstacle may only require re-planning the next few seconds, while a major task reassignment may necessitate a full-horizon re-optimization. Systems often implement multi-horizon planning, using a short horizon for reactive collision avoidance and a longer, slower cycle for strategic task sequencing.

Advanced systems do not use a fixed horizon. Instead, they employ adaptive strategies:

• Anytime Algorithms: Return a valid plan immediately for the current horizon, then iteratively refine it if computation time allows, effectively lengthening the optimized horizon.
• Event-Driven Adjustment: Shorten the horizon in high-traffic zones for agility, and lengthen it in open areas for efficiency.
• Predictive Horizon Scaling: Use fleet state estimation to predict environmental volatility and preemptively adjust the horizon. A forecast of converging agent paths might trigger a temporary horizon extension to plan cooperative maneuvers.

In Model Predictive Control (MPC) and Receding Horizon Control (RHC), the replanning horizon is the prediction horizon. The controller solves an optimization over this horizon, executes the first step, then shifts the horizon forward and repeats. Key parameters include:

• Prediction Horizon (N): The number of future time steps optimized.
• Control Horizon (M): Often shorter, the number of steps over which control inputs are freely optimized. The choice of N is critical: too short leads to instability; too long makes the optimization problem intractable for real-time use.

The replanning horizon is the finite future time window, typically expressed in seconds, over which a real-time planning engine solves an optimization problem to generate or update an agent's trajectory. Its length creates a fundamental trade-off:

• Short Horizon: Enables faster, more frequent replanning cycles (< 100ms) but risks myopic behavior where the agent fails to anticipate future obstacles or dead ends.
• Long Horizon: Provides better foresight and global optimality but increases computational complexity, potentially causing planning latency that degrades real-time responsiveness.

The replanning horizon is the central parameter in Model Predictive Control (MPC), the dominant framework for real-time robotic control. In MPC:

• At each control cycle, the solver optimizes a sequence of control inputs only over the horizon.
• Only the first control action is executed.
• The horizon recedes forward in time at the next cycle (Receding Horizon Control).
• The horizon length must be long enough for the model's predictions to be meaningful. For a warehouse AMR traveling at 2 m/s, a 5-second horizon provides a 10-meter lookahead, which is often the minimum to react to dynamic obstacles.

The horizon's structure directly influences algorithm choice and performance:

• Fixed Horizon: Simplest approach. A constant window (e.g., 3 seconds) is used for all replanning cycles.
• Variable/Adaptive Horizon: The length adjusts dynamically based on environmental complexity or agent speed to conserve compute.
• Search-Based Planners (A, LPA)**: The horizon is implicit in the graph's spatial extent. Space-Time A* explicitly includes time in its search space, creating a 3D horizon.
• *Sampling-Based Planners (RRT)**: The horizon is defined by the maximum branch length or simulation time of motion primitives.
• Optimization-Based Planners (TEB): The horizon is the number of pose samples in the elastic band being optimized.

In a mixed fleet of Autonomous Mobile Robots (AMRs) and manual vehicles, horizon sizing must account for heterogeneity:

• High-Speed Agents: Require longer horizons for safe stopping distances. A forklift may need an 8-second horizon versus a 3-second horizon for a slow-moving cart.
• Predictability: Horizons for replanning around predictable agents (e.g., other AMRs on known routes) can be shorter. Horizons for unpredictable agents (e.g., human-operated vehicles) must be longer to account for greater uncertainty.
• Communication Delays: In decentralized systems, the horizon must incorporate the worst-case latency of inter-agent state broadcasts to avoid planning based on stale data.

The computational cost of replanning typically scales super-linearly with horizon length. To mitigate this, engineers use warm-starting techniques:

• The solver is initialized with the shifted previous solution. The trajectory from t=1...N of the old plan becomes the initial guess for t=0...N-1 of the new horizon.
• This drastically reduces iterations needed for convergence.
• Effectiveness degrades if the environment changes drastically within the horizon, necessitating a cold start.
• The choice of horizon length is therefore a direct lever on worst-case compute time, which must be less than the control cycle period (e.g., 100ms).

The local replanning horizon operates within the context of a global plan. Best practices involve:

• Using a hierarchical planning architecture. A global planner computes a coarse, long-horizon path to the goal. The local MPC-based planner with its short horizon refines this path, avoiding immediate obstacles.
• The local horizon must be sufficiently long to reach the next via-point or milestone on the global plan. If the horizon is too short, the agent may become stuck, unable to see the path around a local obstacle.
• This is often managed by dynamically adjusting the local horizon's goal state to be the next visible sub-goal along the global path, ensuring the local solver always has a feasible target within its window.

The specific event or condition that initiates a replanning cycle. Triggers are evaluated against the current plan and world state to determine if a new plan within the replanning horizon is necessary. Common triggers include:

• Environmental changes: New obstacles, closed pathways, or zone access rule updates.
• Agent state deviations: Localization errors, mechanical failures, or battery level thresholds.
• Task modifications: New high-priority orders, canceled jobs, or updated destination constraints.
• Multi-agent conflicts: Predicted deadlocks or collisions with other agents' planned paths.

The control strategy that implements the replanning horizon in a rolling fashion. At each control step, the system:

1. Optimizes a plan over the finite horizon.
2. Executes only the immediate first step(s) of that plan.
3. Shifts the horizon forward in time.
4. Repeats the optimization with updated state information. This approach, also known as Model Predictive Control (MPC) for robotic systems, balances long-horizon foresight with the computational tractability of solving smaller, frequent optimization problems.

A class of graph-based pathfinding algorithms designed for efficient replanning when edge costs change. They reuse information from previous searches to repair paths faster than planning from scratch. Their efficiency is critical for operating with practical replanning horizons in large state spaces.

• Lifelong Planning A (LPA)**: Maintains consistent heuristic estimates to efficiently find new optimal paths after graph changes.
• D Lite*: A focused version of LPA* optimized for mobile robot navigation in unknown terrain, where new obstacle discoveries trigger local replanning within the horizon.

A software component that validates whether a candidate trajectory or plan satisfies all system constraints before it is committed for execution. It operates in tandem with the planner to ensure any solution within the replanning horizon is executable. It checks for:

• Kinodynamic feasibility: Adherence to velocity, acceleration, and turning radius limits.
• Collision-free status: Verification against the latest map and obstacle predictions.
• Operational compliance: Adherence to zone rules, load stability, and safety protocols. A fast feasibility checker is essential for evaluating multiple candidate plans within real-time constraints.

The continuous process of comparing an agent's actual execution state—from sensors like LiDAR, odometry, and torque sensors—against its expected plan. It provides the critical feedback loop for the replanning system.

• Detects discrepancies between predicted and actual state (e.g., wheel slippage, unexpected delay).
• Assesses if deviations exceed a tolerance threshold, potentially serving as a replanning trigger.
• Provides the current state used to initialize the next planning cycle within the updated replanning horizon. Effective monitoring reduces the "reality gap" that can invalidate a plan.

An optimization technique where the solver for the current replanning cycle is initialized with the solution from the previous cycle. This dramatically reduces computation time, enabling the use of a longer replanning horizon or more complex optimization models.

• Leverages temporal coherence: The optimal plan at time t is typically very similar to the optimal plan at time t+Δt.
• Provides a high-quality initial guess to nonlinear solvers (common in Model Predictive Control), helping them converge faster.
• Is essential for achieving real-time performance with optimization-based planners in dynamic environments.