Chance-Constrained Programming for Autonomous Vehicles in Uncertain Environments

Abstract

Trajectory planning in uncertain environments arises in several autonomous system applications including robotics, air traffic and autonomous driving. An approach to handle uncertainties with sufficiently high safety guarantees is through chance-constrained optimization. In this work, we consider the problem of trajectory planning for an autonomous vehicle in an uncertain environment comprised of a number of obstacles. First, we explore existing chance-constrained optimization techniques and their efficiency in handling this problem. Second, we model the uncertain moving obstacles as polyhedra and deal with the non-convex optimization problem of not colliding with them using mixed-integer chance-constrained optimization. We transform this optimization problem into a tractable form using Boole’s inequality followed by an analytic reformulation based on the sample estimates of the uncertainty’s moments. We derive concentration bounds on the estimation error of these moments. As such, we provide high confidence guarantees on the chance-constrained solution. We finally demonstrate the framework with three motion-planning case studies in finite and receding horizon frameworks.