Matteo Penlington, Alessandro Zanardi, Lorenzo Fiaschi, Emilio Frazzoli
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.
Yueshan Li, Lorenzo Fiaschi, Andrea Censi, Emilio Frazzoli
Independently developed autonomous agents, such as autonomous vehicles, must guarantee joint compatibility, such as safety and task-completion requirements, when they operate in a shared environment. Existing methods require a centrally designed specification, or interaction mechanism before any agent is deployed. However, such centralized design is unrealistic when agent designs are confidential to their developers, and it is not flexible enough to accommodate future agent designs. We study a bi-level structure in which a regulator coordinates developers by publishing seed agents, and each developer independently tests its agent to ensure that it is compatible with every seed-compatible agent, a property we call future-proofness. Under this structure, joint compatibility is guaranteed for any agents that are designed and tested independently, without any coordination with each other. In this work, we first formulate compatibility for general multi-agent systems and show why it is not trivially implied by seed-compatibility. We then characterize the future-proof agents as the closure of the seed and show that this closure is monotone in the seed. Finally, we study a class of executable tests that involve interaction with the seed alone, and we ask to what extent such tests can distinguish the future-proof agents.