PaperlayerView exact revision on arXiv

Source-linked AI summary

Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

Jingtao Tang, Hang Ma

arXiv:2608.21319v1cs.AIcs.RO

TL;DR

Steiner-TSP on GCS must find a minimum-cost closed trajectory through required convex sets while selecting walks, visitation order, and continuous trajectories in an infinite space with revisits. The paper proposes unified branch-and-bound over rooted walk prefixes with additive prefix and connected-flow residual lower bounds. Both traversal variants found feasible solutions on all 180 benchmark instances within 30 s, while also supporting mobile-manipulator inspection with LTL_f precedences.

  • Problem

    Steiner-TSP on GCS couples discrete walk selection with continuous trajectory optimization while required targets, transit vertices, revisits, visitation order, and return walks must be handled.

  • Method

    The paper searches rooted walk prefixes using additive committed-prefix bounds and a cut-separated connected-flow relaxation for remaining targets and return-to-root cost.

  • Results

    Both proposed variants find incumbents on all 180 benchmark instances, compared with 99 for GHOST and 98 for MICP.

  • Takeaways & Limitations

    The unified search supports joint sensing-mode, visitation-order, continuous-trajectory, and LTL_f precedence selection in a mobile-manipulator inspection task.

Abstract

from arXiv · show

We formalize the Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS), 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 $ε\geq1$, 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 (LTL$_f$). 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

I. INTRODUCTION

The paper formalizes Steiner-TSP on GCS as joint discrete walk and continuous trajectory planning over required targets, optional transit vertices, and possible revisits. It motivates unified branch-and-bound search that avoids optimizing every prefix while retaining lower bounds for committed and residual costs.

  • Problem formulation: Joint route selection and continuous trajectory optimization is NP-hard, although trajectory optimization is convex when the route is fixed.GCS represents discrete graph choices and associated continuous trajectories with convex costs and constraints.
  • Problem formulation: Steiner-TSP on GCS requires a minimum-cost closed trajectory visiting every required vertex while allowing transit vertices and revisits.A feasible solution is a closed trajectory conditioned on a closed walk that visits every target at least once.
  • Problem formulation: Compared with shortest-path planning, the problem additionally selects target visitation order, inter-target walks, and the return walk to the root.The required-subset semantics leave non-target vertices available for transit.
  • Search motivation: Graph search must balance expensive continuous optimization of prefixes against the need to bound committed-prefix and remaining-target costs.The paper identifies when to perform continuous trajectory optimization as a central design question.
  • Proposed approach: The proposed search combines additive committed-prefix bounds with a connected-flow relaxation for remaining targets, reserving full trajectory optimization for complete closed walks.Under uniformly positive vertex costs, best-first terminates finitely on feasible instances without an incumbent, while depth-first does so after a finite incumbent exists.

III. UNIFIED BRANCH-AND-BOUND SEARCH

The method represents the infinite solution space as a finitely branching tree of rooted walk prefixes. A single frontier stores prefixes together with cost-to-come and admissible cost-to-go bounds for unified exploration and pruning.

  • Search-space representation: The discrete search space contains every finite rooted GCS walk, including cycles and vertex revisits, and is represented as a finitely branching prefix tree.Vertices may repeat, so the family of walks is generally infinite even though each node has finitely many successors.
  • Search-space representation: Each search node is a full prefix identity, because prefixes ending at the same vertex can impose different boundary conditions and conditioned trajectories.A node is a solution node when it has visited all targets and ends at the root, although its convex restriction may still be infeasible.
  • Frontier management: The algorithm lazily materializes the tree through one frontier of live search nodes selected by a traversal strategy.Every node stores a cost-to-come lower bound and a cost-to-go heuristic.
  • Frontier management: The node lower bound combines cost-to-come and admissible cost-to-go estimates to support frontier ordering and pruning.The heuristic is admissible when it does not exceed the remaining cost of any feasible solution extending the prefix.

B. Search Procedure

