Steiner-TSP on GCS

Unified Search for Steiner-TSP on Graphs of Convex Sets

Abstract

We formalize the Steiner Traveling Salesman Problem on Graphs of Convex Sets, which seeks a minimum-cost closed trajectory through required convex sets while allowing optional transit vertices and revisits. To explore the resulting infinite solution space, we propose a unified branch-and-bound search over rooted walk prefixes. Additive lower-bound-graph costs bound committed prefixes, while a cut-separated connected-flow relaxation lower-bounds the residual cost of visiting every remaining target and returning to the root. Under a uniform positive-cost assumption, best-first traversal terminates after finitely many expansions on every feasible instance without an initial incumbent, whereas depth-first traversal does so once a finite incumbent is available. For a user-specified factor ε ≥ 1, a global lower bound certifies that either strategy's incumbent cost is at most ε times the global optimum. We further demonstrate joint sensing-mode, visitation-order, and continuous-trajectory selection for a mobile-manipulator inspection task, including action precedences expressed in linear temporal logic over finite traces. Both traversal strategies find feasible solutions on all benchmark instances within 30s with mean certified optimality gaps of 28.1% and 29.7%, respectively, whereas two recent baselines succeed on only about half of the instances.

Steiner Traveling Salesman Problem (TSP) on Graphs of Convex Sets (GCS)

A GCS [1] is a directed graph whose vertices are convex regions of continuous states and whose edges encode allowed transitions. Steiner-TSP [2] on a GCS jointly chooses a closed graph walk and its continuous realization: it starts and ends at the red root r, visits every yellow target at least once, and may use green transit sets or revisit vertices to minimize cost. Black arrows show allowed directed transitions, colored circles and segments show the selected states and trajectory, and circled numbers give the traversal order. Panel (a) collapses the GCS to a discrete graph by fixing the continuous state in each visited set to its representative center and disallowing revisits, producing a feasible but suboptimal solution. Panel (b) jointly optimizes the graph walk and the continuous state selected at every visit, permits revisits, and obtains the globally optimal solution.

Unified Branch-and-Bound Search

Our unified branch-and-bound search lazily explores the generally infinite intrinsic tree of rooted GCS walk [3] prefixes. Each child appends one admissible transition, and a prefix becomes a discrete solution node only after it covers every target and returns to the root. A precomputed triplet-based lower-bound graph (LBG) [4] provides an additive cost-to-come lower bound for the committed prefix, while a connected-flow linear program on the same LBG provides a cost-to-go heuristic for visiting the remaining targets and closing the walk. Their sum orders the Frontier and prunes prefixes that cannot improve the incumbent. Each solution node is then optimized by full GCS convex restriction and may update the incumbent, while the smallest combined lower bound on the Frontier determines the certified gap. Best-First (BF) traversal expands the live prefix with the smallest bound; Depth-First (DF) traversal follows a last-in-first-out stack, with siblings locally ordered by the same bound. The following two animations visualizes BF and DF over 100 expansions, where gray polygons are GCS sets, blue opacity counts visits in the current prefix, solid red triplets encode the cost-to-come lower bound, dashed yellow triplets show positive cost-to-go LP flow, and thick solid yellow indictate the optimized trajectory for each solution node.

BF traversal expands the live prefix with the smallest combined lower bound (2 solution nodes in total).

DF traversal follows a last-in-first-out branch, with siblings locally ordered by the combined lower bound (29 solution nodes in total).

Performance Comparison

We compare Ours (BF) and Ours (DF) with two best-first ablations and two existing solvers under a 30 s budget. Alt-G solves a convex restriction at every generated prefix, slowing its search, whereas Alt-H uses a cheaper but looser minimum-spanning-tree completion bound and therefore explores many more prefixes. GHOST [5] hierarchically searches target tours and their realizing GCS walks, while MICP [1] jointly optimizes the discrete walk and continuous trajectory in a mixed-integer convex program.

rand domain instance (31 target red polygons; 30s runtime budget)

rand_seed10_size40_ours_bf.mp4

Ours (BF) [cost: 22.5]

rand_seed10_size40_ours_df.mp4

Ours (DF) [cost: 23.4]

rand_seed10_size40_micp.mp4

MICP [cost: 33.0]

rand_seed10_size40_alt_g.mp4

Alt-G [cost: 35.4]

rand_seed10_size40_alt_h.mp4

Alt-H [cost: 35.4]

rand_seed10_size40_ghost.mp4

GHOST [cost: 25.9]

maze domain instance (10 target red cuboids; 30s runtime budget)

maze_seed7_size10_ours_bf.mp4

Ours (BF) [cost: 131.8]

maze_seed7_size10_ours_df.mp4

Ours (DF) [cost: 131.8]

maze_seed7_size10_micp.mp4

MICP [cost: 154.0]

maze_seed7_size10_alt_g.mp4

Alt-G [cost: 135.9]

maze_seed7_size10_alt_h.mp4

Alt-H [cost: 135.9]

maze_seed7_size10_ghost.mp4

GHOST [cost: 131.8]

iiwa domain instance (9 target red configurations; 30s runtime budget)

iiwa_seed10_size9_ours_bf.mp4

Ours (BF) [cost: 15.3]

iiwa_seed10_size9_ours_df.mp4

Ours (DF) [cost: 15.6]

MICP [timeout]

iiwa_seed10_size9_alt_g.mp4

Alt-G [cost: 20.0]

iiwa_seed10_size9_alt_h.mp4

Alt-H [cost: 15.3]

iiwa_seed10_size9_ghost.mp4

GHOST [cost: 15.6]

Demonstration of Mobile Manipulator Inspection

All three demonstrations share the same task: a mobile manipulator with a 7-DoF arm, wrist-mounted camera, and 3-DoF holonomic base leaves the charging dock, acquires one valid image for each of eight inspection tasks (A–H), and returns to the dock. With one or more feasible sensing modes per task, a solution must select the modes, visitation order, and collision-free trajectory.

A PRM[6]-based generalized-TSP[7] baseline finds a 133.1s solution in 31.6s runtime, without an optimality guarantee:

fig3a_ompl_prm_gtsp.mp4

Ours (BF) finds a 78.4s solution with a 5.64% gap in 1.72s runtime:

fig3b_ours_bf.mp4

Ours (BF) finds an 82.3s solution with a 10.12% gap in 1.3s runtime, under LTLf[8] action precedence of {A,B}≺{E,F}≺D≺{G,H}≺C:

fig3c_ours_bf_ltlf.mp4

References

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

[2] Rodríguez-Pereira, Jessica, et al. "The Steiner traveling salesman problem and its extensions." European Journal of Operational Research 278.2 (2019): 615-628.

[3] Morozov, Savva, et al. "Mixed discrete and continuous planning using shortest walks in graphs of convex sets." arXiv preprint arXiv:2507.10878 (2025).

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

[5] Tang, Jingtao, and Hang Ma. "GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 40. No. 43. 2026.

[6] Kavraki, Lydia E., et al. "Probabilistic roadmaps for path planning in high-dimensional configuration spaces." IEEE transactions on Robotics and Automation 12.4 (1996): 566-580.

[7] Saha, Mitul, et al. "Planning tours of robotic arms among partitioned goals." The International Journal of Robotics Research 25.3 (2006): 207-223.

[8] G. De Giacomo and M. Y. Vardi, “Linear temporal logic and linear dynamic logic on finite traces,” in Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, 2013, pp. 854–860

Page updated

Google Sites

Report abuse