Shortest Paths in Graphs of Convex Sets
Authors:
- Tobia MarcucciTMTobia Marcucci
- Jack UmenbergerJUJack Umenberger
- Pablo A. ParriloPPPablo A. Parrilo
- Russ TedrakeRTRuss Tedrake
Preprint
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
This publication has 26 references indexed in Scilit:
- The Bipartite Boolean Quadric PolytopeDiscrete Optimization, 2022
- New SOCP relaxation and branching rule for bipartite bilinear programsOptimization and Engineering, 2018
- Minimum Spanning Trees with neighborhoods: Mathematical programming formulations and solution methodsEuropean Journal of Operational Research, 2017
- Integer programming formulations for the elementary shortest path problemEuropean Journal of Operational Research, 2016
- Relaxations and discretizations for the pooling problemJournal of Global Optimization, 2016
- The bipartite unconstrained 0–1 quadratic programming problem: Polynomially solvable casesDiscrete Applied Mathematics, 2015
- Perspective cuts for a class of convex 0–1 mixed integer programsMathematical Programming, 2005
- Semidefinite programming relaxations for semialgebraic problemsMathematical Programming, 2003
- The shortest path with at most / nodes in each of the series/parallel clustersNetworks, 1995
- Approximation algorithms for the geometric covering salesman problemDiscrete Applied Mathematics, 1994