Lexicographic Minimum-Violation Motion Planning using Signal Temporal Logic

• URL: http://arxiv.org/abs/2604.20428v1
• Date: Wed, 22 Apr 2026 10:49:09 GMT
• Title: Lexicographic Minimum-Violation Motion Planning using Signal Temporal Logic
• Abstract summary: Motion planning for autonomous vehicles often requires satisfying multiple conditionally conflicting specifications.<n>Signal temporal logic provides a formal language for rigorously defining these specifications.<n>A total ordering of specifications yields a lexicographic optimization problem.<n>We address this problem by transforming the multi-objective lexicographic optimization problem into a single-objective scalar optimization problem.
• Score: 9.646103797793614
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• VeriSimpl: Robust Optimization Modeling from Natural Language using Simplification-based Verification [0.43665049670577916]
  We introduce VeriSimpl, a framework for robust natural-language-to-optimization formalization.<n>Our approach is based on the idea of simplification-based verification.<n>We show how our approach provides consistent improvements in accuracy over existing methods, while also providing a novel high-precision self-verification signal.
  arXiv  Detail & Related papers  (2026-05-24T13:46:54Z)
• Feasibility Restoration under Conflicting STL Specifications with Pareto-Optimal Refinement [18.383508411056944]
  Signal Temporal Logic (STL) is expressive language that specifies expressive requirements in robotics.<n>STL specifications may become conflicting in real-world applications, where safety rules, traffic regulations, task and objectives can be cannot be satisfied together.<n>We propose a unified two-stage framework that first restores feasibility via minimal relaxation, then refine the feasible solution by formulating it as a value-aware multi-objective optimization problem.
  arXiv  Detail & Related papers  (2026-03-06T23:41:01Z)
• Optimality-Informed Neural Networks for Solving Parametric Optimization Problems [0.688204255655161]
  We propose to learn the mapping from parameters to primal optimal solutions and to their corresponding duals using neural networks.<n>Our approach, Optimality-informed Neural Networks (OptINNs), combines (i) a KKT-residual loss that penalizes violations of the first-order optimality conditions.<n>We evaluate OptINNs on different nonlinear optimization problems ranging from low to high dimensions.
  arXiv  Detail & Related papers  (2025-12-23T11:24:45Z)
• A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions [0.0]
  Problems with linear norm-bound constraints arise in a variety of applications, including portfolio optimization, machine learning, feature selection.<n>We propose a novel graphbased method to globally solve these problems.
  arXiv  Detail & Related papers  (2025-05-06T18:09:54Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
  Traditional mathematical programming solvers require long computational times to solve constrained minimization problems. We propose a penalty-based guardrail algorithm (PGA) to efficiently solve them.
  arXiv  Detail & Related papers  (2024-05-03T10:37:34Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.<n>An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  We propose a novel solution for challenging non-problems of multiple variables. Our proposed approach is able to achieve effective iterations in cases while other methods would typically fail.
  arXiv  Detail & Related papers  (2020-09-09T10:45:00Z)
• Goal Kernel Planning: Linearly-Solvable Non-Markovian Policies for Logical Tasks with Goal-Conditioned Options [54.40780660868349]
  We introduce a compositional framework called Linearly-Solvable Goal Kernel Dynamic Programming (LS-GKDP)<n>LS-GKDP combines the Linearly-Solvable Markov Decision Process (LMDP) formalism with the Options Framework of Reinforcement Learning.<n>We show how an LMDP with a goal kernel enables the efficient optimization of meta-policies in a lower-dimensional subspace defined by the task grounding.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.