Learning Mixed-Integer Convex Optimization Strategies for Robot Planning and Control
Authors:
- A. CauligiACA. Cauligi
- P. CulbertsonPCP. Culbertson
- B. StellatoBSB. Stellato
- D. BertsimasDBD. Bertsimas
- M. SchwagerMSM. Schwager
- M. PavoneMPM. Pavone
Preprint
Abstract
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 extend the machine learning optimizer (MLOPT) framework to solve MICPs arising in robotics at very high speed. MLOPT 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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Online Mixed-Integer Optimization in MillisecondsINFORMS Journal on Computing, 2022
- Large scale model predictive control with neural networks and primal active setsAutomatica, 2022
- Machine learning for combinatorial optimization: A methodological tour d’horizonEuropean Journal of Operational Research, 2021
- Warm Start of Mixed-Integer Programs for Model Predictive Control of Hybrid SystemsIEEE Transactions on Automatic Control, 2020
- Collision-Inclusive Trajectory Optimization for Free-Flying SpacecraftJournal of Guidance, Control, and Dynamics, 2020
- Efficient Equilibrium Testing Under Adhesion and Anisotropy Using Empirical Contact Force ModelsIEEE Transactions on Robotics, 2018
- JuMP: A Modeling Language for Mathematical OptimizationSIAM Review, 2017
- Control of systems integrating logic, dynamics, and constraintsAutomatica, 1999
- Task-oriented optimal grasping by multifingered robot handsIEEE Journal on Robotics and Automation, 1988
- On the Computational Complexity of Combinatorial ProblemsNetworks, 1975