💻 computer science

Anytime Global Tensor Motion Planning

This paper generalizes Global Tensor Motion Planning to support any black-box local planner and introduces two anytime policies—one ensuring coverage of all homotopy classes and another converging to optimal cost—while demonstrating that additional sampling exponentially reduces failure probability and achieving state-of-the-art performance on manipulation and navigation benchmarks.

Original authors: Sai Coumar, An T. Le, Zachary Kingston

Published 2026-08-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sai Coumar, An T. Le, Zachary Kingston

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of robotics, moving a machine from point A to point B is rarely as simple as drawing a straight line. The environment is often cluttered with obstacles, and the machine itself might have many moving parts, creating a vast, complex space of possible positions. To navigate this, robots use motion planners, which are algorithms that search for a safe route. Traditionally, these planners work like a hiker exploring a dense forest: they take one step, check if it is safe, and then try to connect to the next step. If they get stuck or hit a dead end, they must backtrack and try a different direction. This sequential approach works well for finding a single path, but it often misses other valid routes that might be safer, shorter, or simply different. In many real-world tasks, such as a robot arm picking up an object from different angles or a self-driving car choosing between various lanes around a construction zone, having a variety of distinct options is just as important as finding one working solution.

Researchers have developed a new approach called Anytime Global Tensor Motion Planning to solve this problem more effectively. Instead of building a path step-by-step, this method treats the entire journey as a series of layers, like rungs on a ladder, and evaluates thousands of potential connections all at once. The core idea is to sample many possible positions at each stage of the journey and then use a flexible tool to try connecting every position in one layer to every position in the next. This tool, known as a local planner, can be as simple as drawing a straight line or as complex as a sophisticated algorithm that twists and turns to avoid obstacles. By running these connections in massive batches, the system can explore the entire landscape of possibilities simultaneously rather than wandering through it one path at a time.

The researchers demonstrated that this method can guarantee coverage of every distinct type of route available in a given space. Imagine a space where a robot can go around an obstacle on the left or on the right; these are two fundamentally different types of paths that cannot be transformed into one another without hitting the obstacle. The new method proves that if a safe path exists for a specific type of route, the system will find it, provided the robot has enough time and computing power. They showed that by simply increasing the number of sample points at each layer, the chance of missing a valid route drops dramatically, much faster than if one were to simply make the local connection tool more powerful. This means the system is highly efficient at finding diverse solutions without needing to be overly complex in its individual steps.

The team tested two specific strategies using this framework. The first strategy, called Anytime-GTMP, keeps the computing resources fixed and repeatedly restarts the search with new random samples. This approach is designed to find a wide variety of different routes, ensuring that the robot has a full menu of topologically distinct options to choose from. In tests on two-dimensional maps, this method successfully returned batches of diverse solutions, exploring different corridors and paths around obstacles, whereas other standard methods tended to focus on just one or two routes. The second strategy, AO-GTMP, gradually increases the number of samples and the complexity of the search over time. This approach is designed to find the single best, most efficient path, converging on the optimal solution as the search continues.

When applied to complex robotic arms with six to eight moving joints, the new method performed as well as the best existing systems in terms of finding a solution quickly. More importantly, it often found paths that were cheaper or more efficient than those found by other top-tier planners. The researchers found that while a very powerful local connection tool can sometimes solve a problem in a single step, it is often more effective to use a moderate connection tool combined with a large number of global samples. This balance allows the system to explore the big picture effectively. The work confirms that by organizing the search into layers and using batch processing, robots can be given a much richer understanding of their environment, allowing them to choose not just a path, but the right path for the task at hand.

Technical Summary: Anytime Global Tensor Motion Planning

Problem Definition

The paper addresses motion planning in cluttered, high-dimensional configuration spaces ( $C \subseteq \mathbb{R}^d$ ). The core challenge is finding connected components of the free space ( $C_{free}$ ) and connecting start ( $q_0$ ) and goal ( $q_g$ ) configurations. Classical sampling-based planners often couple global exploration with local connection attempts, leading to inefficiencies in narrow passages and a tendency to return a single feasible path rather than topologically diverse alternatives.

The authors define a $\delta$ -clear path as one maintaining a minimum distance $\delta$ from obstacles. A homotopy class is a set of paths with fixed endpoints that can be continuously deformed into one another without intersecting obstacles. The goal is to guarantee coverage of all $\delta$ -clear homotopy classes of bounded length and, optionally, converge to the optimal cost within those classes.

Methodology

The paper generalizes Global Tensor Motion Planning (GTMP) [5] by decoupling the global sampling structure from the local connection mechanism.

1. Generalized GTMP Graph

The method constructs a layered multipartite graph where:

