1

Mixed Strategy for
Constrained Stochastic Optimal Control

arXiv:1607.01478v1 [cs.RO] 6 Jul 2016

Masahiro Ono, Mahmoud El Chamie, Marco Pavone, and Behçet Açikmeşe

Abstract—Choosing control inputs randomly can result in a
reduced expected cost in optimal control problems with stochastic
constraints, such as stochastic model predictive control (SMPC).
We consider a controller with initial randomization, meaning that
the controller randomly chooses from K+1 control sequences at
the beginning (called K-randimization). It is known that, for a
finite-state, finite-action Markov Decision Process (MDP) with K
constraints, K-randimization is sufficient to achieve the minimum
cost. We found that the same result holds for stochastic optimal
control problems with continuous state and action spaces. Furthermore, we show the randomization of control input can result
in reduced cost when the optimization problem is nonconvex, and
the cost reduction is equal to the duality gap. We then provide
the necessary and sufficient conditions for the optimality of a
randomized solution, and develop an efficient solution method
based on dual optimization. Furthermore, in a special case with
K = 1 such as a joint chance-constrained problem, the dual
optimization can be solved even more efficiently by root finding.
Finally, we test the theories and demonstrate the solution method
on multiple practical problems ranging from path planning to the
planning of entry, descent, and landing (EDL) for future Mars
missions.

Fig. 1. A toy example illustrating the concept of mixed-strategy SMPC. The
driver chooses between Paths A and B by a coin flip with equal probability.
If the upper bound on risk is 1%, the mixed strategy satisfies the chance
constraint and the expected cost is less than the optimal deterministic choice,
Path A.

I. I NTRODUCTION

T

HE main finding of this paper is that, in optimal control
problems with stochastic constraints, choosing control
inputs randomly can result in a less expected cost than
deterministically optimizing them. To communicate the idea,
consider the following toy problem illustrated in Figure 1.
The goal is to plan a path to go to the goal with a minimum
expected cost while limiting the chance of failure to 1 %. There
are two path options, A and B. A has the expected cost of 20
and the chance of failure is 0.5%; B has the expected cost
of 10 and the chance of failure is 1.5%. Choosing B violates
the chance constraint, hence the optimal solution is A if only
deterministic choice is allowed. However, we can create a
mixed solution by flipping a coin to randomly choose between
A and B. Assuming the probability of head and tail is 0.5, the
resulting mixed solution has the expected cost of 15 and a
1% chance of failure, which satisfies the chance constraint.
The expected cost of the mixed solution is less than that of
A. In the example above, A and B are represented by two
different sequences of control inputs. When a mixed strategy
Masahiro Ono (ono@jpl.nasa.gov) is with Jet Propulsion Laboratory, California Institute of Technology, 4800 Oak Grove Drive, Pasadena,
CA, USA. Copyright 2016 California Institute of Technology. Government
sponsorship acknowledged.
Mahmoud El Chamie (melchami@uw.edu) and Behçet Açikmeşe
(behcet@uw.edu) are with University of Washington, Seattle, WA
98195.
Marco Pavone (pavone@stanford.edu) is with the Department of
Aeronautics and Astronautics, Stanford University, Stanford, CA 94305

Fig. 2. Solutions of Figure 1 in cost-risk space. Mixed strategies convexify
the solution set.

is employed, the system flips a coin once at the beginning,
and choose a sequence according to the result of the coin flip.
Once a sequence is selected, the system sticks to the sequence
until the end.
Mixed strategy is essentially a convexification. As shown in
Figure 2, in the cost-risk space, the set of the pure strategies is
a nonconvex set consisting of two points. The solution set of
mixed strategies is a line segment between A and B, which is
the convex hull of the pure solution set. In general, as shown in
Figure 3, when the original problem is nonconvex, introducing
mixed strategy extends the solution set, which could improve
the cost of the optimal solution. The improvement is equal
to the duality gap. When there is no duality gap, the optimal
mixed solution is equivalent to the optimal pure solution (i.e.,

2

choosing the optimal pure solution with the probability of
one.) Therefore, the optimal solution to the mixed strategy
problem is always as good as the optimal solution to the
original problem.
In general, unlike the illustrative example above, a stochastic optimal control problem has infinitely many solutions.
An optimal mixed-strategy controller first computes a finite
number of control sequences, them randomly chooses one
from them. The formal problem definition is given as an
extension to a standard finite-horizon, constrained stochastic
optimal control problem, where K+1 control sequences and
the probability to choose the control sequences are optimized
(called K-randomization). The degree of randomization, K, is
pre-specified. The controller chooses one control sequence at
the beginning (hence called initial randomization). Then the
chosen control sequence is executed till the end.
The contribution of this paper is three-fold. First, we provide rigorous characterizations of mixed-strategy, constrained
stochastic optimal control, which are summarized in Theorems
1-3 in Section II. Theorem 1 in Section II-B provides the
sufficient degree of randomization. Specifically, for a problem
with K constraints, K-randomization is sufficient for optimality. Theorem 2 in Section II-C states that the attainable cost
reduction by mixed strategy is equivalent to the duality gap
in the original (non-randomized) problem. This is because the
original problem is convexified by mixed strategy. In other
words, mixed strategy can improve the solution only if the
original problem is nonconvex. Theorem 3 in Section II-D
provides the necessary and sufficient conditions for optimality,
which is built upon the consists of a subset of KKT conditions
and an additional constraint requiring that all the candidate
control sequences are the minimizers of the Lagrangian function with the optimal dual variable.
The second contribution of this paper is to develop an
efficient solution approach to the mixed-strategy, constrained
stochastic optimal control problem. A naive solution approach requires co-optimization of K + 1 control sequences
as well as the probability distribution, which is significantly
more complex than the original optimization problem without
randomization. A key observation is that, since the mixedstrategy optimization problem is the convexification of the
original problem, their dual optimal solutions are the same.
This observation leads to our general solution method that
solves the dual of the original optimization problem (without
randomization). The primal optimal solution for the mixedstrategy problem can be recovered from the dual optimal
solution. Furthermore, in a special case with K = 1, we
provide an even more efficient solution approach that solves
the dual problem with root finding. For a more specific
case where the proposed approach is applied to a linear
SMPC with nonconvex constraints, we present an efficient
and approximate solution approach where the minimization
of Lagrangian function is approximated by a MILP through
piece-wise linearization of the cumulative distribution function
of the state uncertainty.
The third contribution is to validate the theories and demonstrate the solution method in various practical scenarios. We
first show an example of SMPC-based path planning with

