Trajectory Optimization for Chance-Constrained
Nonlinear Stochastic Systems
Yashwanth Kumar Nakka and Soon-Jo Chung
Abstract
ó This paper presents a new method of comput-
ing a sub-optimal solution of a continuous-time continuous-
space chance-constrained stochastic nonlinear optimal control
problem (SNOC) problem. The proposed method involves two
steps. The rst step is to derive a deterministic nonlinear
optimal control problem (DNOC) with convex constraints that
are surrogate to the SNOC by using generalized polynomial
chaos (gPC) expansion and tools taken from chance-constrained
programming. The second step is to solve the DNOC problem
using sequential convex programming (SCP) for trajectory
generation. We prove that in the unconstrained case, the optimal
value of the DNOC converges to that of SNOC asymptotically
and that any feasible solution of the constrained DNOC is a
feasible solution of the chance-constrained SNOC because the
gPC approximation of the random variables converges to the
true distribution. The effectiveness of the gPC-SCP method is
demonstrated by computing safe trajectories for a second-order
planar robot model with multiplicative stochastic uncertainty
entering at the input while avoiding collisions with a specied
probability.
I. I
NTRODUCTION
Model-based design strategies for planning [1] and con-
trol [2] of robotic systems often take a deterministic approach
with robustness guarantees [3] to quantify performance un-
der worst-case uncertainties. These approaches assume a
bounded value of uncertainty leading to conservative tra-
jectories and control laws. Central to a condence-based
design solution for a robot or vehicle operating in dynamic
environment is a systematic approach that accounts for un-
certainties in the dynamic model, state and input constraints,
and even state estimation of highly-nonlinear systems to
guarantee safety and performance with high probability.
Examples of systems that require safety guarantees under
uncertainty include spacecraft with thrusters as actuators
during proximity operations [4], and a quadrotor ying in
turbulent winds [5].
Considering safety in conjunction with optimality be-
comes more difcult if the dynamics themselves are sub-
ject to stochastic noise. Such optimal motion planning or
guidance problems with stochastic dynamics can be for-
mulated as a continuous-time continuous-space stochastic
nonlinear optimal control problem (SNOC) with chance con-
straints. Suboptimal-solution methods to solve model-based
SNOC problem based on Pontryagin's minimum principle
include differential dynamic programming [6] and iterative
linear-quadratic-Gaussian [7]. Sampling-based methods like
Monte Carlo motion planning [8] for trajectory optimization,
Yashwanth Kumar Nakka and Soon-Jo Chung are with the De-
partment of Aerospace (GALCIT), California Institute of Technology.
Email:
f
ynakka@caltech.edu, sjchung@caltech.edu
g
Markov chain approximation method [9], and path-integral
approach [10] can be used under certain assumptions on the
cost function, dynamics, and uncertainty for systems afne
in control.
In this paper, we present a novel approach to compute
solution trajectories of a chance-constrained SNOC problem.
The method involves deriving a deterministic nonlinear op-
timal control (DNOC) problem with convex constraints that
are a surrogate to the SNOC problem by systematically ac-
counting for nonlinear stochastic dynamics using generalized
polynomial chaos expansions (gPC) [11], [12] and obtaining
deterministic convex approximations of linear and quadratic
chance constraints using tools taken from chance constrained
programming [13], [14]. The DNOC problem is then solved
using sequential convex programming (SCP) [15], [16] for
real-time trajectory optimization. The gPC approach uses
function approximation theory to model an unknown ran-
dom process with basis functions that are chosen based
on knowledge of the uncertainty affecting the process [11].
For example, a Hermite polynomial basis with the standard
normal distribution is known to yield exponential conver-
gence [11] if the uncertainties in the system are Gaussian.
The gPC approximation is used to derive ordinary differential
equations (ODEs) in terms of gPC coefcients. The DNOC
problem and convex constraints are reformulated in terms of
gPC coefcients as decision variables to apply a trust-region-
based SCP method to compute feasible trajectories.
The gPC expansion approach was used for stability anal-
ysis and control design of uncertain systems [17], [18],
[19]. For trajectory optimization, recent work focuses on
nonlinear systems with parametric uncertainty [20], [21]
with no constraints on the state, or linear systems with
linear chance-constraints that do not extend to the SNOC
problem considered here and lack analysis on the determin-
istic approximation of the uncertain system. In [22], [23]
linear chance constraints were considered for probabilistic
optimal planning, strictly for linear systems. The literature
on chance-constrained programming focuses on problems
with deterministic decision variable and uncertain system
parameters for both linear [13] and nonlinear [14] cases. The
linear chance-constraint results can be readily transformed
to the case with a random decision variable for an unknown
measure. The quadratic chance constraint would lead to an
inner semi-denite program [24] that adds complexity to the
SNOC problem considered in this paper.
The main contribution of the present paper is hence to
solve a class of optimal control problems that include both
chance or probabilistic inequality constraints and stochastic
nonlinear dynamics via gPC-SCP. In order to character-
ize the deterministic approximation obtained using a gPC
method, we present analysis on convergence of a DNOC
problem to the SNOC problem for an unconstrained case.
Then, we prove that any feasible solution of the constrained
DNOC problem is a feasible solution of chance-constrained
SNOC problem with an appropriate gPC transformation
step applied. This proves that solving a DNOC problem
ensures constraint satisfaction with the specied probability.
In order to bound the deviation of the random variable from
its mean, we derive a conservative deterministic quadratic
constraint approximation of the quadratic chance-constraint
using multivariate Chebyshev inequality [25], which can be
used to nd trajectories that have a specied variance.
The paper is organized as follows. We discuss the stochas-
tic nonlinear optimal control (SNOC) problem with results
on deterministic approximations of chance constraints along
with preliminaries on gPC expansions in Sec. II. The deter-
ministic surrogate of the SNOC problem in terms of the gPC
coefcients and a SCP formulation of the DNOC problem are
presented with analysis in Sec. III. In Sec. IV, we apply the
proposed gPC-SCP method for computing a safe trajectory
for Dubin's second-order model with specied probability for
avoiding collisions and discuss the limitations of the method.
We conclude the paper in Sec. V with brief discussion on the
results of the analysis and the application of the gPC-SCP
method.
II. P
ROBLEM AND
P
RELIMINARIES
A. Stochastic Nonlinear Optimal Control Problem
In this section, we present the nite-horizon stochas-
tic nonlinear optimal control problem with joint chance
constraints in continuous time and continuous space. The
problem considered here has an expectation cost function
which is quadratic in the random state variable
x
(
t
)
and
the deterministic control policy
u
(
t
)
. The evolution of the
stochastic process
x
(
t
)
for all sampled paths is dened by a
stochastic differential equation. The joint chance constraints
guarantee constraint feasibility with a probability of
1