Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.14121 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909453293453312 |
|---|---|
| author | Gaspard, Mallory E. Vladimirsky, Alexander |
| author_facet | Gaspard, Mallory E. Vladimirsky, Alexander |
| contents | When traveling through a graph with an accessible deterministic path to a target, is it ever preferable to resort to stochastic node-to-node transitions instead? And if so, what are the conditions guaranteeing that such a stochastic optimal routing policy can be computed efficiently? We aim to answer these questions here by defining a class of Opportunistically Stochastic Shortest Path (OSSP) problems and deriving sufficient conditions for applicability of non-iterative label-setting methods. The usefulness of this framework is demonstrated in two very different contexts: numerical analysis and autonomous vehicle routing. We use OSSPs to derive causality conditions for semi-Lagrangian discretizations of anisotropic Hamilton-Jacobi equations. We also use a Dijkstra-like method to solve OSSPs optimizing the timing and urgency of lane change maneuvers for an autonomous vehicle navigating road networks with a heterogeneous traffic load. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_14121 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Monotone Causality in Opportunistically Stochastic Shortest Path Problems Gaspard, Mallory E. Vladimirsky, Alexander Optimization and Control 90C39, 90C40, 49L20, 65N22, 49L25 When traveling through a graph with an accessible deterministic path to a target, is it ever preferable to resort to stochastic node-to-node transitions instead? And if so, what are the conditions guaranteeing that such a stochastic optimal routing policy can be computed efficiently? We aim to answer these questions here by defining a class of Opportunistically Stochastic Shortest Path (OSSP) problems and deriving sufficient conditions for applicability of non-iterative label-setting methods. The usefulness of this framework is demonstrated in two very different contexts: numerical analysis and autonomous vehicle routing. We use OSSPs to derive causality conditions for semi-Lagrangian discretizations of anisotropic Hamilton-Jacobi equations. We also use a Dijkstra-like method to solve OSSPs optimizing the timing and urgency of lane change maneuvers for an autonomous vehicle navigating road networks with a heterogeneous traffic load. |
| title | Monotone Causality in Opportunistically Stochastic Shortest Path Problems |
| topic | Optimization and Control 90C39, 90C40, 49L20, 65N22, 49L25 |
| url | https://arxiv.org/abs/2310.14121 |