Layers: The path is discretized into $M+2$ layers (including start and goal). Intermediate layers $V_m$ contain $N$ sampled configurations.
Edges: Edges exist only between adjacent layers ( $V_m$ to $V_{m+1}$ ).
Black-Box Local Planner (LP): Unlike the original GTMP which used straight-line interpolation, the generalized version allows any randomized local planner (e.g., linear interpolation, splines, RRT-Connect, trajectory optimization, or generative samplers) to realize edges. An edge $(u, v)$ is realized if the LP finds a collision-free path within a query ellipsoid $E(u, v; \ell)$ .
Sampling Strategy: Samples are drawn via a mixture: with probability $1/2$ from a uniform measure on the free space (ensuring theoretical coverage), and $1/2$ from a heuristic sampler (potentially informed by cost bounds).

2. Graph Search

The realized graph is a Directed Acyclic Graph (DAG). The shortest feasible chain is found via value iteration (dynamic programming) in $O(MN^2)$ time.

Class-Augmented Search: To track topological diversity, the state is augmented with a homotopy label $\kappa$ (e.g., h-signature). The value iteration computes the minimum cost for every realized homotopy class simultaneously.

3. Two Anytime Iteration Policies

The framework supports two distinct policies for iterating the graph construction:

Anytime-GTMP (Fixed Budget, Random Restarts):
- Keeps the graph parameters $(M, N, s)$ fixed.
- Performs random restarts, generating new graphs with fresh samples.
- Maintains an archive of the lowest-cost path found for each discovered homotopy class.
- Goal: Achieve almost-sure coverage of all $\delta$ -clear homotopy classes.
AO-GTMP (Informed Expansion, Growing Budget):
- Keeps the local planner budget $s$ fixed but monotonically increases the number of layers $M$ and samples $N$ .
- Samples are drawn from an informed set (an ellipsoid defined by the current best cost bound), shrinking as the cost improves.
- Goal: Achieve almost-sure convergence to the optimal path cost.

Key Contributions and Theoretical Guarantees

1. Generalization and Coverage

The authors prove that a single sampled graph covers every endpoint-fixed homotopy class admitting a $\delta$ -clear representative of bounded length. Specifically, the probability of coverage tends to 1 as the number of samples $N$ and the local planner budget $s$ increase for a fixed number of layers $M$ .

Tube Argument: A chain of samples within a tube of radius $r < \delta$ around a reference path guarantees homotopy to that reference.
Probability Bounds: The probability of missing a class decreases exponentially with the number of samples $N$ per layer. Conversely, increasing the local planner budget $s$ only reduces the required number of layers $M$ sublinearly.

2. Convergence Guarantees

Anytime-GTMP: Proven to cover every $\delta$ -clear class almost surely given a fixed budget and random restarts (Theorem 2).
AO-GTMP: Proven to converge to the optimal cost $c^*$ almost surely as $M, N \to \infty$ (Theorem 3), applying the AO-x meta-algorithm framework to a layered DAG.

3. Algorithmic Efficiency

The method leverages tensor operations to parallelize edge realization and value iteration. The search complexity is dominated by the number of inter-layer edge evaluations ( $O(MN^2)$ ), which is efficiently handled via batched tensor contractions.

Experimental Results

1. Manipulation Benchmarks (MotionBenchMaker)

Evaluated on 6–8 DoF manipulators (Panda, UR5, Fetch):

Feasibility: Anytime-GTMP (using straight-line edges) achieved a final success rate (~85%) matching the state-of-the-art FCIT planner, though it was slower to find the first solution due to graph construction overhead.
Cost: The variants matched or outperformed the lowest mean path cost in the majority of solved problems (e.g., 7/7 UR5 problems for AO-GTMP) within a 60-second budget.
Local Planner Impact: Experiments showed diminishing returns for increasing the local planner budget (RRT-Connect iterations) beyond ~400–600 iterations, suggesting that moderate local effort combined with extensive global sampling is more effective under fixed time budgets.

2. 2D Navigation

Evaluated on street-view heightmaps:

Topological Diversity: Anytime-GTMP returned batches of topologically diverse solutions, covering the highest average number of homotopy classes.
Comparison: In contrast, informed baselines (like AO-GTMP and FCIT) concentrated samples on one or two near-optimal classes, failing to explore alternative topological routes.
Trade-off: The results empirically demonstrate the trade-off: random restarts (Anytime-GTMP) maximize diversity, while informed expansion (AO-GTMP) maximizes optimality.

Significance and Claims

The paper claims to provide the first motion planning framework that:

Generalizes GTMP to accept any black-box local planner while maintaining rigorous theoretical guarantees.
Guarantees Homotopy Coverage: Proves that a single graph covers all $\delta$ -clear homotopy classes of bounded length with probability approaching 1 as $N$ and $s$ increase, a property not guaranteed by sequential roadmap construction methods.
Offers Distinct Anytime Guarantees: Explicitly separates the objectives of "diversity" (via random restarts) and "optimality" (via informed expansion), providing formal proofs for both convergence modes.
Scalability: Demonstrates that tensor-based parallelization allows the method to match state-of-the-art performance on high-dimensional manipulation tasks while providing unique capabilities in generating topologically diverse solution sets for navigation.

The authors conclude that the method effectively balances global exploration and local connection, offering a flexible tool for applications requiring either diverse alternatives or optimal paths.