# GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2024.

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

- [Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning](https://mlsanity.com/paper/2508.20095/) (2025)
- [Diffusion-Informed Probabilistic Contact Search for Multi-Finger Manipulation](https://mlsanity.com/paper/2410.00841/) (2024)
- [A^* for Graphs of Convex Sets](https://mlsanity.com/paper/2407.17413/) (2024)
- [Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning](https://mlsanity.com/paper/2503.00583/) (2025)
- [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)
- [Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2608.21319/) (2026)

## Abstract (arXiv)

We consider large-scale, implicit-search-based solutions to Shortest Path Problems on Graphs of Convex Sets (GCS). We propose GCS*, a forward heuristic search algorithm that generalizes A* search to the GCS setting, where a continuous-valued decision is made at each graph vertex, and constraints across graph edges couple these decisions, influencing costs and feasibility. Such mixed discrete-continuous planning is needed in many domains, including motion planning around obstacles and planning through contact. This setting provides a unique challenge for best-first search algorithms: the cost and feasibility of a path depend on continuous-valued points chosen along the entire path. We show that by pruning paths that are cost-dominated over their entire terminal vertex, GCS* can search efficiently while still guaranteeing cost-optimality and completeness. To find satisficing solutions quickly, we also present a complete but suboptimal variation, pruning instead reachability-dominated paths. We implement these checks using polyhedral-containment or sampling-based methods. The former implementation is complete and cost-optimal, while the latter is probabilistically complete and asymptotically cost-optimal and performs effectively even with minimal samples in practice. We demonstrate GCS* on planar pushing tasks where the combinatorial explosion of contact modes renders prior methods intractable and show it performs favorably compared to the state-of-the-art. Project website: https://shaoyuan.cc/research/gcs-star/