IEEE Robotics & Automation Magazine - September 2011 - 38

or as the optimal control synthesized according to (4). This
ensures that the system state is driven inside SkÀ1 within s1
time units while avoiding the set AH . Once this occurs,
there exists, by the definition of the set SkÀ1 , a choice of
discrete control to switch the system state into the set
RAH ðSkÀ2 ; AH ; s2 Þ. Specifically, for a given ðq; xÞ 2 SkÀ1 ,
the discrete control can be chosen from the set
È

É
r 2 R : (F(q, x, r), x) 2 RAH (SkÀ2 , AH, s2 ) :

Once the system state enters RAH (SkÀ2 , AH, s2 ), a continuous control can be chosen so as to drive the system state into
SkÀ2 , and the process repeats until S0 ¼ RH is reached.
It can be observed that the performance of the controller obtained from this design procedure will be dependent
on the accuracy of the continuous-time reachability calculations. As discussed in [35], the accuracy of the numerical
solutions obtained from the Level Set Toolbox is directly
related to the size of the discrete grid on which the computation is carried out. For applications requiring stringent
performance guarantees, conservative approximations of
the reach-avoid sets can be obtained when bounds on the
numerical errors are available.
To close this section, we remark that in digital control
applications where the controls can only be exerted at sampling instants, a possible approach is to discretize the

Figure 4. STARMAC quadrotor performing an autonomous
backflip maneuver.

Recovery

Drift

Impulse

Figure 5. The backflip maneuver broken into three modes. The
vehicle travels from right to left, spinning clockwise. The size of
each arrow indicates the relative thrust from each rotor.

IEEE ROBOTICS & AUTOMATION MAGAZINE

SEPTEMBER 2011

continuous input range of u and reduce the problem to a
selection of discrete input levels and switching controls at
sampling instants [10]. This approach is briefly discussed
in the "Applications: Synthesis of Robust Motion Control
Policies" section.
Applications
In this section, we will describe several application examples where the theoretical techniques outlined in the
preceding sections have been used to design and verify
control schemes for complex systems. These examples
have been chosen to illustrate the power and flexibility of
reachability analysis in system verification and controller
design and synthesis. Because of space constraints, each
example is covered briefly, and the reader is encouraged to
review the cited articles for more detail.
Aerobatic Maneuver Design and Execution
The first example shows the reachability-based techniques
applied to the design of guaranteed safe aerobatic maneuvers [22]. In this work, reachability analysis was used to
design and implement a backflip maneuver for a quadrotor
helicopter (Figure 4), part of the Stanford Testbed of
Autonomous Rotorcraft for Multi-Agent Control (STARMAC). Reachable sets were used to guarantee that the
quadrotor would be able to safely complete the backflip
even under worst-case disturbances.
Reachable Sets for Attainability and Safety
Since the quadrotor's propellors cannot generate negative
thrust, the motors must be turned off during inverted flight.
As a result, the backflip was divided into three modes as
shown in Figure 5: 1) impulse, in which the rotation of the
vehicle is initialized; 2) drift, where the vehicle freely rotates
and falls under gravity; and 3) recovery, which brings the
vehicle to a controlled hover condition. For ease of analysis
and visualization, the quadrotor's continuous dynamics was
decoupled into the rotational state space, which was analyzed to ensure attainability, and the vertical state space,
which was analyzed to ensure safety. This application can
thus be viewed as a special case of the hybrid control problem described in the "Reachability: Hybrid System Reachability and Control" section, with a sequence of three modes
and two discrete switches occurring between the impulse
and drift and drift and recovery modes.
For this particular example, Algorithm 1 is initialized
using the final target set R3 . The continuous-time reach-
avoid set calculation is decoupled into a capture set computation in the rotational state space and an avoid set computation in the vertical state space under a particular choice of
closed-loop controller for each mode. Details of the avoid
set computations are omitted here, but the reader is encouraged to refer to [22] for more information. The preimage of
a set in mode i of the mode sequence is simply the same set
in both mode i and i À 1, resulting in a simple computation
for the Pre operator. The resulting capture sets are shown in

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2011