GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets

AI summary

Overview

Research area: Robotics motion planning / combinatorial optimization, sitting at the intersection of trajectory optimization, convex optimization over Graphs of Convex Sets (GCS), and the Traveling Salesman Problem (TSP).

Technical level: Advanced. The paper assumes familiarity with mixed-integer programming, convex optimization, admissible heuristics, and best-first search, and it presents formal definitions, theorems, and integer linear program formulations.

Scope (one sentence): The paper formulates GCS-TSP—a TSP variant where edge costs depend on a continuous trajectory passing through convex regions—and introduces GHOST, a two-level hierarchical search framework that solves it optimally, plus a bounded-suboptimal variant for time-critical use.

What This Paper Is About

In a Graph of Convex Sets (GCS), a robot's configuration space is split into convex regions connected by a sparse graph, which lets planners turn hard nonconvex motion problems into tractable convex ones. Tasks like coverage, inspection, and structured exploration require visiting many of those regions in a good order—a TSP-like problem. But in a GCS, the cost of moving between regions is not a fixed number: it depends on exactly which points the trajectory enters and leaves each convex set, so classical TSP algorithms that assume fixed edge weights do not apply directly. The authors' goal is to compute, for a given GCS, a tour visiting every convex set at least once together with the continuous trajectory realizing that tour, at minimum total trajectory cost.

Key Contributions

1. Formalization of GCS-TSP. The authors define the problem over a directed graph G = (V, E) where each vertex is a non-empty compact convex set, each edge permits transitions, and the objective minimizes a summed convex cost over the trajectory visiting every vertex at least once, starting and ending at the same point.

2. The abstract-path-unfolding algorithm. GHOST introduces a general algorithm (Alg. 1) that computes admissible lower bounds for any sequence of convex sets—even when consecutive sets are not directly connected in the GCS—by unfolding abstract paths into feasible GCS paths. This generalizes earlier lower-bound results (Theorem 3 in Natarajan et al. 2024) from open paths to paths unfolded from abstract paths (Theorem 1) and to abstract tours (Theorem 3).

3. The GHOST framework. A hierarchical best-first search combining a high-level Lawler-Murty-style tour search over the induced complete graph Ĝ, an RTSP integer linear program formulated over triplets rather than edges, and a low-level path unfolding plus convex trajectory optimization.

4. Optimality proof and a bounded-suboptimal variant. The paper proves ε-GHOST returns a solution with cost at most 1/(1−ε) times optimal (Theorem 4), with ε = 0 recovering optimal GHOST (Corollary 5).

Main Findings

• Optimality guarantee: GHOST returns an optimal GCS-TSP solution (Corollary 5), following from Theorem 4 with ε = 0.0.
• Bounded-suboptimal trade-off: For ε ∈ [0, 1), ε-GHOST produces a solution with cost at most 1/(1−ε) times the optimal cost (Theorem 4), by relaxing the termination condition to c(n*.τ) − n.c̄ ≤ ε · c(n*.τ), pruning Alg. 1 with cost (1−ε) · c(n*.τ), and relaxing the EvalNode pruning condition to ℒ(π) ≥ (1−ε) · c(n.τ).
• Speed against the baseline: The abstract states GHOST is "orders-of-magnitude faster than unified mixed-integer convex programming baseline" in simple cases. No specific timing numbers, dataset sizes, or benchmark names are reported in the provided content.
• Problems beyond the baseline's reach: The abstract states GHOST "uniquely handles" complex problems involving high-order continuity constraints and incomplete GCSs, which the baseline cannot.
• Lower-bound metric validity: The LBG triplet cost lb_p never overestimates the true cost segment c(x_u, x_v) + c(x_v, x_w) for any trajectory using that triplet, and the cumulative bound satisfies ℒ(π*) ≤ ℒ(π) ≤ c(τ) for any trajectory τ conditioned on a path π unfolded from an abstract path (Theorem 1).
• LBG as a generalization of prior work: The LBG has previously been used by Natarajan et al. (2024) to obtain an admissible heuristic for accelerating A*-like search in GCSs; GHOST generalizes this to multi-label search over abstract paths.
• Cyclic-path caveat: Because the implementation restricts path unfolding to simple subpaths between tour endpoints, the (bounded-sub)optimality guarantee is limited to trajectories in that class, where each vertex is visited at most |V| times.

Methodology in Plain English

The approach separates the problem into two coupled searches.

Step 1 — Build a cheap estimate of travel cost. Instead of attaching a single cost to each GCS edge (which would be loose, because the cost depends on unknown entry and exit points), the authors build a "lower-bound graph" over triplets: a vertex v together with its predecessor u and successor w. Each triplet gets a cost computed by a relaxed convex program that ignores the constraints on the entry and exit points, so it always underestimates the true cost of any real trajectory using that triplet. This is the key trick that gives tight-enough estimates to prune aggressively.

Step 2 — Search tours from cheapest estimate upward. The high level runs a Lawler-Murty-style best-first search. Each search node is a Restricted-TSP instance with some edges forced to be included (Ê⁺) and others forced to be excluded (Ê⁻). The RTSP is solved as an integer linear program with binary variables over triplets rather than edges, visit-once constraints, flow conservation, inclusion/exclusion constraints, and DFJ-style subtour elimination constraints added iteratively. Solving a node yields an abstract tour and a lower bound on its cost. Nodes are popped in order of that lower bound.

