Optimal Control of Hybrid Systems via Measure Relaxations
作者: Etienne Buehrle, Ömer Şahin Taş, Christoph Stiller
分类: math.OC, eess.SY
发布日期: 2025-07-25
备注: 7 pages, 6 figures, accepted at CDC 2025
🔗 代码/项目: GITHUB
💡 一句话要点
提出基于测度松弛的混合系统最优控制方法，提升轨迹规划效率。
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 混合系统 最优控制 轨迹优化 测度松弛 凸优化
📋 核心要点
- 混合系统的轨迹优化面临计算复杂度高的挑战，尤其是在处理大量离散模式时，传统的混合整数规划方法难以扩展。
- 本文利用凸集图框架和占用测度松弛，将混合系统最优控制问题转化为凸优化问题，从而实现高效的全局最优解。
- 实验结果表明，该方法在时序逻辑规范下规划轨迹时，能提供接近非凸解的成本下界，并显著提升运行速度。
📝 摘要（中文）
本文提出了一种基于凸集图框架的分段多项式系统轨迹优化方法。该框架采用基于占用测度的最优控制凸松弛，形成类似于离散最短路径线性规划的凸优化问题，可以高效地求解到全局最优。虽然该方法继承了半定规划的局限性，但与NP难的混合整数规划相比，其在大量离散模式下的可扩展性得到了提高。我们使用该方法在时序逻辑规范下规划轨迹，并将计算出的成本下界与具有固定模式序列的非凸优化方法进行比较。数值实验表明，该下界通常接近非凸解，且与通常难以处理的混合整数规划相比，运行时加速效果显著。我们的实现可在https://github.com/ebuehrle/hpoc 获取。
🔬 方法详解
问题定义：论文旨在解决分段多项式混合系统的最优控制问题，即在满足特定约束（如时序逻辑规范）下，找到最优的系统轨迹。现有方法，特别是基于混合整数规划的方法，在处理具有大量离散模式的系统时，计算复杂度呈指数增长，难以扩展到复杂场景。
核心思路：论文的核心思路是将混合系统的最优控制问题转化为一个凸优化问题，通过使用占用测度（occupation measures）对状态和控制变量的联合分布进行建模，并利用凸松弛技术，将原问题转化为一个可以高效求解的凸优化问题。这种方法避免了直接处理离散变量，从而降低了计算复杂度。
技术框架：整体框架基于凸集图（graphs of convex sets）的概念。首先，将混合系统的状态空间划分为多个凸集。然后，利用占用测度将系统动力学和约束表示为凸约束。最后，通过求解一个半定规划（SDP）问题，得到最优的占用测度，并从中提取出最优轨迹。该框架包含以下主要阶段：1) 系统建模：将混合系统描述为分段多项式系统；2) 凸松弛：利用占用测度将最优控制问题转化为凸优化问题；3) 求解优化问题：使用半定规划求解器求解凸优化问题；4) 轨迹提取：从最优占用测度中提取出最优轨迹。
关键创新：最重要的技术创新点在于利用占用测度将混合系统的最优控制问题转化为凸优化问题。与传统的混合整数规划方法相比，该方法避免了直接处理离散变量，从而显著降低了计算复杂度，提高了可扩展性。本质区别在于，混合整数规划直接搜索离散模式的组合，而该方法通过凸松弛，将离散模式的选择隐含在连续的占用测度中。
关键设计：关键设计包括：1) 使用分段多项式函数描述系统动力学；2) 利用占用测度对状态和控制变量的联合分布进行建模；3) 使用半定规划求解器求解凸优化问题；4) 设计合适的成本函数，以满足特定的优化目标（例如，最小化能量消耗或最大化安全性）。具体的参数设置和损失函数取决于具体的应用场景和优化目标。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该方法在时序逻辑规范下规划轨迹时，能够提供接近非凸解的成本下界。与传统的混合整数规划方法相比，该方法在运行时速度上有了显著提升，尤其是在处理具有大量离散模式的系统时。具体的性能数据可以在论文的数值实验部分找到，但摘要中未给出具体数值。
🎯 应用场景
该研究成果可应用于机器人运动规划、自动驾驶、飞行器控制等领域。通过高效求解混合系统的最优控制问题，可以实现更安全、更高效的自主系统。例如，在自动驾驶中，可以利用该方法规划车辆在复杂交通环境下的最优行驶轨迹，同时考虑交通规则和车辆动力学约束。未来，该方法有望应用于更复杂的混合系统，如多智能体系统和人机协作系统。
📄 摘要（原文）
We propose an approach to trajectory optimization for piecewise polynomial systems based on the recently proposed graphs of convex sets framework. We instantiate the framework with a convex relaxation of optimal control based on occupation measures, resulting in a convex optimization problem resembling the discrete shortest-paths linear program that can be solved efficiently to global optimality. While this approach inherits the limitations of semidefinite programming, scalability to large numbers of discrete modes improves compared to the NP-hard mixed-integer formulation. We use this to plan trajectories under temporal logic specifications, comparing the computed cost lower bound to a nonconvex optimization approach with fixed mode sequence. In our numerical experiments, we find that this bound is typically in the vicinity of the nonconvex solution, while the runtime speedup is significant compared to the often intractable mixed-integer formulation. Our implementation is available at https://github.com/ebuehrle/hpoc.