Lexicographic Multi-Objective Stochastic Shortest Path with Mixed Max-Sum Costs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911318584328192 |
|---|---|
| author | Zhang, Zhiquan Muhammetkulyyev, Omar Wongpiromsarn, Tichakorn Ornik, Melkior |
| author_facet | Zhang, Zhiquan Muhammetkulyyev, Omar Wongpiromsarn, Tichakorn Ornik, Melkior |
| contents | We study the Stochastic Shortest Path (SSP) problem for autonomous systems with mixed max-sum cost aggregations under Linear Temporal Logic constraints. Classical SSP formulations rely on sum-aggregated costs, which are suitable for cumulative quantities such as time or energy but fail to capture bottleneck-style objectives such as avoiding high-risk transitions, where performance is determined by the worst single event along a trajectory. Such objectives are particularly important in safety-critical systems, where even one hazardous transition can be unacceptable. To address this limitation, we introduce max-aggregated objectives that minimize the bottleneck cost, i.e., the maximum one-step cost along a trajectory. We show that standard Bellman equations on the original state space do not apply in this setting and propose an augmented MDP with a state variable tracking the running maximum cost, together with a value iteration algorithm. We further identify a cyclic policy phenomenon, where zero-marginal-cost cycles prevent goal reaching under max-aggregation, and resolve it via a finite-horizon formulation. To handle richer task requirements, linear temporal logic specifications are translated into deterministic finite automata and combined with the system to construct a product MDP. We propose a lexicographic value iteration algorithm that handles mixed max-sum objectives under lexicographic ordering on this product MDP. Gridworld case studies demonstrate the effectiveness of the proposed framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_12761 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lexicographic Multi-Objective Stochastic Shortest Path with Mixed Max-Sum Costs Zhang, Zhiquan Muhammetkulyyev, Omar Wongpiromsarn, Tichakorn Ornik, Melkior Systems and Control We study the Stochastic Shortest Path (SSP) problem for autonomous systems with mixed max-sum cost aggregations under Linear Temporal Logic constraints. Classical SSP formulations rely on sum-aggregated costs, which are suitable for cumulative quantities such as time or energy but fail to capture bottleneck-style objectives such as avoiding high-risk transitions, where performance is determined by the worst single event along a trajectory. Such objectives are particularly important in safety-critical systems, where even one hazardous transition can be unacceptable. To address this limitation, we introduce max-aggregated objectives that minimize the bottleneck cost, i.e., the maximum one-step cost along a trajectory. We show that standard Bellman equations on the original state space do not apply in this setting and propose an augmented MDP with a state variable tracking the running maximum cost, together with a value iteration algorithm. We further identify a cyclic policy phenomenon, where zero-marginal-cost cycles prevent goal reaching under max-aggregation, and resolve it via a finite-horizon formulation. To handle richer task requirements, linear temporal logic specifications are translated into deterministic finite automata and combined with the system to construct a product MDP. We propose a lexicographic value iteration algorithm that handles mixed max-sum objectives under lexicographic ordering on this product MDP. Gridworld case studies demonstrate the effectiveness of the proposed framework. |
| title | Lexicographic Multi-Objective Stochastic Shortest Path with Mixed Max-Sum Costs |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2512.12761 |