Airways: Optimization-Based Planning of Quadrotor Trajectories according to High-Level User Goals
Christoph Gebhardt Benjamin Hepp Tobias Naegeli Stefan Stevsic Otmar Hilliges





	
		
    < g r a p h i c s >

		Interactive computational design of quadrotor trajectories: (A) user interface to specifiy keyframes and dynamics of quadrotor flight. (B) An optimization algorithm generates feasible trajectories and (C) a 3D preview allows the user to quickly iterate on them. (D) The final motion plan can be flown by real quadrotors. The tool enables the implementation of a number of compelling use cases such as (B) robotic light-painting, aerial racing and (D) aerial videography.



5

Airways: Optimization-Based Planning of Quadrotor Trajectories according to High-Level User Goals
    
	Christoph Gebhardt[2] , Benjamin Hepp[2] , Tobias Nägeli, Stefan Stevšić, Otmar Hilliges

	Departement of Computer Science, AIT Lab

	ETH Zürich


    Received: date / Revised version: date
========================================================================================================================================================





In this paper we propose a computational design tool that allows end-users to create advanced quadrotor trajectories with a variety of application scenarios in mind. Our algorithm allows novice users to create quadrotor based use-cases without requiring deep knowledge in either quadrotor control or the underlying constraints of the target domain. To achieve this goal we propose an optimization-based method that generates feasible trajectories which can be flown in the real world. Furthermore, the method incorporates high-level human objectives into the planning of flight trajectories. An easy to use 3D design tool allows for quick specification and editing of trajectories as well as for intuitive exploration of the resulting solution space. We demonstrate the utility of our approach in several real-world application scenarios, including aerial-videography, robotic light-painting and drone racing. 


[2]The first two authors contributed equally to this work.





 §.§ ACM Classification Keywords

I.2.9 Robotics: Autonomous vehicles; Operator interfaces; H.5.2 User Interfaces;



§ INTRODUCTION

In recent years micro-aerial vehicles (MAVs), in particular Quadrotors, have seen a rapid increase in
popularity both in research and the consumer mainstream.
While the underlying mechatronics and control aspects are complex, the recent emergence of simple to
use hardware and easy programmable software platforms has opened the door to widespread adoption and
enthusiasts have embraced MAVs such as the AR.Drone or DJI Phantom in many compelling scenarios
including aerial photo- and videography. Furthermore, the HCI community has begun to explore these
drones in interactive systems such as sports assistants
<cit.> or display
<cit.> of content.

Clearly there is a desire to use such platforms in a variety of application scenarios. Current SDKs
already give novices access to manual or waypoint based control of MAVs, shielding them from the
underlying complexities. 
However, this simplicity comes at the cost of flexibility. For instance, flying a smooth, spline-like
trajectory or aggressive flight maneuvers
, for example to create an aerial light show (e.g.,
<cit.>), is tedious or impossible with waypoint based
navigation. These limits exist because manufacturers place hard thresholds on the dynamics to ensure
flight stability for inexperienced pilots.

More importantly, state-of-the-art technologies offer only very limited support for users who want to
employ MAVs to reach a certain high-level goal. This is maybe best illustrated by the most successful
application area – that of aerial videography. What a few years ago was limited to professional camera
crews, requiring cost-intensive equipment like a helicopter, can now, in principle, be done by end-users with a MAV
and an action camera. However, producing high-quality aerial footage is not an easy task – it demands
attention to the creative aspects of videography such as frame composition and camera motion
(cf. <cit.>). In the case of airborne cameras, an operator needs to fly smoothly,
accurately and safely around a camera target. Furthermore, the target has to be framed properly
alongside further creative considerations. Thus this is a difficult task and typically requires at
least two experienced operators – one pilot and a camera man
(cf. <cit.>). Our method tackles this problem by enabling a single novice user to  
fly challenging trajectories and still create aesthetically pleasing aerial footage.





 §.§ Overview & Contribution

Embracing the above challenges we propose a computational method that enables novice end-users to create quadrotor use-cases without requiring expertise in either low-level quadrotor control or specific knowledge in the target domain. The core contribution of our method is an optimization-based solution that generates feasible trajectories for flying robots while taking high-level user goals such as visually pleasing video shots, optimal racing trajectories or aesthetically pleasing MAV motion into consideration.
Furthermore, we develop an easy-to-use tool that allows for straightforward specification of flight trajectories and high-level constraints. Our approach guides the users in exploring the resulting design space via a 3D user interface and allows for quick iteration until finding a solution which fits best with the user's intentions. 

We demonstrate the flexibility of our approach in three real-world scenarios including aesthetically pleasing aerial-videos, robotic light-painting and drone racing.





§ RELATED WORK



 §.§ MAVs in HCI

With MAVs becoming consumerized the HCI community has begun to explore this design space. FollowMe
<cit.> is a MAV that follows a user and detects simple gestures via a depth camera, whereas
others have proposed using head motion for MAV control <cit.>,
while <cit.> propose a simple, remote controlled flying projection platform. Several setups have been proposed that turn such MAVs into flying, personal companions. For example, to
act as jogging partner <cit.> or general purpose sports coach <cit.>, or
as an actuated and programmable piece of sports equipment <cit.>.

