Velocity Obstacle (VO)

The Velocity Obstacle for agent A with respect to agent B is defined as the set of all velocities for A that would cause a collision with B within a specified time horizon (τ). It is constructed by taking the Minkowski sum of agent B's shape with agent A's shape, then translating this combined shape into velocity space. Any velocity vector for A that originates from its current velocity and points into this VO region is guaranteed to cause a future collision if B maintains its current velocity.

The Reciprocal Velocity Obstacle (RVO) is a critical extension that assumes cooperative behavior. Instead of one agent bearing full responsibility for avoidance, RVO models the assumption that both agents will share the effort. The algorithm calculates a new, collision-free velocity for each agent that is the average of its preferred velocity and the velocity that would avoid the other agent if it were stationary. This leads to more natural, symmetric, and oscillation-free maneuvers, forming the basis for many modern multi-robot navigation libraries.

Optimal Reciprocal Collision Avoidance (ORCA) is the predominant algorithm derived from VO theory. It transforms the VO problem into a linear programming optimization. For each neighboring agent, ORCA defines a half-plane of permissible velocities that guarantees collision avoidance under reciprocal assumptions. The intersection of all these half-planes forms the ORCA feasible region. The agent then selects the new velocity closest to its preferred velocity within this region, ensuring optimal and provably collision-free navigation in dense, dynamic settings.

The time horizon (τ) is a crucial parameter that defines how far into the future the algorithm predicts collisions. It directly shapes the size of the VO region. A larger τ makes the VO larger and the agent more cautious. Geometrically, the VO for a point agent is a collision cone in velocity space—a cone whose apex is at the agent's current velocity and whose sides are tangent to the expanded obstacle. Velocities inside this cone lead to a collision before time τ. This cone visualization is key to understanding the algorithm's reactive nature.

VO-based methods are fundamentally distributed and reactive. Each agent performs its own calculations based solely on the observed positions and velocities of nearby agents, without centralized coordination or long-term path planning. This makes the approach highly scalable and robust to dynamic changes. However, it is generally non-optimal in a global sense and can lead to local minima (e.g., agents becoming trapped in symmetric scenarios) because it lacks long-horizon reasoning.

In practice, VO/RVO/ORCA is rarely used in isolation. It is typically deployed in a hierarchical architecture alongside a global path planner (e.g., A* on a static map). The global planner computes an optimal path to the goal, while the local VO-based controller handles dynamic obstacle avoidance in real-time, deviating from the planned path as necessary. This combines the benefits of global optimality with local reactivity, which is the standard paradigm for autonomous navigation in warehouses and crowded environments.

Multi-Agent Path Finding (MAPF) is the centralized, discrete optimization problem of finding collision-free paths on a graph for multiple agents from their start to goal vertices. It is a broader planning paradigm within which Velocity Obstacle methods provide a continuous, reactive layer.

• Centralized vs. Decentralized: MAPF is typically solved centrally with full world knowledge, producing a complete plan. VO is a decentralized, reactive policy for continuous spaces.
• Planning Horizon: MAPF plans to completion. VO plans over a short, fixed time horizon (tau).
• Integration: Modern systems often use a hierarchical approach: a MAPF solver provides high-level waypoints, and VO (or ORCA) handles low-level, continuous navigation and dynamic obstacle avoidance.

Conflict-Based Search (CBS) is a leading optimal algorithm for solving the Multi-Agent Path Finding (MAPF) problem. It employs a two-level search to resolve conflicts, which are violations similar to those VO aims to prevent.

• High-Level: Searches a constraint tree, where each node contains a set of constraints (e.g., "Agent A cannot be at vertex V at time T") imposed to resolve conflicts found in the solution.
• Low-Level: For each agent, a single-agent path planner (like A*) finds an optimal path that respects its set of constraints.
• Relation to VO: CBS resolves vertex conflicts (same place, same time) and edge conflicts (swapping positions). VO handles the continuous analogue: velocities that cause an intersection of agent footprints within time tau. CBS is a planning framework; VO is an avoidance mechanism.

Kinodynamic Planning is the problem of finding trajectories that are not only collision-free but also satisfy the kinematic (e.g., non-holonomic constraints like a car's turning radius) and dynamic (e.g., acceleration, velocity limits) constraints of a physical robot.

• Beyond Geometry: VO is primarily a geometric construct. Kinodynamic planning incorporates the physics of motion.
• State Lattices: A common solution approach uses a State Lattice, a graph where nodes are feasible kinematic states (pose, velocity) and edges are motion primitives that obey dynamics.
• Integration with VO: The Velocity Obstacle must be computed within the feasible velocity space of the agent, which is often a subset of all geometrically possible velocities due to dynamic limits. This transforms the VO from a cone in velocity space to a more complex, constrained region.

Safe Interval Path Planning (SIPP) is an efficient algorithm for planning in environments with dynamic obstacles whose movements are known or predictable. It compresses the search space by reasoning about time in intervals rather than discrete steps.

• Core Concept: Instead of planning in a Time-Expanded Graph (location x time), SIPP groups time at each location into safe intervals—continuous periods where the location is unoccupied by a dynamic obstacle.
• Efficiency: This dramatically reduces the number of states the planner must consider compared to a full temporal expansion.
• Relation to VO: Both reason about future occupancy. SIPP is a centralized planning method for known moving obstacles. VO is a decentralized, reactive method for unknown or less-predictable moving agents. They address similar challenges from different algorithmic perspectives.

Sum of Costs (SOC) and Makespan are the two primary performance metrics for evaluating solutions in Multi-Agent Path Finding, providing a quantitative framework that reactive methods like VO indirectly influence.

• Sum of Costs (SOC): Also called Flowtime. Defined as the sum of the path lengths (or travel times) for all individual agents from start to goal. Minimizing SOC improves total fleet efficiency.
• Makespan: Defined as the total time elapsed from the start until the last agent reaches its goal. Minimizing makespan improves overall task completion time.
• VO's Role: While VO itself is not an optimizer for these metrics, the velocities it permits or prohibits directly determine an agent's travel time. Integrating VO with a planner that optimizes for SOC or Makespan is a key systems engineering challenge.