Safety-critical systems, such as autonomous vehicles, must satisfy conflicting constraints and objectives, collectively called rules, typically ordered lexicographically. Preemptive lexicographic optimization solves a sequence of problems, one per priority level. However, higher levels are optimized without considering lower ones, making the approach susceptible to suboptimal solutions. On the other hand, scalarization optimizes all levels jointly and so avoids this myopia, but a finite weighted sum permits trade-offs across priority levels, and exact scalar representations lack the regularity standard solvers require. We propose Lexicographic Descent, which combines the benefits of both: a single weighted sum whose relative weights decay at priority-dependent rates, recovering the lexicographic order in the limit. We show that Lexicographic Descent converges to constrained stationary points of the highest-priority rule, matching preemptive guarantees. Since the lower-priority weights vanish, we derive a necessary condition for the lower-priority rules to keep guiding the iterates, with the aim of avoiding suboptimal stationary points of the higher-priority rules. We show that Lexicographic Descent can exploit problem structure to reach the lexicographic optima, and outperforms the preemptive approach on an autonomous driving case study.
Figures & tables
Figure 1: The toy problem. Left: the rules r0 and r1 , shaded by violation score. Overlaid on r0 is S0 , valleys dashed and ridge dotted. Right: the x2 -coordinates of Sk against w1(k) ( x1=1 throughout). For w1(k)>w⋆ (shaded) Sk is a singleton in the upper valley; below, the lower minimum (solid) and the saddle (dashed) arise.
Figure 2: Executed paths from xinit=(−1.5,−1.5) for 106 solver steps. Red lines are Sk , solid for the minima and dashed for the saddle, darkening as k grows. Shading matches r0 for display of the valleys.
Figure 3: Distance of the iterates to {(x1,x2)∣x2=±1} (left) and to Sk (right). Lines are xinit=(−1.5,−1.5) of Fig. 2 ; shading indicates 95% quantile bands over 104 initializations drawn uniformly on X .
Figure 4: Robustness to the initialization. Each point is an initialization x∈X , colored by where the final iterate lies: at the lexicographic optimum, elsewhere in the upper valley, at the local minimum (1,−1) , or elsewhere in the lower valley; percentages give the fraction reaching within ϵ=5⋅10−2 of the lexicographic optimum.
r0
r1
r2
r3
r4
Nominal driving, 150 scenarios
Ours
5.9⋅10−4
3⋅10−5
1.1⋅10−3
1.5⋅10−3
6.8⋅10−3
Preemptive
2.8⋅10−3
0.19
8.4⋅10−3
0.19
0.33
Cut-in scenario, 15 variants
Ours
3.8⋅10−3
0.051
3.5⋅10−4
0.26
0.25
Preemptive
5.6⋅10−5
0
0
1.2
0.026
Table I : Realized rule violations averaged over the steps of each trajectory and over scenarios.
Figure 5: The cut-in scenario. A vehicle leaves the free lane and brakes to join the traffic jam in the ego vehicle’s lane; boxes show the vehicles every second, labeled by time in seconds, and the star marks the destination. Ours (top) changes into the free lane and passes; the preemptive approach (bottom) stays behind the vehicle.
We consider safety-critical control problems involving multiple requirements with different priorities and uncertainty in their evaluation. We represent these requirements using risk-aware rulebooks, where each requirement is assigned a risk measure and an acceptable threshold, and a priority relation is defined among the requirements. Each requirement induces a risk-evaluation function that maps a policy to the risk associated with its violation. We formulate risk-aware optimal control with rulebooks as a lexicographic optimization problem over excess risks and develop an anytime filtering and branch-and-bound algorithm that progressively tightens the certified optimality gap while characterizing the corresponding set of policies at each priority level. The algorithm returns a policy together with these gaps, which bound its suboptimality. We prove that these gaps are valid for any finite computational budget and, under additional assumptions, converge to zero as the computational budget increases. We evaluate the algorithm on a synthetic benchmark with a known optimum and a realistic highway-merging simulation with CVaR-based collision, rear-braking, headway, and comfort rules.
Tichakorn Wongpiromsarn
Department of Computer Science, Iowa State University, Ames, IA 50010
Deep learning problems rarely involve objectives that are equal in importance. A primary objective defines the goal, whilst secondary objectives, such as sparsity, compression, or robustness constrain the solution. While existing multi-objective methods have proven effective in practice, they have a clear symmetry problem and neglect the inherent objective hierarchy built into these objective spaces. We introduce Priority-Constrained Descent (PCD), a gradient-based optimization framework designed to explicitly exploit hierarchical objective structures. PCD preserves the direction of primary descent whilst allowing for the minimal distortion necessary to guarantee progress on secondary objectives, controlled by a single τ∈[0,1] that dictates the strength of the distortion. The resulting formulation is invariant to objective scaling and admits exact closed-form solutions for problems with two and three objectives. We evaluate PCD within structured network compression settings, unstructured sparsity and low-rankness, and across a variety of synthetic experiments, showing Pareto dominance and better per-objective performance with secondary progress guarantees over existing methods, further exhibiting the interpretable trade-off that τ provides.
Dara Varam, Mohamed I. Alhajri
Department of Computer Science & Engineering, American University of Sharjah · Senseable City Laboratory, Massachusetts Institute of Technology
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.
Patrick Halder, Lothar Kiltz, Hannes Homburger +2
School of Computation, Information and Technology, Technical University of Munich, 85748 Garching, Germany · 2ZF Friedrichshafen AG, 88046 Friedrichshafen, Germany · Institute of System Dynamics, HTWG Konstanz, 78562 Konstanz, Germany