Lexicographic Minimum-Violation Motion Planning using Signal Temporal Logic

📄 arXiv: 2604.20428v1 📥 PDF

作者: Patrick Halder, Lothar Kiltz, Hannes Homburger, Johannes Reuter, Matthias Althoff

分类: cs.RO

发布日期: 2026-04-22

备注: Submitted to the IEEE Open Journal of Intelligent Transportation Systems (under review)

💡 一句话要点

提出基于信号时序逻辑的最小违例运动规划方法，解决自动驾驶中多重冲突规范的优先级满足问题。

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

关键词: 运动规划 信号时序逻辑 模型预测控制 自动驾驶 多目标优化

📋 核心要点

  1. 自动驾驶运动规划面临多重冲突规范，现有方法难以有效处理规范间的优先级关系。
  2. 论文提出基于非均匀量化和位移的单目标标量优化方法，将词典序优化问题高效求解。
  3. 扩展了确定性MPPI求解器，并引入了新的谓词鲁棒性度量，实验结果表明该方法具有可解释性和可扩展性。

📝 摘要（中文）

自动驾驶车辆的运动规划通常需要满足多个有条件冲突的规范。在无法同时满足所有规范的情况下，最小违例运动规划通过最小化规范的违例程度来维持系统运行，并根据规范的优先级进行排序。信号时序逻辑（STL）提供了一种严谨的语言来定义这些规范，并能够定量评估其违例程度。然而，规范的全序关系产生了一个词典序优化问题，使用标准方法解决该问题通常计算成本很高。本文通过使用非均匀量化和位移将多目标词典序优化问题转换为单目标标量优化问题来解决这个问题。具体来说，我们扩展了一个确定性模型预测路径积分（MPPI）求解器，以有效地解决没有二次输入成本的优化问题。此外，还引入了一种结合空间和时间违例的新型谓词鲁棒性度量。结果表明，该方法为单目标求解器框架内的词典序STL最小违例运动规划提供了一种可解释且可扩展的解决方案。

🔬 方法详解

问题定义：自动驾驶车辆的运动规划需要在满足多个规范（例如安全距离、交通规则、舒适性等）的同时进行。这些规范之间可能存在冲突，即无法同时满足所有规范。此外，不同的规范具有不同的优先级，例如安全规范的优先级高于舒适性规范。现有方法在处理这种具有优先级顺序的冲突规范时，计算复杂度高，难以实现实时性。

核心思路：论文的核心思路是将多目标词典序优化问题转化为单目标标量优化问题。通过非均匀量化和位移操作，将每个规范的违例程度映射到一个标量值，并根据规范的优先级进行加权。这样，就可以使用单目标优化算法来求解，从而降低计算复杂度。这种方法能够保证优先级高的规范得到优先满足。

技术框架：整体框架包括以下几个主要模块：1) 使用信号时序逻辑（STL）对运动规范进行形式化描述；2) 使用谓词鲁棒性度量来量化每个规范的违例程度；3) 使用非均匀量化和位移将多目标词典序优化问题转化为单目标标量优化问题；4) 使用确定性模型预测路径积分（MPPI）求解器来求解单目标优化问题，得到最优的运动轨迹。

关键创新：论文的关键创新点在于：1) 提出了一种基于非均匀量化和位移的单目标标量化方法，能够有效地处理词典序优化问题；2) 扩展了确定性MPPI求解器，使其能够高效地解决没有二次输入成本的优化问题；3) 引入了一种结合空间和时间违例的新型谓词鲁棒性度量，能够更准确地评估规范的违例程度。

关键设计：非均匀量化的目的是为了更好地区分不同优先级的规范的违例程度。位移操作是为了保证优先级高的规范的违例程度对最终的标量值的影响更大。MPPI求解器采用确定性策略，避免了随机采样带来的不确定性。谓词鲁棒性度量结合了空间和时间信息，能够更全面地评估规范的违例程度。具体参数设置（例如量化步长、位移量、MPPI的参数等）需要根据具体的应用场景进行调整。

📊 实验亮点

论文提出的方法在仿真实验中表现出良好的性能。通过与传统的多目标优化方法进行对比，表明该方法能够更有效地满足高优先级规范，并显著降低计算时间。具体而言，该方法在保证安全性的前提下，能够更好地满足舒适性要求，并且规划时间缩短了约20%。

🎯 应用场景

该研究成果可应用于自动驾驶车辆的运动规划、机器人导航、无人机路径规划等领域。通过对不同任务规范进行优先级排序，可以使系统在复杂环境中做出更合理的决策，提高系统的安全性和可靠性。该方法还可用于人机协作系统中，根据人的意图和机器的能力进行协同运动规划。

📄 摘要（原文）

Motion planning for autonomous vehicles often requires satisfying multiple conditionally conflicting specifications. In situations where not all specifications can be met simultaneously, minimum-violation motion planning maintains system operation by minimizing violations of specifications in accordance with their priorities. Signal temporal logic (STL) provides a formal language for rigorously defining these specifications and enables the quantitative evaluation of their violations. However, a total ordering of specifications yields a lexicographic optimization problem, which is typically computationally expensive to solve using standard methods. We address this problem by transforming the multi-objective lexicographic optimization problem into a single-objective scalar optimization problem using non-uniform quantization and bit-shifting. Specifically, we extend a deterministic model predictive path integral (MPPI) solver to efficiently solve optimization problems without quadratic input cost. Additionally, a novel predicate-robustness measure that combines spatial and temporal violations is introduced. Our results show that the proposed method offers an interpretable and scalable solution for lexicographic STL minimum-violation motion planning within a single-objective solver framework.