Collision Detection

Collision detection is typically performed in two stages to optimize performance.

• Broad Phase: Quickly identifies pairs of objects that are potentially colliding using computationally cheap bounding volumes (like Axis-Aligned Bounding Boxes - AABBs). This culls obviously non-intersecting pairs.
• Narrow Phase: Performs exact, precise geometric intersection tests on the candidate pairs from the broad phase. This uses algorithms like the Gilbert–Johnson–Keerthi (GJK) algorithm or Separating Axis Theorem (SAT) for convex shapes.

This hierarchical approach is critical for real-time systems with many objects, as it avoids performing O(n²) expensive narrow-phase checks.

The temporal nature of the check is a key differentiator.

• Discrete Collision Detection: Checks for intersections at discrete time steps (e.g., each simulation tick or control cycle). It can suffer from tunneling, where fast-moving objects pass through thin obstacles between checks.
• Continuous Collision Detection (CCD): Models the motion of objects between time steps, often as a swept volume. It computes the exact time of impact (TOI), preventing tunneling. CCD is essential for high-speed robotics (e.g., drone flight) and accurate physics simulation but is computationally more expensive.

Choosing between them is a trade-off between safety and computational cost.

The geometric model of an object directly impacts the algorithm choice and cost.

• Primitive Shapes: Spheres, capsules, boxes, and cylinders allow for closed-form, analytic intersection tests that are extremely fast. Robots are often approximated with collections of primitives.
• Convex Polyhedra: More general than primitives. Efficient algorithms like GJK and EPA (Expanding Polytope Algorithm) are used for intersection and penetration depth calculation.
• Concave (Non-Convex) Meshes: Represent complex geometry (e.g., a detailed robot gripper). They require decomposition into convex parts (convex decomposition) or slower, more general methods like triangle-triangle intersection tests.
• Signed Distance Fields (SDFs): Represent space as a grid of distances to surfaces. Collision checking becomes a fast lookup, and penetration depth is readily available, useful for optimization and control.

The assumed behavior of obstacles dictates algorithmic strategy.

• Static Environments: The obstacle map is fixed. This allows for extensive precomputation, such as building spatial acceleration structures (Bounding Volume Hierarchies - BVHs, kd-trees, octrees) that are queried during runtime for fast broad-phase culling.
• Dynamic Environments: Obstacles can move. This invalidates precomputed structures, requiring incremental updates or algorithms designed for moving objects, like Dynamic AABB Trees. It also introduces the challenge of predicting future obstacle states for proactive avoidance, linking collision detection to motion planning.

Relates to the certainty and completeness of the collision check.

• Deterministic (Exact): Algorithms that provide a definitive yes/no answer and often exact contact data (penetration depth, contact normal). Used for physics simulation and precise manipulation where exact contact resolution is required.
• Probabilistic (Approximate): Used in sampling-based motion planning (e.g., RRT, PRM). A collision checker is queried millions of times. For complex geometry, an exact check may be too slow. Instead, a probabilistic collision detector may sample points on the robot's surface, providing a high-confidence (but not guaranteed) answer much faster, trading perfect accuracy for planning speed.

Collision detection is not an isolated module but deeply integrated into the planning pipeline.

• Validity Checking: The core service: answering isStateValid(config) or isPathValid(trajectory) for a planner.
• Distance Queries: Beyond binary checks, many planners need distance-to-collision or penetration depth. This gradient information is used by gradient-based optimizers (e.g., CHOMP, STOMP) to push trajectories out of collision.
• Time Parameterization: After a geometric path is found, it must be assigned speeds and timings. Collision-aware time parameterization uses velocity-dependent swept volumes and CCD to ensure the final trajectory is dynamically feasible and safe.

Efficient collision checking is often the bottleneck in motion planning systems.

For a robot to manipulate objects, it must understand spatial relationships. Collision detection is used for:

• Grasp Synthesis: Evaluating candidate gripper poses to avoid colliding with the object or the environment.
• Task and Motion Planning (TAMP): Sequencing manipulation actions where each step must be collision-free.
• Contact State Estimation: Determining if and how the end-effector is touching an object, which is critical for force-controlled operations like insertion or assembly. Here, collision models often incorporate tolerances and Signed Distance Fields (SDFs) to measure proximity, not just binary contact.

Self-driving cars and drones use collision detection at multiple levels of their autonomy stack:

• Global Path Planning: Finding a coarse, obstacle-free route using map data.
• Local Perception & Prediction: Using sensor data (LiDAR, radar) to dynamically construct a representation of nearby obstacles (often as bounding boxes or occupancy grids) for continuous collision checking.
• Emergency Braking & Evasion: Executing last-minute, safety-critical maneuvers. The challenge scales with speed and requires probabilistic checks to account for sensor noise and prediction uncertainty.

In industrial engineering, collision detection prevents costly errors:

• Assembly Planning: Verifying that parts can be assembled in a specified sequence without interference.
• CNC Toolpath Verification: Simulating the milling tool's movement to prevent collisions with the workpiece or machine fixtures.
• Robotic Cell Layout: Ensuring industrial robots have sufficient clearance from walls, other robots, and human workers. These applications often use precise, tessellated mesh representations of parts and require static and kinematic collision checks.

This domain demands extremely high-speed collision detection for realism and interactivity:

• Rendering & Physics: Determining object interactions for realistic physics simulations (ragdolls, destruction).
• Character Animation: Enabling inverse kinematics (IK) solvers to position characters without interpenetration (e.g., feet sliding into floors).
• User Interaction: Detecting clicks, grabs, and raycasts in VR/AR environments. Efficiency is paramount, leading to widespread use of broad-phase algorithms (like BVH trees) to quickly cull impossible collisions before precise narrow-phase checks.

The Configuration Space (C-Space) is a mathematical transformation where every possible state of a robot (its joint angles, position, orientation) is mapped to a single point. This simplifies collision checking from complex 3D geometry to a point-in-region test. Obstacles in the physical world become forbidden regions, or C-obstacles, within this abstract space. Planning algorithms like RRT and PRM operate directly in C-Space to find paths where the robot, represented as a point, never enters these forbidden zones.

A Signed Distance Field (SDF) is a volumetric data structure that, for any point in 3D space, stores the Euclidean distance to the nearest object surface. The sign indicates whether the point is inside (negative) or outside (positive) an object. SDFs provide a continuous, differentiable representation of geometry, enabling:

• Efficient proximity queries for collision detection.
• Gradient information for optimization-based planners to push trajectories away from obstacles.
• Smooth cost functions in trajectory optimization, penalizing proximity to surfaces.

Rapidly-exploring Random Tree (RRT) is a sampling-based motion planning algorithm designed for high-dimensional spaces. It incrementally builds a tree of collision-free configurations, randomly exploring the C-Space. At each iteration:

1. A random sample is drawn from C-Space.
2. The nearest node in the existing tree is found.
3. A new node is created by extending from the nearest node toward the random sample.
4. The new edge is validated via collision detection. If collision-free, it's added to the tree. This process continues until a node is placed near the goal. RRT is probabilistically complete, meaning it will find a path if one exists, given enough time.

Probabilistic Roadmap (PRM) is a sampling-based planner that operates in two phases: a learning phase and a query phase.

• Learning Phase: Random, collision-free robot configurations (nodes) are sampled in C-Space. Nearby nodes are connected with local paths, each rigorously checked with collision detection, forming a graph (the roadmap).
• Query Phase: Given a specific start and goal, they are connected to the roadmap, and a standard graph search (e.g., A*) finds a path. PRM is efficient for multiple queries in static environments, as the computationally expensive collision checking is performed once during roadmap construction.

The Velocity Obstacle (VO) is a geometric method for local, reactive collision avoidance with moving obstacles. It works in the robot's velocity space. For each dynamic obstacle, the VO defines the set of all robot velocities that would cause a collision within a specified time window (τ). The core principle:

• The robot selects a new velocity from outside the union of all Velocity Obstacles.
• This velocity is also constrained by the robot's dynamics and kinematic limits. Methods like the Dynamic Window Approach (DWA) use this concept to find safe, reachable velocities in real-time, relying on continuous collision detection predictions.

A Control Barrier Function (CBF) is a mathematical formalism for synthesizing safety-critical controllers. It defines a safety set (e.g., all states where the robot is collision-free) using a continuously differentiable function. The controller is designed to ensure this function's derivative along the system's trajectories keeps it positive, thereby guaranteeing the state remains in the safe set. CBFs provide a formal proof of collision avoidance when integrated with a motion planner or controller, moving beyond heuristic collision checks to provably safe control laws.