PaperlayerView exact revision on arXiv

Source-linked AI summary

Time-Optimal Planning for Quadrotor Waypoint Flight

Philipp Foehn, Angel Romero, Davide Scaramuzza

arXiv:2108.04537v3cs.ROcs.AIeess.SY

TL;DR

Planning minimum-time quadrotor flights through multiple waypoints is difficult because actuator-coupled acceleration and unknown waypoint timing must be handled together. The paper introduces complementary progress constraints for simultaneous trajectory and waypoint-time optimization, and reports consistently faster racing laps than human experts in real-world experiments.

  • Problem

    Time-optimal planning through multiple waypoints must balance actuator-limited linear and rotational accelerations while determining waypoint timing rather than fixing it beforehand.

  • Method

    The method combines waypoint-completion progress with waypoint proximity constraints, allowing simultaneous optimization of the state, input trajectory, and waypoint time allocation.

  • Results

    The experiments show that the approach can outperform human pilots and consistently beat their best lap time in a drone-racing task.

  • Takeaways & Limitations

    Complementary progress constraints provide a formulation for optimizing waypoint timing together with the trajectory instead of imposing waypoint times at predefined discrete instants.

  • Takeaways & Limitations

    Real-world tracking is affected by inaccurate drag and body-z modeling, while the BetaFlight controller provides poor body-rate tracking for closed-loop high-level control.

Abstract

from arXiv · show

Quadrotors are among the most agile flying robots. However, planning time-optimal trajectories at the actuation limit through multiple waypoints remains an open problem. This is crucial for applications such as inspection, delivery, search and rescue, and drone racing. Early works used polynomial trajectory formulations, which do not exploit the full actuator potential because of their inherent smoothness. Recent works resorted to numerical optimization but require waypoints to be allocated as costs or constraints at specific discrete times. However, this time allocation is a priori unknown and renders previous works incapable of producing truly time-optimal trajectories. To generate truly time-optimal trajectories, we propose a solution to the time allocation problem while exploiting the full quadrotor's actuator potential. We achieve this by introducing a formulation of progress along the trajectory, which enables the simultaneous optimization of the time allocation and the trajectory itself. We compare our method against related approaches and validate it in real-world flights in one of the world's largest motion-capture systems, where we outperform human expert drone pilots in a drone-racing task.

MULTIMEDIA MATERIAL

Time-optimal quadrotor waypoint flight is motivated by battery-limited missions and the need to balance coupled linear and rotational accelerations under actuator limits. Prior polynomial and discretized approaches either cannot exploit rapid actuator changes or require waypoint times to be fixed in advance, while the proposed progress formulation jointly optimizes trajectory and allocation.

  • Battery-limited missions often require quadrotors to visit multiple waypoints in minimal time, including inspection, delivery, search-and-rescue, and drone racing.
  • Quadrotor time-optimal planning must trade off linear and rotational acceleration because rotor thrust limits couple both quantities.
  • Polynomial trajectories are smooth by construction, preventing rapid state or input changes and limiting their use of the full actuator potential.
  • Time-discretized optimization permits bounded inputs at each step, but multiple waypoints must be assigned to specific nodes even though their optimal times are unknown.
  • The proposed method uses one progress measure per waypoint and complementary proximity constraints to optimize waypoint allocation without specifying times beforehand.

B. Contribution

The paper introduces complementary progress constraints to jointly optimize quadrotor states, inputs, and waypoint timing. It demonstrates faster-than-human flights and identifies broader applications for sequential goals under complex dynamic constraints.

  • B. Contribution: Complementary progress constraints mark a waypoint complete only when the quadrotor is within a specified tolerance of it.The formulation combines waypoint completion progress with local waypoint proximity.
  • B. Contribution: The formulation enables simultaneous optimization of the state trajectory, input trajectory, and waypoint time allocation.
  • B. Contribution: The method outperforms two professional human drone racing pilots in lap time and consistency on a 3D race track.
  • B. Contribution: The optimization problem is highly non-convex, and supplementary simulations examine effects of non-convexity.
  • B. Contribution: The approach may apply to target interception, orbital maneuvers, mixed-integer avoidance, and sequential task goals with unknown duration.

A. Passing Waypoints through Optimization

