Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments

By Charles Richter, Adam Bry, Nicholas A. Roy. International Symposium of Robotics Research, 2016

792 citations recorded by the source corpus.

We explore the challenges of planning trajectories for quadrotors through cluttered indoor environments. We extend the existing work on polynomial trajectory generation by presenting a method of jointly optimizing polynomial path segments in an unconstrained quadratic program that is numerically stable for high-order polynomials and large numbers of segments, and is easily formulated for efficient sparse computation. We also present a technique for automatically selecting the amount of time allocated to each segment, and hence the quadrotor speeds along the path, as a function of a single parameter determining aggressiveness, subject to actuator constraints. The use of polynomial trajectories, coupled with the differentially flat representation of the quadrotor, eliminates the need for computationally intensive sampling and simulation in the high dimensional state space of the vehicle during motion planning. Our approach generates high-quality trajecrtories much faster than purely sampling-based optimal kinodynamic planning methods, but sacrifices the guarantee of asymptotic convergence to the global optimum that those methods provide. We demonstrate the performance of our algorithm by efficiently generating trajectories through challenging indoor spaces and successfully traversing them at speeds up to 8 m/s. A demonstration of our algorithm and flight performance is available at: http://groups.csail.mit.edu/rrg/quad_polynomial_trajectory_planning.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Control and Systems Engineering

View Paper: https://www.semanticscholar.org/paper/87f2803d2b3e772ddb749af06c1b51b6db6ed4d3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

Citations in the corpus

Thrust Mixing, Saturation, and Body-Rate Control for Accurate Aggressive Quadrotor Flight (2017, background): “They can be generated with a global optimization in which they can be constrained at the start, end, and intermediate waypoints ([13], [14]).”
Asymptotically optimal sampling-based kinodynamic planning (2014, background): “This class of robots includes ground vehicles at high velocities (Likhachev and Ferguson, 2009), unmanned aerial vehicles, such as fixed-wing airplanes (Richter et al., 2013), or articulated robots with dynamics, including balancing and locomotion systems (Kuindersma et al.”
Visual-Inertial Teach and Repeat for Aerial Inspection (2018, methodology): “smooth and dynamically feasible trajectory for the MAV using polynomial trajectory optimization similar to [16].”
Advanced closed loop visual navigation for micro aerial vehicles (2014, methodology): “…indoor spaces using a fixed wing aircraft equipped with a laser-range finder, while having a stall speed of 10m/s. Similar aggressive maneuvers were performed by Richter et al. (2013) with a quad-rotor equipped with a laser range finder, reaching velocities of up to 8m/s in confined spaces as well.”
Safe receding horizon control for aggressive MAV flight with limited range sensing (2015, methodology): “From here we use a QP solver to solve (5).”
Pushbroom stereo for high-speed navigation in cluttered environments (2014, background): “Laser rangefinders usually only support 2D detections and are generally too heavy for flight, although some systems with large wingspans [7] or limited flight time [28] exist.”
Mesh Manifold Based Riemannian Motion Planning for Omnidirectional Micro Aerial Vehicles (2021, background): “Typical examples are spline motion primitives [3] and optimization-based spline planning [4].”
Robust and Efficient Quadrotor Trajectory Generation for Fast Autonomous Flight (2019, background): “[2] shows that minimum snap trajectories can be obtained in closed form, in which the safety of the trajectories is ensured by iteratively adding intermediate waypoints.”
Real-Time Perception Meets Reactive Motion Generation (2017, background): “ODUCTION Robotic systems that integrate perceptual feedback into their planning and control loops have been developed for relatively low-dimensional problems such as autonomous driving or ﬂying [22], [29]. These systems are now mature enough to be on the verge of becoming consumer products. For prob”
Trajectory Planning for Quadrotor Swarms (2018, background): “, [35]), we do not take dynamic limits such as acceleration constraints into account during”
Planning Dynamically Feasible Trajectories for Quadrotors Using Safe Flight Corridors in 3-D Complex Environments (2017, methodology): “Similar to [6], we modify Δti according to the (5) to adjust the Time Allocation such that the final trajectory generated using Δti can be followed by the robot.”
FUEL: Fast UAV Exploration Using Incremental Frontier Structure and Hierarchical Planning (2020, background): “The former is pioneered by minimum-snap trajectory [19], whose closed-form solution was presented [20] later.”
An Efficient Sampling-Based Method for Online Informative Path Planning in Unknown Environments (2019, methodology): “While we use a constant acceleration model for position and yaw to estimate the execution time of future trajectories, polynomial trajectory optimization [22]”
RAPTOR: Robust and Perception-Aware Trajectory Replanning for Quadrotor Fast Flight (2020, methodology): “1) Global Planning: We use the approach [3] to compute global reference trajectories.”