Shortest Paths in Graphs of Convex Sets Article Swipe
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1137/22m1523790
Given a graph, the shortest-path problem requires finding a sequence of edges\nwith minimum cumulative length that connects a source vertex to a target\nvertex. We consider a variant of this classical problem in which the position\nof each vertex in the graph is a continuous decision variable constrained in a\nconvex set, and the length of an edge is a convex function of the position of\nits endpoints. Problems of this form arise naturally in many areas, from motion\nplanning of autonomous vehicles to optimal control of hybrid systems. The price\nfor such a wide applicability is the complexity of this problem, which is\neasily seen to be NP-hard. Our main contribution is a strong and lightweight\nmixed-integer convex formulation based on perspective operators, that makes it\npossible to efficiently find globally optimal paths in large graphs and in\nhigh-dimensional spaces.\n
Related Topics To Compare & Contrast
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1137/22m1523790
- OA Status
- green
- Cited By
- 44
- References
- 105
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3123076862