Paper deep dive
Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets
Jingtao Tang, Hang Ma
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 $\epsilon\geq1$, a global lower bound certifies that either strategy's incumbent cost is at most $\epsilon$ 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
Tags
Links
- Source: https://arxiv.org/abs/2608.21319v1
- Canonical: https://arxiv.org/abs/2608.21319v1
Trouble viewing inline? Open PDF directly →
Full Text
52,768 characters extracted from source content.
Expand or collapse full text
Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets Jingtao Tang Hang Ma Thanks: The authors are with the School of Computing Science, Simon Fraser University, Burnaby, BC V5A1S6, Canada. jingtao_tang, hangma@sfu.ca. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice. Abstract 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 ϵ≥1ε≥ 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 (LTLf). Both traversal strategies find feasible solutions on all benchmark instances within 30s30\,s with mean certified optimality gaps of 28.1%28.1\% and 29.7%29.7\%, respectively, whereas two recent baselines succeed on only about half of the instances. I Introduction Planning a minimum-cost trajectory visiting multiple task regions couples discrete route selection with continuous trajectory optimization. Graphs of Convex Sets (GCS) [15] encode candidate routes as discrete graph choices and their associated trajectories as continuous variables subject to convex costs and constraints. Although trajectory optimization is convex for a fixed route, jointly optimizing the discrete route and continuous trajectory is NP-hard in general [14]. GCS has enabled applications including contact-rich manipulation [5, 3] and multi-robot motion planning [25, 31, 26]. Building on the single-query shortest-path formulation, recent work has considered multi-query shortest paths [16], repeated-vertex shortest walks [17], and temporal-logic planning via product GCSs [9, 28] or augmented GCSs [30]. For multi-region routing, the Traveling Salesman Problem (TSP) on GCS seeks a minimum-cost closed trajectory that visits every GCS vertex while jointly choosing the visitation order and continuous trajectory variables [15, 24, 12]. Existing methods address these coupled decisions through a unified Mixed-Integer Convex Program (MICP) [15], hierarchical tour and path search [24], or an augmented GCS with exponentially many target-subset layers [12]. In many routing tasks, however, only selected GCS vertices correspond to required task regions. Figure 1: Steiner-TSP on a GCS seeks a minimum-cost closed trajectory from root r (red) visiting all target convex sets (yellow). Black dashed arrows denote directed GCS edges (solid if used). The orange solution (a) is feasible without revisits, whereas the blue solution (b) exploits vertex revisits and is globally optimal, with circled numbers identifying the underlying GCS edges. We study the Steiner-TSP on GCS, a required-subset generalization of the TSP on GCS. Only a designated subset of vertices must be visited, while non-required vertices remain available for transit and vertices may be revisited, consistent with discrete Steiner-TSP semantics [20]. A prior inspection-planning demonstration adapted a high-level restricted-TSP [7] formulation to require visits to selected GCS vertices [24]. Here, we formalize the general problem and study its solution structure. Compared with finding a shortest path in GCS [14], the Steiner-TSP on GCS must additionally choose the visitation order of the required vertices, the walks between successive visits, and the return walk to the root. Depending on the GCS topology, visiting all required vertices and returning to the root may require vertex revisits [24]; even when unnecessary for connectivity, revisits may reduce trajectory cost [17]. Candidate solutions therefore cannot be restricted a priori to walks without revisits. Once cyclic subwalks are admitted, the number of repetitions is unbounded, so even a finite GCS can induce infinitely many finite candidate walks. Efficiently searching this infinite family is therefore a central algorithmic challenge in solving the Steiner-TSP on GCS. Recent work has explored graph search as an alternative for GCS optimization. For shortest-path problems, some methods interleave discrete expansion with convex optimization of partial or finite-horizon trajectories [18, 3, 26], whereas another line grows a vertex subset and repeatedly solves restricted GCS relaxations to obtain bounds [23]. Applying graph search to the Steiner-TSP on GCS raises a central design question: when should continuous trajectory optimization be performed? Optimizing every walk prefix can be expensive. Deferring full trajectory optimization until a complete target-covering closed walk is found, however, requires efficient lower bounds on the committed-prefix cost and the cost of visiting the remaining targets and returning to the root. Our unified branch-and-bound search traverses the rooted-walk prefix tree in Fig. 1, maintaining one frontier of live prefixes (Sec. I). The tree represents every finite rooted walk admitted by the problem, including cycles and vertex revisits. To order and prune the frontier without optimizing each prefix, we combine an additive committed-prefix cost bound (Sec. IV-B) with a cut-separated connected-flow relaxation lower-bounding the cost of visiting every remaining target and returning to the root (Sec. IV-C). Their admissible sum reserves full trajectory optimization for complete target-covering closed walks (Sec. I-B). Under the uniform positive-cost assumption, best-first traversal terminates after finitely many expansions on every feasible instance without an initial incumbent; depth-first terminates after finitely many additional expansions once a finite incumbent exists. When either strategy terminates with a finite incumbent, the global lower bound certifies that its cost is at most ϵε times the global optimum for a user-specified factor ϵ≥1ε≥ 1 (Sec. I-C). Both variants return finite incumbents on all 180 benchmark instances within the 30s30\,s budget (Sec. V). A mobile-manipulator case study demonstrates joint sensing-mode, visitation-order, GCS-walk, and continuous-trajectory selection with LTLf action precedences (Sec. VI). I Steiner-TSP on GCS A GCS is a finite directed graph G=(V,E,)G=(V,E,X). Each vertex v∈Vv∈ V is associated with a nonempty compact convex set vX_v and a positive convex cost cv:v→ℝ>0c_v:X_v _>0. Each edge e=(u,v)∈Ee=(u,v)∈ E represents an allowed transition, with a closed convex feasible set e⊆u×vX_e _u×X_v and a nonnegative convex cost ce:e→ℝ≥0c_e:X_e _≥ 0. We assume a uniform per-vertex minimum cost η>0η>0 such that cv()≥ηc_v(x)≥η for every v∈Vv∈ V and ∈vx _v. Notably, we allow a self-loop (v,v)∈E(v,v)∈ E for each v∈Vv∈ V. A walk π=(v1,…,vk)π=(v_1,…,v_k) in G is a finite sequence of vertices such that (vi,vi+1)∈E(v_i,v_i+1)∈ E for all i=1,…,k−1i=1,…,k-1, where vertices may repeat to support more general applications or solutions with smaller costs [17] (see also Fig. 1). Unlike a path that disallows vertex revisits, a walk may be necessary to form a closed route when G is incomplete. A trajectory τ=(1,…,k)τ=(x_1,…,x_k) is conditioned on the walk π if i∈vix_i _v_i for i=1,…,ki=1,…,k and (i,i+1)∈(vi,vi+1)(x_i,x_i+1) _(v_i,v_i+1) for i=1,…,k−1i=1,…,k-1. Each occurrence of a repeated vertex has its own continuous trajectory variable. For a trajectory conditioned on a closed walk, however, we require k=1x_k=x_1 and call the trajectory closed. By convention, the terminal occurrence incurs no additional vertex cost. The trajectory cost is therefore c(τ):=∑i=1k−1[cvi(i)+c(vi,vi+1)(i,i+1)].c(τ):= _i=1^k-1 [c_v_i(x_i)+c_(v_i,v_i+1)(x_i,x_i+1) ]. (1) Given a target set Vt⊆V_t V containing at least two vertices and a designated root r∈Vtr∈ V_t, the Steiner-TSP on GCS is minπ,τ _π,τ c(τ) c(τ) (2a) s.t. (vi−1,vi)∈E, (v_i-1,v_i)∈ E, i=2,…,k, i=2,…,k, (2b) v1=vk=r and 1=k, v_1=v_k=r and x_1=x_k, (2c) Vt⊆v1,…,vk−1, V_t \v_1,…,v_k-1\, (2d) τ is conditioned on π. τ is conditioned on π. (2e) A feasible solution consists of a closed trajectory conditioned on a closed walk that visits every target vertex at least once. This formulation generalizes the TSP on GCS [15, 24], which is recovered when Vt=V_t=V. Its required-subset semantics also coincide with the labeled-target setting of [12], and the Steiner terminology emphasizes that non-target GCS vertices remain available for transit without being required. The Steiner-TSP on GCS couples the discrete walk π with the continuous trajectory τ. A convex restriction fixes π in Eqn. (2) and minimizes c(τ)c(τ) over the continuous variables consistent with that walk. MICP [15] optimizes π and τ jointly within its formulation, whereas GHOST uses a two-level search [24]: a high-level restricted-TSP search explores target tours, while a low-level search constructs their realizing GCS walks and evaluates complete target-covering closed walks by convex restriction. Both baselines allow vertices to recur across different inter-target segments. MICP requires each segment to be vertex-simple, while GHOST prevents vertex revisits while searching toward the next target and advances in the selected tour once that target becomes adjacent. I Unified Branch-and-Bound Search The Steiner-TSP on GCS has an intrinsic solution space with coupled discrete and continuous components. Its discrete component consists of finite rooted GCS walks, while each target-covering return to the root indexes a walk-conditioned convex restriction over the continuous trajectory variables; this restriction may be infeasible. As vertices may be revisited, this family of walks is generally infinite, and unrolling it yields a finitely branching prefix tree determined by the problem. Our unified branch-and-bound search systematically explores this tree by maintaining a single set of live walk prefixes and using the bounds developed in Sec. IV to prioritize and prune them. I-A Search Space Formally, the discrete tree contains a search node n for each prefix walk n.π=(v1=r,v2,…,vk)n.π=(v_1=r,v_2,…,v_k). This full-prefix identity is essential because two prefixes reaching the same frontier vertex vkv_k can induce different feasible boundary conditions and optimal conditioned trajectories even when followed by the same suffix [3, 26]. Let V(n.π):=v1,…,vkV(n.π):=\v_1,…,v_k\ denote the set of vertices visited by n.πn.π. For any successor w of vkv_k, let n.π⊕w:=(v1,…,vk,w)n.π w:=(v_1,…,v_k,w) denote the prefix walk obtained by appending w. A node n is a solution node if Vt⊆V(n.π)V_t V(n.π) and vk=rv_k=r. This is only a discrete condition: the indexed convex restriction may be infeasible; when feasible, its optimal value is the minimum cost among trajectories conditioned on n.πn.π. Every node n, including a solution node, has a child ncn_c with nc.π=n.π⊕wn_c.π=n.π w for each edge (vk,w)∈E(v_k,w)∈ E. Consequently, the tree contains every finite rooted GCS walk, including walks that continue after an earlier target-covering return to r; together with the convex restrictions indexed by its solution nodes, it represents every feasible pair (π,τ)(π,τ) of Eqn. (2). The tree is defined independently of how it is explored. Alg. 1 materializes it lazily by maintaining a set of live search nodes, called the Frontier. A traversal strategy selects which live node to explore next. Each node n additionally stores a cost-to-come lower bound g^(n) g(n) and a cost-to-go heuristic h(n)h(n). We call h admissible with respect to g g if, for every feasible solution (π′,τ)(π ,τ) whose walk extends n.πn.π, h(n)≤c(τ)−g^(n)h(n)≤ c(τ)- g(n). Sec. I-B combines these quantities into the node lower bound used for Frontier ordering and pruning. I-B Search Procedure We first define the node lower bound and traversal strategy used by the proposed Alg. 1. For a search node n and its child ncn_c induced by a successor w, the shared relaxation developed in Sec. IV supplies an incremental lower-bound cost ℓ(n,w) (n,w), yielding g^(nc)=g^(n)+ℓ(n,w) g(n_c)= g(n)+ (n,w). Since each extension commits one vertex cost, the uniform positive-cost assumption in Sec. I gives ℓ(n,w)≥η (n,w)≥η. Together with the admissible cost-to-go heuristic, this defines the node lower bound f(n):=g^(n)+h(n),f(n):= g(n)+h(n), (3) which lower-bounds the cost of every feasible solution whose walk extends n.πn.π. The traversal strategy controls only which live node is selected. We describe two canonical choices: best-first maintains a min-priority queue ordered by f(n)f(n), whereas depth-first uses a last-in-first-out stack and locally orders siblings by f(n)f(n). All traversal strategies prune any node satisfying f(n)≥c¯f(n)≥ c and, once c¯<+∞ c<+∞, use the global stopping condition c¯≤ϵminn∈Frontierf(n) c≤ε _n∈ Frontierf(n) for ϵ≥1ε≥ 1. Alg. 1 accepts an optional initial incumbent to prune in the initial search stage. Our implementation constructs one by solving the convex restriction for a nearest-neighbor closed walk that repeatedly follows a shortest graph path to the closest unvisited target and finally returns to r. If its restriction is infeasible, no initial incumbent is supplied and c¯=+∞ c=+∞. Alg. 1 initializes Frontier with one two-vertex walk (r,v)(r,v) for every outgoing edge of r (lines 1–1). Each iteration checks the global stopping condition, selects a node according to the traversal strategy, and discards it if its bound cannot improve the incumbent (lines 1–1). An unpruned solution node is evaluated by convex restriction and then, like every unpruned node, expanded along all outgoing edges; only children whose cost-to-come and node bounds are below c¯ c are inserted (lines 1–1). If Frontier is exhausted or the stopping condition holds, it returns the incumbent if one exists (line 1). Input: GCS G=(V,E,)G=(V,E,X), targets VtV_t, root r, optional initial incumbent τ∗τ^* with cost c¯ c Param: traversal strategy, suboptimality factor ϵ≥1ε≥ 1 Output: updated incumbent τ∗τ^* and its cost c¯ c Frontier←∅ Frontier← 1 foreach (r,v)∈E(r,v)∈ E do 2 n←Node((r,v),g^=0)n← Node((r,v), g=0) 3 if f(n)<c¯f(n)< c then 4 Frontier.push(n) Frontier.push(n) 5 while Frontier≠∅ Frontier≠ do 6 if c¯<+∞ c<+∞ and c¯≤ϵminn∈Frontierf(n) c≤ε _n∈ Frontierf(n) then 7 break ⊳ ϵε-optimal incumbent found n←Frontier.pop()n← Frontier.pop() 8 if f(n)≥c¯f(n)≥ c then 9 continueif vk=rv_k=r and Vt⊆V(n.π)V_t V(n.π) then 10 τ←ConvexRestriction(G,n.π)τ← ConvexRestriction(G,n.π) 11 if τ is feasible and c(τ)<c¯c(τ)< c then 12 (τ∗,c¯)←(τ,c(τ))(τ^*, c)←(τ,c(τ)) 13 foreach (vk,w)∈E(v_k,w)∈ E do 14 if g^(n)+ℓ(n,w)<c¯ g(n)+ (n,w)< c then 15 nc←Node(n.π⊕w,g^=g^(n)+ℓ(n,w))n_c← Node(n.π w, g= g(n)+ (n,w)) 16 if f(nc)<c¯f(n_c)< c then 17 Frontier.push(nc) Frontier.push(n_c) 18 return (τ∗,c¯)(τ^*, c) 19 Algorithm 1 Unified Branch-and-Bound Search I-C Theoretical Properties We establish finite termination for best-first traversal (Theorem 1) and then show that it also holds for depth-first traversal once a finite incumbent becomes available (Remark 1). Theorem 1 (Finite Best-First Search). Alg. 1 with best-first traversal terminates after finitely many node expansions for a feasible instance. Proof. Let d(n):=|n.π|−2d(n):=|n.π|-2 be the number of extensions after an initial two-vertex node. Suppose first that initialization leaves c¯=+∞ c=+∞, and choose any feasible solution (π¯,τ¯)( π, τ) with cost C:=c(τ¯)C:=c( τ). Every node whose prefix lies on π¯ π satisfies f(n)≤Cf(n)≤ C by the lower-bound property of f. Before an incumbent is found, c¯=+∞ c=+∞, so none of these prefixes is pruned. The proposed relaxation has nonnegative costs, so h(n)≥0h(n)≥ 0. Since every extension increases g g by at least η, any node with f(n)≤Cf(n)≤ C satisfies d(n)η≤g^(n)≤f(n)≤Cd(n)η≤ g(n)≤ f(n)≤ C. Since G is finite, only finitely many nodes have such bounded depth. Because best-first traversal always selects a minimum-key live node, induction over the finitely many prefixes of π¯ π shows that it reaches and evaluates the solution node indexed by π¯ π after finitely many expansions, unless another branch supplies a finite incumbent earlier. Let c¯0<+∞ c_0<+∞ be the first finite incumbent cost, whether supplied initially or found during search. Only finitely many nodes have been generated when it becomes available. Every node inserted afterward satisfies g^(n)<c¯≤c¯0 g(n)< c≤ c_0 and hence d(n)<c¯0/ηd(n)< c_0/η. Finite branching thus allows only finitely many additional nodes to be generated for finite termination. ∎ Remark 1 (Depth-First Traversal). The finite-depth argument in the proof of Theorem 1 is independent of the traversal strategy. Thus, depth-first traversal also terminates after finitely many additional expansions once a finite incumbent is found during search or supplied initially. Before then, pure last-in-first-out traversal may starve a live sibling on the infinite tree. Let c⋆c denote the optimal value of Eqn. (2). The following Theorem 2 show that the same lower-bound property yields an ϵε-optimality certificate for any traversal strategy. Theorem 2 (ϵε-optimality). For any traversal strategy, if Alg. 1 terminates with a finite incumbent of cost c¯ c by satisfying the global stopping condition or exhausting Frontier, then c¯≤ϵc⋆ c≤ε c . Proof. At termination, let L:=minc¯,minn∈Frontierf(n),L:= \ c, _n∈ Frontierf(n) \, where the Frontier minimum is omitted if Frontier is empty. Consider any feasible solution (π,τ)(π,τ) of cost C. Exhaustive successor generation preserves the branch corresponding to π until its complete walk is evaluated, one of its prefixes remains in Frontier, or one of its prefixes is discarded by an incumbent-bound test. In the first case, the walk-conditioned convex restriction gives c¯≤C c≤ C; in the second, minn∈Frontierf(n)≤C _n∈ Frontierf(n)≤ C; and in the third, the lower bound responsible for discarding the prefix gives c¯≤C c≤ C. Therefore L≤CL≤ C for every feasible solution, and taking the infimum over all feasible solutions gives L≤c⋆L≤ c . If the global stopping condition holds, then c¯≤ϵL≤ϵc⋆ c≤ε L≤ε c . If Frontier is exhausted, L=c¯≤c⋆L= c≤ c . Since the incumbent is feasible, c⋆≤c¯c ≤ c and thus c¯=c⋆ c=c . ∎ IV Lower-Bound Graph for Search Bounds Efficient branch-and-bound requires inexpensive cost-to-come and cost-to-go bounds at every prefix, but future extensions can change the continuous trajectory along a prefix and hence its realized cost [3, 26]. Prefix-conditioned convex restrictions preserve continuous consistency [18, 3, 16, 26], while repeated fractional GCS relaxations over expanding vertex subsets offer another online bounding strategy [23]; both require continuous optimization during search, and our ablation shows that solving a prefix restriction at every generated node sharply limits search progress under the fixed runtime budget (Table I). To avoid this repeated online optimization, we precompute local convex-restriction costs for short GCS walks and compose them in a reusable discrete relaxation that enforces feasibility within each piece while relaxing consistency between adjacent pieces. This representation supplies a cost-to-come lower bound g^(n) g(n) for the committed prefix and an admissible cost-to-go heuristic h(n)h(n) for visiting the remaining targets and returning to the root, without a GCS trajectory solve at every generated node. For every feasible solution (π′,τ)(π ,τ) to Eqn. (2) whose walk π′π extends n.πn.π, these bounds satisfy g^(n)+h(n)≤c(τ) g(n)+h(n)≤ c(τ). IV-A Lower-Bound Graph (LBG) Relaxation The triplet-based LBG is one such representation and has previously been used for GCS search bounds [18, 24]; a closely related triplet relaxation is used in [26]. We adopt the LBG as the shared representation underlying both g g and h. Given a GCS G=(V,E,)G=(V,E,X), we construct its LBG L=(E,T)L=(E,T) as follows. Every length-two GCS walk (u,v,w)(u,v,w) defines a triplet t=(u,v,w)∈Tt=(u,v,w)∈ T, directed in L from edge e1=(u,v)∈Ee_1=(u,v)∈ E to edge e2=(v,w)∈Ee_2=(v,w)∈ E. We assign t the optimal value of the local convex program ℓt:=minu,v,w[cv(v)+ce2(v,w)], _t:= _x_u,x_v,x_w [c_v(x_v)+c_e_2(x_v,x_w) ], (4) where u∈ux_u _u, v∈vx_v _v, and w∈wx_w _w are constrained by (u,v)∈e1(x_u,x_v) _e_1 and (v,w)∈e2(x_v,x_w) _e_2. If the program in Eqn. (4) is infeasible, we set ℓt=+∞ _t=+∞. The objective of Eqn. (4) includes exactly the costs of the middle vertex v and its outgoing edge e2e_2, as assigned in Eqn. (1), while the constraints enforce local feasibility with both neighboring edges. Thus, ℓt _t lower-bounds the trajectory cost committed at vertex v by any feasible trajectory whose walk contains t. The uniform positive-cost assumption in Sec. I gives ℓt≥η _t≥η for every finite-cost triplet t∈Tt∈ T. Every GCS walk π=(v1,…,vk)π=(v_1,…,v_k) therefore induces an LBG walk through the consecutive edges (vi,vi+1)(v_i,v_i+1). Because each ℓt _t is computed independently, adjacent triplets need not share consistent GCS variables, so the induced LBG-walk cost lower-bounds the cost of any feasible trajectory conditioned on π. Consider any feasible solution to the Steiner-TSP on GCS, with trajectory τ conditioned on the GCS walk π=(v1=r,v2,…,vk=r)π=(v_1=r,v_2,…,v_k=r). Closing the corresponding LBG walk gives c^(π):=∑i=1k−2ℓ(vi,vi+1,vi+2)+ℓ(vk−1,r,v2)≤c(τ), c(π):= _i=1^k-2 _(v_i,v_i+1,v_i+2)+ _(v_k-1,r,v_2)≤ c(τ), (5) where c^(π) c(π) denotes the cost of the closed LBG walk induced by π. This lower bound is the closed-walk case of Theorem 1 in [24], extending the open-path result in Theorem 3 of [18]. IV-B Cost-to-Come Lower Bound Consider a search node n with n.π=(v1=r,v2,…,vk)n.π=(v_1=r,v_2,…,v_k). We define its cost-to-come lower bound g^(n) g(n) as the cost of the corresponding fixed LBG walk (Lemma 3): g^(n):=∑i=1k−2ℓ(vi,vi+1,vi+2). g(n):= _i=1^k-2 _(v_i,v_i+1,v_i+2). (6) For the initial prefix n.π=(r,v2)n.π=(r,v_2), the sum is empty, so g^(n)=0 g(n)=0. Appending a successor w extends the LBG walk by t=(vk−1,vk,w)∈Tt=(v_k-1,v_k,w)∈ T and produces a child ncn_c satisfying g^(nc)=g^(n)+ℓ(n,w)=g^(n)+ℓt, g(n_c)= g(n)+ (n,w)= g(n)+ _t, (7) where the incremental lower bound in Sec. I-B is instantiated as ℓ(n,w):=ℓt (n,w):= _t. Because ℓt≥η _t≥η, each extension provides the positive progress required by the proof of Theorem 1. Lemma 3. For any search node n and feasible solution (π′,τ)(π ,τ) whose walk extends n.πn.π, we have g^(n)≤c^(π′)≤c(τ) g(n)≤ c(π )≤ c(τ). Proof. The first inequality holds because g^(n) g(n) is a partial sum of the nonnegative LBG-walk cost c^(π′) c(π ), and the second one comes from the LBG lower-bound property [26, 24, 18]. ∎ IV-C Cut-Separated Connected-Flow Cost-to-Go We propose an admissible heuristic h(n)h(n) that lower-bounds the cost of visiting every unvisited target and closing the walk. The heuristic is evaluated online at every search node by a cut-separated connected-flow Linear Program (LP). Consider LBG L=(E,T)L=(E,T). With a slight abuse of notation, T denotes only the finite-cost triplets throughout this subsection. For a search node n with n.π=(v1=r,v2,…,vk)n.π=(v_1=r,v_2,…,v_k), let esrc:=(vk−1,vk)∈E and Vt(n):=Vt∖V(n.π).e_src:=(v_k-1,v_k)∈ E\, and\, V_t(n):=V_t V(n.π). For each v∈Vt(n)v∈ V_t(n), define its incoming-edge set Ev:=(u,v)∈E.E_v:=\(u,v)∈ E\. Because v is unvisited by n.πn.π, esrc∉Eve_src∉ E_v. Because each GCS edge is an LBG vertex, a GCS walk reaches v exactly when its induced LBG walk visits a vertex in EvE_v. For any feasible solution (π′,τ)(π ,τ) to Eqn. (2) with n.πn.π as a prefix of π′π , the residual LBG walk induced by π′π therefore starts at esrce_src, visits a vertex in EvE_v for every v∈Vt(n)v∈ V_t(n), and returns through the initial edge (r,v2)(r,v_2) to close the walk. To enforce closure of the LBG walk through the final triplet (u,r,v2)(u,r,v_2), let ecle_cl denote an artificial sink vertex. Let E♯:=E∪eclE :=E∪\e_cl\, and let T♯T augment T with, for every closing triplet (u,r,v2)∈T(u,r,v_2)∈ T, a terminal transition from (u,r)(u,r) to ecle_cl with cost ℓ(u,r,v2) _(u,r,v_2). Define the admissible source-side sets by (n):=⋃v∈Vt(n)S⊆E∖Ev:esrc∈S.S(n):= _v∈ V_t(n)\S E E_v:e_src∈ S\. For each S∈(n)S (n), define its outgoing finite-triplet cut by δ+(S):=(u,v,w)∈T:(u,v)∈S,(v,w)∉S.δ^+(S):=\(u,v,w)∈ T:(u,v)∈ S,\ (v,w)∉ S\. For a nonnegative flow ξ on T♯T , define divξ∈ℝE♯divξ ^E componentwise, where (divξ)e(divξ)_e is the total outgoing minus incoming flow at edge e∈E♯e∈ E . For each e∈E♯e∈ E , let e∈0,1E♯1_e∈\0,1\^E denote the unit vector at e. Let ℓ♯ contain the corresponding costs on T♯T . We define h(n)h(n) as the optimal value of minξ∈ℝ≥0T♯ _ξ _≥ 0^T (ℓ♯)⊤ξ ( ) ξ (8a) .. .t. divξ=esrc−ecl, ξ=1_e_src-1_e_cl, (8b) ∑t∈δ+(S)ξt≥1,∀S∈(n). _t∈δ^+(S) _t≥ 1, ∀ S (n). (8c) Eqn. (8b) routes one net unit of cost-bearing flow from esrce_src to ecle_cl through a valid closing terminal transition, while permitting additional circulations. Eqn. (8c) requires at least one unit across every directed cut separating esrce_src from each remaining target’s incoming-edge set. Hence, a disconnected target-covering circulation cannot by itself certify target visitation. When Vt(n)=∅V_t(n)= , the LP reduces to a minimum-cost flow from esrce_src to ecle_cl. Whenever the LP is infeasible, h(n)=+∞h(n)=+∞. By the max-flow/min-cut theorem, these cut constraints are equivalent to sending one auxiliary unit of flow from esrce_src to each EvE_v under capacities ξ. This construction adapts the multi-commodity-flow formulation for the classic Steiner-TSP [10] by replacing each required vertex with its incoming-edge set EvE_v. We solve this exponential cut formulation by row generation using a persistent restricted master. After each solve, we use ξ as arc capacities, add any connectivity cuts violated by an esrce_src-to-EvE_v minimum cut, and reoptimize. Lemma 4 establishes that h is an admissible cost-to-go heuristic. Lemma 4 (Admissibility). For any search node n and feasible solution (π′,τ)(π ,τ) whose walk extends n.πn.π, we have g^(n)+h(n)≤c^(π′)≤c(τ). g(n)+h(n)≤ c(π )≤ c(τ). (9) Thus, h is admissible with respect to g g by definition, and f(n)f(n) in Eqn. (3) lower-bounds the cost of every feasible solution whose walk extends n.πn.π. Proof. The multiplicities of the finite triplets in the residual LBG walk of π′π , together with its closing terminal transition, define an integral flow ξ satisfying Eqn. (8b). For each S∈(n)S (n), choose a remaining target v such that S∩Ev=∅S∩ E_v= . The residual walk starts in S and reaches an edge in EvE_v outside S. It must therefore cross δ+(S)δ^+(S) at least once, so every connectivity cut is satisfied. The resulting objective is c^(π′)−g^(n) c(π )- g(n). Optimality gives h(n)≤c^(π′)−g^(n)h(n)≤ c(π )- g(n), and the second inequality follows from Eqn. (5). ∎ V Numerical Results This section presents our numerical results for Steiner-TSP on GCS solvers. We implement the proposed search and its components in Python and evaluate the resulting solver on a machine with an Apple® M4 processor and 16 GB of memory. The GCS-related trajectory optimization uses the Drake [27] library configured with the Gurobi solver [6]. Gurobi also solves the persistent restricted master for the cost-to-go bound, while directed minimum-cut computations identify violated connectivity rows. Source code, numerical results, and additional visualizations will be released upon publication. More detailed visualizations and simulations are available at https://sites.google.com/view/steiner-tsp-gcs. V-A Instances We evaluate the Steiner-TSP on GCS across the three task domains shown in Fig. 2. All instances use the same minimum-time trajectory model [13]. Each visit to a GCS vertex is parameterized by degree-5 Bézier curves for the d-dimensional configuration and scalar time. Accordingly, each variable i∈ℝ6(d+1)x_i ^6(d+1) in Eqn. (2) comprises six d-dimensional configuration control points and six scalar time control points. We impose C2C^2 continuity across internal GCS transitions, constrain all configuration control points to the selected GCS region, and enforce componentwise velocity bounds on each segment. We impose neither acceleration nor torque limits. All edge costs are zero, and each vertex cost equals its segment duration, with a minimum duration of η=0.1sη=0.1\,s. Each domain contains 60 instances generated from seeds 0,…,110,…,11 and five controlled sizes. For rand, point configurations move through convex hulls of six points sampled within 1.5×1.51.5× 1.5 squares on a unit-spaced grid, yielding a size-dependent workspace. Each seed grows a connected cover to undirected intersection-edge thresholds of 10,20,…,5010,20,…,50, with every polygon treated as a target (V=VtV=V_t). For maze, point configurations move through a random 10×10×1010× 10× 10 unit-voxel recursive-division maze [2] with one-voxel-thick walls. We partition its free voxels into a minimum-cardinality set of disjoint axis-aligned cuboids, a 3-D analogue of the minimum-brick decomposition in [11], where cuboids sharing a face define GCS adjacencies. We select 10,20,…,5010,20,…,50 cuboids distributed across each maze GCS as targets. For iiwa, we use a precomputed collision-free 15-region joint-space GCS for a fixed-base 7-DoF KUKA LBR iiwa 14 in a shelves-and-bins scene, with IRIS-NP regions [19] bounded by the robot’s joint-position limits. Each instance adds 3,6,9,123,6,9,12, or 1515 exclusive target boxes with halfwidth at most 0.01rad0.01\,rad, each adjacent only to its owner region. In all three domains, we build two oppositely directed edges if the configuration convex sets of a GCS vertex pair intersect. Table I summarizes the resulting graphs, with Degree computed using undirected adjacency. Figure 2: Steiner-TSP on GCS solution trajectories (blue) in rand with a 2-D GCS of gray polygons, maze with a 3-D GCS exactly partitioning the free voxels outside black walls, and iiwa with a 7-D GCS comprising IRIS-NP [19] regions seeded by representative collision-free configurations. V-B Solvers We compare six solver variants: two traversal strategies for the proposed search, two bound ablations, and two existing solvers. We instantiate the proposed search with the best-first (BF) and depth-first (DF) traversal strategies, denoted Ours (BF) and Ours (DF), respectively. Both use the proposed additive LBG prefix bound g g (Sec. IV-B) and cut-separated connected-flow cost-to-go bound h (Sec. IV-C). The ablation study isolates the two proposed bounds. Alt-G retains h but replaces g g with the optimal committed-prefix cost obtained from a prefix convex restriction at every generated node, whereas Alt-H retains g g but replaces h with an LBG heuristic that connects the current prefix to the remaining targets, spans them with a metric-closure MST, and returns to the root. Both Alt-G and Alt-H use the best-first traversal strategy. For the performance comparison, we include GHOST [24] and MICP [15], as described in Sec. I. We provide the active edges of a greedy closed walk as a partial Mixed-Integer Programming (MIP) start for MICP. The walk repeatedly connects the current vertex to the closest unvisited target by an unweighted shortest path on the input GCS. All solvers receive a runtime budget T=30sT=30\,s.11 1 For the search-based solvers, LBG precomputation is performed offline and excluded from the runtime budget. For MICP, model construction and partial MIP-start generation are also excluded. Table I: Steiner-TSP on GCS instance complexity. The |V||V|, |E||E|, Degree, and |Vt||V_t| columns report the minimum/mean/maximum. The d column reports the configuration-space dimension, and LBG column reports the mean precomputation time in seconds. Domain |V||V| |E||E| Degree |Vt||V_t| d LBG rand 8/23.6/41 20/60.6/104 1/2.51/7 8/23.6/41 2 0.07s maze 63/63/63 124/125.2/130 1/1.99/4 10/30/50 3 0.14s iiwa 18/24/30 104/116.0/128 1/4.93/13 3/9/15 7 4.57s V-C Metrics We evaluate terminal quality, anytime performance, and search effort under runtime budget T, using as each instance’s reference cost the lowest incumbent at T across all six solver variants. Cost Regret is the terminal incumbent’s fractional excess over this reference, whereas Gap is the fractional difference between the terminal incumbent and the solver-reported terminal lower bound, capped at 100%100\%. Both are averaged only over runs with a finite incumbent, with a missing finite lower bound assigned a 100%100\% gap; because GHOST and MICP restrict the walk family (Sec. I), their gaps do not certify the unrestricted problem. Feasible counts runs with a finite incumbent at T. Following [1], the Time-Normalized Primal Integral (NPI) averages over [0,T][0,T] the incumbent’s excess over the reference cost, normalized by the current incumbent and capped at one. Periods without an incumbent contribute one, so lower NPI reflects earlier feasibility and better anytime solution quality. For search effort, Closed Nodes counts popped and processed frontier nodes, whereas Evaluated Walks counts complete target-covering closed walks passed to a convex restriction. Closed Nodes is omitted for GHOST and MICP, and Evaluated Walks is omitted for MICP; for the four search-based variants, Evaluated Walks includes the greedy initial walk but excludes Alt-G’s prefix restrictions, which are not complete walks. Both terminal counters may include the final operation begun before T and completed afterward. V-D Result Analysis Table I shows that both proposed variants find incumbents on all 180 instances, compared with 99 for GHOST and 98 for MICP, while their lower NPI indicates earlier near-reference solutions. Ours (BF) performs best across the three quality metrics on rand and iiwa, whereas Ours (DF) achieves the best gap and NPI on maze and ties GHOST in displayed regret. GHOST and MICP both exhibit complementary bottlenecks. GHOST remains competitive when successful, with mean regret at most 3.9%3.9\%, but none of its 81 failed runs evaluates a complete walk: failures exhaust T in the initial restricted-TSP solve for maze, in the low-level GCS-walk search for iiwa, and at either level for larger rand instances. MICP finds incumbents on all maze instances but none on iiwa, and all its reported gaps reach the 100%100\% cap. This contrast plausibly reflects formulation difficulty rather than raw GCS size: MICP creates one GCS copy per target and initializes only selected edge indicators, while a representative 3-target iiwa model has 4.28 million nonzeros, 5.45.4 times that of a 10-target maze model. This is consistent with easier initialization on nearly tree-structured six-facet maze regions than on rand, where all vertices are targets, or on 7-D iiwa regions with 48–237 facets. The ablations confirm g g and h are complementary. Alt-H is inexpensive but loose because its pairwise LBG connections need not form one ordered residual walk that visits every remaining target and returns to the root, leaving many prefixes competitive and closing 314k–871k nodes while evaluating only 1–56 complete walks. Alt-G instead solves a prefix convex restriction for every generated child before pruning; these solves are not captured by either effort counter and limit the search to 43–736 closed nodes without evaluating a complete walk beyond the greedy initialization. Combining the inexpensive additive g g with the connectivity-aware h avoids both bottlenecks and focuses the frontier on complete walks. The two traversal strategies also have complementary strengths. Ours (BF) globally prioritizes prefixes by g^+h g+h and achieves lower NPI on rand and iiwa, whereas Ours (DF) uses the same bound for pruning and sibling ordering and performs better on the nearly tree-structured maze. Table I: Ablation and performance comparison results. Solver Cost Gap↓ Feasible↑ NPI↓ Closed Eval. Regret↓ Nodes Walks rand GHOST[24] 2.1% 50.4% 43/60 0.386 – 294 MICP[15] 24.5% 100.0% 38/60 0.603 – – Ours (BF) 0.0% 18.3% 60/60 0.011 8.6k 666 Ours (DF) 1.8% 21.7% 60/60 0.023 1.2k 429 Alt-G 28.0% 33.0% 60/60 0.205 736 1 Alt-H 26.8% 54.7% 60/60 0.197 749k 56 maze GHOST[24] 0.0% 3.4% 12/60 0.802 – 23 MICP[15] 2.2% 100.0% 60/60 0.163 – – Ours (BF) 0.7% 3.6% 60/60 0.014 53.5k 168 Ours (DF) 0.0% 3.1% 60/60 0.005 1.3k 173 Alt-G 2.5% 5.2% 60/60 0.027 453 1 Alt-H 2.5% 52.7% 60/60 0.027 871k 1 iiwa GHOST[24] 3.9% 64.6% 44/60 0.383 – 37 MICP[15] – – 0/60 1.000 – – Ours (BF) 0.2% 62.4% 60/60 0.042 830 54 Ours (DF) 4.0% 64.4% 60/60 0.062 98 30 Alt-G 10.6% 64.0% 60/60 0.111 43 1 Alt-H 6.2% 65.1% 60/60 0.083 314k 37 VI Mobile-Manipulator Inspection Case Study We demonstrate Ours (BF) using a mobile manipulator comprising the same 7-DoF arm as in the iiwa domain, a wrist-mounted camera, and a 3-DoF holonomic planar base with pose (xb,yb,θb)∈ℝ2×S1(x_b,y_b, _b) ^2× S^1. As shown in Fig. 3, the robot departs from a charging dock, navigates the workspace to acquire eight inspection images, and returns to the dock. We precompute the GCS G=(V,E,)G=(V,E,X) as coupled navigation and inspection subgraphs, totaling 92 vertices and 208 directed edges. The navigation subgraph contains collision-free regions in the 3-DoF base configuration space, lifted to the full 10-DoF robot configuration space by fixing the manipulator in a retracted posture. The inspection subgraph contains convex regions generated by IRIS-NP [19] in the 7-DoF manipulator configuration space, with the base fixed at one of the inspection base poses represented in the navigation subgraph. The charging-dock vertex serves as the root r∈Vr∈ V, and each inspection task i=1,…,8i=1,…,8 is represented by a nonempty service-vertex subset Vi⊆V∖rV_i V \r\, where each v∈Viv∈ V_i encodes one feasible combination of base pose and manipulator region for acquiring image i. The GCS construction took 0.4s0.4\,s and its LBG precomputation took 6.0s6.0\,s. Figure 3: Mobile-manipulator inspection: (a) PRM-based generalized-TSP baseline, (b) Ours (BF), and (c) Ours (BF) with LTLf [4] action precedences. Translucent arm poses encode normalized active-motion progress from blue (early) to orange (late), as shown by the right color bar. Red circled A–H mark tasks; black circled 1–8 show execution order and simulation timestamps. We formulate this inspection task as a Steiner-TSP on the precomputed GCS G by generalizing the coverage constraint in Eqn. (2d) so that the rooted closed walk must visit at least one vertex in each ViV_i. Across the eight tasks, the alternatives encoded by V1,…,V8V_1,…,V_8 yield 96 sensing-mode assignments; if every ViV_i is a singleton, the formulation reduces to Eqn. (2) with Vt=r∪⋃iViV_t=\r\∪ _iV_i. The search tracks which tasks have been covered and represents each uncovered ViV_i in the connected-flow cost-to-go relaxation by the union ⋃v∈ViEv _v∈ V_iE_v; all other machinery is unchanged, and the search jointly selects the modes, order, walk, and trajectory. We adopt the same benchmark trajectory model in Sec. V-A. Ours (BF) finds an initial 91.4s91.4\,s greedy solution in 0.35s0.35\,s with a 19.03%19.03\% gap, and improves it to 78.4s78.4\,s in 1.72s1.72\,s with a 5.64%5.64\% gap after 642 closed search nodes (Fig. 3(b)). For comparison, we construct a PRM [8] for the 3-DoF base (in 2.0s2.0\,s) with the manipulator fixed in a retracted posture, and augment it with sampled feasible 7-DoF manipulator configurations at the same inspection base poses in the GCS using OMPL [22]. We then solve the resulting generalized-TSP [21] for the same eight inspection tasks. It returns a feasible 133.1s133.1\,s solution in 31.6s31.6\,s without an optimality guarantee (Fig. 3(a)). Fig. 3(c) further demonstrates the versatility of Ours (BF) by augmenting the inspection task with a linear temporal logic over finite traces (LTLf) specification [4]. It additionally enforces A,B≺E,F≺D≺G,H≺C\A,B\ \E,F\ \G,H\ for the task, where ≺ denotes a precedence relation. Following prior works over product GCSs [9, 28], we compile the specification into a deterministic finite automaton and explicitly track its state in each search node. Ours (BF) finds an initial 87.4s87.4\,s greedy incumbent in 0.4s0.4\,s and, after closing 17 search nodes, improves it to 82.3s82.3\,s in about 1.3s1.3\,s with a 10.12%10.12\% gap. VII Conclusion We formalized Steiner-TSP on GCS and proposed a unified branch-and-bound search over rooted walk prefixes. With uniformly positive GCS vertex costs, 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. A global lower bound provides an ϵε-optimality certificate for either strategy. Future work will apply the proposed search to physical robots for energy-aware service and maintenance, study online replanning via incremental space-time GCS [26] updates with ultrafast convex-set construction [29], and develop scalable multi-robot planning through coordinated robot-local product GCSs. References [1] T. Berthold (2013) Measuring the impact of primal heuristics. Operations Research Letters 41 (6), p. 611–614. External Links: Document Cited by: §V-C. [2] J. Buck (2011) Maze generation: recursive division. Note: https://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithmBlog post, accessed 2026-03-09 Cited by: §V-A. [3] S. Y. C. Chia, R. H. Jiang, B. P. Graesdal, L. P. Kaelbling, and R. Tedrake (2024) GCS*: forward heuristic search on implicit graphs of convex sets. arXiv preprint arXiv:2407.08848. Cited by: §I, §I, §I-A, §IV. [4] G. De Giacomo and M. Y. Vardi (2013) Linear temporal logic and linear dynamic logic on finite traces. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, p. 854–860. Cited by: Figure 3, §VI. [5] B. P. Graesdal, S. Y. C. Chia, T. Marcucci, S. Morozov, A. Amice, P. A. Parrilo, and R. Tedrake (2024) Towards tight convex relaxations for contact-rich manipulation. In Proceedings of Robotics: Science and Systems, Delft, Netherlands. External Links: Document Cited by: §I. [6] Gurobi Optimization, LLC (2026) Gurobi Optimizer Reference Manual. External Links: Link Cited by: §V. [7] H. W. Hamacher and M. Queyranne (1985) K best solutions to combinatorial optimization problems. Annals of Operations Research 4 (1), p. 123–143. Cited by: §I. [8] L. E. Kavraki, P. Svestka, J. Latombe, and M. H. Overmars (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transactions on Robotics and Automation 12 (4), p. 566–580. Cited by: §VI. [9] V. Kurtz and H. Lin (2023) Temporal logic motion planning with convex optimization via graphs of convex sets. IEEE Transactions on Robotics 39 (5), p. 3791–3804. External Links: Document Cited by: §I, §VI. [10] A. N. Letchford, S. D. Nasiri, and D. O. Theis (2013) Compact formulations of the Steiner Traveling Salesman Problem and related problems. European Journal of Operational Research 228 (1), p. 83–92. External Links: Document Cited by: §IV-C. [11] J. Lu, B. Zeng, J. Tang, T. L. Lam, and J. Wen (2023) TMSTC*: a path planning algorithm for minimizing turns in multi-robot coverage. IEEE Robotics and Automation Letters 8 (8), p. 5275–5282. Cited by: §V-A. [12] G. Luna and T. Summers (2026) Augmented graphs of convex sets and the traveling salesman problem. arXiv preprint arXiv:2604.06406. Cited by: §I, §I. [13] T. Marcucci, M. Petersen, D. von Wrangel, and R. Tedrake (2023) Motion planning around obstacles with convex optimization. Science robotics 8 (84), p. eadf7843. Cited by: §V-A. [14] T. Marcucci, J. Umenberger, P. Parrilo, and R. Tedrake (2024) Shortest paths in graphs of convex sets. SIAM Journal on Optimization 34 (1), p. 507–532. Cited by: §I, §I. [15] T. Marcucci (2024) Graphs of convex sets with applications to optimal control and motion planning. Ph.D. Thesis, Massachusetts Institute of Technology. Cited by: §I, §I, §I, §V-B, Table I, Table I, Table I. [16] S. Morozov, T. Marcucci, A. Amice, B. P. Graesdal, R. Bosworth, P. A. Parrilo, and R. Tedrake (2024) Multi-query shortest-path problem in graphs of convex sets. In International Workshop on the Algorithmic Foundations of Robotics, p. 67–86. Cited by: §I, §IV. [17] S. Morozov, T. Marcucci, B. P. Graesdal, A. Amice, P. A. Parrilo, and R. Tedrake (2025) Mixed discrete and continuous planning using shortest walks in graphs of convex sets. arXiv preprint arXiv:2507.10878. Cited by: §I, §I, §I. [18] R. Natarajan, C. Liu, H. Choset, and M. Likhachev (2024) Implicit graph search for planning on graphs of convex sets. Robotics: Science and Systems (RSS). Cited by: §I, §IV-A, §IV-A, §IV-B, §IV. [19] M. Petersen and R. Tedrake (2023) Growing convex collision-free regions in configuration space using nonlinear programming. arXiv preprint arXiv:2303.14737. Cited by: Figure 2, §V-A, §VI. [20] J. Rodríguez-Pereira, E. Fernández, G. Laporte, E. Benavent, and A. Martínez-Sykora (2019) The steiner traveling salesman problem and its extensions. European Journal of Operational Research 278 (2), p. 615–628. External Links: ISSN 0377-2217, Document Cited by: §I. [21] M. Saha, T. Roughgarden, J. Latombe, and G. Sánchez-Ante (2006) Planning tours of robotic arms among partitioned goals. The International Journal of Robotics Research 25 (3), p. 207–223. External Links: Document Cited by: §VI. [22] I. A. Şucan, M. Moll, and L. E. Kavraki (2012) The Open Motion Planning Library. IEEE Robotics & Automation Magazine 19 (4), p. 72–82. External Links: Document Cited by: §VI. [23] K. Sundar and S. Rathinam (2025) A∗^* for bounding shortest paths in the graphs of convex sets. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 35, p. 260–268. External Links: Document Cited by: §I, §IV. [24] J. Tang and H. Ma (2026) GHOST: solving the traveling salesman problem on graphs of convex sets. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 36421–36428. Cited by: §I, §I, §I, §I, §IV-A, §IV-A, §IV-B, §V-B, Table I, Table I, Table I. [25] J. Tang, Z. Mao, L. Yang, and H. Ma (2025) Space-time graphs of convex sets for multi-robot motion planning. In 2025 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 8683–8690. External Links: Document Cited by: §I. [26] J. Tang, Z. Mao, L. Yang, and H. Ma (2026) Search-based spatiotemporal and multi-robot motion planning on graphs of space-time convex sets. arXiv preprint arXiv:2607.00444. Cited by: §I, §I, §I-A, §IV-A, §IV-B, §IV, §VII. [27] R. Tedrake and the Drake Development Team (2019) Drake: model-based design and verification for robotics. External Links: Link Cited by: §V. [28] Z. Wei, X. Luo, and C. Liu (2025) Hierarchical temporal logic task and motion planning for multi-robot systems. In Proceedings of Robotics: Science and Systems, Los Angeles, CA, USA. External Links: Document Cited by: §I, §VI. [29] P. Werner, R. Cheng, T. Stewart, R. Tedrake, and D. Rus (2025) Superfast configuration-space convex set computation on GPUs for online motion planning. In Proceedings of Robotics: Science and Systems, Los Angeles, CA, USA. External Links: Document Cited by: §VII. [30] S. You, G. Luna, and T. H. Summers (2026) A framework for motion planning with temporal logic precedence specifications via augmented graphs of convex sets. arXiv preprint arXiv:2606.00842. Cited by: §I. [31] S. Zhao, A. G. Philip, S. Rathinam, H. Choset, and Z. Ren (2025) CB-GCS: conflict-based search on the graph of convex sets for multi-agent motion planning. In 2025 IEEE 21st International Conference on Automation Science and Engineering (CASE), p. 2208–2214. External Links: Document Cited by: §I.