Dynamic Window Approach (DWA)

DWA operates directly in the robot's velocity space (translational velocity v and rotational velocity ω), not in Cartesian space. It evaluates a finite set of velocity pairs (v, ω) within the dynamic window. For each candidate, it simulates the robot's trajectory over a short simulation time horizon (e.g., 1-3 seconds) using a simple motion model. The optimal pair is selected based on an objective function that balances goal heading, clearance from obstacles, and forward speed. This direct velocity selection makes it computationally efficient for real-time control loops.

The dynamic window is the core constraint that defines the set of admissible velocities considered at each planning cycle. It is the intersection of three fundamental sets:

• Velocities achievable by the robot's motors given its acceleration limits.
• Velocities that can be stopped safely before a collision, given the robot's maximum deceleration and the distance to the nearest obstacle.
• The current maximum velocities allowed by the system. This window shrinks dynamically as the robot approaches obstacles, inherently enforcing a braking distance safety margin. It ensures only kinematically feasible and immediately safe velocities are evaluated.

DWA uses a weighted, multi-objective scoring function G(v, ω) to evaluate each candidate velocity (v, ω) within the dynamic window. A typical formulation is: G(v, ω) = α·heading(v, ω) + β·dist(v, ω) + γ·velocity(v, ω)

• Heading: Measures alignment of the simulated trajectory with the goal direction.
• Clearance: Maximizes the minimum distance to obstacles along the simulated arc.
• Velocity: Prefers higher forward speeds to promote progress. The weights (α, β, γ) are tuning parameters. The velocity pair maximizing G is selected for execution. This greedy optimization occurs every control cycle (10-100 Hz).

DWA is a purely local and reactive planner. It has no long-term memory or global path commitment. Its planning horizon is extremely short (seconds), making it highly responsive to dynamic obstacles that appear within sensor range. This reactivity is ideal for cluttered, unpredictable environments. However, this local focus is also its primary limitation: it is susceptible to local minima (e.g., getting stuck in concave obstacles or dead ends). Therefore, DWA is almost always paired with a global path planner (e.g., A*, RRT) that provides a guiding heading or waypoint, turning DWA into a local path follower or controller.

The classic DWA formulation is designed for non-holonomic robots like differential-drive or car-like vehicles, where motion constraints are explicitly modeled in the velocity space and trajectory simulation. The algorithm can be adapted for holonomic robots (e.g., omnidirectional platforms) by expanding the search space to include lateral velocities, though this increases computational complexity. The dynamic window constraints must be updated to reflect the holonomic robot's acceleration capabilities in all translational degrees of freedom. For holonomic robots, alternative reactive methods like the Nearness Diagram or potential fields are sometimes preferred.

DWA and Velocity Obstacles (VO) are both reactive, velocity-space methods but differ fundamentally in approach. VO is a geometric method: it computes the exact set of relative velocities that would cause a collision with each obstacle within a time horizon, then selects a velocity outside all these forbidden sets. DWA is a sampling-based optimization: it simulates trajectories for a sampled set of velocities and scores them. VO provides stronger formal collision avoidance guarantees for the time horizon but can be more computationally intensive for dense obstacle fields. DWA is often simpler to implement and tune for single-robot scenarios.

Robots operating in human spaces, such as vacuum cleaners, delivery robots, and hospital assistants, rely on DWA for safe cohabitation.

• Human-Robot Interaction: The algorithm's short planning window (typically < 1 second) allows for rapid reaction to a person stepping into the robot's path.
• Admissible Velocities: DWA calculates which translational (v) and rotational (ω) velocities are reachable and safe before a potential collision, often choosing to slow down or turn away.
• Example - Vacuum Robot: When a pet or child moves in front of it, the robot's DWA module instantly samples alternative velocity pairs, discarding those that would lead to a collision within the next few sensor cycles, and executes the best remaining option.

DWA is rarely used in isolation. Its primary role is as a local planner or controller within a hierarchical navigation stack.

• Global Path Input: A global planner (e.g., A*, RRT*) provides a coarse, obstacle-free path from start to goal.
• Local Execution: DWA's job is to follow this path while handling immediate, local obstacles. It uses the global path to define an objective function that favors velocities moving the robot toward the next sub-goal.
• Fail-Safe Behavior: If DWA's dynamic window contains zero admissible velocities (a dead-end), it signals the global planner to compute a new route. This combination provides both long-term goal direction and short-term safety.

A key strength of DWA is its explicit incorporation of the robot's kinematic and dynamic constraints directly into the velocity search space.

• Kinematic Constraints: For a differential-drive robot, this enforces the relationship between wheel velocities and the achievable v and ω.
• Dynamic Constraints: The 'dynamic window' is defined by velocities attainable given the robot's maximum acceleration (a_max) and braking capability. Velocities that cannot be reached or stopped from before hitting an obstacle are discarded.
• Mathematical Foundation: The window is computed as: V_a = { (v, ω) | v ∈ [v_curr - a_v*Δt, v_curr + a_v*Δt], ω ∈ [ω_curr - a_ω*Δt, ω_curr + a_ω*Δt] }, where a_v and a_ω are acceleration bounds.

