  Mixed-integer convex programming (MICP) has seen significant algorithmic and
hardware improvements with several orders of magnitude solve time speedups
compared to 25 years ago. Despite these advances, MICP has been rarely applied
to real-world robotic control because the solution times are still too slow for
online applications. In this work, we present the CoCo (Combinatorial Offline,
Convex Online) framework to solve MICPs arising in robotics at very high speed.
CoCo encodes the combinatorial part of the optimal solution into a strategy.
Using data collected from offline problem solutions, we train a multiclass
classifier to predict the optimal strategy given problem-specific parameters
such as states or obstacles. Compared to previous approaches, we use
task-specific strategies and prune redundant ones to significantly reduce the
number of classes the predictor has to select from, thereby greatly improving
scalability. Given the predicted strategy, the control task becomes a small
convex optimization problem that we can solve in milliseconds. Numerical
experiments on a cart-pole system with walls, a free-flying space robot, and
task-oriented grasps show that our method provides not only 1 to 2 orders of
magnitude speedups compared to state-of-the-art solvers but also performance
close to the globally optimal MICP solution.
