Safe Interval Path Planning (SIPP)

The core innovation of SIPP is its abstraction of time into safe intervals. Instead of planning in a standard time-expanded graph where each (node, timestep) is a unique state, SIPP groups consecutive timesteps where a node is collision-free into a single interval state. This dramatically reduces the search space. Each interval is defined by its start time and end time (which can be infinity). The planner only considers transitions between these interval states, not every discrete timestep.

During the A* search, each state is a tuple of (node, interval, g-value). When expanding a state, the algorithm must compute which successor nodes are reachable within the current safe interval, considering the agent's travel time. It then intersects the arrival time window at the successor node with that node's precomputed list of safe intervals. This generates new search states only where viable, collision-free intervals exist. This process inherently respects dynamic obstacle schedules.

SIPP requires a priori knowledge of dynamic obstacle trajectories, typically provided as timed reservations on graph edges or nodes. These reservations are processed to compute the safe intervals for every node in the graph. For example, if an obstacle occupies Node A from t=2 to t=5, the safe intervals for Node A would be [0, 2) and [5, ∞). This model is ideal for environments with scheduled moving obstacles, such as other planned robots in a warehouse or trains on a network.

SIPP is provably optimal (finds the shortest possible path in space and time) and complete (finds a solution if one exists) under its assumptions. This is because the interval abstraction is a lossless compression of the time-expanded graph; no valid path is eliminated. Optimality holds given admissible heuristics (like Euclidean distance divided by max speed). This formal guarantee is critical for safety-critical applications in logistics and autonomous systems where sub-optimal paths cause inefficiency.

The primary advantage of SIPP over naive time-expanded graph search is significantly reduced computational complexity. A time-expanded graph must be unrolled to the planning horizon, creating a state for every node at every timestep. SIPP's interval-based search often reduces the number of evaluated states by one or two orders of magnitude. However, efficiency depends on the obstacle density; highly congested schedules with many short safe intervals can reduce this benefit.

In Heterogeneous Fleet Orchestration, SIPP is used as a high-level, centralized planner for scheduling priority agents (e.g., autonomous mobile robots) through spaces shared with predictable dynamic obstacles (e.g., manually operated forklifts with known routes, scheduled conveyor activity). It enables Spatial-Temporal Scheduling by providing guaranteed collision-free paths in time. The planned path's reservations then become dynamic obstacles for subsequent agent planning, often managed by a Multi-Agent Path Planning coordinator.

SIPP is a cornerstone algorithm for coordinating Autonomous Mobile Robots (AMRs) and Automated Guided Vehicles (AGVs) in distribution centers. It plans efficient paths for robots moving goods while accounting for:

• Dynamic obstacles like other robots, human workers, and temporarily parked pallets.
• Static obstacles with known schedules, such as conveyor belts that operate intermittently.
• The need for predictable throughput, as SIPP's interval-based planning allows for tight scheduling of robot arrivals at pick stations, packing areas, and charging docks.

In flexible manufacturing cells, SIPP enables heterogeneous fleets of robots (e.g., assembly arms, transport carts) to share workspace safely. Key applications include:

• Just-in-Time part delivery: Planning paths for delivery robots to arrive at a workstation precisely when the assembly robot's arm is retracted (a known safe interval).
• Tool sharing: Coordinating the movement of a mobile tool rack between multiple stationary work cells, navigating around the periodic movements of other agents.
• Deadlock prevention: By modeling other agents' reserved paths as time-bound obstacles, SIPP inherently avoids planning into conflicts that could cause system-wide gridlock.

SIPP algorithms manage the movement of autonomous vehicles within structured parking facilities. The environment is ideal for SIPP because obstacle motion is highly predictable. The system:

• Models moving cars (both human-driven and autonomous) as dynamic obstacles with planned paths to/from parking spots.
• Uses safe intervals to schedule a vehicle's traversal of shared aisles, waiting at intersections until a guaranteed clear interval is available.
• Integrates with a central fleet manager to optimize overall garage throughput, reducing the time vehicles spend searching for spots or exiting.

While not used for real-time control of manned aircraft, SIPP is a powerful tool for offline conflict resolution and airspace design. Planners use it to:

• Generate conflict-free 4D trajectories (3D space + time) for multiple aircraft in a sector, especially during dense arrival/departure sequences.
• Analyze airspace capacity by determining the maximum number of aircraft that can be safely scheduled through choke points like runway thresholds or merging waypoints.
• Validate new procedures by simulating proposed flight paths and verifying that safe separation intervals are maintained under various traffic scenarios.