Commercially available  drones, targeted at the consumer market, shield the user form low-level flight aspects and provide simple manual control (e.g. using smartphones as controller) or waypoint based programmatic navigation as well as GPS based person
following. This dramatically lowers the entry barrier for novices but also limits the ceiling of
achievable robotic behavior. 
Our approach also aims for simplicity but gives more power to the users, enabling even novices to design and implement complex flight trajectories, concentrating on the high-level goals of the application domain.




 §.§ Video Stabilization & Camera Path Planning

Improving the visual quality of end-user produced content is a goal we share with post production video
stabilization. Inspired by early work which formulates the problem and discusses the aesthetics of
cinematography <cit.> a number of approaches employ computer vision methods to
estimate the original, jerky camera path. Based on this a new, smooth path is computed to
generate stabilized video <cit.> and even time-lapse
footage <cit.> from the source material. 
Camera path planning has also been
studied extensively in the context of virtual environments using constraint based
<cit.> or probabilistic <cit.> methods. 
However, these methods are not limited by
real-world physics and hence can produce arbitrary camera trajectories and viewpoints. Our approach
differs from the above as we propose a forward method that gives the user full control over the
creative aspect of camera planning while simultaneously optimizing for physical feasibility of the
flight path and cinematographic objectives. A 3D simulation lets the user explore the design space
before flying the actual trajectory and hence helps in understanding the trade-offs to
consider.



 §.§ Computational Design

Sharing the goal of unlocking areas that previously required significant domain knowledge to novice
users, the HCI and graphics communities have proposed several methods that give novice users control
over aesthetic considerations while achieving functionality.
Recent examples include digitally designed gliders
<cit.> and kites <cit.> with optimized aerodynamic properties.
At the core of these approaches are sophisticated simulations or analytical models of the problem
domain that carefully balance accuracy and rapid responses to ensure interactivity while maintaining
guarantees (e.g., physical stability). We build on domain knowledge from the robotics and MAV
literature and propose an interactive design tool for complex MAV behavior usable by non-experts.  



 §.§ Robotic Behavior and Trajectory Generation

Automating the design of robotic systems based on high-level functional specifications is a
long-standing goal in robotics, graphics and HCI. Focussing on robot behavior only, simple direct touch
and tangible UIs <cit.>, and sketch based interfaces to program robotic systems
<cit.> have been
proposed. Visual markers have been used to control robots explicitly, for example as kitchen aides
<cit.>, or implicitly <cit.>, to schedule tasks for robots in-situ
which are then collected and executed asynchronously. 

Generating flight trajectories for MAVs is well-studied in robotics. In particular, the control aspects
of aggressive and acrobatic flight is an active area of research (e.g., <cit.>).
Mellinger et al.'s work on generating minimum snap trajectories <cit.> is the most related to ours.                                  
While they specify a trajectory as a piecewise polynomial spline between keyframes, we discretize the trajectory
into small piecewise linear steps. The result is a more intuitive formulation of the optimization problem, making the incorporation of additional constraints and objectives much easier. We extend the approach in <cit.> by optimizing trajectories for flyability and for high-level human objectives. We place
the users in the loop and provide easy-to-use tools to design quadrotor trajectories according to high-level objectives. 

Joubert et al.  <cit.> share a similar goal in proposing a design tool that allows novice users to
specify a camera trajectory, simulate the result, and execute the motion plan. In contrast to our work,
their method does not automate feasibility checking but delegates the correction of violations to
the user. Furthermore, our method allows to treat keyframes as soft instead of hard constraints,
allowing to trade off feasibility against keyframe matching. We also incorporate a larger number of high-level user constraints, such as additional cinematographic goals and collision-free trajectories, into the algorithm – requiring a different formulation of the optimization problem. Finally, we demonstrate the gain in generality in our approach in the additional use cases of light writing and aerial racing.





§ SYSTEM OVERVIEW

We propose an end-to-end system that allows users to generate motion plans for quadrotors that are
'flyable' and adhere to high-level human-specified objectives for a variety of application
scenarios. fig:sys_overview illustrates the design process. 

Using for example a LeapMotion
controller the user specifies keyframes, each consisting of a position and a time (1). The optimization
algorithm generates an initial 'flyable' trajectory from these inputs, i.e., one that lies within the
physical capabilities of the underlying quadrotor hardware (2). 
The method aims to find a solution that
goes through all specified keyframes,
however the user
may now adjust both a keyframe's position and timing as well as other parameters such as the overall flight
time, the optimization's objective (e.g., minimization of velocity) or the extend to which the generated
trajectory should follow the optimization's objective versus the position of the specified
keyframes (3). This can result in trajectories that do not directly meet the user inputs but are the best
trade-off between the potentially conflicting use-case specific constraints. 
A built-in physics simulation allows the user to virtually fly the
quadrotor and thus provides a better understanding of the expected real-world behavior and enables rapid iteration of trajectories (4). 
This tool already enables the design of various flight-maneuvers for example designing an aerial race-course or a
light-show (please see video for an illustration of the design process and results).



However, the goal of our work is to enable more complex end-user scenarios as well. To this end we have
extended our method to also integrate high-level aesthetic constraints that are not necessarily
directly associated with the basics of quadrotor control. fig:sys_overview_camera illustrates
how our tool can be used to plan aerial videography shots. In this case, the user designs an initial
camera trajectory around one or several targets. In addition to the keyframes the user specifies
targets which shall be captured by the on-board camera (fig:sys_overview_camera, B). Our
algorithm generates both a quadrotor trajectory and a gimbal trajectory within the physical bounds. To
acquire visually pleasing footage our method incorporates cinematographic constraints such as smooth camera and target
motion, smooth transitions between multiple targets and reduction of perspective
distortions. Furthermore, the algorithm takes obstacle information into account and automatically
routes the trajectory through free-space (see fig:sys_overview_camera, C). It would also be
straightforward to integrate other constraints such as limits of the coverage of a tracking system or government flight regulations.

