Unified Branch-and-Bound Search for the Steiner Tra...

Unified Branch-and-Bound Search for the Steiner Tra... | AI Research

Key Takeaways

The Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS) involves finding the lowest-cost closed trajectory that visits a specific...
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.
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.
Researchers Jingtao Tang and Hang Ma propose a unified branch-and-bound search algorithm to solve this problem, which is NP-hard due to the coupling of discrete route selection and continuous trajectory optimization.

Paper AbstractExpand

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

The Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS) involves finding the lowest-cost closed trajectory that visits a specific subset of required locations while allowing for optional transit and revisits. Researchers Jingtao Tang and Hang Ma propose a unified branch-and-bound search algorithm to solve this problem, which is NP-hard due to the coupling of discrete route selection and continuous trajectory optimization.

Solving the Steiner-TSP on GCS

The Steiner-TSP on GCS requires selecting a visitation order for target regions and determining the continuous trajectory between them. Because the graph allows for vertex revisits, the number of potential walks is infinite, making it difficult to find an optimal solution. The authors address this by formalizing the problem and creating a search tree that represents every finite rooted walk. Their approach avoids the high cost of performing full trajectory optimization at every step of the search by using a combination of lower-bound costs and a connected-flow relaxation.

How the Search Works

The proposed algorithm uses a branch-and-bound search over rooted walk prefixes. It maintains a "Frontier" of potential paths and uses two primary tools to prioritize and prune the search:

Additive lower-bound-graph costs: These bound the cost of the path already committed to by the search.
Cut-separated connected-flow relaxation: This provides a lower bound on the cost required to visit all remaining targets and return to the starting point.
By summing these values, the algorithm can estimate the total cost of a path without needing to solve the full continuous trajectory optimization until a complete, target-covering walk is identified. The search can be configured for either best-first or depth-first traversal, and it includes a mechanism to provide an $\epsilon$-optimal solution, where the cost is guaranteed to be within a user-specified factor of the global optimum.

Performance and Results

In testing, the authors evaluated their method on 180 benchmark instances. Both the best-first and depth-first traversal strategies successfully found feasible solutions for all instances within a 30-second time limit. The mean certified optimality gaps were 28.1% and 29.7%, respectively. The authors note that two existing baseline methods were only able to find solutions for approximately half of the same benchmark instances.

Practical Applications

The researchers demonstrated the utility of their approach through a mobile-manipulator inspection task. This application required the robot to jointly select sensing modes, determine the order of visitation for inspection targets, and plan continuous trajectories. The system also successfully incorporated action precedences expressed in linear temporal logic over finite traces (LTL$_f$), showing that the method can handle complex, multi-layered planning requirements in robotics.