Efficient mixed-integer planning for UAVs in cluttered environments

We present a new approach to the design of smooth trajectories for quadrotor unmanned aerial vehicles (UAVs), which are free of collisions with obstacles along their entire length. To avoid the non-convex constraints normally required for obstacle-avoidance, we perform a mixed-integer optimization in which polynomial trajectories are assigned to convex regions which are known to be obstacle-free. Prior approaches have used the faces of the obstacles themselves to define these convex regions. We instead use IRIS, a recently developed technique for greedy convex segmentation [1], to pre-compute convex regions of safe space. This results in a substantially reduced number of integer variables, which improves the speed with which the optimization can be solved to its global optimum, even for tens or hundreds of obstacle faces. In addition, prior approaches have typically enforced obstacle avoidance at a finite set of sample or knot points. We introduce a technique based on sums-of-squares (SOS) programming that allows us to ensure that the entire piecewise polynomial trajectory is free of collisions using convex constraints. We demonstrate this technique in 2D and in 3D using a dynamical model in the Drake toolbox for Matlab [2].

I. Introduction

We consider the problem of planning a feasible trajectory for a quadrotor UAV from an initial state to a goal state while avoiding obstacles. Rather than explicitly considering the full state of the quadrotor, including its pose, velocity, and rotor thrusts, we rely on the recent results from Mellinger and Kumar, who demonstrated that the quadrotor system is differentially flat with respect to the 3D position and yaw of the vehicle's center of mass [3]. That is, the entire state of the system can be expressed as a function of the instantaneous value of the x, y, z positions of the CoM and the yaw of the vehicle, along with their derivatives. As a result, any smooth trajectory with sufficiently bounded derivatives can be executed by the quadrotor. This means that we are free to design smooth trajectories of the position and yaw of the vehicle's center of mass without explicitly considering the dynamics.