In order to better understand the implications of the camera planning our tool allows the user to
virtually fly the shot by dragging the virtual quadrotor along the trajectory
(fig:sys_overview_camera, D). For each point in time the tool renders the scene as it would be
captured in reality. The user can then edit the plan and iterate over different alternatives. 
Once satisfied the generated trajectories for quadrotor and gimbal can be deployed as a reference
to be followed by a real quadrotor.








§ METHOD

So far we have discussed the proposed design tool at a high-level and focused on how the user
accomplishes certain tasks.

We now introduce the underlying method we use to generate trajectories. To be able to reason about flight plans computationally, a model of the quadrotor and its dynamics are needed. This is a complex and challenging topic and we refer the reader to the Appendix for the full non-linear model that is needed to control the position and dynamics of the robot during flight (please see also <cit.>). The full model directly relates the inputs of a quadrotor to its dynamics – this however makes trajectory generation a challenging problem and integrating such a highly non-linear model into an optimization scheme is complicated, incurs high computational cost and negates convergence guarantees <cit.>. However, for most application scenarios considered here a full non-linear treatment is not necessary as demonstrated by our results. In particular if the goal is to generate trajectories only (i.e., position and velocities) rather than the full control inputs as in <cit.>. Therefore, we present a linear
approximative model of the quadrotor and detail the optimization-based algorithm based on it.






 §.§ Approximate Quadrotor Model for Trajectory Generation


When generating a trajectory we want to ensure that it can be followed by a quadrotor,
i.e. a flight plan where each specified position and velocity can be reached within the time limits without exceeding the limits of the qudrotors	 inputs.

Therefore, we chose to approximate the quadrotor as a rigid body, described by its moment of inertia only along the world frame z-axis (i.e. we ignore pitch and roll of the quadrotor):

    m𝐫̈ = 𝐅 + m 𝐠   ∈ℝ^3 
    
    I_ψψ̈ = M_ψ   ∈ℝ ,

where 𝐫 describes the center of mass of the quadrotor,
ψ is the yaw angle of the quadrotor, m is the mass of the quadrotor,
I_ψ is the moment of inertia about the body-frame z-axis,
𝐮_r is the the force acting on the quadrotor
and M_ψ is the torque along the z-axis.
This approximation allows to generate trajectories in the flat output space of the
full quadrotor model (see Appendix for more details). 

In addition to the equations of motion we introduce bounds on the maximum
achievable force and torque:

    𝐮_𝑚𝑖𝑛≤𝐮≤𝐮_𝑚𝑎𝑥∈ℝ^4  ,

where 𝐮 = [𝐅, M_ψ]^T is the input of the system.

With this model it is not possible to exploit the full dynamic agility of a quadrotor.
As an example, consider the situation of accelerating straight upwards  by rotating all motors at maximum speed. To now also rotate around the body-frame z-axis we would have to lower the speed of motors 2 and 4, reducing the total thrust of the quadrotor. Currently we do not incorporate this coupling between the translational
and rotational dynamics into the bounds (<ref>) of our approximate
linear model (<ref>). 
Therefore, to still ensure that a quadrotor can follow trajectories generated on base of this approximation conservative bounds are required.
Nonetheless, our results and applications demonstrate that these bounds still allow the quadrotor's agility to be sufficiently rich for many use cases. 
We refer the interested reader to the Appendix for details on how to choose these bounds.

For trajectory generation we rewrite the approximate model as a first-order dynamical system and discretize it in time with a time-step Δ t
assuming a zero-order hold strategy, i.e. keeping the inputs constant in between stages:

    𝐱_i+1 = A_d 𝐱_i + B_d 𝐮_i + c_d ,

where 𝐱_i = [𝐫, ψ, 𝐫̇, ψ̇]^T∈ℝ^4
is the state and 𝐮_i is the input of the system at time i Δ t. The matrix
A_d ∈ℝ^8x8 propagates
the state 𝐱 forward by one time-step, the matrix
B_d ∈ℝ^8x4 describes the effect of the
input 𝐮 on the state and the vector
c_d∈ℝ^8 that of gravity after one time-step.



 §.§ Trajectory Generation

With this approximate quadrotor model in place we can now discuss the optimization scheme to generate
trajectories. The user specifies M keyframes
describing a desired position k_j 
at a specific time-point η(j) Δ t, where
η: ℕ→ℕ maps the index of the keyframe to the corresponding time-point.
In the case of mouse-based user input we assume constant
time between consecutive positions. To compute a feasible trajectory  over the whole time horizon
[0, t_f] we discretize time with a time-step Δ t into N stages.
The variables we optimize for
are the quadrotor state x_i and the inputs u_i of the system
(<ref>) at each stage i Δ t.

The first goal of our optimization scheme is then to follow the user inputs as closely as possible,
expressed by the cost

    E^k = ∑_j=1^M || r_η(j) - k_j || ^ 2 .

