Shortest Paths in Graphs of Convex Sets

Abstract

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