Fast Second-Order Cone Programming for Safe Mission Planning

Kai Zhong1, Prateek Jain2, Ashish Kapoor3

  • 1University of Texas at Austin
  • 2Microsoft
  • 3Microsoft Research



Regular Papers


09:55 - 11:10 | Tue 30 May | Room 4111 | TUA2

Optimization and Optimal Control

Full Text


This paper considers the problem of safe mission planning of dynamic systems operating under uncertain environments. Much of the prior work on achieving robust and safe control requires solving second-order cone programs (SOCP). Unfortunately, existing general purpose SOCP methods are often infeasible for real-time robotic tasks due to high memory and computational requirements imposed by existing general optimization methods. The key contribution of this paper is a fast and memory-efficient algorithm for SOCP that would enable robust and safe mission planning onboard robots in real-time. Our algorithm does not have any external dependency, can efficiently utilize warm start provided in safe planning settings, and in fact leads to significant speed up over standard optimization packages (like SDPT3) for even standard SOCP problems. For example, for a standard quadrotor problem, our method leads to speedup of 1000x over SDPT3 without any deterioration in the solution quality. Our method is based on two insights: a) SOCPs can be interpreted as optimizing a function over a polytope with infinite sides, b) a linear function can be efficiently optimized over this polytope. We combine the above observations with a novel utilization of Wolfe's algorithm to obtain an efficient optimization method that can be easily implemented on small embedded devices. We also design an efficient two-level sensing method based on Gaussian Process for complex obstacles such as a cylinder.

Additional Information

No information added