Game engines utilize SIPP variants for coordinated unit movement in strategy games or for creating believable crowd simulations. The algorithm allows:

• Squads of units to navigate complex maps while maintaining formation, treating allied units as dynamic obstacles with known future positions.
• Scripted event sequencing, where NPCs move through crowded marketplaces by reasoning about the timed movements of carts or other characters.
• Efficient pathfinding for many agents by reusing the computed safe interval graph, enabling hundreds of entities to plan collision-free paths in real-time without expensive pairwise collision checks.

SIPP serves as the baseline and benchmark in academic and industrial research for temporal planning. It is the foundation for numerous advanced extensions, including:

• SIPP with Uncertainty (SIPPU): Modifies the algorithm to account for imperfect execution or sensor noise, shrinking safe intervals probabilistically.
• Multi-Agent SIPP (MA-SIPP): Coordinates plans for multiple agents from the start, searching a joint state-space to find optimal, conflict-free paths for the entire group.
• SIPP for Kinodynamic Constraints: Extends the classic graph search to incorporate acceleration and velocity limits, generating dynamically feasible trajectories that respect safe intervals. Research implementations are often benchmarked against classic SIPP to measure improvements in success rate, path optimality, or computational speed.

Kinodynamic Planning is a motion planning paradigm that simultaneously enforces both kinematic constraints (e.g., non-holonomic turning radius) and dynamic constraints (e.g., acceleration and velocity limits) to generate physically feasible, collision-free trajectories. Unlike geometric planners, it directly reasons about the agent's equations of motion.

• Contrast with SIPP: While SIPP primarily reasons about temporal safety intervals on a graph, kinodynamic planning focuses on the physical feasibility of continuous state-space trajectories. They are often used in tandem, with SIPP providing a high-level plan that a kinodynamic planner refines.

The Velocity Obstacle (VO) is a geometric, reactive collision avoidance algorithm. For a moving agent, it defines the set of all velocities that would cause a collision with another moving obstacle within a specified time window. Optimal Reciprocal Collision Avoidance (ORCA) is its decentralized, cooperative extension, providing provably collision-free navigation for multiple agents by efficiently computing permitted velocity half-planes.

• Reactive vs. Predictive: VO/ORCA are reactive, computing avoidance maneuvers in real-time based on current sensor data. SIPP is predictive, planning a full path in advance using known obstacle schedules. They address different timescales of the avoidance problem.

Model Predictive Control (MPC) for collision avoidance is an optimization-based, receding-horizon control strategy. At each time step, it solves a finite-horizon optimal control problem to compute a sequence of control inputs that minimizes cost (e.g., deviation from goal) while satisfying dynamic constraints and collision avoidance constraints, then executes the first step before re-planning.

• Application Context: MPC is often used for local, continuous trajectory optimization and control. SIPP can provide the global, discrete path and safe intervals that serve as constraints or a reference trajectory within the MPC's optimization framework.

A Control Barrier Function (CBF) is a mathematical tool for safety-critical control. It defines a barrier around an unsafe set (e.g., obstacles) and synthesizes a controller that formally guarantees the system state will never enter this set. Predictive CBFs extend this guarantee over a future time horizon.

• Formal Guarantees: CBFs provide rigorous safety certificates for continuous control systems. SIPP provides discrete, graph-based safety guarantees. In a hierarchical architecture, SIPP's safe intervals can inform the design of the CBF's safe set for low-level control.

Time to Collision (TTC) is a fundamental risk metric estimating the time until collision if two agents maintain their current relative velocity. The Closest Point of Approach (CPA), defined by Distance to CPA (DCPA) and Time to CPA (TCPA), predicts the minimum future separation.

• Role in SIPP: These metrics are used for dynamic risk assessment and trajectory prediction of moving obstacles. SIPP's core innovation is converting predicted obstacle movements into static safe intervals on a graph, abstracting away continuous metrics like TTC into discrete, searchable time windows.

Runtime Assurance (RTA) is a safety architecture that pairs a complex, high-performance primary controller (e.g., a learning-based planner) with a simple, verifiable safety monitor or safety controller. If the primary controller's actions are predicted to violate a safety property (like collision avoidance), the RTA layer overrides them with a guaranteed-safe action.

• Complementary Role: SIPP can function as the verified safety planner within an RTA framework. A high-level, non-guaranteed planner generates a nominal path, while a SIPP-based monitor continuously checks it against safe intervals and provides a certified fallback plan if needed.