A small residual of E^k indicates a good match of the planned quadrotor position and the specified
keyframe. The bounds (<ref>) together with (<ref>) and (<ref>) can then be formulated as a quadratic program

    Xminimize    1/2 X^T H X + f^T X  
     subject to     A_𝑖𝑛𝑒𝑞 X ≤ b_𝑖𝑛𝑒𝑞
     and     A_𝑒𝑞 X = b_𝑒𝑞 ,

where X denotes the stacked state vectors x_i and inputs u_i for each time-point, H and f contain the
quadratic and linear cost coefficients respectively which are defined by (<ref>)
, A_𝑖𝑛𝑒𝑞, b_𝑖𝑛𝑒𝑞 comprise the linear inequality
constraints of the inputs (<ref>) and
A_𝑒𝑞, b_𝑒𝑞 are the linear equality constraints
from our model (<ref>)
for each time-point i ∈1,…,N.
This problem has a sparse structure and can be readily solved by most optimization software
packages. However, this problem
is ill-posed and the result for a particular set of keyframes might be counterintuitive at first.
Since we only measure the match of quadrotor position at the keyframe times the state at other
time-points is not constrained in any way except for the quadrotor dynamics. Therefore a straight
path between two keyframe positions is as good as a zig-zag pattern if it is feasible.
An example of this is shown in fig:position_vs_derivatives.
To attain better results we have to further regularize the solution.

 

In many robotics application one goal is to minimize energy expenditure and this is often done by
penalizing non-zero inputs or in other words attempting to reach desired positions with minimal
wasted effort. For end-user applications, for example in the context of a racing game, one can also
aim to attain smooth trajectories by penalizing higher derivatives of the quadrotor's position with
respect to time such as acceleration (2nd) or jerk (3rd).
We introduce the cost

    E^d = ∑_i=q^N || D^q[   x_i;     …; x_i-q;       ] || ^ 2 ,

where D^q is a finite-difference approximation of the q-th derivative from the last q states.
Since the term jerk is not commonly known outside of engineering fields an intuition is to think of
high values of jerk as a feeling of discomfort caused by too sudden motion. Humans tend to plan
motion by minimizing the norm of jerk <cit.> and thus, minimizing jerk results in motion plans
that appear pleasant to a human.



The combined cost E = λ_k E^k + λ_d E^d with weights λ_k|d is
still a quadratic program and enables us to generate trajectories that are feasible and
that are optimal in the sense of (<ref>).
While still relatively basic in functionality this already enables a variety of use-cases such as aerial
light-shows and racing-games as illustrated in the next section.



 §.§ Optimizing for Human Objectives

With the basics in place we now turn our attention to including high-level human objectives into the
optimization. As a running example we will consider the task of planning an aerial video-shot but we
would like to emphasize that many other tasks such as 3D reconstruction or projector based
augmented reality could be implemented in the same way.

We have already discussed how this process works from the user's perspective in the system overview.
Here the user provides additional camera targets that should be recorded at a specific time
(see fig:sys_overview_camera). Furthermore, we assume that the quadrotor is equipped with a
gimbal that we can control programmatically. From a cinematographic standpoint, the most pleasant
viewing experience is conveyed by the use of either static cameras, panning ones mounted on tripods
or cameras placed onto a dolly (cf. <cit.>). Changes between these shot types can
be obtained by the introduction of a cut or jerk-free transitions, i.e. avoiding sudden changes in
acceleration. Furthermore, it is desirable to introduce saliency constraints or in other words we
want not only the camera path to be smooth but also want to keep the target motion within the image
frame as steady as possible and constrain it's motion to smooth motion.



To achieve these high-level objectives, we include a target position for each stage into the
optimization variable. Analogous to the quadrotor position we introduce a cost term E^t that
measures the deviations of user-specified keytarget points from the target positions at the
corresponding stages. We penalize higher temporal derivatives (acceleration and jerk) of the target
position by including finite differences in the cost term E^t,d.
To link the quadrotor and target trajectories we introduce a simple gimbal model:

    ψ̇_̇𝑔̇ = u_𝑔,ψ
    ϕ̇_̇𝑔̇ = u_𝑔,ϕ
    
    [ψ_𝑔,𝑚𝑖𝑛, ϕ_𝑔,𝑚𝑖𝑛]^T≤ [ψ_𝑔, ϕ_𝑔]^T≤ [ψ_𝑔,𝑚𝑎𝑥, ϕ_𝑔,𝑚𝑎𝑥]^T
    𝐮_𝑔,𝑚𝑖𝑛≤ [u_𝑔,ψ, u_𝑔,ϕ]^T≤𝐮_𝑔,𝑚𝑎𝑥 ,

where the inputs u_g,ψ, u_g,ϕ represent the angular velocities
of the yaw ψ_𝑔 and pitch ϕ_𝑔 of the gimbal
and both the inputs and the absolute angles are bounded according to the physical gimbal.
The bounds specify the limits on the absolute angles and the angular velocities.
To ensure a smooth motion of the gimbal we introduce a cost
E^𝑔 on temporal finite differences of the yaw and pitch angles analogous to
(<ref>).
We do not incorporate the attitude of the quadrotor into our gimbal model and therefore the
bounds have to be chosen conservatively.



The angle between the current camera direction 𝐩_𝐥 and the direction of the target
𝐩_𝐝 is depicted in fig:camera_angle_error. The error is
then computed by

    α_𝑒𝑟𝑟 = cos^-1( 𝐩_𝐝·𝐩_𝐥/| 𝐩_𝐝 | | 𝐩_𝐥 |) 
    𝐩_𝐝 = 𝐫_𝐭 - 𝐫 and 𝐩_𝐥 = [ cosϕ_gcos(ψ + ψ_g); cosϕ_gsin(ψ + ψ_g);             sinϕ_g;                    ] ,

