IEEE Robotics & Automation Magazine - September 2011 - 35
set of continuous control inputs U, and a set of continuous
disturbance inputs D.
In each mode i 2 Q, the continuous state evolves according to an ordinary differential equation model
_ ¼ fi (x(t), u(t), d(t)),
x(t)
⋅
x = f1(x, u, d )
(1)
where u and d are the continuous control and disturbance
inputs, respectively. The evolution of the discrete state is
described by a transition function F : Q 3 X 3 R ! Q,
which can be viewed as a slight generalization of the state
transition function used in formal descriptions of finite
automata and discrete event systems (see [26]). As an
example, the transition logic for Mode 1 in Figure 1 is
described by F(1, x, r) ¼ 2 when either x 2 E12 or r ¼ 2,
and Fð1; x; rÞ ¼ 1 otherwise.
Under this model, an execution of the hybrid system proceeds roughly as follows. From an initial state
ði; x0 Þ 2 Q 3 X, the continuous state evolves according to
(1), while the discrete state remains constant until the first
time t1 when the function F evaluates to a discrete state
j 6¼ i. This triggers a discrete jump from i to j while the
continuous state remains constant. The continuous state
then evolves according to the dynamics in mode j, and the
whole process is repeated. A simple example of a hybrid
trajectory is given in Figure 1, where the mode transitions
at time instants t1 and t4 are autonomous jumps due to the
continuous state x hitting the guard conditions E12 and
E21 , while the ones at t2 and t3 are controlled transitions
triggered by changes in the discrete command r.
The rest of the article focuses on controller design and
synthesis methods for the class of hybrid systems described
here. More specifically, the goal is to find control policies
for the continuous and discrete inputs that drive the hybrid
state into a designated region at the end of the control horizon without hitting some known unsafe sets during the
process. Such a design goal is difficult to achieve for hybrid
systems because of the entanglement between their discrete
and continuous dynamics. In the following section, a
reachability-based approach will be introduced to tackle
this challenging problem.
Reachability
Background
Reachability analysis for hybrid systems has been a prolific
area of research over the past two decades. Existing methods in this field can be broadly classified according to the
assumptions on the continuous time dynamics (clocks
[27], linear [12], [28], and nonlinear [9], [14]) and the
types of set computation (discrete abstraction [19], [29],
polytopes [17], ellipsoids [13], and numerical discretization [30], [31]).
In this article, the methods for controller design and
synthesis are based upon the Hamilton-Jacobi approach to
reachability analysis as described in [9] and [31], with the
x ∈ E21 or σ = 1
Mode q = 1
x (t )
Mode q = 2
⋅
x = f2(x, u, d )
x ∈ E12 or σ = 2
Guard-Triggered Transition
Controlled
Transition
x0
q=1
q=2
t1
q=1
t2
q=2
t3
q=1
t4
t
Figure 1. An example of a hybrid system model and its
trajectory.
advantages of being able to handle nonlinear system
dynamics and bounded time-varying disturbances. The
effectiveness of this approach has been demonstrated in
applications such as design of aerobatic maneuvers [32],
synthesis of robust motion control strategies [10], and
planning in adversarial scenarios [33].
Continuous-Time Hamilton-Jacobi Reachability
Before going into the specifics of the controller design and
synthesis methods, some basic definitions of continuoustime reachable sets will be introduced along with a brief
review of how these sets can be computed using the
method of Hamilton-Jacobi reachability. In this preliminary discussion, the system dynamics are assumed to be
_ ¼ f ðxðtÞ; uðtÞ; dðtÞÞ, xð0Þ ¼ x0 , evolving in Rn subxðtÞ
ject to uðtÞ 2 U, dðtÞ 2 D.
First, consider a safety verification problem where some
unsafe terminal set A & Rn to be avoided is specified,
along with a set of permissible initial conditions X0 ; the
task is to prove that X0 does not contain any state from
which the system trajectory terminates inside A within
some time s. This involves computing the set of states for
which regardless of the input u, there exists some choice of
disturbance d such that xðsÞ 2 A. This will be referred to
as the avoid set over time s denoted by AðA; sÞ.
One possible way of computing this set is via optimal
control. As a first step, a continuous function l : Rn ! R is
constructed such that lðxÞ 0 if and only if x 2 A, where l
is commonly referred to as a level set function. Now, consider a terminal cost problem where the control seeks to
maximize lðxðsÞÞ while the disturbance tries to minimize
the same. The value function at the initial time is then given
by Jðx; 0Þ ¼ maxuðÁÞ mindðÁÞ lðxðsÞÞ, where the maximization
and minimization are taken over realizations of the input
and disturbance over the interval ½0; s. Here, the input u is
allowed to be selected according to a state feedback strategy.
Clearly, AðA; sÞ is the set of states x such that Jðx; 0Þ 0
(see Figure 2). Moreover, it has been shown [34] that J is the
SEPTEMBER 2011
*
IEEE ROBOTICS & AUTOMATION MAGAZINE
*
35
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2011
IEEE Robotics & Automation Magazine - September 2011 - Cover1
IEEE Robotics & Automation Magazine - September 2011 - Cover2
IEEE Robotics & Automation Magazine - September 2011 - 1
IEEE Robotics & Automation Magazine - September 2011 - 2
IEEE Robotics & Automation Magazine - September 2011 - 3
IEEE Robotics & Automation Magazine - September 2011 - 4
IEEE Robotics & Automation Magazine - September 2011 - 5
IEEE Robotics & Automation Magazine - September 2011 - 6
IEEE Robotics & Automation Magazine - September 2011 - 7
IEEE Robotics & Automation Magazine - September 2011 - 8
IEEE Robotics & Automation Magazine - September 2011 - 9
IEEE Robotics & Automation Magazine - September 2011 - 10
IEEE Robotics & Automation Magazine - September 2011 - 11
IEEE Robotics & Automation Magazine - September 2011 - 12
IEEE Robotics & Automation Magazine - September 2011 - 13
IEEE Robotics & Automation Magazine - September 2011 - 14
IEEE Robotics & Automation Magazine - September 2011 - 15
IEEE Robotics & Automation Magazine - September 2011 - 16
IEEE Robotics & Automation Magazine - September 2011 - 17
IEEE Robotics & Automation Magazine - September 2011 - 18
IEEE Robotics & Automation Magazine - September 2011 - 19
IEEE Robotics & Automation Magazine - September 2011 - 20
IEEE Robotics & Automation Magazine - September 2011 - 21
IEEE Robotics & Automation Magazine - September 2011 - 22
IEEE Robotics & Automation Magazine - September 2011 - 23
IEEE Robotics & Automation Magazine - September 2011 - 24
IEEE Robotics & Automation Magazine - September 2011 - 25
IEEE Robotics & Automation Magazine - September 2011 - 26
IEEE Robotics & Automation Magazine - September 2011 - 27
IEEE Robotics & Automation Magazine - September 2011 - 28
IEEE Robotics & Automation Magazine - September 2011 - 29
IEEE Robotics & Automation Magazine - September 2011 - 30
IEEE Robotics & Automation Magazine - September 2011 - 31
IEEE Robotics & Automation Magazine - September 2011 - 32
IEEE Robotics & Automation Magazine - September 2011 - 33
IEEE Robotics & Automation Magazine - September 2011 - 34
IEEE Robotics & Automation Magazine - September 2011 - 35
IEEE Robotics & Automation Magazine - September 2011 - 36
IEEE Robotics & Automation Magazine - September 2011 - 37
IEEE Robotics & Automation Magazine - September 2011 - 38
IEEE Robotics & Automation Magazine - September 2011 - 39
IEEE Robotics & Automation Magazine - September 2011 - 40
IEEE Robotics & Automation Magazine - September 2011 - 41
IEEE Robotics & Automation Magazine - September 2011 - 42
IEEE Robotics & Automation Magazine - September 2011 - 43
IEEE Robotics & Automation Magazine - September 2011 - 44
IEEE Robotics & Automation Magazine - September 2011 - 45
IEEE Robotics & Automation Magazine - September 2011 - 46
IEEE Robotics & Automation Magazine - September 2011 - 47
IEEE Robotics & Automation Magazine - September 2011 - 48
IEEE Robotics & Automation Magazine - September 2011 - 49
IEEE Robotics & Automation Magazine - September 2011 - 50
IEEE Robotics & Automation Magazine - September 2011 - 51
IEEE Robotics & Automation Magazine - September 2011 - 52
IEEE Robotics & Automation Magazine - September 2011 - 53
IEEE Robotics & Automation Magazine - September 2011 - 54
IEEE Robotics & Automation Magazine - September 2011 - 55
IEEE Robotics & Automation Magazine - September 2011 - 56
IEEE Robotics & Automation Magazine - September 2011 - 57
IEEE Robotics & Automation Magazine - September 2011 - 58
IEEE Robotics & Automation Magazine - September 2011 - 59
IEEE Robotics & Automation Magazine - September 2011 - 60
IEEE Robotics & Automation Magazine - September 2011 - 61
IEEE Robotics & Automation Magazine - September 2011 - 62
IEEE Robotics & Automation Magazine - September 2011 - 63
IEEE Robotics & Automation Magazine - September 2011 - 64
IEEE Robotics & Automation Magazine - September 2011 - 65
IEEE Robotics & Automation Magazine - September 2011 - 66
IEEE Robotics & Automation Magazine - September 2011 - 67
IEEE Robotics & Automation Magazine - September 2011 - 68
IEEE Robotics & Automation Magazine - September 2011 - 69
IEEE Robotics & Automation Magazine - September 2011 - 70
IEEE Robotics & Automation Magazine - September 2011 - 71
IEEE Robotics & Automation Magazine - September 2011 - 72
IEEE Robotics & Automation Magazine - September 2011 - 73
IEEE Robotics & Automation Magazine - September 2011 - 74
IEEE Robotics & Automation Magazine - September 2011 - 75
IEEE Robotics & Automation Magazine - September 2011 - 76
IEEE Robotics & Automation Magazine - September 2011 - 77
IEEE Robotics & Automation Magazine - September 2011 - 78
IEEE Robotics & Automation Magazine - September 2011 - 79
IEEE Robotics & Automation Magazine - September 2011 - 80
IEEE Robotics & Automation Magazine - September 2011 - 81
IEEE Robotics & Automation Magazine - September 2011 - 82
IEEE Robotics & Automation Magazine - September 2011 - 83
IEEE Robotics & Automation Magazine - September 2011 - 84
IEEE Robotics & Automation Magazine - September 2011 - 85
IEEE Robotics & Automation Magazine - September 2011 - 86
IEEE Robotics & Automation Magazine - September 2011 - 87
IEEE Robotics & Automation Magazine - September 2011 - 88
IEEE Robotics & Automation Magazine - September 2011 - 89
IEEE Robotics & Automation Magazine - September 2011 - 90
IEEE Robotics & Automation Magazine - September 2011 - 91
IEEE Robotics & Automation Magazine - September 2011 - 92
IEEE Robotics & Automation Magazine - September 2011 - 93
IEEE Robotics & Automation Magazine - September 2011 - 94
IEEE Robotics & Automation Magazine - September 2011 - 95
IEEE Robotics & Automation Magazine - September 2011 - 96
IEEE Robotics & Automation Magazine - September 2011 - 97
IEEE Robotics & Automation Magazine - September 2011 - 98
IEEE Robotics & Automation Magazine - September 2011 - 99
IEEE Robotics & Automation Magazine - September 2011 - 100
IEEE Robotics & Automation Magazine - September 2011 - 101
IEEE Robotics & Automation Magazine - September 2011 - 102
IEEE Robotics & Automation Magazine - September 2011 - 103
IEEE Robotics & Automation Magazine - September 2011 - 104
IEEE Robotics & Automation Magazine - September 2011 - 105
IEEE Robotics & Automation Magazine - September 2011 - 106
IEEE Robotics & Automation Magazine - September 2011 - 107
IEEE Robotics & Automation Magazine - September 2011 - 108
IEEE Robotics & Automation Magazine - September 2011 - 109
IEEE Robotics & Automation Magazine - September 2011 - 110
IEEE Robotics & Automation Magazine - September 2011 - 111
IEEE Robotics & Automation Magazine - September 2011 - 112
IEEE Robotics & Automation Magazine - September 2011 - 113
IEEE Robotics & Automation Magazine - September 2011 - 114
IEEE Robotics & Automation Magazine - September 2011 - 115
IEEE Robotics & Automation Magazine - September 2011 - 116
IEEE Robotics & Automation Magazine - September 2011 - 117
IEEE Robotics & Automation Magazine - September 2011 - 118
IEEE Robotics & Automation Magazine - September 2011 - 119
IEEE Robotics & Automation Magazine - September 2011 - 120
IEEE Robotics & Automation Magazine - September 2011 - 121
IEEE Robotics & Automation Magazine - September 2011 - 122
IEEE Robotics & Automation Magazine - September 2011 - 123
IEEE Robotics & Automation Magazine - September 2011 - 124
IEEE Robotics & Automation Magazine - September 2011 - 125
IEEE Robotics & Automation Magazine - September 2011 - 126
IEEE Robotics & Automation Magazine - September 2011 - 127
IEEE Robotics & Automation Magazine - September 2011 - 128
IEEE Robotics & Automation Magazine - September 2011 - 129
IEEE Robotics & Automation Magazine - September 2011 - 130
IEEE Robotics & Automation Magazine - September 2011 - 131
IEEE Robotics & Automation Magazine - September 2011 - 132
IEEE Robotics & Automation Magazine - September 2011 - 133
IEEE Robotics & Automation Magazine - September 2011 - 134
IEEE Robotics & Automation Magazine - September 2011 - 135
IEEE Robotics & Automation Magazine - September 2011 - 136
IEEE Robotics & Automation Magazine - September 2011 - Cover3
IEEE Robotics & Automation Magazine - September 2011 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2023
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2022
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2021
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2020
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2019
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2018
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2017
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2016
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2015
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2014
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2013
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2012
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_june2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_march2011
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_december2010
https://www.nxtbook.com/nxtbooks/ieee/roboticsautomation_september2010
https://www.nxtbookmedia.com