Conventional waypoint optimization assigns each waypoint to a predetermined trajectory node, either softly through a distance cost or strictly through a timed constraint. The paper instead introduces chained progress variables whose changes are allowed only near the corresponding waypoints, preserving waypoint order without fixed timing.

  • A. Passing Waypoints through Optimization: Conventional formulations allocate each waypoint to a user-defined state and time along the discretized trajectory.
  • A. Passing Waypoints through Optimization: Quadratic distance costs are robust for convergence but remain soft requirements and do not guarantee passage within a tolerance.
  • A. Passing Waypoints through Optimization: Constraint-based formulations guarantee passage near waypoint pw_j within tolerance τ_j at a specified node time t_k.
  • B. Progress Measure Variables: The method defines one progress variable per waypoint, initialized at 1 and required to reach 0 by the trajectory endpoint.
  • B. Progress Measure Variables: Progress changes are nonnegative optimization variables constrained so that waypoint completion can occur only within the waypoint’s distance tolerance.
  • B. Progress Measure Variables: Chained progress variables enforce that waypoints are completed in the prescribed sequence, while the final waypoint is reached at the last node.

Complementary Progress Constraints

Complementary progress constraints jointly enforce waypoint completion and waypoint proximity, allowing waypoint timing to be optimized rather than fixed. A tolerance slack relaxes exact passage while requiring spatial discretization fine enough to encounter each waypoint tolerance.

  • Complementary progress constraints: Complementarity requires either waypoint progress or waypoint distance to be zero, so progress changes only near the corresponding waypoint.The formulation acts as a mathematical NAND: progress and distance complement each other.
  • Tolerance relaxation: Exact waypoint constraints can harm convergence and time-optimality because a discrete timestep must coincide exactly with the waypoint.The method therefore relaxes the waypoint constraint by a prescribed tolerance.
  • Tolerance relaxation: A slack variable permits waypoint distance to reach zero whenever it is below the maximum tolerance d_tol.Progress variables cannot change except at timesteps within waypoint tolerance.
  • Tolerance relaxation: Spatial discretization should satisfy δs < d_tol so at least one node lies within tolerance; beforehand, δs ≈ D/N estimates this condition.D is the cumulative distance between waypoints and N is the number of nodes.
  • Optimization problem: The optimization variables include total time, dynamic states, inputs, and progress-related variables at each discretization node.The full problem imposes dynamics, initial, progress-evolution, boundary, sequence, and complementary progress constraints.
  • Optimization problem: The progress constraints are non-linear because waypoint distance uses a norm and progress change multiplies the tolerance slack.These nonlinearities arise in constraints (13, 14).

E. Quadrotor Dynamics

The quadrotor model represents position, orientation, velocity, and body rates between inertial and body frames, with collective thrust and body torque as inputs. Its dynamics use quaternion operations, rotation, mass, and inertia.

  • State representation: The state comprises position p_IB, unit-quaternion orientation q_IB, velocity v_IB, and bodyrate ω_B.The quaternion lies on SO(3) and satisfies ∥q∥ = 1.
  • Inputs and dynamics: The input modality consists of collective thrust T_B and body torque τ_B.Frame indices are subsequently omitted because they remain consistent throughout the model description.
  • Inputs and dynamics: The dynamic equations use quaternion multiplication Λ, quaternion rotation R(q), quadrotor mass m, and inertia J.These quantities parameterize the translational and rotational dynamics.

Quadrotor Inputs

The formulation models rotor-level thrust limits and their coupled thrust–torque consequences rather than treating collective thrust and torque as independent. It also includes a diagonal linear-drag approximation and evaluates the method in a real racing experiment.

  • Rotor-level inputs: Collective thrust and body torque are decomposed into four rotor thrusts u = [T_1, T_2, T_3, T_4].T_i denotes the thrust produced by rotor i.
  • Rotor-level inputs: Actuator limits constrain each rotor thrust, with thrust and torque coupled through the quadrotor geometry and rotor torque constant.The coupling reflects the arm length l and torque constant c_τ.
  • Input-space geometry: The acceleration space is non-convex because minimum rotor thrust is positive, while achievable thrust and torque limits depend on each other.The figure visualizes both acceleration and thrust/torque spaces for a standard configuration.
  • Aerodynamic model: The dynamics include a linear drag model with D approximated as the diagonal matrix diag(d_x, d_y, d_z).The model targets dominant aerodynamic effects.
  • Experimental setting: The real-world experiment uses a 3D seven-gate race track and compares the planned trajectory with two professional human drone-racing pilots.The autonomous trajectory is executed on the same track and in the same motion-capture environment.

A. Experimental Drone Platform

