Graph-Based Invariant Set Planning for Quadrotors

We propose a motion planner for quadrotor unmanned aerial vehicles (UAVs)
implemented as a graph search over robust positively invariant (PI) sets. We model the
positional error dynamics of the quadrotor in closed-loop with an onboard controller as a
second-order system, with polytopic uncertainty in the gains under idealized conditions.
In addition to this structured uncertainty, we also consider bounded attitude tracking
errors from an imperfect attitude control loop and additive input disturbances to account
for modeling errors. In this setting, we propose a method for computing ellipsoidal robust
PI sets using linear matrix inequalities. Given obstacles and control constraints, the sets
are scaled to produce inflated safe sets. We use the sets to construct a graph in which
each vertex contains a setpoint, a robust PI set, and a safe inflated set. We characterize
free-space as the union of the safe inflated sets and show that for any initial configuration
in free-space, any robust PI set in the graph is reachable in finite time subject to the
properties of the graph. The computationally heavy construction of the graph is done
offline, but the online search of the graph is fast and feasible for real-time replanning
applications. This is demonstrated both with extensive simulation results and by
experiments with real-time motion planning of a Crazyflie 2.1 quadrotor in a cluttered
indoor environment.