Pruning the Augmented Graphs of Convex Sets for Scalable Joint Task and Motion Planning

Abstract

We present top-down and bottom-up approaches for solving large-scale instances of joint task and motion planning problems in Graphs of Convex Sets (GCS). Planning what tasks to perform and how to move between them can be encoded exactly as a Shortest Path Problem (SPP) using an Augmented GCS (AGCS), but this graph grows exponentially with the number of tasks, limiting prior work to only 11 tasks. Both of our approaches significantly improve scalability by carefully pruning the AGCS before it is constructed. The top-down approach replaces the complete graph with a sparse Delaunay graph that maintains a natural nearest-neighbor connectivity, reducing the number of vertices, edges, and subgraphs relative to the full AGCS. The bottom-up approach uses classical Traveling Salesman Problem (TSP) heuristics to create an initial ordering, then expands it within a fixed search window, pruning the AGCS to a bounded maximum width independent of the problem size. Both approaches can obtain optimal or near-optimal solutions in a fraction of the time required by the original AGCS. The bottom-up approach can solve instances with 1000 tasks in about two minutes. We additionally discuss lower bounds based on minimum 1-trees to quantify suboptimality of the proposed approaches.

arXiv commentv2: This version is a complete rewrite of v1, while still addressing the same problem statement from v1. The heuristic has been improved compared to the one in v1. A title change was needed to better reflect the contents of the paper