obstacles and a joint chance constraint, and show that mixed
strategy indeed improves the expected cost. We also show
that the proposed dual solution approach is also applicable
to a finite-state optimal control problem. Two examples are
presented in this domain: path planning with obstacles, and
the planning of entry, descent, and landing (EDL) for future
Mars rover/lander missions.
A. Related Work
In game theory, mixed strategy is usually discussed in a
context of simultaneous adversary game. A classical example
is paper-rock-scissors, where the sole Nash equilibrium is
to uniformly randomize the strategy for both players. An
underlying assumption here is that both players optimize their
strategy given the strategy of the other player. The SMPC
problem is different in that one player (controller) optimizes
her strategy given the strategy of the other (the nature) but not
vice versa. In other words, one player is cognitive while the
other is blind. In paper-rick-scissors with cognitive and blind
players, the cognitive player cannot be better off by employing
a mixed strategy. Therefore, the fact that the cognitive player
can be better off with a mixed strategy in optimal control
is seemingly contradictory. This is because, unlike players
in classical game-theoretic settings, the controller solves a
constrained optimization. Intuitively, the constraint and the objective work adversarially, like two players within a controller.
It is known that mixed strategy can improve the solution
of constrained Markov decision process (MDP). Major results
on this subject, including randomization, are summarized in
[1]. A stochastic optimal control problem can be viewed as an
MDP with continuous state and control spaces.
The majority of the existing methods for solving constrained
MDPs use the idea of convex-analytical (CA) approach [2].
The CA approach optimizes the performance metric of the
MDP by reducing the problem to an optimization of a
linear function over the set of occupancy measures; hence,
formulated as a linear program. The CA has shown to be
useful for solving MDPs with multiple criteria and constraints
when the constraints have the same additive structure as the
performance measure (i.e., linear function over the set of
occupancy measures). This paper on the other hand, do not
limit the constraints/performance metric to any structure, thus
it can be used for solving a more general class of constrained
MDPs.
The scope of our work considers the performance of a
mixture of nonrandomized policies (i.e., only considers initial
randomization). It is worth mentioning that previous work has
studied whether it is possible to split a randomized policy
(i.e., randomization of feedback control law) into a mixture of
deterministic policies while preserving performance [3]. It is
shown that any Markov policy is a mixture of nonrandomized
Markov policies [4, Theorem 5.2]. This inclusion suggests that
this work also generalizes to randomization of control policy.
Note that the proposed method is fundamentally different
from randomized SMPC methods such as scenario-based MPC
[5], [6]. In scenario-based MPC, the optimal control inputs
are deterministic but the solution method to obtain them is

3

