Lexicographic Minimum-Violation Motion Planning using Signal Temporal Logic
This addresses motion planning for autonomous vehicles where not all specifications can be met, offering a more efficient method for handling prioritized violations, though it appears incremental as it builds on existing STL and MPPI frameworks.
The paper tackled the problem of computationally expensive lexicographic optimization in motion planning for autonomous vehicles with conflicting specifications, achieving an interpretable and scalable solution by transforming it into a single-objective problem using non-uniform quantization and bit-shifting.
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.