Lexicographic Descent: A Gradient-Based Approach to Optimize Totally Ordered Rulebooks via Parametric Scalarization

Matteo Penlington; Alessandro Zanardi; Lorenzo Fiaschi; Emilio Frazzoli

cs.ROSep 17, 2024

Lexicographic Descent: A Gradient-Based Approach to Optimize Totally Ordered Rulebooks via Parametric Scalarization

Authors: Matteo Penlington, Alessandro Zanardi, Lorenzo Fiaschi, Emilio Frazzoli

Organizations: Institute for Dynamic Systems and Control, ETH Zürich, Switzerland

Abstract

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 $r_{0}$ and $r_{1}$ , shaded by violation score. Overlaid on $r_{0}$ is $S^{0}$ , valleys dashed and ridge dotted. Right: the $x_{2}$ -coordinates of $S_{k}$ against $w_{1}(k)$ ( $x_{1}=1$ throughout). For $w_{1}(k)>w^{\star}$ (shaded) $S_{k}$ is a singleton in the upper valley; below, the lower minimum (solid) and the saddle (dashed) arise.

Figure 2: Executed paths from $x_{\mathrm{init}}=(-1.5,-1.5)$ for $10^{6}$ solver steps. Red lines are $S_{k}$ , solid for the minima and dashed for the saddle, darkening as $k$ grows. Shading matches $r_{0}$ for display of the valleys.

Figure 3: Distance of the iterates to

\{(x_{1},x_{2})\mid x_{2}=\pm 1\}

(left) and to

S_{k}

(right). Lines are

x_{\mathrm{init}}=(-1.5,-1.5)

of Fig. 2 ; shading indicates

95\%

quantile bands over

10^{4}

initializations drawn uniformly on

\mathcal{X}

Figure 4: Robustness to the initialization. Each point is an initialization $x\in\mathcal{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 $\epsilon=5\cdot 10^{-2}$ of the lexicographic optimum.

Nominal driving, $150$ scenarios
	$r_{0}$	$r_{1}$	$r_{2}$	$r_{3}$	$r_{4}$
Ours	$5.9{\cdot}10^{-4}$	$3{\cdot}10^{-5}$	$1.1{\cdot}10^{-3}$	$1.5{\cdot}10^{-3}$	$6.8{\cdot}10^{-3}$
Preemptive	$2.8{\cdot}10^{-3}$	$0.19$	$8.4{\cdot}10^{-3}$	$0.19$	$0.33$
Cut-in scenario, $15$ variants
Ours	$3.8{\cdot}10^{-3}$	$0.051$	$3.5{\cdot}10^{-4}$	$0.26$	$0.25$
Preemptive	$5.6{\cdot}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.

Constrained Optimization

Constrained optimization finds the best decisions while satisfying equality, inequality, resource, safety, or fairness requirements.

See all 342 papers

Risk-Aware Optimal Control with Rulebooks
Sep 4, 2026Tichakorn WongpiromsarnOptimal Control Safety-Critical Control
Department of Computer Science, Iowa State University, Ames, IA 50010
Not All Objectives Are Born Equal: Priority-Constrained Descent for Hierarchical Multi-Objective Optimization
Jun 28, 2026Dara Varam, Mohamed I. AlhajriConstrained Optimization Multi-Objective Optimization
Department of Computer Science & Engineering, American University of Sharjah · Senseable City Laboratory, Massachusetts Institute of Technology
Lexicographic Minimum-Violation Motion Planning using Signal Temporal Logic
Apr 22, 2026Patrick Halder, Lothar Kiltz, Hannes Homburger +2STL Motion Planning Motion Planning
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

Sep 4, 2026J/K move · Enter open · S save

Risk-Aware Optimal Control with Rulebooks

Tichakorn Wongpiromsarn

Department of Computer Science, Iowa State University, Ames, IA 50010

Optimal Control Safety-Critical Control Multi-Objective Optimization

Open paper AskPDF arXiv

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.

Abstract

Constrained Optimization

Explore similar work

Risk-Aware Optimal Control with Rulebooks

Not All Objectives Are Born Equal: Priority-Constrained Descent for Hierarchical Multi-Objective Optimization

Lexicographic Minimum-Violation Motion Planning using Signal Temporal Logic