where 𝐫 is the quadrotor position, 𝐫_𝐭 is the target position
and ψ is the pitch angle of the quadrotor.


Deviations of the camera direction from the desired target are penalized by

    E^c = ∑_i=1^N( α_𝑒𝑟𝑟^i)^2 ,

where α_𝑒𝑟𝑟^i is the camera angle error at stage i.
Here the separation of target trajectory from the camera direction might seem surprising but it gives more
flexibility as the user can choose the weights of the importance of target keypoints and the camera direction separately.



The final aesthetic cost is related to perspective effects. Viewpoints that are to high or low relative
to the recorded object of interest lead to skew and results in strong vanishing lines in the image. This is
illustrated in fig:skewness_error. While this effect maybe desired in some situations
(imagine an overhead shot) we allow the user to supress these types of distortions by optionally including a skewness cost E^s: 

    s_𝑒𝑟𝑟 = b_1/b_2 - 1 = 
    		(𝐩_𝐝 + 𝐡̃/2) ·𝐩_𝐝/
    	(𝐩_𝐝 - 𝐡̃/2) ·𝐩_𝐝 - 1 
    𝐡̃ =
    𝐡 ,     if  p_d,3 >= p_t,3
    -𝐡 ,     else  , 
    
    E^s = ∑_i=1^N( s_𝑒𝑟𝑟^i)^2

where 𝐡 is a vertical vector pointing from the center of the target to the upper edge of the bounding box
and s_𝑒𝑟𝑟^i is the skewness error at stage i. In the computation we distinguish the case of a quadrotor flying above the target and the
case of flying below a target.

Summing up the individual cost terms gives results in the final cost
E = ∑_i={k, s, t, g, c}λ_i E^i
Unfortunately α_𝑒𝑟𝑟 and s_𝑒𝑟𝑟 are non-linear in the variables of the motion
plan and in consequence minimizing E can no longer be written as a quadratic program. We describe how we
minimize E in the implementation section.

By penalizing snap of the quadrotor position and jerk of the camera motion the combined cost results in
aesthetically pleasing footage (see the accompanying video). We can now generate a motion plan for a
quadrotor that follows a target trajectory with the camera.
To further support novice users we included an approximate collision-free scheme that
can be used to keep a minimum distance from the target or stay at a safe distance from
obstacles. Again we refer to the implementation section for details.
Note that this only works for static objects where the position is known at the time of trajectory generation.



§ IMPLEMENTATION