Step 3 — Unfold each tour into a realizable path, cheapest-first. For a given abstract tour, its consecutive vertices may not be directly adjacent in the GCS, so a path must be "unfolded" through intermediate vertices. The authors run a multi-label A*-like best-first search (Alg. 1) that enumerates feasible unfolded paths in non-decreasing order of their lower-bound cost, using an admissible multi-label heuristic that sums the minimal lower-bound subpath costs for the remaining segments.

Step 4 — Solve the actual trajectory. For each unfolded path, a convex program (following the "GCS convex restriction" idea of Marcucci et al. 2023) computes the optimal trajectory. The authors extend this formulation to allow visiting vertices and edges multiple times, which matters when the GCS is incomplete. Trajectories are cached because the same path can be unfolded from different abstract tours.

Step 5 — Prune and terminate. Once a real trajectory cost is known, any tour or path whose lower bound is no smaller can be discarded. If the best remaining node's lower bound is no worse than the current best trajectory cost, the search terminates with the optimal answer. For the ε variant, the termination and pruning thresholds are relaxed proportionally, giving the 1/(1−ε) guarantee.

Why This Matters

Impact on research: The paper connects GCS shortest-path planning—a mature line of work (e.g., Marcucci et al. 2023, Marcucci et al. 2024b, Natarajan et al. 2024)—with combinatorial tour optimization. It shows that the triplet-based lower-bound decomposition is general enough to serve as a common currency for both tour ordering and path unfolding, and it generalizes prior lower-bound theorems from open paths to arbitrary unfolded paths and closed tours. It also addresses settings the earlier MICP formulation of GCS-TSP (Marcucci 2024) could not scale to, and that the two-level moving-target approach of Bhat et al. (2025) handled only under problem-specific time-window assumptions, small branching factors, and piecewise-linear motion.

Real-world applications (as named in the paper):

• Area coverage and inspection planning—visiting multiple regions in a cost-effective order while respecting kinodynamic constraints, in contrast to grid-based coverage methods (Gabriely and Rimon 2001; Tang et al. 2025a) that often restrict robots to disk-shaped sweeps.
• Structured exploration and constrained multi-target visitation—trips that must reach a set of regions in sequence under trajectory constraints.
• Task and motion planning—coupling discrete task ordering with continuous feasible motion.
• Non-Euclidean motion planning, quadrotor navigation, and multi-robot planning—application areas cited from prior GCS work (Cohn et al. 2025; Marcucci et al. 2024a; Tang et al. 2025b) where a tour over convex sets arises naturally.

Industry relevance: Inspection and coverage routing is central to infrastructure monitoring, autonomous inspection of industrial sites, warehouse and agricultural robotics, and drones executing multi-waypoint missions. A solver that returns provably optimal tours under real kinodynamic constraints, with a tunable speed-optimality dial for time-critical operation, is directly usable where a full mixed-integer convex program is too slow.

Future Directions

• Extending optimality to cyclic paths. The current implementation restricts unfolding to simple subpaths, which caps the guarantee to that path class. Lifting this restriction would extend optimality to trajectories where a vertex may be visited more than |V| times.
• Scaling the RTSP subroutine. The high-level search depends on repeatedly solving an ILP over triplets, so improvements to that subroutine or to the LBG construction would directly affect overall runtime.
• Characterizing where ε-GHOST is worth it. The paper provides the 1/(1−ε) bound but does not report, in the provided content, how solution quality and runtime vary with ε across problem classes—an obvious empirical question.
• Broader problem variants. The paper notes the formulation extends to a fixed starting set and point, and prior work extended GCS-TSP to moving targets (Philip et al. 2024). Combining GHOST with moving targets, multi-robot settings, or richer constraint classes such as the Watchman Route Problem is a natural next step.

Target Audience

Robotics researchers and graduate students working on motion planning, trajectory optimization, and task-and-motion planning will get the most from this paper, particularly those already familiar with the GCS framework (Marcucci et al. 2023) and GCS shortest-path planners. It is also relevant to operations researchers interested in TSP variants with dynamic, trajectory-dependent edge costs and to practitioners building inspection, coverage, or multi-waypoint routing systems who need optimality guarantees under kinodynamic constraints. Readers without a background in convex optimization and mixed-integer programming will find the methodology sections demanding.

Authors’ abstract

We study GCS-TSP, a new variant of the Traveling Salesman Problem (TSP) defined over a Graph of Convex Sets (GCS) -- a powerful representation for trajectory planning that decomposes the configuration space into convex regions connected by a sparse graph. In this setting, edge costs are not fixed but depend on the specific trajectory selected through each convex region, making classical TSP methods inapplicable. We introduce GHOST, a hierarchical framework that optimally solves the GCS-TSP by combining combinatorial tour search with convex trajectory optimization. GHOST systematically explores tours on a complete graph induced by the GCS, using a novel abstract-path-unfolding algorithm to compute admissible lower bounds that guide best-first search at both the high level (over tours) and the low level (over feasible GCS paths realizing the tour). These bounds provide strong pruning power, enabling efficient search while avoiding unnecessary convex optimization calls. We prove that GHOST guarantees optimality and present a bounded-suboptimal variant for time-critical scenarios. Experiments show that GHOST is orders-of-magnitude faster than unified mixed-integer convex programming baselines for simple cases and uniquely handles complex trajectory planning problems involving high-order continuity constraints and an incomplete GCS.