# A^* for Graphs of Convex Sets

arXiv: https://arxiv.org/abs/2407.17413 · HTML: https://mlsanity.com/paper/2407.17413/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 13 references that are in the map.
- First posted on arXiv 24 Jul 2024.

## Builds on (most cited first, 6 of 6)

- [Motion Planning around Obstacles with Convex Optimization](https://mlsanity.com/paper/2205.04422/) (2022)
- [Shortest Paths in Graphs of Convex Sets](https://mlsanity.com/paper/2101.11565/) (2021)
- [GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets](https://mlsanity.com/paper/2407.08848/) (2024)
- [Fast Path Planning Through Large Collections of Safe Boxes](https://mlsanity.com/paper/2305.01072/) (2023)
- [Approximation algorithms for TSP with neighborhoods in the plane](https://mlsanity.com/paper/1703.01640/) (2017)
- [Mobile Robot Sensory Coverage in 2-D Environments: An Optimization Approach with Efficiency Bounds](https://mlsanity.com/paper/2405.15100/) (2024)

## Built on by (most cited first, 2 of 2)

- [GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2511.06471/) (2025)
- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)

## Abstract (arXiv)

We present a novel algorithm that fuses the existing convex-programming based approach with heuristic information to find optimality guarantees and near-optimal paths for the Shortest Path Problem in the Graph of Convex Sets (SPP-GCS). Our method, inspired by A^*, initiates a best-first-like procedure from a designated subset of vertices and iteratively expands it until further growth is neither possible nor beneficial. Traditionally, obtaining solutions with bounds for an optimization problem involves solving a relaxation, modifying the relaxed solution to a feasible one, and then comparing the two solutions to establish bounds. However, for SPP-GCS, we demonstrate that reversing this process can be more advantageous, especially with Euclidean travel costs. In other words, we initially employ A^* to find a feasible solution for SPP-GCS, then solve a convex relaxation restricted to the vertices explored by A^* to obtain a relaxed solution, and finally, compare the solutions to derive bounds. We present numerical results to highlight the advantages of our algorithm over the existing approach in terms of the sizes of the convex programs solved and computation time.