In this section we describe how we implemented the different components of our
system. We start with describing the iterative quadratic programming scheme, then
explain the onboard controller and the quadrotor hardware and finally show how we
realized the design tool. 






  
Iterative Quadratic Programming To solve the non-linear problem described
above we resort to a scheme of iterative quadratic programming (IQP).
The general idea is to linearly or quadratically approximate the problem around the
current estimate of the
solution. This approximate system is then solved and a better, consistent estimate of
the solution is found.
These iterative schemes usually converge within a few iterations despite the cost
functions not being convex
anymore. In our concrete implementation we start with an initial guess of the
trajectory by interpolating
the quadrotor positions and the camera targets between the keyframes. We also
enforce all initial equality
constraints to be fulfilled. As the proposed energies are usually non-convex a good
initial guess is important
to find a good solution. For each major iteration of our solver we build the H and
f matrices of a quadratic program. This is done by quadratically approximating each
of the cost terms around
the trajectory X, note that this does not affect the quadratic terms in E.
We also assemble the
bounds and equality and inequality constraints and linearize them analogously. The
fully assembled system is
a sparse quadratic program and can be solved by most optimization packages. The
solution gives us a change
dX of the current motion plan. We perform a line search with the step length
α to find a new motion
plan X_𝑛𝑒𝑥𝑡 = X + α dX. We lower α until we find a
X_𝑛𝑒𝑥𝑡 with a cost
C(X_𝑛𝑒𝑥𝑡) < C(X). This step is necessary as the cost of the approximated
quadratic program is only an approximation of the real residual. An empirically derived serves as termination criteria.
 


  
Obstacle Avoidance: We approximate each obstacle as a static sphere with a radius
o_r and introduce a non-convex constraint || r ≥ o_r || ^ 2.
We linearize these constraints in each IQP iteration for each
stage in time around the current trajectory X.
Although we cannot guarantee global optimality of the resulting trajectories, this approach
can be helpful for planning trajectories in scenes with known geometry and many objects. More advanced collision avoidance schemes, potentially taking dynamic targets into consideration (e.g., <cit.>), could be included in future work. 



  
Algorithm Performance: To evaluate the performance of our optimization scheme we measured the time necessary to generate different trajectories. The runtime of the algorithm depends on the flight duration, the number of keyframes and the constraints which are incorporated into the optimization problem. Typical run times (Intel Core i7 4GHz CPU, Matlab's quadprog solver) are ∼1 sec for pure QPs (e.g., the trajectory in fig:apps_light_writing had a flight time of 30 sec and was generated in 1.4 sec) and tens of sec for IQPs (e.g., the trajectory in fig:apps_cinematography_dolly had a flight time of 20 sec and was generated in 14 sec). Optimizing over a receding horizon which is shifted along the trajectory may be a fruitful strategy to speed up the algorithm. Another idea would be to split a trajectory in overlapping and reasonable constrained sub-trajectories and optimize them separately. Both approaches would negate the global optimality property of generated trajectories, requiring evaluation of real-world feasibility.



  
Onboard Control and Hardware: Once we generate trajectory control inputs
these can be transmitted to a real quadrotor.
Our real-time control system builds on the PIXHAWK autopilot
software <cit.>.
Desired positions along the motion plan, camera look-at vectors and target
trajectories are transmitted from a ground-station via the Robot Operating System
(ROS). An LQR (Linear-quadratic regulator) running on a
dedicated single-board computer computes the necessary forces and moments to track
the motion planas well as compensates for air disturbances and other sources of error.
These forces are then translated into low-level
rotor and gimbal speeds by further controllers running on a PX4 FMU. We created result figures using two different quadrotor platforms: the 3DR Solo and a custom-build Pixhawk-based platform.


Design Tool: The 3D trajectory design tool has been implemented as Unity 3D
tool which allows for easy adaptation and
integration of a variety of IO devices. A further advantage of this design decision is
that it is easy to develop
augmented reality applications such as mixing real and virtual quadrotors in a
racing scenario. We have
interfaced the design tool with our optimization algorithm implemented using the
Matlab optimization toolbox. 
The source code for the optimization algorithm can be found in the supplementary materials as
self-contained Matlab code.  






§ RESULTS AND APPLICATION SCENARIOS

Despite having used camera planning as running example we note that our method is general and can be applied in many different application scenarios. In particular, the discrete nature of the proposed IQP scheme makes it straightforward to incorporate application specific constraints. In this section we want to illustrate a number of interactive usage scenarios which we have implemented using our method.  



 §.§ Light Painting

Quadrotors have already been used in entertainment settings, in particular to create spectacular aerial light shows (cf. <cit.>). However, creating such complex and coordinated flight patterns is not possible with consumer grade technologies and hence has not been accessible to the end-user. Our tool allows for straightforward end-user design of such creative scenarios. 



One such example is illustrated in fig:apps_light_writing. Here the user provides input position constraints by writing or sketching the desired shape. Our method then generates a feasible trajectory which as a side-effect of minimizing snap also smooths the input strokes.  However, the generated trajectory may not coincide with the desired output e.g. because it linearly interpolates the keyframes so that handwriting may not be legible anymore (see fig:apps_light_writing, B). The user can correct for this by changing the parameters of the optimization scheme (e.g., weights of the energies) or by adjusting keyframe positions and timings. 

Once satisfied the trajectory can be flown by a real robot. In fig:apps_light_writing we have mounted a bright LED to the robot and captured the flight path via long-exposure photography. 



 §.§ Racing

Another interesting application domain is that of aerial racing. First person drone racing is an emerging sport that requires a lot of expertise in manual quadrotor control. Our tool can bring this within reach of the end-user. As a proof of concept we have developed a simple aerial racing game. In this scenario a user can design a free-form race course, specifying length, curvature and other parameters as well as overall race-time. 




For the race itself we implemented a semi-manual flight mode for which we changed the position controller, by remapping the feedforward term (m𝐫̈_d) of (<ref>) to the joystick of a game controller. Thereby, the user can choose the direction and the strength of the feedforward-force allowing him to deviate with the quadrotor from the generated reference trajectory. Users can then, for instance, take a short cut in a curve or fly the trajectory with a higher velocity than generated by the optimization method. The score is calculated as a function of the deviation from the generated trajectory and the time needed to complete all laps. In other words, the player who managed to stay on the trajectory as fast as possible will win. We note that by manipulating the underlying controller, it would be possible to introduce further video game concepts such as player strength balancing into real-world quad racing. 
For example, allowing a player to temporarily race on a faster reference trajectory than his opponents.



 §.§ Aerial Videography

Our main results stem from the application scenario of aerial videography. We have already mentioned the technical details and how we incorporate cinematographic goals into our optimization scheme. Here we briefly summarize a number of interesting and challenging video-shots (best viewed in video).

fig:apps_cinematography_dolly illustrates a shot where a quadrotor flies over a toy castle and at the same time records it. Here the gimbal has to smoothly track the target just as the quadrotor swoops over the object and turns around its own axis once reaching the highest point. Such a shot composition is difficult to achieve manually due to the complicated quadrotor-camera-target coordination. 



 

Even with conventional cameras, composition of multi target shots is a very challenging task. Aerial-videography makes this even more difficult due to the many
degrees of freedom and complex geometric dependencies requiring coordination for smooth, jerk-free transitions from one to the next target while airborne. 
In fig:apps_cinematography_couch_slider we illustrate a sliding shot, transitioning between targets – the two actors – while the camera is moving from left to right and steadily rising in altitude. Throughout the entire trajectory the oerientations of quad and camera never remain constant, yet the camera targets are kept in focus and the transitions are smooth. Flying such a trajectory manually would only be possible with two operators, one for steering the camera, the other the quadrotor.








 


§ DISCUSSION AND FUTURE WORK

So far we presented a novel method to generate quadrotor trajectories subject to high-level goals and demonstrated its feasibility in different applications. In the remainder of this paper we are going to discuss the limitations of our approach and highlight interesting areas for future work.



 §.§ Limitations

The optimization framework proposed in this paper has proven to be powerful and versatile however there are of course a number of limitations. First, our goal is to enable non-expert users to design arbitrary MAV use cases. While the method is generic and designed to be extensible it does require expertise and effort to formalize further objectives (that we have not treated so far) and to integrate them into the algorithm. We believe that our high-level design tool bridges the gap between the underlying optimization algorithm and end-user goals sufficiently well. Nonetheless it is an interesting future research question how end-users could extend not only the use-cases we have demonstrated but also the optimization itself.   

Currently all our application scenarios depend on a high precision indoor tracking system. This is a limiting factor as one would of course like to fly many of the examples outdoors using GPS sensing. To this end our method is generic and could be made to work with any localization system, in particular with GPS position data in outdoor scenarios. However, we have not implemented this and of course the localization accuracy would impact the exact results. 



 §.§ Future Work

The optimization-based design of quadrotor trajectories subject to high-level user constraints is a comprehensive research space and our work only started to cover it. The investigations we did so far raised a number of additional research problems. In our method, the time at which a certain keyframe is reached cannot be changed by the optimization scheme. To extend our algorithm, it would be interesting to formalize the optimization problem in a way that both, the keyframe's position and its time can be optimized.


Furthermore, the use case of aerial videography raised the question: what is an aesthetic aerial video sequence and is it possible to optimize for it? By incorporating human objectives into the optimization, our work already presents a starting point, nevertheless it would be interesting to see whether further concepts and rules of cinematography can be incorporated into the optimization problem. 

Nonetheless, our method is generic and can be applied to further use cases. For example, it would be possible to extend the method to 3D scanning of buildings and other objects of interest. Here one could integrate objectives that capture e.g., reconstruction quality and surface coverage. Another possible example includes an advanced flying action camera for outdoor usage enabling users to trigger pre-defined trajectories on-the-fly. These scenarios would obviously require additional information such as the environment's 3D geometry for collision avoidance and accurate localization of drone and human in the outdoor case. Finally, it is not only drones that our method applies to. Most straightforward would be an extension to other actuated camera platforms such as dollies and robotic arms. 





§ CONCLUSION

In summary we have proposed a user in the loop design tool for the creation of aerial robotic behavior. At its core lies an optimization-based algorithm that integrates low-level quadrotor control constraints and high-level human objectives. Therefore, we used a linear approximation of the quadrotor model enabling us to generate trajectories subject to the physical limits of a quadrotor. Stating the problem as discrete, additionally permits the easy incorporation of high-level constraints to support the user, for instance, in the creation of pleasing aerial footage. This allows users to concentrate on the creative and aesthetic aspects of the task at hand and requires little to no expertise in quadrotor control or the target domain. We have demonstrated the flexibility and utility of our approach in three different use cases including aerial videography, light painting and racing.



§ ACKNOWLEDGEMENTS

We thank Cécile Edwards-Rietmann for providing the video voiceover and Gábor Sörös for creating the aerial light-painting videos.
We are also grateful for the valuable feedback from the associate chairs and external reviewers. This work was partially funded by the Swiss Science Foundations (UFO 200021L_153644) and Microsoft Research.


SIGCHI-Reference-Format






In the work proposed here we use an approximation of a full, non-linear quadcopter model for the optimization-based generation of  trajectories. However, the resulting trajectories need to be flown by a real quadcopter and hence one must relate the approximate model to the full model of the quadcopter. Here we briefly summarize the modeling and control aspects necessary for replication of our method. A full introduction to this topic is beyond the scope of this work and we refer the interested reader to <cit.>.



 §.§ Quadrotor Model

A quadrotor is a robot with four identical rotors which generate a thrust and a moment orthogonal to
the square they span. Our quadrotor model closely follows <cit.>.
To describe the configuration of a quadrotor we define its position as the
location of the center of mass in an inertial world coordinate frame
(𝐱_W, 𝐲_W, 𝐳_W),
and its attitude as the rotation of the body-fixed frame
(𝐱_B, 𝐲_B, 𝐳_B) with
respect to the world frame (see fig:quadrotor). The rotation matrix from body
to world frame is then given by
R_BW = [𝐱_B 𝐲_B 𝐳_B] ∈𝕊𝕆(3).
Each rotor of the drone has an angular speed
ω_i and produces a force F_i and moment M_i, according to

    F_i = k_Fω_i^2 ,    M_i = k_M ω_i^2 ,

where k_F and k_M are constants specific to the rotors. Therefore, the control input to the
quadrotor can be written as 𝐮 where u_1 is the net force in
𝐳_B direction and
u_2, u_3, u_4 are the moments in 𝐱_B, 𝐲_B, 𝐳_B direction
acting on the quadrotor.
The input can be expressed in terms of
the rotor speeds ω_1, ω_2, ω_3, ω_4:

    [ u_1; u_2; u_3; u_4 ]
    =
    [   k_F   k_F   k_F   k_F;     0  k_FL     0 -k_FL; -k_FL     0  k_FL     0;   k_M  -k_M   k_M  -k_M ][ ω_1^2; ω_2^2; ω_3^2; ω_4^2 ] ,

where L is the distance from the axis of rotation of the rotors to the center of mass of the quadrotor.

The position of the quadrotor in the world frame can be specified according to Newton's
equation of motion governing the acceleration of a mass point:

    m𝐫̈ = u_1 𝐳_B + m 𝐠∈ℝ^3 ,

where 𝐫 is the position vector, 𝐠 = [0, 0, -g]^T is the gravity vector pointing along the -z axis of the
world frame, g is the gravitational constant and m is the mass of the quadrotor.



The Euler rotation equations are

    𝐌_B = I ω̇_BW + ω_BW× I ω_BW∈ℝ^3 ,

where 𝐌_B = [u_2, u_3, u_4]^T = [ω_x, ω_y, ω_z]^T is the moment vector acting on the quadrotor in
the body frame, ω_BW is the angular velocity of the body frame in the world frame
and I is the moment of inertia of the quadrotor in the body frame.






 §.§ Quadrotor Control

As can be seen from the equations (<ref>),
(<ref>) and (<ref>),
the quadrotor configuration has 6 degrees of freedom but only 4 actuators.
Therefore it is an underactuated system and cannot follow arbitrary trajectories in
the configuration space.
However, Mellinger et al. show that the system is
flat <cit.> with respect to the
4 flat outputs
[𝐫, ψ]^T and thus a quadrotor can follow trajectories in this space, given that the corresponding inputs are bounded to values that the quadrotor can achieve <cit.>.
This flat output space is the configuration of our approximate quadrotor model.
 
We use the linear controller from <cit.> to generate the corresponding inputs for the quadrotor.
The desired thrust along the z-axis of the body frame is computed as

    𝐅_d = -K(𝐱 - 𝐱_d) + m(g𝐳_w + 𝐫̈_d) ,

where x=[𝐫,ṙ]^T is the actual and 𝐱_d the desired position and velocity of the quadrotor and m(g𝐳_w +𝐫̈_d) the feedforward term which compensates for gravity and known accelerations. 
The state feedback matrix K is computed using a linear quadratic control strategy with integral action. 

The desired force F_d already defines two degrees of freedom of the quadrotor attitude. Using the nonlinear control strategy on SO(3) described in <cit.> we employ the desired yaw angle ψ_d to compute the desired
attitude R_BWd of the quadrotor:

    𝐳_Bd    = 𝐅_d/||𝐅_d||
    𝐲_Bd    = 𝐳_Bd× [cos(ψ_d), sin(ψ_d), 0]^T/|| 𝐳_Bd× [cos(ψ_d), sin(ψ_d), 0]^T||
    𝐱_Bd    = 𝐲_Bd×𝐳_Bd
    
    	R_BWd    = [𝐱_Bd,𝐲_Bd,𝐳_Bd] ,

where
𝐲_Bd are the desired x- and y-axis of the body frame.
To control the attitude we can now calculate the desired moment vector 𝐌_Bd in
𝐱_B,𝐲_B,𝐳_B direction,

    𝐞_R     = 1/2𝑣𝑒𝑒( R_d^T R_BW - R_BW^T R_d) 
    𝐞_ω    = R_BW^-1( ω_BW - ω_BWd) 
    𝐌_Bd    = -K_R𝐞_R - K_ω𝐞_ω ,

where R_BW is the actual rotation of the quadrotor, 𝐞_R is the rotation error,
ω_BW, ω_BWd are the angular and desired angular velocity, 𝐞_ω is
the angular velocity error and 𝑣𝑒𝑒 is the vee map from
so(3) →ℝ^3.
From 𝐅_d and 𝐌_Bd we can calculate the input u
and thereby the velocities of the rotors needed
to reach the desired position and yaw angle:

    u_1    = 𝐅_d·𝐳_B
    
    	[u_2,u_3,u_4]^T    = 𝐌_Bd ,

where (<ref>) is the projection of the desired thrust 𝐅_d on the actual
z-vector of the body frame 𝐳_B. Finally, using (<ref>)
we can compute the angular velocities ω_i corresponding to the input u.



 §.§ Validity of Approximate Quadrotor Model

Following the approach in <cit.>, we assume that the rotational dynamics of a quadrotor are fast compared to its
translational dynamics thus we can describe the behavior of the quadrotor by the thrust
vector 𝐮_r and the moment u_ψ along the body-frame z-axis.
In the following we will only refer to the norm u_r of the force vector
𝐮_r

Let F_max be the maximum force and M_max be the maximum moment each motor can produce.
Then the bound on the maximum possible thrust that the quadrotor can
achieve (i.e. all motors full on) is

    u_r≤ u_r,max = 4 F_max

and the bound on the maximum possible moment (i.e. two motors rotating in same
direction full on and the other two off) is

    u_ψ≤ u_ψ,max = 2 M_max .

Because the force and moment are coupled it is not possible to
achieve full thrust u_r,max and full moment
u_ψ,max at the same time.

Let us now assume a stricter bound on the maximum moment of the quadrotor:

    u_ψ≤ u_ψ,𝑙𝑖𝑚 = β u_ψ,max

where β∈ [0, 1].
If we want to be able to achieve a moment of u_ψ,𝑙𝑖𝑚 at
all times we have to take into account that in the extreme case
two motors will be limited to a force of
F_𝑙𝑖𝑚 = (1 - β) F_max
and thus the bound on the thrust of the quadrotor is

    u_r≤ u_r,𝑙𝑖𝑚 = (2 + 2 (1 - β)) F_max
    = ( 1 - β/2) u_r,max.

For example, if β = 0.2, i.e. bounding the moment
to 20% of the quadrotors maximum moment the quadrotor can still achieve 90% of 
its maximum thrust at all times.
These limits still allow the agility of a quadrotor to be sufficient for  many use cases.






