Hybrid model predictive control with both continuous and discrete variables is widely applicable to robotic control tasks, especially those involving contact with the environment. Due to the combinatorial complexity, the solving speed of hybrid MPC can be insufficient for real-time applications. In this paper, we proposed a hybrid MPC solver based on Generalized Benders Decomposition (GBD). The algorithm enumerates and stores cutting planes online inside a finite buffer. After a short cold-start phase, the stored cuts provide warm-starts for the new problem instances to enhance the solving speed. Despite the disturbance and randomly changing environment, the solving speed maintains. Leveraging on the sparsity of feasibility cuts, we also propose a fast algorithm for Benders master problems. Our solver is validated through controlling a cart-pole system with randomly moving soft contact walls, and a free-flying robot navigating around obstacles. The results show that with significantly less data than previous works, the solver reaches competitive speeds to the off-the-shelf solver Gurobi despite the Python overhead.

翻译：混合模型预测控制（MPC）同时包含连续变量和离散变量，广泛应用于机器人控制任务，特别是涉及与环境接触的场景。由于组合复杂性，混合MPC的求解速度可能无法满足实时应用需求。本文提出了一种基于广义Benders分解（GBD）的混合MPC求解器。该算法在线枚举并存储切割平面至有限缓冲区中。经过短暂的冷启动阶段后，存储的切割平面为新问题实例提供热启动，从而提升求解速度。即使在存在扰动和随机变化环境的情况下，求解速度仍能保持稳定。利用可行性切割的稀疏性，我们还提出了一种针对Benders主问题的快速求解算法。通过在具有随机移动软接触壁的倒立摆控制系统以及绕障碍物导航的自由飞行机器人上进行验证，结果表明：与现有工作相比，本求解器使用显著更少的数据量，在Python环境开销下仍能达到与商用求解器Gurobi相竞争的求解速度。