Optimal Reciprocal Collision Avoidance (ORCA)

The algorithm's foundation is the Velocity Obstacle (VO), a cone-shaped region in velocity space representing all velocities that would cause a collision with another agent within a specified time horizon. ORCA's key innovation is the Optimal Reciprocal Collision Avoidance (ORCA) set, a half-plane of collision-free velocities derived from the VO. It is constructed under the assumption of reciprocal responsibility, meaning each agent selects a new velocity from its ORCA set while assuming the other agent will do the same, ensuring mutual avoidance without explicit communication of intent.

For each pair of agents, the algorithm generates a linear constraint (the ORCA half-plane). The combined set of constraints from all neighboring agents forms a convex region of permissible velocities. The agent's new velocity is selected by solving a low-dimensional linear program that finds the velocity within this region closest to its preferred velocity (e.g., its goal-directed velocity). This optimization ensures the deviation from the intended path is minimal, making the avoidance maneuver both safe and efficient.

• Objective: Minimize the distance to the preferred velocity.
• Constraints: Defined by the ORCA half-planes from all nearby agents.

ORCA operates in a fully decentralized manner. Each robot requires only local sensing (e.g., position and velocity of nearby agents) and executes the algorithm independently. It does not require:

• A central coordinator.
• Negotiation or explicit trajectory sharing with other agents.
• Prior agreement on roles (like leader-follower).

This architecture provides inherent scalability, as computational load per agent depends only on its local neighborhood, not the total swarm size. It also enhances robustness to individual agent failures.

ORCA is a reactive algorithm, computing new velocities every control cycle (often at 10-100 Hz). The linear programming solution is computationally inexpensive, enabling real-time performance on embedded hardware. Crucially, under its assumptions (accurate sensing, holonomic agents, reciprocal cooperation), ORCA provides provable collision avoidance. If all agents adhere to the algorithm, no collisions will occur for the defined time horizon. This deterministic safety guarantee is critical for deployment in safety-sensitive environments like human-robot collaboration or dense autonomous vehicle traffic.

ORCA's theoretical guarantees rely on specific assumptions that must be considered in real-world applications:

• Holonomic Dynamics: The base algorithm assumes agents can instantaneously change velocity (holonomic). Extensions (NH-ORCA) handle non-holonomic constraints like differential drive.
• Reciprocal Cooperation: All agents must be running ORCA or a behaviorally equivalent algorithm. It cannot avoid passive obstacles or non-cooperative agents without modification.
• Perfect Sensing: Requires accurate, low-latency knowledge of other agents' positions and velocities. Noise can degrade performance.
• Dense Environments: In extremely crowded scenarios, the convex feasible region can become empty, requiring a fallback strategy.

The core ORCA framework has been extensively extended to address its limitations and apply it to new domains:

• NH-ORCA: For non-holonomic robots (e.g., cars, differential-drive robots).
• 3D ORCA: For aerial vehicles (drones).
• Pedestrian Simulation: The RVO2 Library is a widely used implementation for simulating human crowd movement.
• Integration with Global Planners: ORCA is often used as a local, reactive collision avoidance layer within a hierarchical architecture, where a global planner (like A* or RRT) provides the high-level path and preferred velocity.

It is a foundational technique within the broader field of Multi-Agent Path Finding (MAPF) and Decentralized Control.

Multi-Agent Path Finding (MAPF) is the centralized, discrete planning problem of computing collision-free paths for multiple agents on a graph, optimizing for metrics like makespan or sum-of-costs. Unlike reactive ORCA, MAPF typically operates in a discrete grid or roadmap and plans full paths before execution.

• Key Difference: MAPF is a planning problem (pre-computed), while ORCA is a reactive algorithm (real-time velocity selection).
• Common Algorithms: Includes Conflict-Based Search (CBS) and A*-based variants.
• Use Case: Ideal for warehouse automation where robots follow predefined lanes and schedules.

The Velocity Obstacle (VO) is the foundational geometric construct upon which ORCA is built. It defines the set of all velocities for a robot that would result in a collision with another moving object within a given time horizon.

• Core Concept: For each neighboring robot, a collision cone is computed in velocity space. Choosing a velocity outside all cones guarantees collision avoidance.
• ORCA's Advancement: ORCA improves upon basic VO by computing the optimal reciprocal half-plane, ensuring a mutually collision-free velocity is always available if one exists.
• Basis: Essential for understanding the mathematical principles of decentralized, velocity-based collision avoidance.

Decentralized control is a system architecture where each robot makes autonomous decisions based on local sensor data and limited communication, without a central orchestrator. ORCA is a canonical example of a decentralized algorithm for collision avoidance.

• Key Benefits: Scalability, as computation is distributed, and robustness, as there is no single point of failure.
• Contrast with Centralized: Centralized systems (like some MAPF solvers) have global knowledge but face computational bottlenecks and latency issues with large teams.
• Application: Fundamental to swarm robotics, autonomous vehicle fleets, and any large-scale multi-robot system.

Reactive navigation refers to motion strategies where a robot's actions are determined by immediate sensor inputs without maintaining a world model or long-term plan. ORCA is a highly sophisticated form of reactive navigation for dynamic environments.

• Characteristics: Low computational latency, minimal memory requirements, but can lead to local minima (e.g., robots getting stuck).
• Other Methods: Includes Potential Fields and simple Bug Algorithms.
• Hybrid Systems: Often combined with a global planner (e.g., A*) where the global planner provides a guiding path and ORCA handles local dynamic obstacles.

Formation control is the problem of coordinating a team of robots to achieve and maintain a specific geometric shape (e.g., a line, wedge, or circle) while in motion. ORCA can serve as a safety layer within formation control architectures.

• Primary Goal: Maintain relative positions between robots despite external disturbances.
• Approaches: Includes Leader-Follower, Virtual Structure, and Behavior-Based methods.
• Integration with ORCA: A formation controller generates desired velocities to maintain shape, which are then fed into ORCA to ensure they are collision-free with respect to teammates and external obstacles.

Model Predictive Control (MPC) is an advanced control technique that repeatedly solves a finite-horizon optimization problem using an internal dynamic model to predict future states. It can be integrated with or serve as an alternative to ORCA for multi-robot coordination.

• Key Feature: Explicitly handles system dynamics and constraints (e.g., acceleration limits).
• Comparison to ORCA: MPC is more computationally intensive but can produce smoother, more optimal trajectories over a horizon. ORCA is lighter and guarantees real-time performance.
• Hybrid Use: MPC can be used for high-level trajectory generation, with ORCA acting as a fast, certifiable safety controller.