randomized. In contrast, in this work, the optimal control
inputs are randomized but the solution method is deterministic.
Randomized control input was considered in a control theoretical context by [7], [8]. The problem considered in these studies
is the probabilistic coordination of swarms of autonomous
agents using a Markov chain controller. Here randomized
control is used for a different purpose than in our work.
In the Markov chain control randomized control inputs are
used to achieve the desired spacial density distribution of the
swarm agents without assuming inter-agent communication. In
contrast, in our work, randomized control inputs are used to
achieve less expected cost.
II. M ETHOD
The following is the rough sketch of the proposed solution
process.
1) Prove that the original problem and the mixed strategy
problem share the same dual optimal solution
2) Compute the dual optimal solution by solving the dual
of the original problem
3) Recover the primal optimal solution of the mixed strategy problem from the dual optimal solution
The solution method is explained in detail in the following
subsections.
A. Problem Formulation
We first formulate a pure-strategy problem that does not involve randomization. Consider a discrete-time optimal control
problem with K stochastic constraints, where the objective
and constraints are on the expected cost over a finite horizon,
{1 · · · T }. Let u := {u1 , u2 , · · · , uT } ∈ U T be the control
sequence, x := {x1 , x2 , · · · , xT } ∈ X T be the state sequence,
where U and X are the feasible control set and the state
space, respectively. We denote by w := {w1 , w2 , · · · , wT }
the sequence of exogenous disturbance, which follows a
known probability distribution. The system has a dynamics
represented by g(x, u, w) = 0. We consider a close-loop
control, where the feedback law at k-th time step is given
by a deterministic control policy µk : X 7→ U. Let M be the
set of deterministic control policy that we consider. Hence,
we seek for an optimal sequence of deterministic control
policy, µ := {µ1 , µ2 , · · · , µT } ∈ MT . We define K + 1 cost
functions, fi : X T × U T → R, for i = 0 · · · K. With a slight
abuse of notation, we denote the close-loop cost and dynamics
by fi (x, µ) and g(x, µ, w) = 0, respectively.
The problem is to minimize the expectation of f0 while
constraining the expectations of f1 · · · fK below V1 · · · Vk . The
minimized expected cost is denoted by c?P .
PSOC (Pure-strategy Stochastic Optimal Control
c?P =

min

µ∈MT
g(x,µ,w)=0

E [f0 (x, µ)]

s.t. E [fi (x, µ)] ≤ Vi ,

(1)
i = 1 · · · K.

(2)

A notable example of constraints in the form of (2) is a chance
constraint. Let XF ⊂ X be the set of feasible states. A chance

constraint imposes a bound on the probability that the state
stays within XF over the planning horizon:


Pr x ∈ XFT ≥ 1 − V.
(3)
This constraint is posed in the form of (2) by

0
(x ∈ XFT )
fi (x, µ) :=
.
1
(Otherwise)
The problem is reduced to an open-loop control problem
(i.e., optimization of control sequence) if M is limited to
constant functions. Typical feedback MPCs limits M to linear
feedback laws, u = Kx, where K is optimized. MDP usually
considers all the possible mappings with finite X and U.
Discussion in Section 2 poses no assumptions on X , U, and
M (except for standard assumptions such as ), hence it can be
applied to a variety of problems ranging from stochastic MPC
with continuous state and control to MDP with finite state and
control. Then, Sections 3 and 4 discusses more specialized
cases.
We next define the mixed-strategy problem, in which one of
N + 1 policy sequences is chosen at the beginning. Following
the convention in constrained MDP, we call such a randomization the N -randomization in this paper. Consider mixing
N + 1 policy sequences, µ1 · · · µN +1 . Let 0 ≤ pi ≤ 1 be the
probability that µi is chosen. The mixed strategy problem is
to optimize µ1 · · · µN +1 as well as p1 · · · pN +1 to minimize
the expected cost. The minimized expected cost is denoted by
c?N
M .
MSOCN (Mixed-strategy Stochastic Optimal Control)
c?N
M =

1

min
N +1

N
+1
X
T

µ ···µ
∈M
PN
j=1
j
j
j=1 p =1, p ≥0
g(x,µ,w)=0

s.t.

N
+1
X



pj E f0 (x, µj )

(4)



pj E fi (x, µj ) ≤ Vi

(5)

j=1

i = 1···K

B. Sufficient Degree of Randomization
Before solving MSOCN , we have to determine N . In other
words, we have to know what is the sufficient number of
control sequence to be mixed. We will show in this subsection
that K-randomization (N = K) is sufficient in order to
minimize c?N
M . In other words, for a problem with K stochastic
constraints, at most K + 1 control sequences need to be mixed
to form an optimal solution. The formal statement is given in
Theorem 1 later in this subsection. But we first need a few
preparations.
Let c = (c0 , c1 , · · · cK ) where ci is the i-th cost value:
ci = E [fi (x, µ)] .
We denote by F ⊂ RK+1 the feasible set of the costs of
the original problem, that is,
F := {c | µ ∈ M ∧ g(x, µ, w) = 0} .

(6)

4

We assume that F is a closed set, which typically holds when
U and X are closed sets. With F, PSOC (1), (2) can be written
in a simpler form as follows
PSOC’:
c?P = min c0

(7)

c∈F

s.t.

ci ≤ Vi ,

i = 1 · · · K.

(8)

play an important role in the analysis further in the paper.
Therefore, we will further assume that the Slater condition is
satisfied for the MSOC problem, i.e., there exists a feasible
point in the relative interior of conv(F). The Slater condition
guarantees a zero-duality gap. In general, it is easy to check
and is rarely violated in practical problems.
We also use the following simplified notation:
c?M := c?K
M .

Likewise, MSOCN is equivalent to:
MSOCN ’:

C. Cost Reduction by Randomization
1

N
+1
X

min

N +1

···c
∈F
PNc+1
j
j
j=1 p =1, p ≥0

pj cj0

(9)

j=1
N
+1
X

s.t.

pj cji ≤ Vi ,

(10)

j=1

where cj is the j-th cost vector and cji is its i-th component.
We note that, when actually solving the problem, we do
not explicitly compute F. We introduce it for the ease of
understanding.
For later convenience, we will derive another equivalent
form to MSOCN . Let


N
+1
+1

NX
X
N
pj = 1 . (11)
pj cj | cj ∈ F, 0 ≤ pj ,
FM
:=



We next discuss under what condition the mixed strategy
control can outperform pure strategies, and if it does, by how
much.
Lemma 1. The optimal mixed strategy control is at least as
good as the optimal pure strategy control, that is:
c?M ≤ c?P
Proof. If follows from the following:
0
K
F = FM
⊆ FM
.

Observe that MSOC ’ is equivalent to:

This result is obvious because a pure strategy control can
be viewed as a mixed strategy control that always assigns
the probability of one to a single control sequence. The next
question then is under what condition mixed strategies strictly
dominate pure strategies.

MSOCN ”:

Lemma 2. The necessary condition for

j=1

j=1

N

c?N
M

= min

N
c∈FM

s.t.

c0

c?M < c?P

(12)

ci ≤ Vi ,

i = 1 · · · K.

(13)

Let N be the set of positive integers. The following theorem
holds:
Theorem 1.
K ∈ arg min c?N
M .
N ∈N

is that F is a non-convex set.
Proof. We prove the contraposition. If F is a convex set, then
K
F = conv(F) = FM
.

Hence,
(14)

c?M = c?P .

N
Proof. From the definition of FM
, it is obvious that
i+1
i
FM
⊆ FM
,

∀i ∈ N.

?i+1
c?i
M ≥ cM ,

∀i ∈ N.

Therefore,
(15)

Also, since F ⊂ RK+1 , it follows from Caratheodory’s
Theorem that
i
FM
= conv(F),

∀i ∈ N, i ≥ K,

where conv(·) is the convex hull of a set. Therefore,
?i+1
c?i
M = cM ,

∀i ∈ N, i ≥ K.

(16)

The theorem follows from (15) and (16).
Theorem 1 means that we only need to consider Krandomization in order to minimize the expected cost. In the
remainder of this paper we only consider MSOCK , which we
simply denote by MSOC. Its dual problem DMSOCK will

The non-convexity of F is not a sufficient condition for
the strict dominance because the optimal solution to MSOCK
could be in F. Also note that the convexity of F is implied
by the convexity of PSOC, but not vice versa.
Figure 3 provides a graphical interpretation of the above
Lemmas in the case of K = 1. The set painted in solid blue
is F. Among F, the areas to the left of the vertical line at
c1 = V1 satisfies the constraint. Hence, the optimal solution to
PSOC is located at the intersection of the vertical line and the
lower edge of F, called the minimum common point and shown
in the green dot in Figure 3. Likewise, the optimal solution to
MSOCK is the minimum common point of conv(F) and the
vertical line. The dominance of mixed strategy (Lemma 1), as
well as the necessary condition for strict dominance (Lemma
2), is graphically obvious from Figure 3.
What follows next is the discussion on by how much the
mixed strategy can improve the expected cost, which requires

5

The left hand side of the above is equivalent to
K+1
X

min

c1 ···cK+1 ∈F
PK+1
i
i
i=1 p =1, p ≥0

pi (ci0 + λci1:K ).

i=1

A convex combination of a set of
cannot be less than
Pscalers
n
the minimum of the set, i.e., for i=1 pi = 1, pi ≥ 0, ci ∈ F,
K+1
X

pi (ci0 + λci1:K ) ≥ min c0 + λc1:K .
c∈F

i=1

Hence,
min
c∈conv(F )

c0 + λc1:K ≥ min c0 + λc1:K .
c∈F

(20)

From (19) and (20), it follows that
min
c∈conv(F )

c0 + λc1:K = min c0 + λc1:K .
c∈F

?
?
Since V is a constant, it follows from the above that qM
= qP
.
Therefore,
?
?
c?M = qM
= qP
= c?P − ∆.
(21)

Fig. 3.
A graphical interpretation of Lemmas 1 and 2 and Theorem
XX through the MC/MC framework [9]. Mixed strategy improves cost by
extending the feasible search space through convexification.

some preparations. The following is the dual optimization
problem of PSOC’, where the dual optimal cost is denoted
by p?P :
DPSOC (Dual of PSOC)
?
qP
= max min c0 + λ(c1:K − V ),
λ≥0 c∈F

(17)

where λ = [λ1 , · · · λK ] is the dual variables, c1:K =
[c1 , · · · cK ]T , and V = [V1 , · · · VK ]T (·T is the matrix trans?
pose). From a standard result in optimization, qP
≤ c?P . . The
duality gap is denoted by ∆, that is,

The graphical interpretation of Theorem 2 is given by Figure
3. Consider a hyperplane L that contain F in their upper closed
halfspace and intersects with F, that is, F ∩L is nonempty. Let
the normal vector of L be [λ1 , · · · λK , 1]. The points in F ∩ L
correspond to the optimal solutions to the inner optimization
problem of (17) given λ. The value of c0 at the crossing point
between L and c1 = V is the dual objective value. Therefore,
the optimal dual solution to DPSOC corresponds to the line
that has the maximum crossing point of c1 = V [9]. Observe
that the maximum crossing point for DPSOC, shown as the
orange point in Figure 3, is the same for the minimum common
point (i.e., the primal optimal solution) for MSOCK . Therefore
the reduction in expected cost brought by mixed strategy is
equivalent to the duality gap in PSOC.

?
∆ = c?P − qP
.

D. Solution approach
The dual optimization of MSOCK ’ is given as follows:
DMSOC

K

K

(Dual of MSOC ’)

?
qM
= max

min

λ≥0 c∈conv(F )

c0 + λ(c1:K − V ).

(18)

?
Since conv(F) is convex, there is no duality gap, hence qM
=
?
cM .

It turns out that the improvement in expected cost by the
optimal mixed strategy is equal to the duality gap of PSOC.
Theorem 2.

C(λ) = arg min

c?M = c?P − ∆.

c∈F

c∈conv(F )

c0 + λ(c1:K − V ).

(22)

For example, in case of Figure 3, C(λ) = {c1 , c2 }.

Proof. Since F ⊆ conv(F),
min

A naive approach to solve MSOCK is simply to solve (4)(5). However, the multiplication of pj increases the problem
complexity (e.g., linear v.s. bilinear), making it difficult to
solve. Instead, in this paper, we present an efficient approach
to solve MSOCK by solving the dual of PSOC. This approach
is built on the fact revealed in the proof of Theorem 2 that the
optimal dual solutions to MSOCK and PSOC are the same.
Let λ? be the optimal solution to DPSOC, (17). Let C(λ)
be the set of all the optimal solutions to the inner optimization
problem of DPSOC, that is,

c0 + λc1:K ≤ min c0 + λc1:K .
c∈F

(19)

Theorem 3. The necessary and sufficient condition for
(c1 · · · cK+1 , p1 · · · pK+1 ) to be an optimal solution to

6

MSOCK ’, (9)-(10), is that there exist λ = [λ1 · · · λK ], λi ≥ 0,
that satisfy the followings:
a) ci ∈ C(λ) ∨ pi = 0, ∀i = 1 · · · K + 1
K+1
X