The experiments use an in-house racing quadrotor, VICON state estimation, and real-time MPC, then evaluate time-optimal trajectories against trained professional pilots using statistically defined lap timings. Across tested thrust-to-weight configurations, the autonomous trajectories outperform the human baseline while maintaining a safety margin below the platform limit.

  • Experimental drone platform: The platform uses off-the-shelf racing hardware, an NVIDIA Jetson TX2, wireless communication, and a BetaFlight flight controller.Its maximum single-rotor thrust was measured with a load cell and verified in flight.
  • Experimental drone platform: State estimation uses a 36-camera VICON system, while MPC runs for 20 steps of 0.05 s with single-rotor thrust constraints.The controller executes in real time at 100 Hz using qpOASES and a real-time iteration scheme.
  • Human expert pilot baseline: The human baseline comprises two professional pilots trained on the same 3D track, with the autonomous and human platforms restricted to the same thrust-to-weight limit.The comparison uses each human pilot’s overall best lap time, favoring the human baseline.
  • Trajectory generation: The planned trajectories concatenate waypoints over 2.5 laps to reduce start, end, and battery-voltage transient effects.Timing excludes takeoff and landing segments.
  • Trajectory generation: Lap time decreases from 7.14 s at thrust-to-weight ratio 2.5 to 5.81 s at 3.6; tested configurations achieve 6.27 s at 3.15 and 6.10 s at 3.3.Both tested configurations are faster than the human trajectory while remaining below the approximately 4 thrust-to-weight absolute limit.
  • Timing analysis: Timing uses repeated visits to points along each closed lap, producing a statistically valid measure independent of the timing start and stop location.Forty timing points are distributed over each lap for statistically meaningful segment timings.
  • Timing analysis: The autonomous drone outperforms the human pilots in both absolute lap time and consistency across the evaluated trajectories.The time-optimal trajectories are reported as faster than the best human lap time with substantially lower variance.

IV. DISCUSSION

The time-optimal trajectory achieves a similar but faster speed profile than human pilots by exploiting acceleration more fully, while real-world deployment exhibits substantial tracking error from system and modeling limitations.

  • Velocity and Acceleration Distribution: The human trajectory varies more in acceleration and often falls below the time-optimal trajectory, especially between the right-most gates.The time-optimal trajectory uses the full acceleration capability, whereas reduced human acceleration leads to lower subsequent speeds.
  • Velocity and Acceleration Distribution: The autonomous and human trajectories show similar velocity distributions, but the time-optimal trajectory exceeds the human speed profile.Both platforms spend more acceleration in the velocity direction in low-curvature regions.
  • Discussion: Human pilots reach similar but slower velocity distributions and lap times, while the approach optimizes the full trajectory rather than using a receding planning horizon.The comparison concerns two professional human pilots and the autonomous reference trajectory on the race track.
  • Tracking Error Considerations: Real-world deployment achieved successful flight but incurred approximately 0.7 m positional RMSE tracking error.The authors identify latency, aerodynamic-model inaccuracies at high speed, and flight-controller behavior as contributing factors.

D. Convexity and Optimality

The optimization problem is generally non-convex because of nonlinear dynamics, non-convex acceleration constraints, and non-convex progress formulations; initialization helps approach globally good solutions, while local solutions remain feasible.

  • D. Convexity and Optimality: The nonlinear quadrotor dynamics make the trajectory optimization non-convex.This non-convexity arises in the context of the stated optimization formulation.
  • D. Convexity and Optimality: A nonzero minimum thrust makes the quadrotor acceleration space non-convex.The stated condition is Tmin > 0.0.
  • D. Convexity and Optimality: The progress equation is non-convex because it combines a distance norm with bilinearity between progress change µ and tolerance slack ν.The experiments use advanced initialization to start near the global optimum.
  • D. Convexity and Optimality: Reducing the nonlinear model to a bounded-acceleration point-mass model provides an initialization for translational trajectories and orientation.The reduced model uses ∥a∥≤amax and removes prominent non-convex dynamics, although the resulting orientation guess is not dynamically feasible initially.
  • D. Convexity and Optimality: Even a local optimum satisfies the vehicle dynamics and therefore remains dynamically feasible.The method does not guarantee global optimality for non-convex problems.
  • E. Real-World Deployment: Time-optimal trajectories require actuator margins for disturbance robustness, trading platform-specific minimum time for control authority.The true solution typically lies at actuator constraints and leaves no control authority.
  • E. Real-World Deployment: The method is computationally demanding, taking under 20 minutes for smaller scenarios and approximately 40–65 minutes for larger ones on a desktop computer.The authors note that implementation improvements or precomputation could reduce these times.
  • E. Real-World Deployment: Real-world deployment relies on motion capture, while onboard visual-inertial odometry may suffer motion blur during fast flight.The authors identify further research and development as necessary for sufficient robustness.

APPENDIX A PREFACE: TIME-OPTIMAL QUADROTOR TRAJECTORY

