IEEE Robotics & Automation Magazine - September 2011 - 47

Problem Solution
The control problem can be interpreted as a game between u
and d in which d has full information about the environment
state (the mode) while u is uninformed. In the theory of
games, such problems with imperfect information have been
elegantly solved by first translating them into equivalent
problems with full-state information and then leveraging the
available techniques for solving games of perfect information
[36]. To formulate an equivalent problem with full-state
information, an estimator is introduced. For details on the
conditions for equivalence, the reader is referred to [37]-[39].
Definition 3
An estimator is a hybrid automaton with uncontrolled
^ X, U, D, Y, ^Inv, R,
^ ¼ (Q,
^ ^f ), in which
mode transitions H
Q ^
X
^
^
^
Q  2 , Inv ¼ fg, f : X 3 Q 3 U 3
S D ! 2 is a set^
valued map such that f (x, ^q, u, d) :¼ q2^q f (x, q, u, d), ^q(t)
is such that q(t) 2 ^q(t) for all t ! 0, and ^x_ (t) 2 ^f (^x(t),
^q(t), u(t), d(t)) while ^q(t) is constant.
Here, 2Q denotes the set of all subsets of Q. The estimator
keeps track of a set of possible modes compatible with the
measurements and with the system dynamics (see [10] and
[14] and the references therein). Here, we show how to construct a suitable estimator for the application example.

^ in which we have set u(t) ¼ p^(^q(t), ^x(t)). The capsystem H
S
^ :¼
^ ^q ), in
^ is given by C
ture set for system H
q3C
^ (^
^q2Q
p^
^
which C^q :¼ fx0 2 X j8 p^, 9d, y, t ! 0 s:t: some/^x (t, (^q, x0 ),
d, y) 2 Badg is called a mode-dependent capture set. It is
the set of all continuous states that are taken to Bad for all
feedback maps when the initial mode estimate is equal to ^q.
Problem 1
^ and a feedback map p^ that keeps any
Determine the set C
^ outside it.
trajectory starting outside C
We briefly describe the solution as it appears in
^ and F  X, define
[37]-[39]. For this purpose, for any ^q 2 Q
the operator Pre as Pre(^q, F) :¼ fx 2 X j 8 p^, 9 d, t ! 0
s:t:some /^px^ (t, (^q, x), d, ) 2 Fg, in which /^px^ (t, (^q, x), d, )
^ when the mode ^q(t) stays
is the continuous trajectory of H
constant. Hence, Pre(^q, F) is a set of all continuous states that
are taken to F for all feedback maps when the mode estimate
^ can be obtained
^ ^q for ^q 2 Q
is kept constant to ^q. The sets C
as a fixed point of the following algorithmic procedure.
^ ¼ f^q1 , ...,^qM g, Si  X for i 2 f1, ...,Mg, and define
Let Q
S ¼ (S1 , ...,SM ). We define the map G : (2X )M ! (2X )M as
2
 S
 3
S
[
Bad
Pre ^q1 , fjj^qj 2R(^
^ q , Y)g j
1
6
7
6
7
..
G(S) :¼ 6
7:
.


4
5
S
Pre ^qM , fjj^qj 2R(^
^ qM , Y)g Sj [ Bad

Application Scenario
^ X, U, D, Y, ^Inv, R,
^ ¼ (Q,
^ ^f ), in which
We have H
*
^
Q ¼ f^q1 , ^q2 , ^q3 g with ^q1 ¼ fA, Bg, ^q2 ¼ fAg, ^q3 ¼ fBg,
Algorithm 1
and ^qð0Þ ¼ ^q1 . We define Y ¼ fyA , yB g. Starting in ^q1 ,
S0 :¼ (S01 , S02 , . . .0M ) :¼ (Ø, . . . , Ø)
event yA occurs as soon as B is not currently possible given
S1 ¼ G(S0 )
the measurement x, and event yB occurs as soon as A is not
while
SkÀ1 6¼ Sk do
currently possible given the measurement x. This results in
^
^
^
Skþ1 ¼G(Sk )
the map R defined as R(^q1 , yA ) :¼ ^q2 and R(^q1 , yB ) :¼ ^q3
leads to the automaton given in Figure 2.
end while.
To establish when A or B is ruled
out given the measurement of x, we
^
consider
the estimate b(t)¼(1=t)
Rt
_
0 v2 (s)ds, t !T, where T >0 is a
∧
time window. Note that, in practice,
P
q1 = {A, B }
we will not require measurement
f1(p1, v1, u )
⋅
≤
x ∈ ±
of acceleration, as we will consider
h ∧ f2(p2, v2, q , D )
q
∈
q
discrete time models where derivative
is replaced by time anticipation. If
the mode is q, then we necessarily
 Thus, for
^
cq d:
have that jbðtÞÀb
qj
yA
yB
^
t >T, define yðtÞ¼yA if jb(t)Àb
Bj >
P
^
 yðtÞ ¼ yB if jb(t)Àb

cB d,
A j > cA d,
and y(t) ¼  otherwise.
∧
Basically, the continuous dynam∧
q3 = {B }
q2 = {A}
^
ics of H describes a set of dynamics
f1(p1, v1, u ) ≤
f1(p1, v1, u ) ≤
⋅
⋅
x ∈ ±
x ∈ ±
of x that are compatible with the
h ∧ f2(p2, v2, q , D )
h ∧ f2(p2, v2, q , D )
q ∈q
q ∈q
current discrete state estimate. Let
^
p^ : Q 3 X ! U be a feedback map.
We denote the x trajectories of the
closed-loop system by /^px^ (t, (q0 , x0 ),
^
d, y), which are given by the Figure 2. Hybrid automaton H.
1

P

3

2

SEPTEMBER 2011

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

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