New Branch-and-Bound Method Speeds Robot Path Planning Through Convex Regions

A team of researchers has introduced a new algorithmic framework for planning robot trajectories through complex environments made up of convex regions, according to a preprint posted to arXiv. The paper, submitted by lead author Jing Tao Tang and colleagues, tackles what the authors call the Steiner Traveling Salesman Problem on Graphs of Convex Sets (Steiner-TSP on GCS).

The problem is essentially a routing puzzle: a robot must find the cheapest possible closed loop that passes through a set of required convex regions, while also being allowed to pass through optional "transit" regions and revisit locations if that helps reduce cost. Convex sets — regions where a straight line between any two points inside stays inside the region — are a common way to represent free, obstacle-free space or valid poses in motion planning. Because the space of possible paths through such a network is effectively infinite, solving the problem exactly is computationally difficult.

To address this, the authors propose a unified branch-and-bound search that explores partial paths, or "rooted walk prefixes," while using two mathematical bounding techniques to prune the search space. One bound tracks the accumulated cost of the path already committed to, while the other — a "cut-separated connected-flow relaxation" — estimates the minimum remaining cost needed to visit all outstanding required regions and return to the starting point. Under the assumption that all costs are positive, the paper proves that a best-first version of the search always terminates in finitely many steps for any solvable instance, even without a starting guess (an "incumbent" solution), while a depth-first version terminates once such a guess exists. The method also lets users specify a tolerance factor epsilon, giving a certified guarantee that the solution found is no worse than epsilon times the true optimal cost.

The researchers demonstrate the approach on a mobile-manipulator inspection task, where the robot must jointly decide which sensing mode to use, in what order to visit targets, and what continuous trajectory to follow — all while respecting task ordering rules expressed using linear temporal logic over finite traces (LTL_f), a formal language for specifying sequences of actions and constraints over time.

In benchmark testing, both the best-first and depth-first versions of the algorithm found feasible solutions on every test instance within 30 seconds, with mean certified optimality gaps of 28.1% and 29.7% respectively — meaning the solutions found were provably within roughly that percentage of the best possible answer. By comparison, two recent baseline methods used for comparison managed to find solutions on only about half of the same benchmark instances, according to the paper.

While the work is theoretical and benchmark-based rather than a hardware demonstration, it addresses a practical bottleneck for robots that need to plan inspection routes, sensing decisions, and movement trajectories simultaneously in cluttered or structured environments — a combination that has historically been difficult to solve efficiently and with guaranteed solution quality.