We develop online methods to generate safe and smooth trajectories for aerial navigation through unknown, complex, and possibly dynamic environments. We use convex optimization tools to ensure both collision avoidance and dynamic feasibility.
Micro aerial vehicles (MAVs), especially quadrotors, have drawn increasing attention in recent years thanks to their superior mobility in complex environments that are inaccessible or dangerous for human or other ground vehicles. In autonomous navigation missions, quadrotors should be able to online generate and execute smooth and safe trajectories from a start position to a target position, while avoiding unexpected obstacles. The generated trajectories should have the guarantee of safety and smoothness considering the dynamic ability of the quadrotor.
In this project, some novel methods are developed to generate safe and smooth trajectories in cluttered environments. Based on good localization and mapping techniques, a flight corridor with safety guarantee is obtained in the cluttered environments first, following an optimization-based algorithm to assign a global optimal trajectory within the flight corridor entirely. Our works are implemented onboard a quadrotor and are suitable for fast online re-planning, making them able to work in unknown dynamic environments with unexpected obstacles.
Our algorithms can be widely used on various types of mapping modules, such as laser-based octomap and point clouds or monocular dense mapping. Both simulation results and indoor and outdoor autonomous flights in unknown cluttered environments show the good performance of our methods.
Gradient-based online safe trajectory generation for quadrotor flight in complex environments
By Fei GAO
We propose a trajectory generation framework for quadrotor autonomous navigation in unknown 3-D complex environments using gradient information. We decouple the trajectory generation problem as front-end path searching and back-end trajectory refinement. Based on the map that is incrementally built onboard, we adopt a sampling- based informed path searching method to find a safe path passing through obstacles. We convert the path consists of line segments to an initial safe trajectory. An optimization- based method which minimizes the penalty of collision cost, smoothness and dynamical feasibility is used to refine the trajectory. Our method shows the ability to online gener- ate smooth and dynamical feasible trajectories with safety guarantee. We integrate the state estimation, dense mapping and motion planning module into a customized light-weight quadrotor platform. We validate our proposed method by presenting fully autonomous navigation in unknown cluttered indoor and outdoor environments.
Tracking a moving target in cluttered environments using a quadrotor
By Jing CHEN
We address the challenging problem of tracking a moving target in cluttered environments using a quadrotor. Our online trajectory planning method generates smooth, dynamically feasible, and collision-free polynomial trajectories that follow a visually-tracked moving target. As visual observations of the target are obtained, the target trajectory can be estimated and used to predict the target motion for a short time horizon. We propose a formulation to embed both limited horizon tracking error and quadrotor control costs in the cost function for a quadratic programming (QP), while encoding both collision avoidance and dynamical feasibility as linear inequality constraints for the QP. Our method generates tracking trajectories in the order of milliseconds and is therefore suitable for online target tracking with a limited sensing range. We implement our approach on-board a quadrotor testbed equipped with cameras, a laser range finder, an IMU, and onboard computing. Statistical analysis, simulation, and real-world experiments are conducted to demonstrate the effectiveness of our approach.
Online quadrotor trajectory generation and autonomous navigation on point clouds
By Fei GAO
We present a framework for online generation of safe trajectories directly on point cloud for autonomous quadrotor flight. Considering a quadrotor operating in unknown environments, we use a 3-D laser range finder for state estimation and simultaneously build a point cloud map of the environment. Based on the incrementally built point cloud map, we utilize the property of the fast nearest neighbor search in KD-tree and adopt the sampling-based path finding method to generate a flight corridor with safety guarantee in 3-D space. A trajectory generation method formulated in quadratically constrained quadratic programming (QCQP) is then used to generate trajectories that constrained entirely within the corridor. Our method runs onboard within 100 milliseconds, making it suitable for online re-planning. We integrate the proposed planning method with laser-based state estimation and mapping modules, and demonstrate the autonomous quadrotor flight in unknown indoor and outdoor environments.
Online generation of collision-free trajectories for quadrotor flight in unknown cluttered environments
By Jing CHEN
We present an online method for generating collision-free trajectories for autonomous quadrotor flight through cluttered environments. We consider the real-world scenario that the quadrotor aerial robot is equipped with limited sensing and operates in initially unknown environments. During flight, an octree-based environment representation is incrementally built using onboard sensors. Utilizing efficient operations in the octree data structure, we are able to generate free-space flight corridors consisting of large overlapping 3-D grids in an online fashion. A novel optimization-based method then generates smooth trajectories that both are bounded entirely within the safe flight corridor and satisfy higher order dynamical constraints. Our method computes valid trajectories within fractions of a second on a moderately fast computer, thus permitting online re-generation of trajectories for reaction to new obstacles. We build a complete quadrotor testbed with onboard sensing, state estimation, mapping, and control, and integrate the proposed method to show online navigation through complex unknown environments.
Improving octree-based occupancy maps using environment sparsity with application to aerial robot navigation
By Jing CHEN
We present an improved octree-based mapping framework for autonomous navigation of mobile robots. Octree is best known for its memory efficiency for representing large-scale environments. However, existing implementations, including the state-of-the-art OctoMap [1], are computationally too expensive for online applications that require frequent map updates and inquiries. Utilizing the sparse nature of the environment, we propose a ray tracing method with early termination for efficient probabilistic map update. We also propose a divide-and-conquer volume occupancy inquiry method which serves as the core operation for generation of free-space configurations for optimization-based trajectory generation. We experimentally demonstrate that our method maintains the same storage advantage of the original OctoMap, but being computationally more efficient for map update and occupancy inquiry. Finally, by integrating the proposed map structure in a complete navigation pipeline, we show autonomous quadrotor flight through complex environments.
Quadrotor trajectory generation in dynamic environments using semi-definite relaxation on nonconvex QCQP
By Fei GAO
We present an optimization-based framework for generating quadrotor trajectories which are free of collision in dynamic environments with both static and moving obstacles. Using the finite-horizon motion prediction of moving obstacles, our method is able to generate safe and smooth trajectories with minimum control efforts. Our method optimizes trajectories globally for all observed moving and static obstacles, such that the avoidance behavior is most unnoticeable. This method first utilizes semi-definite relaxation on a quadratically constrained quadratic programming (QCQP) problem to eliminate the nonconvex constraints in the moving obstacle avoidance problem. A feasible and reasonably good solution to the original nonconvex problem is obtained using a randomization method and convex linear restriction. We detail the trajectory generation formulation and the solving procedure of the nonconvex quadratic program. Our approach is validated by both simulation and experimental results.