Optimal Reciprocal Collision Avoidance (ORCA)

ORCA's foundation is the Velocity Obstacle (VO), a geometric construct. For a pair of agents, the VO defines the set of relative velocities that would cause a collision within a specified time horizon (τ). ORCA transforms this forbidden set into a half-plane constraint on each agent's absolute velocity, representing velocities that are guaranteed collision-free if the other agent selects a velocity from a reciprocal set. This geometric translation is computationally efficient, enabling real-time evaluation.

A defining principle of ORCA is that collision avoidance is a shared responsibility. Unlike methods where one agent bears the full avoidance burden, ORCA assumes all agents are running a similar algorithm. For each pairwise constraint, each agent agrees to adjust its velocity by at least half the minimum required change to avoid collision. This reciprocity prevents oscillatory or non-cooperative behavior and leads to smoother, more predictable trajectories for the entire fleet.

Each agent solves a low-dimensional Linear Program (LP) at every control cycle. The agent's preferred velocity (e.g., toward its goal) is the objective to minimize deviation from. The constraints are the half-planes (ORCA constraints) derived from all nearby agents and static obstacles. The solution is the new velocity that is closest to the preferred velocity while satisfying all safety constraints. This optimization ensures locally optimal decisions that balance progress with safety.

ORCA is inherently decentralized. Each agent requires only the current position, velocity, and radius of its neighbors within a local perception range. There is no central coordinator or global plan. This architecture provides key advantages:

• Scalability: Computation is distributed; adding more agents does not cripple a central planner.
• Robustness: The failure of one agent does not collapse the system.
• Responsiveness: Agents react immediately to local changes without waiting for global re-planning.

Under ideal conditions (perfect sensing, identical algorithms, holonomic agents), ORCA provides formal guarantees. If the linear program for an agent is feasible, the chosen velocity is provably collision-free for at least the time horizon τ. This guarantee holds for all agents simultaneously due to the reciprocal construction. In practice, with non-holonomic constraints (like differential-drive robots), post-processing is required to follow the ORCA-computed velocity, which may weaken the formal guarantee but maintains high practical safety.

ORCA is a local, reactive collision avoidance layer. It is typically not used for long-range goal-oriented planning. In a full navigation stack, a global planner (e.g., A*, RRT) generates an initial path. ORCA then acts as the local controller, using the direction toward the next sub-goal on this path as its 'preferred velocity.' This hybrid approach combines the foresight of global planning with the reactivity needed for dynamic, crowded environments.

Velocity Obstacles is the foundational geometric framework upon which ORCA is built. 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 core concept is to compute a collision cone in velocity space. Any velocity chosen from within this cone leads to a future collision.

• Key Difference from ORCA: VO is a non-reciprocal formulation. It assumes the other agent will not change its velocity, placing the entire burden of avoidance on the planning agent. ORCA extends this by defining a reciprocal set of permissible velocities for both agents, enabling decentralized cooperation.

The Dynamic Window Approach is a reactive, local obstacle avoidance method for differential-drive robots. Instead of planning in configuration space, it operates directly in the robot's velocity space (v, ω).

• Mechanism: It samples admissible velocities within a dynamic window defined by the robot's acceleration limits and simulates short-term trajectories. It selects the velocity pair that maximizes an objective function balancing progress towards the goal, speed, and clearance from obstacles.
• Contrast with ORCA: DWA is primarily for a single robot avoiding static and dynamic obstacles. ORCA is fundamentally multi-agent and reciprocal, designed for symmetric cooperation among many agents. DWA does not explicitly model the reactive behavior of other agents.

Model Predictive Control is an advanced, optimization-based control paradigm used for trajectory following and dynamic obstacle avoidance. At each control step, it solves a finite-horizon optimal control problem using an internal dynamic model of the system to predict future states.

• Relation to ORCA: MPC can incorporate ORCA's velocity constraints directly into its optimization problem. This creates a hybrid approach: MPC handles high-level trajectory optimization and system dynamics, while ORCA constraints ensure collision avoidance with other agents. MPC provides a natural framework for integrating reciprocal avoidance with other objectives like energy efficiency and smoothness.

Multi-Agent Path Finding is the centralized, planning counterpart to ORCA's decentralized, reactive approach. The goal is to find collision-free paths for all agents from start to goal locations, optimizing a global metric like makespan or sum-of-costs.

• Key Algorithms: Includes Conflict-Based Search (CBS) and A* variants like Space-Time A*.
• Planning vs. Reaction: MAPF is typically computed offline or with significant lookahead. ORCA operates in real-time with minimal computation per agent, reacting to immediate sensor data. They are often used in tandem: a MAPF solver provides a high-level plan, and ORCA handles local deviations and unpredicted dynamics during execution.

A Control Barrier Function is a formal mathematical tool from control theory used to guarantee safety (e.g., collision avoidance) for dynamical systems. It defines a safety set (e.g., all states where agents are separated) and synthesizes a controller that ensures the system state never leaves this set.

• Formal Guarantees: CBFs provide provable safety certificates, unlike the heuristic nature of many reactive methods.
• Comparison to ORCA: ORCA can be interpreted as generating a specific, geometric form of barrier constraint. Recent research integrates CBFs with ORCA-like constraints to create controllers that are both safe-by-design and reciprocal, offering stronger theoretical guarantees for multi-agent systems.

Receding Horizon Control is the implementation strategy used by Model Predictive Control (MPC) and is a core principle for real-time replanning. Only the first control action from the optimized plan is executed. The horizon then "recedes" forward in time, and the optimization is re-solved with new state information.

• Connection to ORCA: ORCA inherently operates on a receding horizon principle. At each time step (typically every 50-100ms), each agent observes the current positions and velocities of neighbors, solves the ORCA linear program to find a new admissible velocity for the next time window, and executes it. This continuous cycle of sensing, computing, and acting defines its reactive nature.