Mixed-Integer MPC-Based Motion Planning Using Hybrid Zonotopes with Tight Relaxations

📄 arXiv: 2411.01286v1 📥 PDF

作者: Joshua A. Robbins, Jacob A. Siefert, Sean Brennan, Herschel C. Pangborn

分类: eess.SY, cs.RO

发布日期: 2024-11-02

💡 一句话要点

提出基于混合Zonotope和混合整数MPC的运动规划方法，加速自动驾驶车辆实时决策。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱三：空间感知与语义 (Perception & Semantics)

关键词: 自动驾驶 运动规划 模型预测控制 混合整数规划 混合Zonotope

📋 核心要点

  1. 自动驾驶运动规划面临非凸约束，传统MPC难以在嵌入式硬件上实时运行。
  2. 利用混合Zonotope表示非凸约束，将MPC问题转化为可高效求解的混合整数二次规划。
  3. 实验表明，该方法比现有求解器快一个数量级，并验证了在嵌入式硬件上的实时性。

📝 摘要（中文）

本文提出了一种利用混合Zonotope表示无障碍空间，高效解决混合整数MPC运动规划问题的方法。该方法将MPC优化问题构建为多阶段混合整数二次规划(MIQP)，并利用混合Zonotope表示非凸约束。通过在MPC成本函数中为无障碍空间的不同区域分配成本，支持风险感知的规划。提出了一种多阶段MIQP求解器，该求解器利用了混合Zonotope约束的结构。对于某些混合Zonotope表示，证明了凸松弛是紧的，即等于凸包。结合从AV运动规划背景中导出的逻辑约束，利用此属性在分支定界混合整数求解器中生成紧二次规划(QP)子问题。进一步利用混合Zonotope结构来减少需要在QP子问题中计算的矩阵分解的数量。仿真研究表明，该求解器在多面体地图和占用网格中，能够解决避障和风险感知运动规划问题。在大多数情况下，所提出的求解器比最先进的商业求解器快一个数量级。处理器在环研究证明了该求解器在嵌入式硬件上实时实现的实用性。

🔬 方法详解

问题定义：自动驾驶车辆的运动规划问题通常涉及非凸约束，例如避障。传统的模型预测控制(MPC)方法在处理这些非凸约束时计算复杂度高，难以在嵌入式硬件上实现实时控制。现有的商业求解器虽然可以解决这些问题，但在计算效率上仍有提升空间。

核心思路：本文的核心思路是利用混合Zonotope来表示车辆周围的无障碍空间，并将运动规划问题转化为一个混合整数二次规划(MIQP)问题。混合Zonotope能够有效地表示非凸区域，并且其结构可以被用于设计高效的求解器。通过将风险感知融入到MPC的成本函数中，可以实现更安全的运动规划。

技术框架：该方法主要包含以下几个阶段：1) 使用混合Zonotope表示车辆周围的无障碍空间；2) 将MPC问题转化为一个多阶段MIQP问题，其中混合Zonotope约束被用于表示非凸约束；3) 设计一个专门的MIQP求解器，该求解器利用混合Zonotope的结构来加速求解过程；4) 在嵌入式硬件上进行实时测试，验证该方法的有效性。

关键创新：该方法最重要的技术创新点在于利用混合Zonotope来表示非凸约束，并设计了一个专门的MIQP求解器来加速求解过程。与传统的MPC方法相比，该方法能够更有效地处理非凸约束，并且具有更高的计算效率。此外，该方法还利用了混合Zonotope的结构来减少需要在QP子问题中计算的矩阵分解的数量，进一步提高了计算效率。

关键设计：在混合Zonotope的表示方面，论文选择合适的生成器数量和方向是关键。在MIQP求解器设计方面，论文利用了混合Zonotope约束的结构，并结合逻辑约束，生成紧二次规划(QP)子问题，从而加速分支定界算法的收敛。成本函数的设计也至关重要，需要合理地权衡安全性、舒适性和效率。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，该方法在避障和风险感知运动规划问题中，比最先进的商业求解器快一个数量级。处理器在环测试验证了该方法在嵌入式硬件上的实时性。这些结果表明，该方法具有很高的实用价值，可以有效地解决自动驾驶运动规划中的实际问题。

🎯 应用场景

该研究成果可应用于自动驾驶车辆的运动规划、机器人导航、无人机路径规划等领域。通过高效地解决非凸约束下的运动规划问题，可以提高自动驾驶系统的安全性、可靠性和实时性，加速自动驾驶技术的商业化落地。此外，该方法还可以扩展到其他需要处理非凸约束的优化问题中。

📄 摘要（原文）

Autonomous vehicle (AV) motion planning problems often involve non-convex constraints, which present a major barrier to applying model predictive control (MPC) in real time on embedded hardware. This paper presents an approach for efficiently solving mixed-integer MPC motion planning problems using a hybrid zonotope representation of the obstacle-free space. The MPC optimization problem is formulated as a multi-stage mixed-integer quadratic program (MIQP) using a hybrid zonotope representation of the non-convex constraints. Risk-aware planning is supported by assigning costs to different regions of the obstacle-free space within the MPC cost function. A multi-stage MIQP solver is presented that exploits the structure of the hybrid zonotope constraints. For some hybrid zonotope representations, it is shown that the convex relaxation is tight, i.e., equal to the convex hull. In conjunction with logical constraints derived from the AV motion planning context, this property is leveraged to generate tight quadratic program (QP) sub-problems within a branch-and-bound mixed-integer solver. The hybrid zonotope structure is further leveraged to reduce the number of matrix factorizations that need to be computed within the QP sub-problems. Simulation studies are presented for obstacle-avoidance and risk-aware motion planning problems using polytopic maps and occupancy grids. In most cases, the proposed solver finds the optimal solution an order of magnitude faster than a state-of-the-art commercial solver. Processor-in-the-loop studies demonstrate the utility of the solver for real-time implementations on embedded hardware.