A Fast Semidefinite Convex Relaxation for Optimal Control Problems With Spatio-Temporal Constraints

📄 arXiv: 2601.03055v1 📥 PDF

作者: Shiying Dong, Zhipeng Shen, Rudolf Reiter, Hailong Huang, Bingzhao Gao, Hong Chen, Wen-Hua Chen

分类: cs.RO

发布日期: 2026-01-06

备注: 9 pages, 6 figures

💡 一句话要点

提出一种快速半定凸松弛算法，用于求解具有时空约束的最优控制问题。

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

关键词: 最优控制 半定规划 凸松弛 时空约束 自主系统

📋 核心要点

  1. 现有方法在解决具有时空约束的最优控制问题时，由于非凸性，难以保证解的最优性和计算效率。
  2. 论文提出一种基于时间尺度直接多重射击方案和半定规划凸松弛的快速算法，利用稀疏性提升计算效率。
  3. 仿真和真实四旋翼飞行实验验证了该方法在复杂环境中求解最优控制问题的有效性和实用性。

📝 摘要（中文）

在自动驾驶车辆的节能驾驶和四旋翼飞行器导航等应用中，快速准确地求解具有时空约束的自主代理最优控制问题（OCP）至关重要。然而，由于动力学和事件时序之间的耦合，逼近OCP的非线性程序本质上是非凸的，因此难以求解。大多数方法通过预定义航路点时间或仅使用非凸轨迹优化来简化问题，但通常会产生次优解。为了显著改善数值特性，我们提出了一种时间尺度直接多重射击方案，该方案将预测范围划分为与特征时间约束对齐的段。此外，我们开发了一种快速的基于半定规划的凸松弛算法，该算法利用了提升公式的稀疏模式。全面的仿真研究证明了该解决方案的最优性和计算效率。此外，在具有约束开放时间窗口的四旋翼航路点飞行任务中的真实实验验证了该方法在复杂环境中的实际适用性。

🔬 方法详解

问题定义：论文旨在解决具有时空约束的自主代理的最优控制问题（OCP）。现有方法，如预定义航路点时间或非凸轨迹优化，通常会产生次优解，并且计算效率较低。问题的核心在于动力学和事件时序之间的耦合导致非线性程序的高度非凸性，使得求解变得困难。

核心思路：论文的核心思路是利用时间尺度变换将问题转化为更易于处理的形式，并采用半定规划（SDP）进行凸松弛。通过时间尺度变换，可以将时间约束显式地纳入优化问题中。利用SDP凸松弛，可以将非凸问题转化为凸问题，从而保证解的最优性。此外，论文还利用了问题结构的稀疏性，进一步提升了计算效率。

技术框架：整体框架包括以下几个主要步骤：1) 使用时间尺度直接多重射击方案对预测范围进行分割，使其与特征时间约束对齐。2) 将原始非凸OCP转化为一个等价的提升公式。3) 对提升后的公式进行半定规划凸松弛，得到一个凸优化问题。4) 求解凸优化问题，得到松弛解。5) 将松弛解映射回原始问题，得到次优解。

关键创新：论文的关键创新在于提出了一种快速的基于半定规划的凸松弛算法，该算法能够有效地解决具有时空约束的最优控制问题。与现有方法相比，该方法能够保证解的最优性，并且具有更高的计算效率。此外，论文还利用了问题结构的稀疏性，进一步提升了计算效率。

关键设计：论文的关键设计包括：1) 时间尺度直接多重射击方案，用于将预测范围分割成与特征时间约束对齐的段。2) 半定规划凸松弛，用于将非凸问题转化为凸问题。3) 利用问题结构的稀疏性，减少计算复杂度。具体的参数设置和损失函数等细节在论文中有详细描述，但此处不便展开。

📊 实验亮点

论文通过仿真实验验证了所提出方法的有效性和计算效率。实验结果表明，该方法能够以较高的精度和较低的计算成本求解具有时空约束的最优控制问题。此外，在四旋翼飞行器航路点飞行任务的真实实验中，该方法也取得了良好的效果，验证了其在复杂环境中的实际适用性。具体性能数据和对比基线在论文中有详细描述。

🎯 应用场景

该研究成果可广泛应用于需要考虑时空约束的自主系统，例如自动驾驶车辆的节能驾驶、四旋翼飞行器的导航、机器人路径规划、以及其他需要精确控制时间和空间轨迹的应用场景。该方法能够提高系统的性能和安全性，并降低计算成本，具有重要的实际应用价值和潜在的未来影响。

📄 摘要（原文）

Solving optimal control problems (OCPs) of autonomous agents operating under spatial and temporal constraints fast and accurately is essential in applications ranging from eco-driving of autonomous vehicles to quadrotor navigation. However, the nonlinear programs approximating the OCPs are inherently nonconvex due to the coupling between the dynamics and the event timing, and therefore, they are challenging to solve. Most approaches address this challenge by predefining waypoint times or just using nonconvex trajectory optimization, which simplifies the problem but often yields suboptimal solutions. To significantly improve the numerical properties, we propose a formulation with a time-scaling direct multiple shooting scheme that partitions the prediction horizon into segments aligned with characteristic time constraints. Moreover, we develop a fast semidefinite-programming-based convex relaxation that exploits the sparsity pattern of the lifted formulation. Comprehensive simulation studies demonstrate the solution optimality and computational efficiency. Furthermore, real-world experiments on a quadrotor waypoint flight task with constrained open time windows validate the practical applicability of the approach in complex environments.