Efficient Uniform Feasible Set Sampling for Approximate Linear MPC

📄 arXiv: 2604.09118v1 📥 PDF

作者: Elias Milios, Felix Berkel, Felix Gruber, Melanie N. Zeilinger, Kim P. Wabersich

分类: eess.SY

发布日期: 2026-04-10

💡 一句话要点

提出线性MPC Hit-and-Run采样器，加速近似线性MPC的训练数据生成。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 模型预测控制 近似MPC 可行集采样 Hit-and-Run算法 线性规划

📋 核心要点

  1. 传统MPC计算成本高，近似MPC通过学习替代策略降低成本，但训练数据生成效率低。
  2. 论文提出LMPC-HR采样器，利用凸线性规划高效确定可行集边界，加速均匀采样。
  3. 实验表明，LMPC-HR相比传统方法，在生成均匀分布样本时，计算时间减少一个数量级。

📝 摘要（中文）

模型预测控制(MPC)提供安全且接近最优的控制，但计算成本高昂。近似MPC(AMPC)通过学习一个更廉价的替代策略来缓解这个问题，通常通过在状态-MPC输入对上训练神经网络。生成训练数据是一个主要的瓶颈，需要为从其可行集中采样的多个状态求解MPC。由于这个可行集是隐式定义且未知的，因此高效采样并非易事，但至关重要。我们提出了一种用于线性MPC的线性MPC Hit-and-Run (LMPC-HR)采样器，用于具有多面体约束的线性MPC。我们通过将问题表述为凸线性规划，识别沿搜索方向的可行集边界，这是HR中的一个关键步骤，用单个优化步骤代替了昂贵的迭代搜索。数值研究表明，与朴素的基线相比，LMPC-HR在从可行集中生成均匀分布的样本时，计算时间减少了一个数量级。

🔬 方法详解

问题定义：论文旨在解决近似线性MPC中训练数据生成效率低下的问题。近似MPC需要大量可行集内的状态样本来训练替代策略。然而，线性MPC的可行集由多面体约束隐式定义，直接采样非常困难，传统的采样方法效率低下，成为训练的瓶颈。

核心思路：论文的核心思路是利用Hit-and-Run (HR) 算法进行可行集采样，并通过凸优化方法高效地确定HR算法中沿搜索方向的可行集边界。传统的HR算法需要迭代搜索边界，计算成本高。论文将边界搜索问题转化为线性规划问题，从而实现高效求解。

技术框架：LMPC-HR采样器的整体流程如下： 1. 初始化： 在可行集中找到一个初始点。 2. 选择方向： 随机选择一个搜索方向。 3. 边界确定： 利用线性规划确定沿该方向的可行集边界。 4. 采样： 在边界之间均匀采样一个点。 5. 迭代： 将该点作为新的起点，重复步骤2-4。

关键创新：论文的关键创新在于将Hit-and-Run算法中的边界搜索问题转化为凸线性规划问题。这避免了传统HR算法中耗时的迭代搜索，显著提高了采样效率。与现有方法相比，LMPC-HR能够更快速地生成均匀分布的可行集样本。

关键设计：LMPC-HR的关键设计在于将边界搜索问题建模为线性规划。具体来说，对于给定的状态和搜索方向，通过求解一个线性规划问题，可以同时确定沿该方向的上界和下界。线性规划的目标函数可以是任意的，约束条件则由MPC的约束条件构成。求解器选择方面，可以使用任何成熟的线性规划求解器，如Gurobi或CPLEX。论文未提及具体的参数设置或损失函数，因为其核心在于将边界搜索转化为线性规划问题。

🖼️ 关键图片

fig_0

📊 实验亮点

数值实验表明，LMPC-HR采样器在生成均匀分布的可行集样本时，相比于朴素的基线方法，计算时间减少了一个数量级。这意味着在相同的计算资源下，LMPC-HR能够生成更多的训练数据，从而提高近似MPC策略的性能。

🎯 应用场景

该研究成果可应用于各种需要近似线性MPC的控制场景，例如机器人运动规划、自动驾驶、电力系统控制等。通过高效生成训练数据，可以加速近似MPC策略的学习，降低控制系统的计算成本，使其能够应用于实时性要求更高的场景。未来，该方法可以扩展到非线性MPC或其他类型的约束条件，进一步提高采样效率和适用性。

📄 摘要（原文）

Model Predictive Control (MPC) offers safe and near-optimal control but suffers from high computational costs. Approximate MPC (AMPC) mitigates this by learning a cheaper surrogate policy, typically by training a neural network on state-MPC input pairs. Generating training data is a major bottleneck, requiring solving the MPC for numerous states sampled from its feasible set. Since this feasible set is implicitly defined and unknown, efficient sampling is nontrivial but crucial. We propose the linear MPC Hit-and-Run (LMPC-HR) sampler for linear MPC with polyhedral constraints. We identify the feasible set boundaries along search directions, a crucial step within HR, by formulating the problem as a convex linear program, replacing expensive iterative searches with a single optimization step. A numerical study demonstrates that LMPC-HR achieves an order of magnitude reduction in computation time for generating uniformly distributed samples from the feasible set compared to naive baselines.