Skip to content

Shortest Paths in Graphs of Convex Sets

Authors: Tobia Marcucci, Jack Umenberger, Pablo A. Parrilo, Russ Tedrake

Published: 2021 (Journal Paper)

Source: SIAM Journal on Optimization

Algorithm: SPP-GCS

arXiv: 2101.11565

DOI: 10.1137/22M1523790

Summary

Each graph vertex is associated with a convex set and edge lengths are convex functions of the endpoints' positions. The key contribution is a strong mixed-integer convex program (MICP) formulation based on perspective operators that yields a tight relaxation, enabling globally optimal paths in large graphs and high-dimensional spaces. Forms the theoretical foundation for GCS-based motion planning.

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.

Primary

Paper arxiv.org

Standard

arXiv Abstract 2101.11565 arXiv PDF 2101.11565 arXiv HTML 2101.11565 DOI 10.1137/22M1523790

Alternate

epubs.siam.org epubs.siam.org GitHub: TobiaMarcucci/shortest-paths-in-graphs-of-convex-sets github.com

Tags

  • Graphs of convex sets

  • GCS

  • Graph search

  • Convex

  • Convex set

  • Convex optimization

  • Mixed-integer programming

  • Motion planning

  • Optimal control

  • Trajectory optimization