GHOST

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

Jingtao Tang, Hang Ma

Simon Fraser University

* AAAI 2026 (To Appear)

An optimal hierarchical framework for the Traveling Salesman Problem on Graphs of Convex Sets

Paper

Code

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.

Traveling Salesman Problem on a Graph of Convex Sets (GCS-TSP)

TSP Instance & Solution [image source]

The TSP seeks the shortest Hamiltonian cycle on a weighted graph, given pairwise distances between vertices. When the input graph is incomplete and may not admit a Hamiltonian cycle, the problem is typically solved on its metric closure [1] --- a complete graph with edges weighted by shortest-path distances in the original graph.

GCS-TSP Instances & Solutions

The input to GCS-TSP [2] is a GCS whose vertices represent convex subsets of configuration space and whose edges represent feasible transitions. The goal is to compute both a tour that visits each convex set at least once and a continuous trajectory that sequentially visits points in each set, subject to trajectory constraints. In the figure above, "Point", "Linear", and "Bézier" correspond to 1, 2, and 3 points in each set of GCS, respectively. "Point"-GCS is unconstrained, while "Linear" and "Bézier"-GCSs are edge-constrained for trajectory continuity.

GHOST for Mixed Discrete-Continuous Optimization of GCS-TSP

GCS-TSP (and other graph optimization problems on GCSs) tightly couple combinatorial, discrete tour optimization with optimization of continuous states constrained by convex sets. It is natural to decouple the two optimizations of discrete tour (or more generally, "subgraph") variables and continuous state variables [3,4,5,6,7]. Following this principle, we introduce a greedy baseline and a basic GHOST version without any pruning power.

A Greedy

Baseline

We propose GHOST, which employs a two-level hierarchical search: At the high level, it systematically explores TSP tours on the complete graph induced by the input GCS, ordered by lower bounds on their trajectory costs; At the low level, it searches for feasible GCS paths that realize each tour and computes the optimal trajectory for each path via convex optimization.

Simulations

We demonstrate several applications by solving GCS-TSP via GHOST in the following:

ghost.mp4

Coverage Planning: Gray polygons are convex sets that needs to be visited at least once.

maze.mp4

Inspection Planning: Each inspection spot (square) needs to be visited at least once. The inspection spots come from a selected subset of the precomputed convex regions (not visualized).

iiwa.mp4

Task and Motion Planning: A 7-DoF manipulator (KUKA LBR iiwa) reaching 8 convex sets without precedence, each corresponding to an independent task pose.

References

[1] Cornuéjols, Gérard, Jean Fonlupt, and Denis Naddef. "The traveling salesman problem on a graph and some related integer polyhedra." Mathematical programming 33.1 (1985): 1-27.

[2] Marcucci, Tobia. Graphs of convex sets with applications to optimal control and motion planning. Diss. Massachusetts Institute of Technology, 2024.

[3] Chia, Shao Yuan Chew, et al. "GCS*: Forward heuristic search on implicit graphs of convex sets." arXiv preprint arXiv:2407.08848 (2024).

[4] Natarajan, Ramkumar, et al. "Implicit graph search for planning on graphs of convex sets." arXiv preprint arXiv:2410.08909 (2024).

[5] Sundar, Kaarthik, and Sivakumar Rathinam. "A* for Bounding Shortest Paths in the Graphs of Convex Sets." Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 35. No. 1. 2025.

[6] Philip, Allen George, et al. "A mixed-integer conic program for the moving-target traveling salesman problem based on a graph of convex sets." 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2024.

[7] Bhat, Anoop, et al. "A Complete and Bounded-Suboptimal Algorithm for a Moving Target Traveling Salesman Problem with Obstacles in 3D." arXiv preprint arXiv:2504.14680 (2025).

[8] Murty, Katta G. "An algorithm for ranking all the assignments in order of increasing cost." Operations research 16.3 (1968): 682-687.

[9] Lawler, Eugene L. "A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem." Management science 18.7 (1972): 401-405.

Page updated

Google Sites

Report abuse