Reciprocal Velocity Obstacle (RVO)

The foundational assumption of RVO is that all moving agents share equal responsibility for collision avoidance. Unlike the original Velocity Obstacle (VO) method, which assumes only one agent maneuvers, RVO models each agent as adjusting its velocity by half the required avoidance vector.

• This leads to more natural and efficient maneuvers, as both agents deviate smoothly.
• It prevents the oscillatory behavior and reciprocal dances common in purely reactive systems where agents over-correct.

RVO operates directly in velocity space, not positional space. For each neighboring agent, it constructs a Reciprocal Velocity Obstacle (RVO) set. This is the set of an agent's own velocities that would cause a collision assuming the other agent simultaneously selects a velocity from its own reciprocal set.

• Planning in velocity space allows agents to reason about future collisions over a time horizon (tau).
• The agent selects a new velocity from outside the union of all RVO sets, guaranteeing collision-free motion for the defined horizon.

Each agent computes its own avoidance maneuver using only local information: its own state, the observed or communicated states of nearby agents, and a shared assumption of reciprocity.

• There is no central planner coordinating all agents, making the system highly robust to single-point failures.
• Computational complexity scales with the number of nearby agents, not the total fleet size, enabling real-time performance in dense environments.

Under ideal conditions (perfect sensing, synchronized reasoning, and adherence to the reciprocal model), RVO provides formal guarantees.

• Collision Avoidance: If a feasible solution exists, the selected velocity will not cause a collision within the time horizon.
• Convergence: Agents are guaranteed to reach their goals if the environment is well-formed (e.g., not densely packed).
• These guarantees are foundational for deploying autonomous systems in safety-critical applications.

RVO's core ideas were formalized and optimized in the Optimal Reciprocal Collision Avoidance (ORCA) algorithm. ORCA improves upon RVO by defining the permitted velocity set as a half-plane, making the selection of an optimal new velocity a simple linear program.

• ORCA is considered the standard, efficient implementation of the reciprocal velocity obstacle concept.
• It provides stronger optimality guarantees, selecting the velocity closest to the agent's preferred velocity while ensuring safety.

Real-world deployment of RVO/ORCA requires handling non-ideal conditions.

• Sensing Uncertainty: Agents must inflate obstacle representations or use probabilistic velocity obstacles to account for sensor noise.
• Dynamic Constraints: Selected velocities must be feasible given the agent's kinematic and dynamic limits (max acceleration, turning radius). This is often integrated via a kinodynamic filter.
• Communication: While designed for minimal communication, sharing intent (preferred velocity) improves cooperation, especially at bottlenecks.

RVO is the de facto standard for coordinating fleets of Autonomous Mobile Robots (AMRs) in distribution centers. It enables:

• Scalable navigation for hundreds of robots in shared aisles without central traffic control.
• Smooth, human-like maneuvers that prevent the "freezing robot problem" common in less cooperative algorithms.
• Mixed-traffic safety by allowing AMRs to share space safely with manual forklifts and human pickers, assuming reciprocal responsibility for avoidance. Primary use cases include goods-to-person systems, automated pallet transport, and sortation robots.

In manufacturing and port logistics, RVO coordinates the movement of Automated Guided Vehicles (AGVs) along semi-structured paths. It provides:

• Dynamic obstacle avoidance for unexpected blockages (e.g., fallen pallets, workers) without requiring full path replanning.
• Fleet interoperability between different AGV models and brands by using a common velocity-space reasoning framework.
• Predictable behavior that allows human operators to intuitively understand vehicle intent, increasing trust and safety on the factory floor.

RVO enables robots to navigate safely and politely in human-centric environments like hospitals, hotels, and airports. Key features include:

• Socially compliant navigation by modeling humans as cooperative agents, allowing robots to yield appropriately and pass on the correct side.
• Natural velocity profiles that avoid jarring stops and starts, making robots less disruptive in shared spaces.
• Crowd navigation in dense, dynamic settings like airport terminals, where centralized planning is infeasible. This application is critical for delivery robots, disinfection robots, and customer service assistants.

For drone swarms and urban air mobility, RVO provides a lightweight, communication-efficient method for in-flight collision avoidance. It is used for:

• Drone light shows to maintain precise formations while avoiding mid-air collisions.
• Beyond visual line of sight (BVLOS) operations where drones must autonomously avoid each other and static obstacles.
• Urban Air Traffic Management concepts, where eVTOL aircraft (air taxis) would use RVO-like protocols for last-second, decentralized conflict resolution.

In constrained, low-speed environments like parking garages, RVO manages the complex interactions between multiple autonomous vehicles with no central coordinator. It enables:

• Deadlock resolution in narrow aisles where vehicles must negotiate right-of-way.
• Efficient space utilization by allowing vehicles to pass closely but safely.
• Integration with V2X where basic intent (e.g., target parking spot) can be shared to improve cooperative predictions. This demonstrates RVO's strength in confined, highly interactive scenarios common in Mobility-as-a-Service (MaaS) operations.

The foundational geometric algorithm upon which RVO is built. A Velocity Obstacle defines, for a moving agent, the set of all velocities that would result in a collision with another moving obstacle within a specified time horizon. It is a centralized or non-reciprocal concept, meaning it assumes only the planning agent will take evasive action.

• Key Difference from RVO: VO does not assume other agents will cooperate, leading to more conservative, less efficient maneuvers.
• Application: Serves as the core collision-checking primitive for many early robot navigation systems.

A formal, optimization-based extension of the RVO concept. ORCA provides provably collision-free navigation for multiple agents by efficiently computing a half-plane of permitted velocities for each agent, assuming reciprocal cooperation.

• Mathematical Rigor: Uses linear programming to select the optimal velocity closest to the agent's preferred velocity from within the permitted set.
• Guarantees: Under ideal conditions (perfect sensing, synchronized reasoning), ORCA guarantees no collisions for holonomic agents.
• Performance: Generally produces smoother and more optimal paths than basic RVO, with formal safety proofs.

The overarching coordination paradigm that includes RVO. In decentralized collision avoidance, each agent independently makes its own avoidance decisions based on local sensor data or limited communication, without a central planning authority.

• Core Principle: Scalability and robustness; failure of one agent does not cripple the system.
• Challenges: Requires algorithms that converge to globally good solutions despite local views. Can lead to sub-optimal global behavior or oscillations (e.g., the 'dancing robots' problem).
• Contrast with Centralized: Centralized planners have a global view but suffer from computational complexity and single-point-of-failure risks.

A fundamental risk metric used to evaluate and trigger collision avoidance maneuvers. Time to Collision estimates the time remaining before two objects on a constant relative velocity course will collide if no evasive action is taken.

• Calculation: (TTC = \frac{\text{Distance to Obstacle}}{\text{Relative Speed}}) (for head-on scenarios).
• Role in RVO: The VO and RVO algorithms use a defined time horizon (tau), which is directly related to TTC. They plan to avoid collisions within this window.
• Critical Threshold: Systems often define a minimum TTC below which an emergency protocol (e.g., emergency stop) is invoked.

A reactive, local motion planner that represents an alternative philosophy to velocity-space methods like RVO. DWA searches a space of achievable velocities (the 'dynamic window'), limited by acceleration and braking constraints, to select the command that maximizes progress toward a goal while avoiding imminent collisions.

• Key Difference: DWA operates in velocity-time space and directly incorporates robot dynamics, whereas RVO reasons purely in instantaneous velocity space.
• Strengths: Naturally handles non-holonomic constraints. Good for goal-oriented navigation in cluttered spaces.
• Weaknesses: Can be more myopic and get trapped in local minima compared to methods with longer horizons.

An optimization-based control strategy that represents a more computationally intensive but highly flexible approach. MPC repeatedly solves a finite-horizon optimal control problem to compute a sequence of control inputs that satisfies dynamic constraints and explicitly avoids predicted collisions.

• Philosophy: Predictive vs. Reactive. MPC plans a short trajectory, whereas RVO selects an instantaneous velocity.
• Advantages: Can seamlessly integrate collision avoidance with other objectives (energy use, comfort) and complex constraints.
• Trade-off: High computational cost limits agent density and requires powerful onboard compute compared to lightweight geometric methods like RVO.