Timed Elastic Band (TEB)

The core data structure is an elastic band, a discrete sequence of robot poses (x, y, θ) connected by springs and damping elements. This representation allows the algorithm to 'stretch' and 'bend' the initial path.

• Springs penalize the distance between consecutive poses, encouraging path shortening.
• Damping elements penalize changes in velocity between poses, promoting smooth motion.
• The band is deformed via gradient descent to minimize a total cost function, balancing path length, smoothness, and obstacle clearance.

Unlike purely geometric planners, TEB incorporates time as a first-class optimization variable. Each pose in the elastic band has an associated time stamp ΔT_i.

• This allows TEB to directly optimize for kinodynamic feasibility, ensuring the planned velocities and accelerations between poses respect the robot's dynamic limits.
• The optimizer can trade off spatial path length against traversal time, enabling time-optimal planning.
• Temporal constraints, such as maximum velocity or desired arrival time, are naturally integrated into the cost function.

TEB performs a weighted optimization across several competing objectives. The total cost is a sum of individual penalty terms:

• Path Length: Minimizes the total Euclidean distance traveled.
• Smoothness: Penalizes high curvature and abrupt changes in velocity/acceleration.
• Obstacle Clearance: Uses a repulsive potential field or minimum distance constraint to keep the band away from obstacles.
• Kinematic/Dynamic Constraints: Hard or soft constraints on maximum velocity, acceleration, and turning radius.
• Time Optimality: Penalizes total traversal time. The weights allow engineers to prioritize, e.g., smoothness over speed for a delicate payload.

TEB formulates trajectory deformation as a Nonlinear Programming (NLP) problem. It uses efficient gradient-based solvers like Levenberg-Marquardt or Gauss-Newton from libraries such as g2o or Ceres Solver.

• The solver iteratively adjusts all poses and time stamps to minimize the total cost.
• Sparsity in the problem's Jacobian matrix (each pose only affects a local neighborhood) is exploited for real-time performance.
• This approach allows TEB to handle complex, non-convex constraints that are difficult for graph-search methods.

TEB is primarily a local planner. It requires a kinematically feasible initial guess, typically provided by a global planner (e.g., A*, Dijkstra, RRT*).

• The global planner finds a topologically correct, coarse path from start to goal.
• TEB then locally optimizes this path, smoothing it, adding time information, and adapting it to dynamic obstacles.
• This hybrid architecture combines the global foresight of graph search with the local, constraint-aware optimization of TEB.

TEB supports real-time replanning in dynamic environments by incorporating moving obstacle predictions.

• Obstacle trajectories (position over time) are modeled and added as time-dependent constraints to the optimization problem.
• The solver can deform the elastic band in both space and time to find a collision-free trajectory, potentially slowing down or speeding up to avoid conflicts.
• This is a key advantage over purely reactive methods like Dynamic Window Approach (DWA), as TEB plans a consistent, look-ahead trajectory rather than just selecting the next velocity.

For industrial vehicles with more complex kinematics (e.g., car-like Ackermann steering or differential-drive forklifts), TEB provides precise trajectory control.

• It respects the vehicle's specific non-holonomic constraints, preventing commands that would require sideways sliding.
• Optimizes for time-efficient docking and precise loading/unloading maneuvers.
• Incorporates temporal constraints to synchronize with conveyor belts or other automated systems in a just-in-time manufacturing workflow.

This application is critical for automated storage and retrieval systems (AS/RS) and flexible manufacturing lines.

Unlike purely geometric planners, TEB's optimization framework explicitly incorporates predictions of moving agents.

• By modeling dynamic obstacles within its cost function, TEB can compute velocities that proactively steer clear of predicted collision points.
• It performs local re-planning at high frequency (10-100 Hz), allowing it to react to sudden changes, such as a person stepping into the path.
• This makes it ideal for last-mile delivery robots navigating sidewalks and airport baggage carts moving among passengers.

TEB can be extended for coordinating small groups of robots that must maintain a specific spatial formation while navigating.