The search incrementally extends rooted prefixes, evaluates complete target-covering returns through convex restriction, and prunes using a combined lower bound. Best-first and depth-first differ only in frontier selection, while shared bounds provide termination and approximation guarantees.

  • Bounds and traversal: Each child receives an incremental lower-bound cost, and the uniform positive-cost assumption ensures every extension increases cost-to-come by at least η.This positive increment is central to bounding explored prefix depth.
  • Bounds and traversal: Best-first orders the frontier by f(n), whereas depth-first uses a stack with siblings locally ordered by the same bound.Both strategies prune nodes with f(n) ≥ c and can stop when c ≤ ϵ min_n∈Frontier f(n).
  • Search procedure: The procedure evaluates an unpruned solution node by convex restriction and inserts only children whose cost-to-come and node bounds improve the incumbent.An optional incumbent can be initialized from a nearest-neighbor closed walk, but the algorithm can begin without one.
  • Theoretical properties: Best-first traversal terminates after finitely many expansions on every feasible instance, including when initialization provides no finite incumbent.Finite branching and the positive per-extension lower bound limit the number of prefixes below any feasible solution cost.
  • Theoretical properties: Depth-first traversal terminates after finitely many additional expansions once a finite incumbent exists, but pure last-in-first-out search may otherwise starve a live sibling.The finite-depth argument is independent of traversal strategy.
  • Theoretical properties: For any traversal strategy, termination with a finite incumbent c certifies c ≤ ϵc⋆ under the global stopping condition or exhausted frontier.The lower bound applies to every feasible solution, yielding the stated ϵ-optimality guarantee.

IV. LOWER-BOUND GRAPH FOR SEARCH BOUNDS

Efficient search requires lower bounds that remain useful as continuous trajectories evolve along prefixes. The paper contrasts prefix-conditioned convex restrictions and repeated fractional relaxations, both of which require continuous optimization during search.

  • Online bounding: Prefix-conditioned convex restrictions preserve continuous consistency, while repeated fractional GCS relaxations provide an alternative online bounding strategy.Both approaches require continuous optimization during search because future extensions can alter the realized trajectory cost of a prefix.

A. Lower-Bound Graph (LBG) Relaxation

The LBG represents GCS walks as directed sequences of length-two transitions, assigning each transition a local convex-program cost that lower-bounds any compatible trajectory cost. Summing these costs yields a closed-walk lower bound despite independently computed adjacent triplets.

  • LBG construction: Each length-two GCS walk defines a directed LBG triplet between its consecutive GCS edges.The LBG is constructed as L = (E, T), with GCS edges as LBG vertices.
  • Local costs: Each triplet cost is the optimum of a local convex program enforcing feasibility across both neighboring GCS edges.If the local program is infeasible, the triplet cost is set to +∞.
  • Lower-bound property: The induced LBG-walk cost lower-bounds every feasible trajectory conditioned on the same GCS walk.Adjacent triplets need not share consistent GCS variables, which makes the representation a relaxation.
  • Closed walks: For a closed GCS walk, closing the corresponding LBG walk produces the closed-walk lower bound used by the method.This bound is identified as the closed-walk case of a prior theorem.

B. Cost-to-Come Lower Bound

The search assigns each prefix an additive LBG cost-to-come lower bound and combines it with a connected-flow cost-to-go heuristic for remaining targets and closure. These bounds are admissible for every feasible solution extending the prefix.

  • Prefix bound: The cost-to-come bound ˆg(n) is the cost of the fixed LBG walk induced by a search prefix.For the initial prefix, ˆg(n) = 0.
  • Prefix bound: Appending a successor adds its triplet lower-bound cost, with every extension contributing at least η under the uniform positive-cost assumption.This positive increment supplies the progress condition used in the termination proof.
  • Admissibility: For any feasible extension, the cost-to-come bound satisfies ˆg(n) ≤ ˆc(π′) ≤ c(τ).The first inequality follows from nonnegative partial LBG costs, and the second from the LBG lower-bound property.
  • Residual bound: The cost-to-go heuristic h(n) lower-bounds visiting every unvisited target and closing the walk through an online cut-separated connected-flow LP.The LP is solved by row generation with a persistent restricted master and violated connectivity cuts.
  • Residual bound: The flow formulation routes cost-bearing flow from the current source edge to an artificial closure sink while requiring connectivity to every remaining target.When no targets remain, the LP reduces to a minimum-cost source-to-sink flow; infeasibility gives h(n) = +∞.
  • Admissibility: The residual LBG walk of any feasible extension defines an integral flow satisfying the connectivity cuts, proving h(n) is admissible.The proof maps each remaining target to its incoming-edge set and shows every relevant cut is crossed.

V. NUMERICAL RESULTS

The numerical evaluation implements the proposed search and its components in Python and combines Drake and Gurobi for trajectory optimization and cost-to-go bounding.

  • Implementation: The solver is implemented in Python and evaluated on an Apple M4 processor with 16 GB of memory.Drake with Gurobi handles GCS trajectory optimization, while Gurobi also solves the persistent restricted master.
  • Implementation: Directed minimum-cut computations identify violated connectivity rows for the cost-to-go bound.These cuts are added during solution of the persistent restricted master.

A. Instances

