A Long-Short-Term Mixed-Integer Formulation for Highway Lane Change Planning

📄 arXiv: 2405.02979v1 📥 PDF

作者: Rudolf Reiter, Armin Nurkanovic, Daniele Bernadini, Moritz Diehl, Alberto Bemporad

分类: cs.RO, eess.SY

发布日期: 2024-05-05

💡 一句话要点

提出一种长短期混合整数规划方法，用于高速公路多智能体环境下的车道变换规划。

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

关键词: 车道变换规划 混合整数规划 模型预测控制 运动规划 多智能体系统

📋 核心要点

  1. 现有车道变换规划方法难以同时兼顾长时程决策和短时程精确动力学建模，导致次优或不安全的行为。
  2. 该论文提出一种长短期混合整数规划方法，利用几何近似处理长时程组合问题，并结合离散时间短时程优化。
  3. 实验结果表明，该算法在闭环性能和计算时间上优于其他先进的运动规划算法，并在SUMO等仿真环境中验证。

📝 摘要（中文）

本文研究了结构化多智能体道路环境中最佳车道变换问题。提出了一种新的运动规划算法，该算法能够捕获长时程依赖关系以及短时程动力学。我们方法的关键在于对长时程组合过渡问题的几何近似，我们将其公式化为连续时空域。此外，还提出了短时程最优运动规划问题的离散时间公式，并将其与长时程规划器相结合。单个问题及其组合都被公式化为MIQP（混合整数二次规划），并使用最先进的求解器实时求解。我们展示了所提出的算法在闭环性能和车道变换问题的计算时间方面优于其他两种最先进的运动规划算法。评估使用交通模拟器SUMO、定制的低级跟踪模型预测控制器以及CommonRoad环境提供的高保真车辆模型和场景进行。

🔬 方法详解

问题定义：论文旨在解决高速公路多智能体环境下车辆进行最优车道变换的运动规划问题。现有方法通常难以同时处理长时程的策略决策（例如，何时以及如何变道）和短时程的精确动力学控制（例如，避免碰撞，保持舒适性）。这导致规划结果可能不是全局最优，或者在实际执行中出现问题。

核心思路：论文的核心思路是将车道变换问题分解为长时程的组合优化问题和短时程的精确运动规划问题，并分别进行建模和求解。长时程规划负责确定变道的时机和目标车道，采用几何近似的方式简化计算复杂度。短时程规划则负责生成具体的运动轨迹，保证车辆的安全性和舒适性。

技术框架：整体框架包含两个主要模块：长时程规划器和短时程规划器。长时程规划器首先在连续时空域中对车道变换的组合问题进行几何近似，生成一个粗略的变道方案。然后，短时程规划器基于该方案，利用离散时间模型预测控制（MPC）生成精确的运动轨迹。两个规划器通过混合整数二次规划（MIQP）进行求解，并使用SUMO交通模拟器进行验证。

关键创新：该论文的关键创新在于提出了一种长短期混合整数规划的框架，能够有效地处理车道变换问题中的长时程决策和短时程动力学约束。通过几何近似简化了长时程组合优化问题，使其能够在实时性要求下求解。同时，将长时程规划和短时程规划相结合，实现了全局最优和局部精确的平衡。

关键设计：长时程规划器采用几何近似方法，将车道变换的组合问题转化为连续时空域中的优化问题。短时程规划器使用离散时间模型预测控制（MPC），并考虑了车辆的动力学约束、交通规则和安全距离等因素。混合整数二次规划（MIQP）被用于求解这两个规划问题，并使用最先进的求解器进行实时优化。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的算法在闭环性能和计算时间方面优于其他两种最先进的运动规划算法。具体而言，该算法在车道变换任务中能够更快地完成变道，并且能够更好地避免碰撞。此外，该算法的计算时间也得到了显著的降低，使其能够在实时性要求较高的场景中使用。

🎯 应用场景

该研究成果可应用于自动驾驶车辆的车道变换功能，提高车辆在复杂交通环境中的行驶效率和安全性。此外，该方法还可以扩展到其他运动规划问题，例如车辆汇流、避障等，具有广泛的应用前景。未来，该研究可以进一步探索在更加复杂的交通场景下的应用，例如城市道路、交叉路口等。

📄 摘要（原文）

This work considers the problem of optimal lane changing in a structured multi-agent road environment. A novel motion planning algorithm that can capture long-horizon dependencies as well as short-horizon dynamics is presented. Pivotal to our approach is a geometric approximation of the long-horizon combinatorial transition problem which we formulate in the continuous time-space domain. Moreover, a discrete-time formulation of a short-horizon optimal motion planning problem is formulated and combined with the long-horizon planner. Both individual problems, as well as their combination, are formulated as MIQP and solved in real-time by using state-of-the-art solvers. We show how the presented algorithm outperforms two other state-of-the-art motion planning algorithms in closed-loop performance and computation time in lane changing problems. Evaluations are performed using the traffic simulator SUMO, a custom low-level tracking model predictive controller, and high-fidelity vehicle models and scenarios, provided by the CommonRoad environment.