b) λ

c)

!
pi ci1:K

−V

= 0,

i=1
K+1
X
i

p = 1,

i=1
i

d) p ≥ 0 ∀i = 1 · · · K + 1,
e)

K+1
X

pi ci1:K ≤ V, and

i=1

f ) ci ∈ F, ∀i = 1 · · · K + 1.

(23)

Proof.
Sufficiency: It follows from d), e), and f) that
(c1 · · · cK+1 , p1 · · · pK+1 ) satisfies all the constraints of
MSOCK ’. With regard to a), note that:
?
ci ∈ C(λ) ⇐⇒ ci0 + λ(ci1:K − V ) = qP
.

It follows from a), b), and c) that
N
+1
X

=

=

i=1
N
+1
X
i=1
N
+1
X

pi ci0
pi ci0

+λ

K+1
X

!
pi ci1:K

−V

i=1
?
pi {ci0 + λ(ci1:K − V )} = qP
= c?M .

(24)

i=1

Since we know that the minimum objective value of MSOCK ’
is c?M , (c1 · · · cK+1 , p1 · · · pK+1 ) is an optimal solution to
MSOCK ’.
Necessity: We prove the contraposition. Note that b)-f) are
part of the KKT conditions [] for MSOCK ’. Therefore, if any
of b)-f) does not hold, (c1 · · · cK+1 , p1 · · · pK+1 ) is not an
optimal solution. Next, assume that only a) does not hold,
that is,
?
ci0 + λ(ci1:K − V ) = qP
∧ pi > 0, ∀i = 1 · · · K + 1.
PN +1 i i
Using (eq:th3-2), we have
> c?M . Therei=1 p c0
1
K+1 1
K+1
fore (c · · · c
,p ···p
) is not an optimal solution to
MSOCK ’.

Remark 1. Theorem 3 can be immediately adapted to the
original MSOCK , i.e., (4)-(5). Let
U (λ) = arg

min

µ∈MT
g(x,µ,w)=0

E [f0 (x, µ)] − λ (E [fi:K (x, µ)] − V ) .

strategy problem. More specifically, MSOCK can be solved
in the following process:
1) Solve DPSOC and obtain the optimal dual solution, λ?
2) If λ? = 0, optimal solutions to PSOC are also optimal
for MSOCK because (22) reduces to PSOC with λ = 0.
3) If λ? > 0,
?
• Solve (22) to obtain C(λ )
i?
?
• Find c
∈ C(λ ) and
pi? ≥ 0 such that
PK+1 i? i?
PK+1
i?
i=1 p c1:K = V and
i=1 p = 1.
The concrete solution method of DPSOC depends on problems. In general it can be solved by a general convex optimization method such as subgradient method. The multidimensional bisection method [10] can solve it more efficiently
if applicable. More efficient and specialized solution approach
would be available for special cases of MSOCK . However,
such specialized solution approaches are out of the scope of
this paper, except for the one that is discussed in the following
subsection.
E. Efficient Solution for K = 1
PSOC with K = 1 (i.e., there is only one stochastic constraint) has important applications, most notably the problems
with a joint chance-constraint, which imposes the upper bound
on the probability of violating any constraints at any time
steps during the planning horizon. A joint chance-constraint
has a practical importance since it provides the operator of
a system an intuitive way to specify the acceptable level of
risk of an entire plan. For example, in the Mars Exploration
Rovers (MER) mission, ground operators made decisions on
trajectory correction maneuver before atmospheric entry with
a lower bound on the probability of successful landing (the
thresholds for Spirit and Opportunity rovers were 91% and
96%, respectively) [11].
When K = 1, DPSOC can be solved very efficiently by
a root finding method. Furthermore, µ1 , µ2 ∈ U (λ? ) and
c1 , c2 ∈ C(λ? ) are obtained as by-products of root finding.
This involves evaluating the dual objective function repeatedly
by solving (25) with varying λ ≥ 0. The convergence is very
fast; some of standard root finding algorithms, such as Brent’s
method, have a superlinear convergence rate.
Let q(λ) be the dual objective function of DPSOC, that is,
q(λ) = min
c∈F

