Shortest Paths in Graphs of Convex Sets

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.

Cited by in corpus (10)

• Toward Globally Optimal State Estimation Using Automatically Tightened Semidefinite Relaxations
• A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
• Towards Optimizing a Convex Cover of Collision-Free Space for Trajectory Generation
• PAAMP: Polytopic Action-Set And Motion Planning for Long Horizon Dynamic Motion Planning via Mixed Integer Linear Programming
• Constant-time Motion Planning with Anytime Refinement for Manipulation
• Sharp Hybrid Zonotopes: Set Operations and the Reformulation-linearization Technique
• Toward Generalist Neural Motion Planners for Robotic Manipulators: Challenges and Opportunities
• A MILP-Based Solution to Multi-Agent Motion Planning and Collision Avoidance in Constrained Environments
• Trusted Polytopic Action Sets for Fast Planning in Underactuated Systems
• Generalized Parametric Path Problems