Chance constrained finite horizon optimal control with nonconvex constraints

This paper considers finite-horizon optimal control for dynamic systems subject to additive Gaussian-distributed stochastic disturbance and a chance constraint on the system state defined on a non-convex feasible space. The chance constraint requires that the probability of constraint violation is below a user-specified risk bound. A great deal of recent work has studied joint chance constraints, which are defined on the a conjunction of linear state constraints. These constraints can handle convex feasible regions, but do not extend readily to problems with non-convex state spaces, such as path planning with obstacles. In this paper we extend our prior work on chance constrained control in non-convex feasible regions to develop a new algorithm that solves the chance constrained control problem with very little conservatism compared to prior approaches. In order to address the non-convex chance constrained optimization problem, we present two innovative ideas in this paper. First, we develop a new bounding method to obtain a set of decomposed chance constraints that is a sufficient condition of the original chance constraint. The decomposition of the chance constraint enables its efficient evaluation, as well as the application of the branch and bound method. However, the slow computation of the branch and bound algorithm prevents practical applications. This issue is addressed by our second innovation called Fixed Risk Relaxation (FRR), which efficiently gives a tight lower bound to the convex chance-constrained optimization problem. Our empirical results show that the FRR typically makes branch and bound algorithm 10-20 times faster. In addition we show that the new algorithm is significantly less conservative than the existing approach.