c0 + λ(c1 − V1 ).

(26)

From a standard result of convex optimization theory, q(λ)
is a concave function [12], hence its subgradient ∂q(λ) is
monotonically decreasing, as shown in Figure 4. Dual optimal
solution, λ? , lies at the zero-crossing of q(λ). Also from a
standard result of convex optimization theory is that:
c ∈ C(λ) ⇒ c1 − V ∈ ∂q(λ).

(25)
Then a) is replaced by the following condition:
a’) µi ∈ U (λ) ∨ pi = 0, ∀i = 1 · · · K + 1.
The uniqueness of Theorem 3 is in a). It means that the K
candidate control sequences, from which the controller choose
randomly, can be obtained by solving the dual of the pure-

Therefore the dual optimization problem can be solved by
finding a root of c1 − V . Standard root finding algorithms can
be used, such as bisection method and Brent’s method [13].
We assume that there is an algorithm that takes λ and
returns an optimal solution solution to (25), µ(λ) ∈ U (λ),
as well as an optimal solution to (26), c(λ) ∈ C(λ), which

7

III. D EPLOYMENT ON L INEAR SMPC

Fig. 4. The optimal dual solution is at the zero crossing of the subgradient
of the dual objective, which is found by a root finding algorithm.

The proposed algorithm is demonstrated with an implementation on a linear SMPC with normally distributed disturbance
and polygonal obstacles in the state space. Since the problem
is nonconvex, a mixed strategy may outperform pure strategies.
A practical challenge is that (25) is nonlinear, nonconvex
programming. The nonlinearity comes from the cumulative
distribution function (CDF) that is used to evaluate the probability of constraint violation. Although an efficient solvers
are available for a limited classes of nonconvex programming
such as mixed integer linear programming (MILP) and mixed
integer quadratic programming (MIQP), the problem does not
fall under these classes.
Repeatedly solving such a problem could result in a prohibitive cost. Our approach is to approximate the CDF with a
piecewise linear function and convert the problem into MILP.
A. Formulation
We assume a linear discrete-time dynamics with xk ∈ Rn
and uk ∈ U ⊂ Rm :
xk+1 = Axk + Buk + wk ,
where wk is a normally distributed zero-mean disturbance
with the covariance of Σw . U is assumed to be a polytope,
hence U = {u ∈ Rm |P u  q}, where  and  are the
componentwise inequalities. We assume that there are M
polytopic obstacles, whose interior is represented as:
Hi xk  gi ,

i = 1 · · · M, k = 1 · · · N.

A chance constraint in the form of (3) is imposed to limit the
probability of the violation of the obstacles is limited to V .
1
The cost function is the
PNtotal L norm of uk over the horizon,
that is, f0 (x, u) =
|u
|
k 1 . Since this cost function is
k=1
deterministic, E [f0 (x, u)] = f0 (x, u). The PSOC is given as
follows:

Fig. 5.

satisfies a) and f) of Theorem 3. We denote by ci (λ) the i-th
component of ci (λ). The root finding algorithm is initiated
with an interval, [λ1 , λ2 ], which includes λ? . The interval
is tightened iteratively until a certain terminal condition is
met. Through the iteration, c(λ1 ), c(λ2 ), µ(λ1 ), and µ(λ2 )
converge to c1? , c2? , µ1? , and µ2? , respectively, while λ1 and
λ2 converge to λ? , as illustrated in Figure 4. If λ? > 0, p1?
and p2? that satisfies b), c), and e) in Theorem 3 are computed
by solving the following:
2? 2?
p1? c1?
1 + p c1 = V1

p1? + p2? = 1.
The solution to the above also satisfies d) because λ? ∈
[λ1 , λ2 ] implies c1 (λ1 ) ≥ V1 and c1 (λ2 ) ≤ V1 . Therefore,
(c1? , c2? , p1? , p2? ) satisfies a)-f) of Theorem 3, hence it is an
optimal solution to MSOC1 . If λ? = 0, an optimal solution is
c1? = c2? = c(λ? ) and p1? and p2? ) can be any that satisfies
c) and d).
The optimal mixed control is to execute µ1? with probability
1?
p and µ2? with p2? .

N
X

min

|uk |1

k=1

s.t. Pr

"M N
_ _

#
Hi xk  gi ≤ V

i=1 k=1

xk+1 = Axk + Buk + wk , k = 1 · · · N
P uk  q, k = 1 · · · N,
W

where
is the logical disjunction. The inner optimization
problem of the dual optimization, (25), is given as:
"M N
#
!
N
X
_ _
min
|uk |1 + λ Pr
Hi xk  gi − V
k=1

i=1 k=1

s.t. xk+1 = Axk + Buk + wk , k = 1 · · · N
P uk  q, k = 1 · · · N.
B. Conversion to MILP
We use a few tricks and approximations to convert the above
problem into MILP. We note that the probability of constraint
violation is always approximated conservatively (meaning that

8

it is overestimated) so that a solution to the approximated
problem is always a feasible solution to the original problem.
First, by replacing absolute values with slack variables, the L1
norm objective is equivalent to the following:
min |u|1 = min

m
X

min

N X
m
X
k=1 i=1

vki + λ

M X
N
X

!
δik − V

i=1 k=1

s.t. vkd ≥ ukd , vkd ≥ −ukd , P uk  q
vd

s.t. vd ≥ ud , vd ≥ −ud ,

d=1

