Collision Avoidance

Collision avoidance systems operate on a spectrum from purely reactive to proactively predictive.

• Reactive Control (e.g., Artificial Potential Fields) generates repulsive forces from nearby obstacles in real-time, providing immediate safety but can lead to local minima (getting stuck).
• Predictive Planning integrates with a world model to anticipate obstacle trajectories, allowing the system to plan smoother, globally optimal paths. Modern systems often blend both approaches, using reactive layers as a safety-critical fallback for a predictive planner.

A foundational mathematical technique that transforms the physical robot and environment into an abstract space where planning occurs.

• Each point in C-Space represents a unique robot configuration (e.g., all joint angles).
• Physical obstacles are inflated and mapped to forbidden regions (C-obstacles) in this space.
• This reduces the problem of planning for a multi-jointed arm to finding a path for a single point through the C-Space, simplifying collision checking. The complexity of C-space grows exponentially with the robot's degrees of freedom (the curse of dimensionality).

The dominant algorithmic family for high-dimensional motion planning, which probes the free space rather than modeling obstacles explicitly.

• RRT (Rapidly-exploring Random Tree) and its variants (like RRT*) grow a tree of random, collision-free configurations from the start state until it connects to the goal region. It is probabilistically complete.
• PRM (Probabilistic Roadmap) builds a graph of random configurations in a pre-processing phase, which is then queried for specific start-goal pairs. This is efficient for multiple queries in static environments.
• These algorithms are central to Task and Motion Planning (TAMP), where discrete task sequences must be paired with continuous collision-free motions.

The capability to avoid moving obstacles, such as people, vehicles, or other robots, which is essential for deployment in human environments.

• Requires real-time perception (e.g., LiDAR, depth cameras) and tracking to estimate obstacle velocity and predict future states (trajectory prediction).
• Algorithms like Velocity Obstacles (VO) and its modern variant, Reciprocal Velocity Obstacles (RVO), directly compute velocity vectors that will lead to a collision and select safe alternatives. This is crucial for multi-agent navigation in warehouses or hospitals.
• These methods are often integrated with Model Predictive Control (MPC) to optimize smooth, safe trajectories over a finite time horizon.

Collision avoidance is not an isolated function but is deeply intertwined with high-level task decomposition and logic.

• A Hierarchical Task Network (HTN) planner might decompose "fetch object from shelf" into subtasks. Each subtask (e.g., "navigate to shelf," "reach for object") must have its motion plans validated for collisions.
• This integration is the core challenge of Task and Motion Planning (TAMP): simultaneously reasoning about discrete symbolic actions (e.g., grasp(block_A)) and the continuous geometric feasibility of those actions.
• Failure at the motion level (e.g., an unreachable grasp) must trigger replanning at the task level.

The runtime layer that ensures the planned collision-free trajectory is executed safely despite sensor noise, model inaccuracies, and true environmental surprises.

• Execution Monitoring continuously compares expected sensor readings against real observations to detect anomalies, such as an unexpected obstacle entering the path.
• Upon detecting a potential collision, the system must invoke replanning or trigger a pre-defined safety behavior (e.g., a protective stop).
• This forms a closed-loop sense-plan-act cycle where collision avoidance is the perpetual background process, often implemented with a high-frequency reactive control loop running in parallel with a slower deliberative planning loop.

This method treats obstacles as repulsive forces and the goal as an attractive force, generating a resultant virtual force that guides the robot. The robot's velocity is directly proportional to this force.

• Attractive Potential: Pulls the robot toward the goal position.
• Repulsive Potential: Pushes the robot away from detected obstacles, with strength inversely proportional to distance.
• Key Limitation: Can create local minima where attractive and repulsive forces cancel, trapping the robot. Often combined with global planners to escape these traps.

A velocity-space sampling algorithm used for differential-drive and holonomic robots. It operates in a short time horizon by:

1. Sampling feasible velocities within dynamic constraints (max acceleration/deceleration).
2. Simulating trajectories for each velocity pair (v, ω) over a brief window.
3. Scoring trajectories based on:
   • Goal heading: Alignment with the target.
   • Clearance: Distance to the nearest obstacle.
   • Velocity: Preference for higher speeds.
4. Executing the optimal velocity for one control cycle before re-planning.

This makes DWA highly responsive to dynamic environments but inherently short-sighted.

A geometric formalism for multi-agent collision avoidance. For each moving obstacle, a Velocity Obstacle (VO) cone is constructed in the robot's velocity space. Any velocity selected from within this cone will lead to a collision within a specified time horizon (τ).

