Velocity Obstacle (VO)

A Velocity Obstacle (VO) is a cone-shaped region in the robot's velocity space. For a given obstacle, the VO is constructed by translating the Minkowski sum of the robot and obstacle shapes into velocity space, originating from the relative position vector. Any velocity vector whose tip lies inside this cone would cause a collision within a specified time horizon (τ). The apex of the cone is at the robot's current velocity. This transforms the physical collision problem into a simpler geometric test in velocity space.

VO is fundamentally a local and reactive planner. It does not require a global map or long-term plan, making it highly efficient for dynamic environments.

• Local Horizon: It only considers collisions within a short look-ahead time (τ), typically 2-10 seconds.
• Sensor-Based: It operates directly on instantaneous sensor data (e.g., LiDAR, camera detections) of nearby obstacles' positions and velocities.
• Computational Speed: The velocity selection is often a simple geometric optimization, enabling real-time execution at control loop frequencies (10-100 Hz). This makes it ideal for dynamic obstacle avoidance where paths change rapidly.

The robot's objective is to select a new velocity outside all Velocity Obstacles that is as close as possible to a preferred, goal-directed velocity.

• Feasible Velocity Space: The set of velocities achievable by the robot given its dynamic constraints (max acceleration, turn rate).
• Optimization Criterion: The chosen velocity v_new minimizes a cost function, often: ||v_new - v_pref||, where v_pref is the velocity directed toward the global goal.
• Reciprocity: In multi-agent settings, algorithms like Reciprocal Velocity Obstacles (RVO) adjust the VO formulation so that agents share the responsibility of avoiding each other, preventing oscillatory behavior.

The basic VO formulation has been extended to handle more complex scenarios:

• Reciprocal Velocity Obstacle (RVO): Assumes other agents are also running a similar algorithm, leading to smoother, more predictable maneuvers.
• Hybrid Reciprocal Velocity Obstacle (HRVO): Combines concepts from VO and RVO to guarantee collision avoidance even with non-cooperative agents.
• Generalized Velocity Obstacle (GVO): Extends VO to robots with arbitrary non-linear dynamics.
• Nonlinear Velocity Obstacle (NLVO): Accounts for the curved trajectories that result from applying constant accelerations over the time horizon, rather than assuming constant velocity.

VO occupies a specific niche in the motion planning hierarchy.

• *Vs. Global Planners (A, RRT)**: VO is not for finding a full path from start to goal in a complex static map. It is a local collision avoidance module that executes within the corridor provided by a global planner.
• Vs. Trajectory Optimization (MPC): While Model Predictive Control (MPC) also optimizes over a future horizon, it uses a full dynamic model and is more computationally intensive. VO is a lighter, geometry-first approach.
• Vs. Dynamic Window Approach (DWA): DWA also searches in velocity space but does so by forward simulation of trajectories. VO uses a direct geometric construction, which can be faster but may make different simplifying assumptions.

Applications:

• Warehouse AMRs: For avoiding other robots and human workers in dynamic aisles.
• Drone Swarms: Enabling dense, decentralized flight without collisions.
• Service Robots: Navigating crowded, human-populated environments like hospitals or hotels.

Key Limitations:

• Oscillations: In dense, symmetric scenarios, agents can get stuck in back-and-forth motions.
• Local Minima: The robot can become trapped (e.g., in a concave obstacle or dense crowd) with no local velocity leading toward the goal.
• Assumption of Constant Velocity: The basic VO assumes obstacles move at constant velocity over τ, which can fail for highly agile or accelerating objects.
• Responsibility: In human-robot interaction, purely reactive VO can lead to robot behavior perceived as aggressive or unpredictable.

The primary application of Velocity Obstacle is enabling mobile robots and autonomous vehicles to navigate safely among moving obstacles. The algorithm continuously calculates the VO cone for each nearby dynamic object. By selecting a velocity outside all VO cones, the robot guarantees collision-free motion for a defined time horizon (τ). This is critical for:

• Warehouse logistics: AMRs (Autonomous Mobile Robots) avoiding each other and human workers.
• Service robots: Navigating crowded public spaces like airports or hospitals.
• Last-mile delivery vehicles: Reacting to pedestrians and cyclists in urban environments. Its reactive nature makes it robust to unpredictable motion, a key advantage over purely predictive planners.

VO scales naturally to multi-robot systems where each agent is both an obstacle and a planner. In Reciprocal Velocity Obstacle (RVO) and its optimal variant ORCA, agents share the responsibility of collision avoidance. Each robot assumes others will also select collision-avoiding velocities, leading to smoother, more efficient group motion. This is foundational for:

• Drone swarms: Coordinated flight patterns and formations.
• Fleet coordination: Warehouses with dozens of interacting AMRs.
• Robotic search and rescue: Multiple agents exploring an area without centralized control. The method's decentralized nature avoids a single point of failure and scales computationally with the number of nearby agents.

VO is typically a local planner or collision checker within a larger hierarchical architecture. A global planner (e.g., A*, RRT) computes a long-term, coarse path. VO then executes this plan while handling local, unmodeled dynamic obstacles. This hybrid approach combines the optimality of global planning with the reactivity of VO. Common integration patterns include:

• Using the global plan's direction to bias velocity selection within the admissible velocity space.
• Treating VO as the low-level controller in a Model Predictive Control (MPC) framework, where the optimization cost function penalizes velocities inside VO cones.
• Employing VO for real-time safety in legged robot locomotion, where the global planner handles footstep placement.

VO is extensively applied in domains governed by COLREGs (International Regulations for Preventing Collisions at Sea) and aviation standards. For autonomous surface vessels and unmanned aerial vehicles (UAVs), the VO formulation is extended to account for complex kinematic constraints (e.g., minimum turning radius) and right-of-way rules. The admissible velocity space is filtered not just for collision, but also for regulatory compliance. This is vital for:

• Autonomous shipping: Large vessels avoiding each other in congested waterways.
• Drone delivery in controlled airspace: Adhering to strict separation standards.
• Search and rescue UAVs: Operating safely near other aircraft in dynamic missions.

In collaborative robotics (cobots), VO ensures safe physical interaction by modeling the human operator as a dynamic obstacle with predictable intent. Advanced implementations use sensor fusion (e.g., depth cameras, LiDAR) to estimate human velocity and generate a protective VO. The robot's speed and trajectory are modulated in real-time, allowing for:

• Close-proximity assembly: A robot arm handing tools to a worker while avoiding accidental contact.
• Mobile manipulators in factories: Navigating aisles where humans are present.
• Rehabilitation robotics: Assisting a patient's movement while maintaining a safe boundary. This application emphasizes the need for accurate velocity estimation and a carefully chosen time-to-collision (τ) parameter.

Beyond physical robotics, VO principles are used in computer graphics and real-time strategy (RTS) games for simulating believable crowd and unit movement. The algorithm allows hundreds of agents to navigate towards individual goals while avoiding collisions, creating emergent, fluid group behaviors. Game engines implement optimized 2D versions of RVO2 for pathfinding. Key benefits include:

• Computational efficiency: Handles dense crowds with O(n) complexity relative to nearby agents.
• Natural-looking motion: Avoids the "robotic" grid-locked movement of simpler rule-based systems.
• Dynamic replanning: Agents instantly react to new obstacles or changing goals. This demonstrates VO's utility as a general algorithm for multi-agent navigation in virtual spaces.

The computational process of determining whether two or more geometric objects intersect or are in contact. This is the fundamental geometric query that underlies the construction of any Velocity Obstacle.

• Broad Phase: Quickly identifies pairs of objects that might collide using bounding volumes (e.g., Axis-Aligned Bounding Boxes).
• Narrow Phase: Performs exact geometric intersection tests on candidate pairs.
• Continuous Collision Detection (CCD): Determines if two objects moving along predicted paths will collide within a time interval, which is essential for VO's time-to-collision reasoning.

A mathematical framework for planning under uncertainty where an agent must make decisions based on incomplete and noisy observations. VO methods often assume perfect knowledge of obstacle positions and velocities. POMDPs provide a formalism for extending VO-like reasoning to realistic, uncertain environments.

• Belief State: A probability distribution over possible true states, updated via a Bayesian filter (e.g., Kalman Filter).
• Policy: A mapping from belief states to actions that maximizes expected long-term reward.
• Application: Used for navigation where obstacle motions are uncertain or must be inferred from noisy sensor data.

A kinematic restriction on a system's motion that is non-integrable, meaning it limits possible velocities but not necessarily achievable configurations. Standard VO formulations assume holonomic (omnidirectional) motion. For real robots like cars or differential-drive platforms, the VO must be computed within the subspace of velocities that satisfy these constraints.

• Classic Example: A car cannot move directly sideways; its velocity is constrained by the steering angle v_x = v * cos(θ), v_y = v * sin(θ).
• Velocity Space: The VO is intersected with the admissible velocity cone defined by the nonholonomic constraints.
• Planning Implication: Makes collision avoidance more challenging, as the robot cannot simply select any velocity outside the VO.