where ud is the d-th component of vector u. Second, the
joint probability is decomposed by Boole’s inequality, whose
conservatism is trivial in most practical cases where the risk
bound V is very small (e.g., < 0.01) [14]:
"M N
#
M X
N
_ _
X
Pr
Hi x k  g ∼
Pr [Hi xk  g] .
i=1 k=1

s.t.

Ri
_

Ri
X

zij ≤ Ri − 1, zij ∈ {0, 1}

j=1

k = 1 · · · N, d = 1 · · · m, i = 1 · · · M,
j = 1 · · · Ri , l = 1 · · · L.

i=1 k=1

The componentwise inequality in the probability is decomposed using the risk selection approach [15], which is again
a conservative approximation. Let hij and gij be the j-th row
of Hi and gi , and Ri be the number of rows,
min Pr [Hi xk  gi ] ∼ min δ

x̄k+1 = Ax̄k + Buk + wk
!
hij x̄k − gij
+ bl ≤ δik + Mzij
al
hij Σxk hTij

Pr [hij xk ≥ gij ] ≤ δ.

j=1

(27)
The probability above is univariate, hence it can be easily
evaluated by CDF:
!
hij x̄k − gij
,
Pr [hij xk ≥ gij ] = F
hij Σxk hTij
where x̄k is the mean of xk and F (·) is the CDF of the
standard normal distribution. The covariance matrix of xk is
computed recursively by Σxk+1 = AΣxk AT + Σw .

We apply a piecewise linear approximation of the CDF.
Since the CDF of the standard normal distribution F (y) is
convex at y ≤ 0, the piecewise linear approximation can
be done without introducing integer variables. An underlying
assumption is that the mean state x̄k is always outside of
obstacles, hence hij x̄k − gij < 0. This assumption is implied
by V < 0.5 because if the mean state is on a constraint
boundary, the probability of violating the constraint is 0.5.
In practical cases the users usually do not allow 50 % of risk.
Let al y + bl be the linear approximation of F (y) at yl ≤ 0,
l = 1 · · · L. The right hand side of (27) is approximated as
follows:
!
Ri ^
L
_
hij x̄k − gij
min δ s.t.
al
+ bl ≤ δ.
hij Σxk hTij
j=1 l=1

Finally, the disjunction is replaced by mixed-integer constraints using a standard trick called the big-M method [16].
Letting M be a very large positive constant, the optimization
problem formulated in the previous subsection is now converted to MILP as follows:

C. Simulation Results
We performed simulations on a double integrator plant:


 1

2
1 0 ∆T
0
0
2 ∆T
1
2 
 0 1

0
∆T 
0
2 ∆T
, B = 
,
A=
 0 0
 ∆T

1
0 
0
0 0
0
0
0
∆T

 2
σw 0 0 0
2
 0 σw
0 0 
 , ∆T = 1, σw = 0.1.
Σw = 
 0
0 0 0 
0
0 0 0
We first considered an illustrative example shown in Figure
6, where two obstacles were placed between which there was
a narrow shortcut passage. Initial state was at [0, 0, 0, 0]T
and the mean final state was constrained at [10, 10, 0, 0]T .
Horizon length was N = 15, and finally the risk bound is
V = 0.01. The simulation was performed on a machine with
Intel Core i7-3612QM CUP clocked at 2.10 GHz and 8.00
GB RAM. The algorithm was implemented in MATLAB using
YALMIP [17] and MILP was solved by CPLEX. The bisection
method was used for root finding. For comparison, the optimal
pure strategy was also computed by using the same MILP
approximation presented in Section III-B.
Figure 6 shows the mixed and pure strategy solutions computed by the proposed algorithm. The mixed strategy consisted
of the two control sequences shown in blue lines. The lower
dual solution λL corresponds to a risk-taking path that goes
through the narrow passage, while the upper dual solution λU
results in a risk-averse path that go around the obstacles. The
former took rL = 0.0278 of risk and cL = 3.692 of cost, while
the latter took rU = 0.0021 of risk and cU = 4.175 of cost.
The mixed strategy chose between them with the probabilities
of 0.306 and 0.694, resulting in the risk of exactly 0.01
and the expected cost of 4.027. On the other hand, the pure
optimal strategy took the risk of exactly 0.01 and the cost of
4.175. Therefore this example validates our claim that mixed
strategy can result in less expected cost than pure strategy in
a nonconvex SMPC.
We next performed a Monte Carlo simulation in order to
empirically validate our claim that the optimal solution to
the mixed strategy problem is always as good as the optimal
solution to the original (pure) problem. We randomly placed

9

Fig. 6. Simulation result on an illustrative example. The optimal mixed
strategy chooses between the two blue control sequences. The expected cost
of the mixed control strategy is 4.027 while that of the optimal pure control
strategy is 4.105. cL = 3.692, cU = 4.175. The three-sigma ellipses are
shown in green.

Fig. 7. Cost of the optimal pure and mixed solutions to 200 problems with
randomly generated obstacles. Red dots are the samples where the cost of the
optimal mixed solution is strictly less than the optimal pure solution. Blue
dots are the samples where two costs are identical. No optimal pure solutions
outperform the optimal mixed solutions.

four square obstacles in a 2-D state space. The center of
each square was sampled from a uniform distribution within
[−3, 3] × [−3, 3]. The size of each square was sampled
from a uniform distribution in [1, 3]. The initial state was
[−5, 0, 0, 0]T , and the mean final state was constrained at
[5, 0, 0, 0]T .
Figure 7 shows the resulting cost of the optimal mixed
and pure solutions to 200 randomized problems. The average
computation time was 59.8 sec. There were 163 samples on
the 45◦ line in the plot, meaning that the cost of optimal
mixed and pure solutions were identical in those samples.
There were 37 samples below the 45◦ line, meaning that
the cost of optimal mixed solution was strictly less than the
cost of the optimal pure solution. There was no sample above
the 45◦ line. This result supports our claim that the optimal
solution to the mixed strategy problem is always as good
as the optimal solution to the original problem. At least in
this particular problem domain, mixed strategy outperforms
pure strategy not very frequently, and as is seen in Figure
7 the improvement is often marginal. It is certainly possible
to engineer a problem that better highlights the advantage of
mixed strategy, but that does not serve the objective of this
paper. The most important contributions of this paper are the
theoretical finding that mixed strategy can outperform pure
strategy in nonconvex SMPCs, as well as the algorithm to
compute the optimal mixed strategy solutions. The empirical
results validate the theoretical finding and the algorithm.