• A virtual structure approach defines the formation relative to a leader or a virtual reference point.
• Individual TEB instances for each robot optimize their local trajectories while incorporating additional cost terms to penalize deviations from their assigned position in the formation.
• This is used for applications like convoying in logistics yards or coordinated sensor deployment in search and rescue scenarios.

TEB functions as the trajectory generator within a larger Model Predictive Control (MPC) or Receding Horizon Control architecture.

• A higher-level planner or policy sets the intermediate goals (the 'band's' end-point).
• TEB rapidly solves the local optimization problem over the short-term horizon, providing a feasible, optimized trajectory.
• The first segment of this trajectory is executed, and the process repeats. This hybrid approach combines the reactivity of TEB with the long-horizon reasoning of MPC, used in complex scenarios like autonomous valet parking.

TEB enables smooth and natural following behaviors for robots that accompany humans.

• The goal pose for the TEB optimizer is continuously updated based on the tracked position of the person, maintaining a set following distance.
• The optimization ensures the robot's motion remains predictable and non-threatening to the human, avoiding sudden accelerations or sharp turns.
• Similarly, in shared control teleoperation, TEB can smooth and correct a human operator's joystick commands to ensure kinematic feasibility and obstacle avoidance, enhancing safety and ease of use.

A reactive collision avoidance algorithm that selects optimal robot velocities by evaluating a dynamic window of admissible speeds over a short time horizon. It directly considers the robot's kinematic constraints (max velocity, acceleration) and immediate obstacle proximity.

• Core Mechanism: Simulates short-term trajectories for sampled velocity pairs (v, ω), scores them based on goal heading, clearance, and speed, and selects the highest-scoring command.
• Contrast with TEB: DWA is purely reactive and short-sighted, while TEB performs local optimization over a longer, deformable trajectory, balancing smoothness and global path adherence.

An advanced control paradigm where a dynamic model of the system is used to predict future states and solve a finite-horizon optimization problem at each control step to determine optimal actions. The first action is executed, and the process repeats (receding horizon control).

• Mathematical Foundation: Solves a constrained optimization problem at each timestep, minimizing a cost function (e.g., tracking error, control effort) subject to system dynamics and constraints.
• Relation to TEB: TEB is a specific instance of MPC applied to local trajectory deformation. It uses a parameterized band (the elastic band) as its prediction model and optimizes its control points.

The problem of finding a trajectory that satisfies both kinematic constraints (e.g., non-holonomic wheeled motion) and dynamic constraints (e.g., acceleration, torque limits). It moves beyond pure geometric path planning to generate physically executable motions.

• Key Challenge: The search space includes full state (pose, velocities) and is subject to differential constraints derived from physics.
• TEB's Role: TEB is a kinodynamic planner. Its optimization explicitly incorporates velocity and acceleration terms, ensuring the deformed trajectory respects the robot's dynamic capabilities.

Geometric frameworks for collision avoidance among moving agents. Velocity Obstacles defines the set of relative velocities that would cause a collision within a time window. Optimal Reciprocal Collision Avoidance (ORCA) is a decentralized, reactive algorithm where agents independently select velocities from mutually collision-free sets.

• Reactive vs. Optimizing: VO/ORCA are instantaneous velocity selectors. TEB is a trajectory optimizer that can incorporate similar collision constraints over its entire planning horizon, leading to smoother, more anticipatory avoidance.

A mathematical tool from control theory used to synthesize controllers that provably keep a dynamical system within a safe set. A CBF defines a constraint on the system's derivatives that, if enforced, guarantees forward invariance of the safe region.

• Formal Safety Guarantees: Provides a framework for certifiable safety, unlike heuristic methods.
• Integration with TEB: CBFs can be incorporated as hard constraints within the TEB optimization problem, transforming soft penalty terms for obstacle proximity into formally verified safety constraints.

A short, kinematically and dynamically feasible trajectory segment that serves as a building block for complex paths. Primitives are often precomputed and stored in a library for use in lattice-based planners.

• Usage: Planners search over sequences of primitives to connect start and goal states.
• Contrast with TEB: TEB does not use a discrete library of primitives. Instead, it continuously deforms a parameterized trajectory. However, the initial guess provided to TEB is often generated by a planner that may use motion primitives.