The evaluation spans rand, maze, and iiwa domains with common minimum-time trajectory modeling but distinct geometric and configuration-space constructions. Instances vary target counts and workspace or robot complexity across these domains.

  • Common model: All instances use the same minimum-time trajectory model with degree-5 Bézier curves for configuration and scalar time.Internal transitions enforce C2 continuity, region containment, and componentwise velocity bounds.
  • Instances: Each domain contains 60 instances generated from seeds 0, . . . , 11 and five controlled sizes.The rand domain uses polygonal convex hulls on a unit-spaced grid, with every polygon treated as a target.
  • Instances: The maze domain uses 3-D axis-aligned cuboids formed by recursive division, selecting 10, 20, . . . , 50 cuboids as targets.Cuboids sharing a face define GCS adjacencies.
  • Instances: The iiwa domain uses a precomputed collision-free 15-region 7-DoF KUKA GCS and adds 3, 6, 9, 12, or 15 exclusive target boxes.The regions are bounded by joint-position limits in a shelves-and-bins scene.

B. Solvers

The evaluation compares traversal strategies, bound ablations, and existing solvers using terminal quality, anytime performance, and search-effort metrics under a runtime budget.

  • Solver variants: Six solver variants comprise best-first and depth-first proposed searches, two bound ablations, and two existing solvers.Both proposed variants use the additive LBG prefix bound ˆg and cut-separated connected-flow cost-to-go bound h.
  • Evaluation metrics: Terminal quality, anytime performance, and search effort are evaluated under runtime budget T.The evaluation includes solution-quality and computational-effort measures.
  • Instance complexity: Table I reports instance complexity through minimum, mean, and maximum values for |V|, |E|, degree, and |Vt|, alongside dimension d and mean LBG precomputation time.The table summarizes graph size, target count, configuration-space dimension, and preprocessing cost.
  • Evaluation metrics: Lower Time-Normalized Primal Integral indicates earlier feasibility and better anytime solution quality.NPI averages normalized incumbent excess over the interval [0,T], with periods without an incumbent contributing one.
  • Evaluation metrics: Closed Nodes counts processed frontier nodes, while Evaluated Walks counts complete target-covering closed walks passed to convex restriction.For search variants, Evaluated Walks includes the greedy initial walk but excludes Alt-G prefix restrictions.

D. Result Analysis

The proposed search is more consistently successful than the baselines, while its complementary bounds and traversal strategies show domain-dependent strengths; the inspection study extends the method to mode, order, trajectory, and precedence selection.

  • Benchmark results: Both proposed variants find incumbents on all 180 instances, compared with 99 for GHOST and 98 for MICP.Their lower NPI also indicates earlier near-reference solutions.
  • Baseline comparison: GHOST has mean regret at most 3.9% when successful but fails to evaluate complete walks in 81 runs, whereas MICP reaches the 100% gap cap on all reported gaps.GHOST failures exhaust the runtime in different search levels across domains; MICP finds no iiwa incumbents.
  • Bound ablations: The ablations show that ˆg and h are complementary: Alt-H closes 314k–871k nodes, whereas Alt-G closes only 43–736 nodes but performs costly prefix restrictions.Combining the inexpensive additive prefix bound with the connectivity-aware cost-to-go bound focuses the search on complete walks.
  • Traversal strategies: Ours (BF) has lower NPI on rand and iiwa, while Ours (DF) performs better on the nearly tree-structured maze.Both strategies use the same bound for pruning, but differ in frontier traversal and sibling ordering.
  • Mobile-manipulator inspection: The inspection formulation jointly selects sensing modes, visitation order, walk, and continuous trajectory across eight tasks.The task alternatives yield 96 sensing-mode assignments, and uncovered task sets are incorporated into the connected-flow relaxation.
  • Mobile-manipulator inspection: With LTLf action precedences, Ours (BF) improves an 87.4 s greedy incumbent to 82.3 s with a 10.12% gap after 17 closed nodes.The precedence relation orders {A, B}, {E, F}, D, {G, H}, and C.

VII. CONCLUSION

The paper formalizes Steiner-TSP on GCS and develops a unified branch-and-bound search over rooted walk prefixes, with finite-termination and ε-optimality guarantees under stated conditions.

  • Contributions: The method searches rooted walk prefixes and uses positive vertex costs to establish finite termination conditions.Best-first terminates on every feasible instance without an initial incumbent, while depth-first requires a finite incumbent.
  • Guarantees: A global lower bound provides an ε-optimality certificate for either traversal strategy.The certificate applies for a user-specified factor ε≥1.
  • Future work: The paper identifies physical-robot deployment, online replanning, and scalable multi-robot planning as future work.These directions include energy-aware service and maintenance and coordinated robot-local product GCSs.
Loading 2608.21319v1…