DWA selects the optimal velocity pair by maximizing a weighted objective function G(v, ω) over the admissible window. This function balances competing goals:

• Heading: Alignment towards the goal or next waypoint. α * heading(v, ω)
• Clearance: Distance to the nearest obstacle on the projected trajectory. β * dist(v, ω)
• Velocity: Preference for forward progress. γ * vel(v)

Engineering Trade-off: Tuning the weights (α, β, γ) is critical. High β creates cautious, stand-offish robots. High α creates goal-focused robots that may brush past obstacles. This tuning is domain-specific.

DWA occupies a specific niche compared to other collision avoidance paradigms.

• vs. Potential Fields: DWA is less prone to getting stuck in local minima because it evaluates discrete trajectories, not just repulsive forces.
• vs. Velocity Obstacles (VO) / ORCA: VO/ORCA are geometric, often assuming other agents also run avoidance algorithms. DWA is more pragmatic for robot-to-static or unpredictable obstacle avoidance.
• vs. Model Predictive Control (MPC): MPC solves an optimization over a horizon. DWA is a simpler, faster sampling-based approximation suitable for limited onboard compute. MPC is more optimal but computationally heavier.
• Best Use Case: DWA excels in unknown or semi-structured environments where sensor noise and dynamic changes are the primary challenges, and computational resources are limited.

Velocity Obstacles is a geometric collision avoidance framework. It defines the set of all relative velocities for a robot that would result in a collision with another moving object within a specified time horizon. The robot selects a velocity outside this forbidden set.

• Core Principle: Projects the obstacle's shape into the robot's velocity space.
• Contrast with DWA: VO provides a continuous set of inadmissible velocities, while DWA samples a discrete window of dynamically feasible velocities for evaluation.
• Application: Foundational for many reciprocal collision avoidance algorithms.

Optimal Reciprocal Collision Avoidance is a decentralized, velocity-based algorithm for multi-agent navigation. Each agent independently computes a half-plane of permitted velocities that guarantees collision avoidance, assuming other agents perform a symmetric reasoning process.

• Reciprocity: Agents share responsibility for avoiding collisions.
• Mathematical Guarantee: Provides formally proven collision-free motion under ideal assumptions.
• Relation to DWA: While DWA is often used for a single robot with passive obstacles, ORCA is designed for cooperative avoidance among multiple active agents. They can be combined in hybrid architectures.

Model Predictive Control is an advanced control methodology. At each time step, it solves a finite-horizon optimal control problem using an internal dynamic model of the system to predict future states. Only the first control input is executed before the horizon recedes and the process repeats.

• Optimization-Based: Explicitly minimizes a cost function (e.g., tracking error, control effort).
• Constraint Handling: Can directly incorporate kinematic, dynamic, and obstacle constraints.
• Contrast with DWA: DWA is a reactive, sampling-based method within a short window. MPC is a more general optimization framework that can subsume DWA-like objectives but is computationally more intensive.

The Timed Elastic Band is a local trajectory optimization method. It deforms an initial, kinematically feasible path (the "elastic band") by optimizing the positions and time intervals of a sequence of robot poses.

• Simultaneous Optimization: Optimizes for path geometry and temporal profile (velocity, acceleration).
• Gradient-Based: Uses numerical optimization to minimize costs related to path length, proximity to obstacles, and dynamic feasibility.
• Relation to DWA: Both are local planners. TEB performs continuous optimization on a pose sequence, while DWA performs discrete search over velocity space for the immediate next step. TEB generally produces smoother global trajectories.

A Control Barrier Function is a mathematical tool for guaranteeing safety in control systems. It defines a function whose value indicates proximity to an unsafe set. The controller is synthesized to ensure this function never decreases below zero, formally keeping the system within a safe "invariant set."

• Formal Safety Guarantees: Provides rigorous, constraint-certifying controllers.
• Filtering Approach: Can be used as a safety filter atop a nominal controller (like DWA).
• Relation to DWA: CBFs offer a complementary, formal method to enforce collision constraints that can be integrated with the heuristic objective maximization of DWA to create certifiably safe reactive navigation.

Receding Horizon Control is the implementation strategy underpinning Model Predictive Control (MPC). It refers to the process of solving a finite-time optimal control problem at each step, applying the first control action, and then shifting the planning horizon forward in time for the next iteration.

• Core Loop: Plan → Execute first step → Re-plan with updated state.
• Handles Uncertainty: Continuously incorporates new sensor data.
• Fundamental to DWA: DWA is a specific, simplified instantiation of the receding horizon principle applied to velocity space search for collision avoidance, typically with a very short horizon (the dynamic window).