Decentralized Collision Avoidance

At unsignalized intersections, Connected and Autonomous Vehicles (CAVs) can negotiate right-of-way without traffic lights using decentralized protocols. Vehicles broadcast their trajectory predictions and intent via Vehicle-to-Everything (V2X) communication. Each vehicle then independently solves a local optimization (often using Model Predictive Control (MPC)) to adjust speed and yield, creating a fluid 'virtual roundabout' that maximizes throughput and safety.

ORCA is the formal, velocity-based algorithm that underpins most modern decentralized collision avoidance systems. It provides provable, collision-free navigation for multiple agents by efficiently computing a half-plane of permitted velocities for each agent, assuming reciprocal cooperation. Unlike simpler methods, ORCA guarantees safety and convergence for holonomic agents.

• Key Mechanism: Each agent calculates a set of infeasible velocities (Velocity Obstacles) based on the positions and velocities of nearby agents. ORCA then finds the optimal new velocity closest to the agent's preferred velocity that lies outside all infeasible sets.
• Assumption: Requires all agents to run a compatible algorithm and share responsibility for avoidance.
• Application: Foundational for robot fleets in warehouses, drone swarms, and crowd simulation.

The Velocity Obstacle (VO) is the fundamental geometric construct from which algorithms like ORCA are derived. For a given agent, the VO defines the set of all velocities that would result in a collision with another moving obstacle within a specified time horizon (τ).

• Core Concept: Visualized as a cone emanating from the agent's position in velocity space. Any velocity vector pointing into this cone leads to a future collision.

• Decentralized Use: Each agent independently computes VOs for all perceived obstacles. Its collision avoidance logic then selects a new velocity outside the union of all VOs.

• Limitation: The basic VO formulation does not assume cooperation, which can lead to oscillatory 'reciprocal dances' between two agents.

MPC is an optimization-based control strategy often used as a higher-level complement to reactive decentralized methods. It repeatedly solves a finite-horizon optimal control problem to compute a sequence of control inputs that satisfies dynamic constraints and avoids predicted collisions.

• Predictive vs. Reactive: While ORCA/RVO react to the current state, MPC plans a short-term trajectory, allowing it to better handle complex kinematic/dynamic constraints and anticipate interactions.

• Hybrid Architectures: A common design uses a decentralized algorithm (e.g., ORCA) to define collision constraints within the MPC's optimization problem, blending reactive safety with predictive optimality.

• Application: Used for autonomous vehicles and mobile robots where smooth, dynamically feasible trajectories are critical.

TTC and CPA are the fundamental risk assessment metrics that feed decentralized decision-making.

• Time to Collision (TTC): Estimates the time until collision if two agents continue on their current relative velocity vector. A core trigger for avoidance maneuvers.

• Closest Point of Approach (CPA): Comprises two values:

  • DCPA: The predicted minimum future distance between two agents.
  • TCPA: The time until that minimum distance is reached.

• Role in Decentralized Systems: Each agent continuously calculates TTC/CPA for nearby agents using its local sensor data. These metrics prioritize threats (low TTC, small DCPA) and determine the urgency of the avoidance response, often parameterizing the τ (time horizon) in VO/ORCA calculations.

Runtime Assurance (RTA) is a safety architecture designed to provide a formal safety guarantee for complex, potentially learning-based primary controllers. In a decentralized context, RTA acts as a verified safety filter.

• Architecture: The primary controller (e.g., a neural network planner) generates a desired command. A separate, simpler, and formally verified safety monitor (often using a decentralized algorithm like ORCA) checks if this command is safe. If unsafe, the monitor overrides it with a provably safe alternative.

• Purpose: Enables the use of high-performance but difficult-to-verify AI models while guaranteeing that low-level collision avoidance properties are never violated.

• Critical for Certification: This 'simplex' architecture is key to deploying autonomous systems in safety-critical domains like aviation and automotive.

V2X communication extends the perceptual horizon of decentralized agents beyond the line-of-sight limitations of onboard sensors, enabling cooperative collision avoidance.

• Protocols: Uses dedicated short-range communications (DSRC) or cellular-V2X (C-V2X) to broadcast Basic Safety Messages (BSMs).

• Message Content: Includes precise position, velocity, acceleration, and vehicle intent.

• Impact on Decentralized Avoidance: Agents receive BSMs from occluded or distant vehicles, allowing them to incorporate these agents into their local VO/ORCA calculations much earlier. This transforms the problem from sensor-based decentralized avoidance to cooperative decentralized avoidance, significantly improving safety and traffic flow at intersections and in adverse weather.

• Standard: Defined by the IEEE 1609 (Wireless Access in Vehicular Environments - WAVE) suite.