# Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2023.

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

- [Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning](https://mlsanity.com/paper/2508.20095/) (2025)
- [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)
- [VisDiff: SDF-Guided Polygon Generation for Visibility Reconstruction and Recognition](https://mlsanity.com/paper/2410.05530/) (2024)

## Abstract (arXiv)

Many computations in robotics can be dramatically accelerated if the robot configuration space is described as a collection of simple sets. For example, recently developed motion planners rely on a convex decomposition of the free space to design collision-free trajectories using fast convex optimization. In this work, we present an efficient method for approximately covering complex configuration spaces with a small number of polytopes. The approach constructs a visibility graph using sampling and generates a clique cover of this graph to find clusters of samples that have mutual line of sight. These clusters are then inflated into large, full-dimensional, polytopes. We evaluate our method on a variety of robotic systems and show that it consistently covers larger portions of free configuration space, with fewer polytopes, and in a fraction of the time compared to previous methods.