Collision Avoidance

The computational foundation of collision avoidance, determining if two or more rigid bodies intersect in space. This process is typically divided into two phases:

• Broad Phase: Quickly eliminates pairs of objects that are too far apart to collide using bounding volume hierarchies (BVH) like Axis-Aligned Bounding Boxes (AABB) or Oriented Bounding Boxes (OBB).
• Narrow Phase: Performs precise intersection tests on remaining pairs. The Gilbert-Johnson-Keerthi (GJK) algorithm is the industry standard for computing the minimum distance between convex shapes, while the Expanding Polytope Algorithm (EPA) calculates penetration depth.
• Discrete vs. Continuous: Discrete checking samples at timesteps and can miss fast-moving objects (tunneling). Continuous Collision Detection (CCD) sweeps the volume between states to guarantee no intersection is missed.

A volumetric representation where each voxel in a 3D grid stores the shortest distance to the nearest obstacle surface. Negative values indicate interior points, and positive values indicate free space.

• Efficient Queries: Collision checking becomes a simple O(1) lookup—if the SDF value at a robot's sampled configuration is negative, a collision exists.
• Gradient Information: The gradient of the SDF provides the direction to the nearest obstacle, which is directly usable as a repulsive force in trajectory optimization and reactive control.
• Precomputation Trade-off: SDFs are computationally expensive to generate for dynamic environments but provide unmatched speed for static workspaces, making them ideal for known factory floor layouts.

Path planning transforms the physical robot into a point in its Configuration Space (C-Space), where each axis represents a degree of freedom. Obstacles in the workspace are mapped to C-Space obstacles (C-obstacles) by inflating them with the robot's geometry.

• Minkowski Sum: The C-obstacle for a rigid body is the Minkowski sum of the physical obstacle and the robot's shape (reflected about its origin).
• Dimensionality Challenge: A 6-DOF industrial arm has a 6-dimensional C-Space, making explicit C-obstacle computation intractable. Sampling-based planners like RRT and PRM bypass this by checking collisions only at sampled points.
• Self-Collision: The robot's own links must also be treated as mutual obstacles, requiring pairwise collision checks between all link geometries at each configuration.

Real-time methods that modify a planned trajectory or generate control commands based on immediate sensor data, without full replanning. These are essential for handling dynamic obstacles like human workers or other AGVs.

• Artificial Potential Fields: The goal exerts an attractive force while obstacles exert repulsive forces. The robot follows the negative gradient of the combined potential field. Suffers from local minima where forces cancel.
• Vector Field Histogram (VFH): Builds a polar histogram of obstacle densities around the robot from sensor data (e.g., LiDAR). Steering commands are selected from sectors with obstacle density below a threshold, balancing goal direction and clearance.
• Dynamic Window Approach (DWA): Searches the robot's velocity space for admissible commands that bring the robot to a stop before colliding, then selects the velocity that maximizes progress toward the goal.

Formal methods that provide mathematical guarantees that a control system will never enter an unsafe state. These act as an independent safety layer decoupled from the planner.

• Control Barrier Functions (CBF): A scalar function that defines a safe set. A CBF constraint is enforced as a quadratic program at each control cycle, minimally modifying the nominal control input to guarantee forward invariance of the safe set.
• Inevitable Collision States (ICS): A state is an ICS if no sequence of future actions can avoid a collision. Safety frameworks compute the set of ICS offline and ensure the robot's reachable set never intersects it.
• Passive Safety: A weaker guarantee where the robot is allowed to collide only if it is stationary or moving below a specified energy threshold, ensuring no injury to human co-workers in human-robot collaboration scenarios.

Coordinating collision-free motion for multiple robots sharing a workspace introduces combinatorial complexity and requires resolving deadlocks.

• Prioritized Planning: Assigns a fixed priority to each agent. Higher-priority agents plan first, treating lower-priority agents as dynamic obstacles. Simple but can fail if a low-priority agent blocks a high-priority one.
• Multi-Agent Path Finding (MAPF): Computes paths for all agents simultaneously, typically on a discretized graph. Optimal MAPF is NP-hard, so solvers like Conflict-Based Search (CBS) use a two-level search: a high-level search resolves conflicts, and a low-level search finds individual paths.
• Velocity Obstacles (VO): A geometric construct representing the set of relative velocities that will cause a collision within a time horizon. The Optimal Reciprocal Collision Avoidance (ORCA) algorithm extends VO for decentralized, reciprocal avoidance without explicit communication.