• Collision-Free Navigation: The robot selects any velocity outside all VO cones.
• Reciprocal Velocity Obstacle (RVO): An extension where agents share responsibility, assuming the other will also avoid. This leads to smoother, more predictable maneuvers in dense crowds (e.g., warehouse AMR fleets).
• ORCA (Optimal Reciprocal Collision Avoidance): A linear programming formulation of RVO that efficiently computes the optimal collision-avoiding velocity.

MPC formulates collision avoidance as a constrained optimization problem solved in real-time over a receding horizon.

• At each time step, MPC solves for a sequence of control inputs that minimizes a cost function (e.g., deviation from path, control effort) while satisfying hard constraints (e.g., minimum distance from obstacles, joint limits).
• Key Advantage: It explicitly accounts for the robot's dynamics and future states, producing smoother, more physically feasible trajectories than geometric methods.
• Computational Challenge: Solving the optimization within the control loop's latency budget (often <100ms) requires efficient solvers and simplified models.

Neural network policies, typically trained via Reinforcement Learning (RL) or Imitation Learning, map raw sensor observations (e.g., lidar scans, camera images) directly to steering or velocity commands.

• Pro: Can learn complex, nuanced avoidance behaviors from experience that are difficult to hand-code.
• Con: Verification and safety guarantees are extremely challenging. These 'black-box' policies may fail unpredictably in unseen scenarios.
• Common Architecture: A Visuomotor Control Policy uses a convolutional neural network (CNN) to process visual input, followed by fully connected layers to output motor commands.
• Safety Layer: Often deployed with a handcrafted safety controller (e.g., a simple potential field) that overrides the learned policy if an imminent collision is detected.

Reliable avoidance depends on accurate, low-latency perception of the environment. No single sensor is sufficient.

• Lidar: Provides precise, long-range distance measurements for geometric mapping and obstacle detection. Essential for constructing local costmaps.
• Depth Cameras (RGB-D): Provide dense 3D point clouds, useful for identifying low-lying or complex-shaped obstacles that lidar might miss.
• Ultrasonic Sensors: Effective at very short ranges and for detecting transparent objects (like glass) that confound optical sensors.
• Sensor Fusion Pipeline: Data from all sensors is typically fused into a unified 2D or 3D occupancy grid (costmap), where each cell has a cost value representing the probability of occupancy or collision danger.

The overarching algorithmic process of computing a sequence of valid configurations for a robot to move from a start to a goal state. It encompasses path planning (finding a geometric route) and trajectory generation (adding timing and dynamics). Collision avoidance is a core constraint within any motion planning problem, ensuring the computed path lies within the free space of the environment.

A fundamental mathematical abstraction where every possible pose of a robot is mapped to a single point. Physical obstacles in the world become forbidden regions (C-obstacles) in this space. Motion planning, and thus collision avoidance, is transformed into the problem of finding a path for a point robot through the free regions of C-space. This representation is crucial for sampling-based planners like RRT and PRM.

A specific subproblem of motion planning focused on finding a purely geometric, collision-free route through an environment. It does not consider dynamics, timing, or velocity. Common algorithms include:

• A*: A heuristic graph search algorithm optimal for finding shortest paths on a discrete grid.
• RRT (Rapidly-exploring Random Tree): A sampling-based algorithm efficient for high-dimensional spaces.
• PRM (Probabilistic Roadmap): A method that builds a graph of collision-free samples in a preprocessing phase for fast online queries.

The process of computing a time-parameterized path (a trajectory) that minimizes a cost function—such as energy, time, or jerk—while satisfying dynamic constraints (e.g., torque limits) and enforcing collision avoidance. Unlike pure path planning, it produces smooth motions executable by physical hardware. Model Predictive Control (MPC) is a real-time, receding-horizon variant of trajectory optimization used for dynamic collision avoidance.

The computational geometry process that determines whether two or more objects (or a robot and its environment) intersect or are in contact. It is the enabling primitive for collision avoidance. Methods range from simple bounding volume checks (spheres, boxes) for broad-phase culling to precise convex decomposition and GJK (Gilbert–Johnson–Keerthi) algorithms for exact contact determination. Real-time performance is critical for reactive avoidance systems.

The higher-level processes that manage collision avoidance within a dynamic world. Execution monitoring observes the robot's state and sensor streams to detect deviations from the expected plan or the appearance of new obstacles. When a collision risk is detected or the current plan becomes invalid, replanning is triggered. This involves invoking the motion planner from the robot's current state to compute a new, safe trajectory, closing the perception-planning-action loop.