Shortest Paths in Graphs of Convex Sets
- 1 February 2024
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (1) , 507-532
Abstract
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.Keywords
All Related Versions
Funding Information
- Office of Naval Research (N00014-18-1-2210, N00014-17-1-2699)
- National Science Foundation (EFMA-1830901)
This publication has 45 references indexed in Scilit:
- The travelling salesman problem with neighbourhoods: MINLP solutionOptimization Methods and Software, 2013
- Perspective reformulations of mixed integer nonlinear programs with indicator variablesMathematical Programming, 2010
- Perspective cuts for a class of convex 0–1 mixed integer programsMathematical Programming, 2005
- Semidefinite programming relaxations for semialgebraic problemsMathematical Programming, 2003
- Equivalence of hybrid dynamical modelsAutomatica, 2001
- Convex programming for disjunctive convex optimizationMathematical Programming, 1999
- A branch-and-cut method for 0-1 mixed convex programmingMathematical Programming, 1999
- Control of systems integrating logic, dynamics, and constraintsAutomatica, 1999
- The shortest path with at most / nodes in each of the series/parallel clustersNetworks, 1995
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979