EUVIMEDEUVIMED entdecken
Crossref

Shortest Paths in Graphs of Convex Sets

Tobia Marcucci, Jack Umenberger, Pablo Parrilo, Russ Tedrake

SIAM Journal on Optimization · 31.03.2024 · 34 (1) · 507-532

DOI: 10.1137/22m1523790 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 01.02.2024. Verfasst von Tobia Marcucci und 3 weiteren Autor:innen. Die Arbeit wurde bisher 80-mal zitiert (Crossref) und nennt 51 Literaturangaben. Gefördert von: Office of Naval Research, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a variant of this classical problem in which the position of each vertex in the graph is a continuous decision variable constrained in a convex set, and the length of an edge is a convex function of the position of its endpoints. Problems of this form arise naturally in many areas, from motion planning of autonomous vehicles to optimal control of hybrid systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong and lightweight mixed-integer convex formulation based on perspective operators, that makes it possible to efficiently find globally optimal paths in large graphs and in high-dimensional spaces.

Förderung

  • Office of Naval Research
  • National Science Foundation

Zitieren

APA

Marcucci, T., Umenberger, J., Parrilo, P., & Tedrake, R. (2024). Shortest Paths in Graphs of Convex Sets. SIAM Journal on Optimization, 34(1), 507-532. https://doi.org/10.1137/22m1523790

Vancouver

Marcucci T, Umenberger J, Parrilo P, Tedrake R. Shortest Paths in Graphs of Convex Sets. SIAM Journal on Optimization. 2024;34(1):507-532. doi:10.1137/22m1523790

BibTeX
@article{Marcucci2024,
  author = {Marcucci, Tobia and Umenberger, Jack and Parrilo, Pablo and Tedrake, Russ},
  title = {Shortest Paths in Graphs of Convex Sets},
  journal = {SIAM Journal on Optimization},
  year = {2024},
  volume = {34},
  number = {1},
  pages = {507--532},
  doi = {10.1137/22m1523790}
}
Kostenlos starten →