as xk ∈ Xk and uk ∈ Uk . A control policy is a map
µk : Xk → Uk . The sequence of control policy is denoted
by µ := [µ1 , · · · , µT ]. A mixed strategy finds multiple control
policy sequences, µ1 , µ2 , · · · µK+1 , and randomly choose one.
The
hPcontrol objectivei is to minimize the expected total cost,
T
F
E
k=1 f0 (xk , uk ) . A set of failure states, Xk ⊂ Xk , is
specified for each time step. A joint chance constraint limits
the probability that one of the failure states is visited at any
time step:
" T
#
_
F
Pr
xk ∈ Xk ≤ V.
k=1

Since K = 1, the mixed-strategy problem can be solved
by root finding, as in Section II-E. The inner optimization
problem is solved through the chance-constrained dynamic
programming[18] 1 . In the reminder of this section we present
two applications: path planning and Mars Entry, Descent, and
Landing (EDL).
A. Application to Path Planning
In this application, we assume T = 50 and a twodimensional state space in [0, 100]2 discretized into a 100x100
grid. Obstacles are placed as shown in Figure 8. A single
integrator dynamics is assumed:
xk+1 = xk + uk + wk
kuk k2 ≤ dk ,

IV. D EPLOYMENT ON C HANCE - CONSTRAINED MDP
The application of the proposed approach is not limited to
SMPC. In this section we present applications to finite-state
MDPs with a chance constraint.
We consider a finite time steps, k = 1 · · · T . The state space
and action space are finite and time-varying, denoted by Xk
and Uk . State and control sequence variables are represented

wk ∼ N (0, σ 2 I),

where uk is a two dimensional vector specifying the increment
in position, wk is a discritized, Gaussian-distributed noise,
dk and σ are constant parameters, N (0, Σ) is a zero-mean
Gaussian distribution with the covariance matrix Σ, and I
is the two-dimensional identity matrix. We set dk = 6 and
1

10

Fig. 8. Application of mixed-strategy stochastic control to a path planning
problem. The optimal mixed control strategy chooses between the two paths,
u1 , u2 , with probabilities of 17.0% and 83.0%, respectively.

σ = 1. The cost function is the expected length of the resulting
path that connects the start and goal states. The risk bound is
V = 0.02.
The optimal solution to MSOC consists of two control
policy sequences, µ1 and µ2 , which have expected path lengths
of 130.8 and 98.7 while the risks of hitting obstacles being
0.64% and 2.28%, respectively. The nominal paths resulting
from µ1 and µ2 (i.e, state sequence assuming when wk = 0)
are shown in Figure 8. The two pure control strategies are
chosen with probabilities of 17.0% and 83.0%, respectively.
As a result, the mixed control strategy has a expected path
length of 104.2 while the risk of hitting obstacles is exactly
2.0%. On the other hand, solving PSOC results in the same
pure control strategy as µ1 , whose expected path length is
130.8. As expected, mixed strategy resulted in a less expected
cost while respecting the stochastic constraint.
The solution time of MSOC was 20.52 seconds while that of
the PSOC was 20.38 seconds2 . The difference in computation
time is small because solving PSOC also requires iterative dual
optimization in this case[18].
B. Application to Mars Entry, Descent, and Landing
We next present an application to the planning of entry,
descent, and landing (EDL) for future Mars missions[18].
Mars EDL is subject to various source of uncertainties such
as atmospheric variability and imperfect aerodynamics model.
The resulting dispersions of the landing position typically
spans over tens of kilometers for a 99.9% confidence ellipse [11]. Given such a highly uncertain nature of EDL, a
target landing site must be carefully chosen in order to limit
the risk of landing on rocky or uneven terrain. At the same
time, it is equally important to land near science targets in
order to minimize the traverse distance after the landing.
Future Mars lander/rover missions would aim to reduce the
uncertainty by using several new active control technologies,
consisting of the following three stages: entry-phase targeting,
powered-descent guidance (PDG) [19], and hazard detection
2 Simulations are conducted on a machine with the Intel(R) Xenon(R)
X5690 CPU clocked at 3.47GHz and 96GB of RAM

and avoidance (HDA) [20]. Each control stage is capable of
making corrections to the predicted landing position by a
certain distance, but each stage is subject to execution errors,
which deviates the spacecraft away from the planned landing
position.
We pose this problem as an optimal sequential decision
making under a persisting uncertainty. At the kth control stage,
xk represents the projected landing location without further
control. By applying a control at the kth stage, the lander
can correct the projected landing location to uk , which must
be within an ellipsoid centered around xk . At the end of the
kth control stage, the projected landing location xk+1 deviates
from uk due to a disturbance wk , which is assumed to have a
Gaussian distribution. This EDL model is described as follows:
xk+1 = uk + wk
(uk − xk )T Dk (uk − xk ) ≤ d2k ,

wk ∼ N (0, Σk ),

where Dk and Σk are positive definite matrices, and dk is a
scalar constant. We use the same parameter settings as [21].
We consider three control stages, i.e., T = 3 and x3 is the
final landing location. The state space X is a 2 km-by-2 km
square, which is discretized at a one meter resolution. As a
result, the problem has four million states at each time step.
The control and the disturbance are also discretized at the
same resolution. The cost function is the expected distance to
drive on surface to visit two science targets, shown in magenta
squares in Figure 9, starting from the landing location. The
infeasible areas are specified using the data of HiRISE (High
Resolution Imaging Science Experiment) camera on the Mars
Reconnaissance Orbiter. We use the real landscape of a site
named “East Margaritifer” on Mars.
Figure 9 show the simulation result with a risk bound
V = 0.1%. The optimal solution to MSOC chooses between
two control policy sequences, µ1 and µ1 , with the probabilities
of 84.9% and 15.1%. The probability of failure of the two
control policy sequences are 0.016% and 0.574% while their
costs being 645.49 and 641.02. The resulting probability of
failure of the mixed strategy is exactly 0.1% The optimal
solution to PSOC is equivalent to µ1 . Again, as expected,
mixed strategy reduces the expected cost while respecting the
stochastic constraint.
Note that the optimal pure control policy takes significantly
less risk than the risk bound. This is because there is no
other solution that is within the risk bound and has less cost.
The mixed control strategy improves the cost by mixing this
optimal pure control strategy with another control policy that
has an excessive risk but a less cost.
It may sound unrealistic to decide a landing site probabilistically. However, consider a situation where there are 1,000
vehicles and we require 999 of them to land successfully
while minimizing the total cost. Then our result means that the
optimal strategy is to send 849 of them to the first landing site
and 151 of them to the other. When having only one vehicle,
the interpretation of this result varies with viewpoint. For a
person who knows the result of the coin flip in advance of the
landing, the resulting action is no more mixed and hence it
may violate the given chance constraint. However, if the result

