Velocity Obstacles (VO)

The core of VO is the transformation of physical obstacles into constraints in the velocity space of the robot. For each obstacle, the algorithm constructs a Collision Cone (CC)—the set of relative velocities that would cause an intersection between the robot and the obstacle within a time window τ. The Velocity Obstacle (VO) is then this cone translated by the obstacle's current velocity. Any velocity selected from outside the union of all VOs is guaranteed to be collision-free for at least time τ.

A critical advancement that enables smooth, oscillation-free navigation in multi-agent settings. In the basic VO formulation, each agent assumes others will not change their velocity, which can lead to indecisive 'dancing' behavior. Reciprocal Velocity Obstacles (RVO) assumes all agents share the responsibility for collision avoidance. Each agent selects a velocity outside the VO that is the average of its preferred velocity and the velocity that would avoid the collision if the other agent acted similarly. This leads to more natural and predictable trajectories.

• Key Benefit: Eliminates oscillatory behavior in dense traffic.
• Assumption: Requires other agents to run a compatible algorithm.

ORCA is the de facto standard implementation of the RVO concept, providing formal guarantees. For each pair of agents, ORCA defines a half-plane of permissible velocities in velocity space. The optimal collision-avoiding velocity is found by solving a low-dimensional linear program that selects the velocity closest to the agent's preferred velocity while lying within the intersection of all permissible half-planes.

• Guarantee: Provides provably collision-free navigation for holonomic agents.
• Efficiency: The linear program can be solved in real-time for dozens of agents.
• Limitation: Primarily designed for agents with holonomic (omnidirectional) dynamics.

The time horizon τ is a fundamental parameter that defines the predictive scope of the VO. It represents the future time window over which collisions are predicted and avoided. A larger τ makes the agent more conservative, avoiding potential collisions further in the future but potentially leading to unnecessary detours. A smaller τ makes the agent more aggressive, reacting only to imminent threats, which can be risky in high-speed scenarios.

• Trade-off: Balances safety against efficiency and responsiveness.
• Dynamic Adjustment: Advanced implementations may vary τ based on agent density or speed.

VO is inherently a local, reactive method. To be effective in complex environments, it must be integrated with a global path planner (e.g., A*, RRT*). The global planner provides a long-term goal and a coarse path, while the VO layer acts as a local collision avoidance module. The agent's 'preferred velocity' is typically set towards the next sub-goal on the global path. This hybrid architecture combines optimal long-range planning with safe, real-time reaction to dynamic obstacles.

The classic VO/ORCA formulation assumes agents are holonomic (can move in any direction instantaneously). For real robots with non-holonomic constraints (e.g., differential-drive or Ackermann-steering vehicles), extensions are required. Common approaches include:

• Kinodynamic VO: Sampling feasible motions that respect acceleration and turning limits.
• Unicycle VO: Defining constraints directly in the space of linear and angular velocities.
• Hybrid Planning: Using VO to select a safe guiding direction, then employing a low-level controller (e.g., Model Predictive Control) to track it with dynamic feasibility.

These extensions bridge the gap between geometric collision avoidance and physical robot dynamics.

A reactive, velocity-space algorithm for local obstacle avoidance. Unlike Velocity Obstacles, which defines inadmissible velocities, DWA directly searches within a dynamic window of achievable velocities given the robot's acceleration limits. It evaluates trajectories over a short time horizon based on:

• Objective heading towards the goal
• Clearance from obstacles
• Forward velocity for progress DWA is computationally lightweight and well-suited for real-time control of differential-drive robots but is generally non-holonomic and short-sighted compared to VO's geometric foresight.

A decentralized, velocity-based collision avoidance framework that extends the Velocity Obstacles concept for reciprocal cooperation among multiple agents. For each pair of agents, ORCA defines a half-plane of permissible velocities that guarantees collision avoidance if both agents select a velocity from within it. Key principles:

• Reciprocity: Assumes other agents will perform a symmetric avoidance maneuver.
• Linear constraints: Permissible velocities form a convex region, enabling fast linear optimization.
• Optimality: Selects the velocity closest to the agent's preferred velocity. ORCA is foundational for dense, multi-agent navigation in shared spaces like warehouses.

An advanced control paradigm that uses a dynamic model of the system to predict future states over a finite horizon and solves an optimization problem at each time step to determine optimal control inputs. In motion planning, MPC can incorporate Velocity Obstacles as constraints within its optimization. Distinctions:

• Holistic Optimization: Considers system dynamics, actuator limits, and task objectives simultaneously.
• Receding Horizon: Executes only the first control input before re-planning.
• Constraint Handling: Can formally integrate VO, kinodynamic, and environmental constraints. MPC provides a unifying framework for combining predictive collision avoidance with optimal control.

A mathematical formalism for ensuring a dynamical system remains within a safe set. CBFs provide a constraint-driven approach to safety, contrasting with the geometric inference of Velocity Obstacles. A CBF defines a scalar function whose value indicates proximity to an unsafe state (e.g., collision). The controller is synthesized to ensure the derivative of this function maintains safety.

• Formal Guarantees: Provides provable safety certificates under defined dynamics.
• Integration with Controllers: Can be combined with MPC or other controllers as a safety filter.
• Dynamic Constraints: Naturally incorporates system dynamics, whereas basic VO is kinematic. CBFs represent a control-theoretic complement to geometric VO methods.

The centralized, combinatorial planning problem of finding collision-free paths for multiple agents from start to goal locations, optimizing a global cost (e.g., sum-of-costs). MAPF operates at the discrete planning level, while Velocity Obstacles address continuous, reactive avoidance.

• Planning vs. Execution: MAPF generates a full plan a priori; VO handles deviations during execution.
• Optimality vs. Reactivity: MAPF seeks globally optimal sequences; VO ensures local, real-time safety.
• Integration: Modern systems often use MAPF for high-level scheduling and VO for low-level, dynamic navigation, with replanning triggers bridging the two.

The motion planning problem that requires solutions to satisfy both kinematic constraints (e.g., non-holonomic steering) and dynamic constraints (e.g., acceleration, torque limits). Velocity Obstacles primarily address kinematic collision avoidance in velocity space.

• Feasibility: Kinodynamic planning finds trajectories that are dynamically executable by the robot's actuators.
• State Space: Searches in the full state space (position, velocity, etc.), not just velocity space.
• Algorithms: Solved by planners like RRT* or lattice planners that use motion primitives derived from the dynamics model. Kinodynamic planning provides the feasible trajectory that VO-based controllers then safely track in dynamic environments.