Technical Summary: SPOT – Spatio-Temporal Obstacle-free Trajectory Planning for UAVs

Problem Statement

The paper addresses the challenge of reactive motion planning for quadrotors operating in unknown environments containing dynamic obstacles. While existing two-stage planning frameworks (global path + local trajectory optimization) perform well in static settings, their efficacy degrades significantly in dynamic, cluttered environments. Current state-of-the-art methods often suffer from several limitations:

• They rely on map fusion or static local maps, which are computationally heavy and impractical for real-world deployment.
• They often assume access to ground-truth obstacle trajectories (e.g., via motion capture), which is unrealistic for autonomous UAVs.
• They frequently fail to incorporate backup or contingency trajectories. In densely populated environments with multiple dynamic obstacles, trajectory optimization alone can lead to deadlocks where the UAV is trapped with no feasible path to the goal, leaving it vulnerable to collisions.

Methodology

The authors propose SPOT (Spatio-Temporal Obstacle-free Trajectory), a mapless, vision-based framework designed for robust navigation in unknown dynamic environments. The system architecture (Fig. 2) integrates three primary components:

1. Object Motion Segmentation

Instead of building a global map, SPOT operates directly on point clouds from an onboard depth camera. It employs a vision-based dynamic object tracking pipeline to estimate the position and velocity of objects.

• Points within detected bounding boxes inherit the object's velocity (dynamic).
• Points outside these boxes are treated as static.
• This creates a real-time spatio-temporal representation of the environment without requiring a pre-built map.

2. Spatio-Temporal RRT* (ST-RRT*)

The core planning algorithm is a 4-dimensional extension of RRT* that incorporates time ($t$) as a dimension alongside spatial coordinates ($x, y, z$).

• Node Representation: Each node is defined as $n_i = (x_i, y_i, z_i, t_i)$, encoding both position and arrival time.
• Feasibility: Edges in the search tree must satisfy causality ($t_{child} > t_{parent}$) and kinematic feasibility (velocity constraints).
• Informed Sampling: The algorithm uses an informed sampling strategy extended to the spatio-temporal domain. It restricts exploration to a prolate hyperspheroid in space and a specific time distribution, accelerating convergence to optimal, time-efficient paths.
• Collision Checking: To handle dynamic obstacles efficiently, SPOT utilizes a Spatio-Temporal Hash Grid. Dynamic obstacles are propagated forward in time using a constant velocity model. The grid allows for approximate nearest-neighbor queries to check collisions at specific time steps, combining static clearance (from a kd-tree) with dynamic clearance.

3. Safe Flight Corridor (SFC) and Trajectory Optimization

• SFC Generation: The skeletal path from ST-RRT* is inflated into a sequence of overlapping convex polyhedra (Safe Flight Corridors). Unlike methods that only consider static obstacles, SPOT constructs these corridors by aggregating predicted dynamic obstacle point clouds over the relevant time horizon, ensuring the corridor remains collision-free for the duration of the flight.
• Trajectory Optimization: A smooth, dynamically feasible trajectory is generated within the SFC using the MINCO framework. The optimization minimizes squared-jerk control effort while adhering to dynamic limits (velocity, acceleration) and staying within the time-allocated polyhedra.

4. Backup Planning Module

A critical contribution of SPOT is its reactive Backup Planning mechanism to handle deadlocks.

• Trigger: Activated when the planner fails to find a feasible path within a time budget or when the UAV hovers in an unsafe location.
• Mechanism: The system constructs a convex polygon around the UAV (considering only static obstacles) and uses a repulsive Cauchy Artificial Potential Field (CAPF) to compute an escape vector away from obstacles.
• Execution: A temporary "backup goal" is set at the intersection of this vector and the static polygon. The planner generates a reactive trajectory to this safe region. Once the UAV reaches this region, the Finite State Machine (FSM) resets to the initial mode to resume goal-directed planning.

Key Contributions

1. Novel Formulation: A mapless, vision-based spatio-temporal RRT* planner that directly processes point clouds and object velocities for dynamic environments.
2. Robust Deadlock Handling: The explicit integration of a backup trajectory generation module that prevents collisions in deadlock scenarios, a feature often missing in prior art.
3. Comprehensive Validation: Extensive testing in both simulation (up to 30 dynamic obstacles) and real-world hardware experiments using only onboard sensing and computation, demonstrating sim-to-real transfer capabilities.

Experimental Results

The authors validated SPOT against state-of-the-art methods (including [14] and [7]) in both simulation and hardware.

• Simulation (Ground Truth): In environments with 10, 20, and 30 dynamic obstacles, SPOT achieved success rates of 100%, 92%, and 80.2%, respectively.
  • Ablation Study: Removing the backup module ("SPOT-w/o backup") caused success rates to drop significantly (e.g., to 52.2% with 30 obstacles), highlighting the critical role of the backup planner in avoiding deadlocks.
  • Comparison: SPOT outperformed method [14] (which failed to escape deadlocks) and method [7] (which lacked object motion compensation), even when [7] was tested at higher UAV speeds.
• Pipeline Validation: Simulations in the PX4 SITL environment with Gazebo demonstrated the system's ability to navigate around humans using only onboard detector data, validating the sim-to-real pipeline.
• Hardware: Experiments were conducted on a custom micro-quadcopter equipped with an Intel RealSense D455 (depth) and T265 (odometry) cameras, running on an NVIDIA Jetson Xavier NX. The UAV successfully navigated static and dynamic obstacles in real-world conditions.

Significance and Claims

The paper claims that SPOT represents a significant advancement for reactive UAV navigation in dynamic, unknown environments. Its primary significance lies in:

• Mapless Operation: By avoiding map fusion, the framework reduces computational overhead and is more scalable to highly dynamic settings.
• Robustness: The inclusion of a backup planning module directly addresses the "deadlock" problem, ensuring the UAV does not remain stationary and vulnerable when a direct path is blocked.
• Real-World Applicability: The reliance solely on onboard vision and computation, validated through hardware experiments, demonstrates the feasibility of deploying such systems without external infrastructure (like motion capture).

The authors conclude that while the current work focuses on constant-velocity predictions for dynamic obstacles, future efforts will aim to improve motion model estimation and extend capabilities to higher-speed, more challenging environments.