11

R EFERENCES

(a) Optimal pure control strategy

15.1%

84.9%

(b) Optimal mixed control strategy
Fig. 9. (a) The optimal pure control strategy and (b) the optimal mixed control
strategy for the Mars EDL scenario with a risk bound V = 0.01. The red
×-marks are the optimal EDL target of the pure control strategies, while the
red circles represents 3σ of the disturbance in the first stage, wo . The mixed
strategy chooses between the two pure control strategies with the probabilities
of 15.1% and 84.9%.

of the coin flip is hidden from the observer, like Schrödinger’s
cat in a box, then this mixed strategy results in the minimum
expected cost while the probability of failure is still within the
specified bound.
C ONCLUSIONS
We found that, in nonconvex SMPC, choosing control inputs
randomly can result in a less expected cost than deterministically optimizing them. We developed a solution method based
on dual optimization and deployed it on a linear nonconvex
SMPC problem, which was efficiently solved using an MILP
approximation. Finally, we validated our theoretical findings
through simulations.
ACKNOWLEDGMENT
The research described in this paper was in part carried
out at the Jet Propulsion Laboratory, California Institute of
Technology, under a contract with the National Aeronautics
and Space Administration. This research was supported by
the Office of Naval Research, Science of Autonomy Program,
under Contracts N00014-15-IP-00052 and N00014-15-1-2673.

[1] E. Altman, Constrained Markov decision processes, ser. Stochastic
modeling. Chapman & Hall/CRC, 1999. [Online]. Available: http:
//books.google.com/books?id=3X9S1NM2iOgC
[2] V. S. Borkar, Convex Analytic Methods in Markov Decision Processes.
Boston, MA: Springer US, 2002, pp. 347–375.
[3] E. A. Feinberg and U. G. Rothblum, “Splitting randomized stationary
policies in total-reward markov decision processes,” Math. Oper. Res.,
vol. 37, no. 1, pp. 129–153, Feb. 2012.
[4] E. A. Feinberg, On measurability and representation of strategic measures in Markov decision processes, ser. Lecture Notes–Monograph
Series. Hayward, CA: Institute of Mathematical Statistics, 1996, vol.
Volume 30, pp. 29–43.
[5] D. Bernardini and A. Bemporad, “Scenario-based model predictive
control of stochastic constrained linear systems,” in Proceedings of
Joint 48th IEEE Conference on Decision and Control and 28th Chinese
Control Conference, 2009.
[6] G. C. Calafiore, F. Dabbene, and R. Tempo, “Research on probabilistic
methods for control system design,” Automatica, vol. 47, no. 7, pp.
1279 – 1293, 2011. [Online]. Available: http://www.sciencedirect.com/
science/article/pii/S0005109811001300
[7] B. Acikmese and D. Bayard, “A markov chain approach to probabilistic
swarm guidance,” in American Control Conference (ACC), 2012, June
2012, pp. 6300–6307.
[8] B. Acikmese, N. Demir, and M. Harris, “Convex necessary and sufficient
conditions for density safety constraints in markov chain synthesis,”
Automatic Control, IEEE Transactions on, vol. 60, no. 10, pp. 2813–
2818, Oct 2015.
[9] D. P. Bertsekas, Convex Optimization Theory. Athena Scientific, 2009.
[10] Z. Baoping, G. R. Wood, and W. P. Baritompa, “Multidimensional
bisection: The performance and the context,” Journal of Global
Optimization, vol. 3, no. 3, pp. 337–358. [Online]. Available:
http://dx.doi.org/10.1007/BF01096775
[11] P. C. Knocke, G. G. Wawrzyniak, B. M. Kennedy, P. N. Desai, T. J.
Parker, M. P. Golombek, T. C. Duxbury, and D. M. Kass, “Mars exploration rovers landing dispersion analysis,” in Proceedings of AIAA/AAS
Astrodynamics Specialist Conferencec and Exhibit, 2004.
[12] S. Boyd and L. Vandenberghe, Convex Optimization.
Cambridge
University Press, mar 2004.
[13] K. E. Atkinson, An Introduction to Numerical Analysis, Second Edition.
John Wiley & Sons, 1989.
[14] M. Ono and B. C. Williams, “An efficient motion planning algorithm for
stochastic dynamic systems with constraints on probability of failure,”
in Proceedings of the Twenty-Third AAAI Conference on Artificial
Intelligence (AAAI-08), 2008.
[15] M. Ono, L. Blackmore, and B. C. Williams, “Chance constrained finite
horizon optimal control with nonconvex constraints,” in Proceedings of
American Control Conference, 2010, pp. 1145–1152.
[16] D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization,
1st ed. Athena Scientific, 1997.
[17] J. Lofberg, “Yalmip : A toolbox for modeling and optimization in
MATLAB,” in Proceedings of the CACSD Conference, Taipei, Taiwan,
2004. [Online]. Available: http://control.ee.ethz.ch/∼joloef/yalmip.php
[18] M. Ono, M. Pavone, Y. Kuwata, and J. Balaram, “Chance-constrained
dynamic programming with application to risk-aware robotic space
exploration,” Auton. Robots, vol. 39, no. 4, pp. 555–571, Dec. 2015.
[Online]. Available: http://dx.doi.org/10.1007/s10514-015-9467-7
[19] B. Acikmese and S. Ploen, “Convex programming approach to powered
descent guidance for mars landing,” AIAA Journal of Guidance, Control,
and Dynamics, vol. 30, no. 5, pp. 1353–1366, 2007.
[20] A. Johnson, A. Huertas, R. Werner, and J. Montgomery, “Analysis of
On-Board Hazard Detection and Avoidance for Safe Lunar Landing,” in
IEEE Aerospace Conference, 2008.
[21] M. Ono, Y. Kuwata, and J. B. Balaram, “Joint chance-constrained
dynamic programming,” in Proceedings of the IEEE Conference on
Decision and Control, 2012.