The appendix frames quadrotor trajectory generation around point-mass bang-bang solutions, then contrasts them with underactuated quadrotor dynamics and smooth polynomial approaches. It also reports comparisons, experimental settings, and initialization choices.

  • A. Point-Mass Bang-Bang: For a point mass moving between rest states, the time-optimal solution accelerates at amax for half the duration and decelerates at amax for the remainder.Multiple-waypoint trajectories can similarly be generated by optimizing switching times and intermediate waypoint velocities.
  • B. Bang-Bang Relation for Quadrotors: Quadrotor time optimality trades rotational and linear acceleration because limited rotor thrusts jointly control both and cannot instantaneously change acceleration direction.Thrusts deviate from maximum primarily to adjust rotational rates.
  • Trajectory Representations: Polynomial trajectories are smooth by construction, conflicting with sustained maximal acceleration and limiting their ability to represent bang-bang behavior.Figure 6 contrasts multiple polynomial orders with a limited-slope bang-bang trajectory that spends more time at the input limit and achieves lower overall time.
  • Trajectory Representations: Lowering input bounds below the physical actuator limits adds control authority and makes planned trajectories more trackable, but removes platform-specific time optimality.The unrestricted time-optimal solution represents an upper performance bound for the track.
  • Comparative Evaluation: Compared with [21] and [22], the approach is 2.00% and 2.68% slower because it accounts for rotation dynamics and single-rotor limits.When applied using the earlier works’ dynamics and limits, the approach closely reproduces their results.
  • Experimental Setup: The experiments cover point-to-point flight, waypoint time alignment, initialization and non-convexity, and longer tracks with at least 10 waypoints.Evaluations use CasADi with IPOPT across multiple quadrotor configurations.
  • Experimental Setup: Initialization uses identity orientation, zero body rates, 1 m s−1 velocity, interpolated waypoint positions, hover thrusts, and equally distributed waypoint-passing nodes.The initial total time is the waypoint-path distance divided by the velocity guess.

B. Time-Optimal Hover-to-Hover Trajectories

The experiments evaluate waypoint-constrained trajectory generation, time allocation, initialization sensitivity, and non-convexity under different quadrotor models. The method adjusts waypoint-passage times while preserving the same trajectory across waypoint distributions, but non-convex dynamics can yield initialization-dependent solutions.

  • Hover-to-hover setup: The hover-to-hover setup constrains endpoint velocity and orientation while evaluating trajectories between the origin and positions from 3 to 15 m.The optimization uses N = 300 nodes, dtol = 10^-3, acceleration limits [1, 20] m s^-2, and maximum bodyrate 10 rad s^-1.
  • Model comparison: Increased model fidelity makes the proposed approach 2.00% slower than and 2.68% slower than.The difference is attributed to added rotational dynamics; the simplified collective-thrust model produces timings similar to the compared methods.
  • Optimal time allocation on multiple waypoints: Both regular and irregular waypoint distributions converge to the same tN = 2.430 s solution on the 50 m straight track.The state and input trajectories remain equal despite different waypoint locations, while progress-variable distributions differ.
  • Initialization and convergence: Good and poor initializations require 216 and 303 iterations, respectively, while 100 random translation initializations converge to the same solution.The results indicate sensitivity to initialization quality in iteration count, but not to translation-space initialization for the tested hairpin track.
  • Influence of convexity: The standard configuration produces different solutions from two orientation initializations, with the flip taking 4.115 s versus 4.171 s for the other solution.The flip is 1.3% faster, consistent with non-convex achievable acceleration caused by positive minimum thrust.
  • Influence of convexity: With the race configuration’s Tmin = 0 N, both initialization setups converge to the same solution despite the full formulation remaining non-convex.The tested race configuration has a convex achievable acceleration space, while nonlinear dynamics and constraints preserve overall non-convexity.

F. Local-vs-Global Optimum

The paper examines how non-convex dynamics can produce feasible local optima and how initialization can recover faster solutions. It also reports a large-track qualification result that serves as a theoretical lower bound under the model parameters.

  • Local versus global optimum: An upright initialization for vertical descent converges to a feasible free-fall local optimum rather than the globally optimal flip trajectory.The setup descends from 5 m to the origin using the race quadrotor configuration.
  • Local versus global optimum: A bang-bang point-mass initialization resolves the vertical-descent local optimum and converges to the global solution.The initialization supplies an orientation guess that accelerates toward the endpoint and then symmetrically decelerates.
  • Local versus global optimum: The global flip solution takes 0.808 s, compared with 1.212 s for the locally optimal free-fall solution.The comparison is reported for travel from 5 m height to the origin.
  • Microsoft AirSim qualification: On the NeurIPS AirSim Qualification 1 track, the method passes all waypoints in tN = 24.11 s versus the best team’s 30.11 s.The trajectory is presented as a theoretical lower bound on achievable time given the model parameters.
Loading 2108.04537v3…