Source-linked AI summary
Anytime Global Tensor Motion Planning
Sai Coumar, An T. Le, Zachary Kingston
TL;DR
Motion planning needs efficient exploration of cluttered spaces and batches of topologically diverse routes, but sequential planners lack coverage guarantees. The paper generalizes GTMP with black-box local planners and introduces fixed-budget random restarts and growing-budget informed expansion. The resulting methods provide almost-sure homotopy-class coverage or cost convergence, while matching strong manipulation results and producing diverse 2D navigation solutions.
Problem
Sequential motion planners couple global exploration with local connection failure, and existing topological planners lack guarantees that all relevant homotopy classes are covered.
Method
The paper generalizes GTMP by realizing adjacent-layer edges with arbitrary black-box local planners and adds fixed-budget random-restart and growing-budget informed-expansion policies.
Results
The methods cover every δ-clear bounded-length homotopy class under the stated theory, achieve almost-sure class coverage or cost convergence, and match strong manipulation performance while producing diverse navigation batches.
Takeaways & Limitations
Anytime-GTMP supports batches of topologically diverse solutions, while AO-GTMP targets asymptotic cost optimality through informed expansion on a layered DAG.
Abstract
from arXiv · showhide
Global Tensor Motion Planning (GTMP) solves motion planning with batched tensor operations over a layered multipartite graph. We generalize GTMP so that adjacent-layer edges are realized by any black-box local planner (e.g., linear interpolation, splines, sampling-based planning, trajectory optimization, or generative sampling). We provide two anytime policies on top of this generalization: Anytime GTMP with random restarts at a fixed budget, which covers every homotopy class almost surely, and AO-GTMP with informed expansion with growing budgets, which converges to the optimal cost. We prove that a single sampled graph covers every endpoint-fixed homotopy class admitting a \(δ\)-clear representative of bounded length. We also prove that additional samples per layer reduce the per-layer miss probability exponentially, whereas stronger local planners reduce the required layer count only sublinearly. On manipulation benchmarks the method matches state-of-the-art performance, and on 2D navigation it returns batches of topologically diverse solutions, while the informed baselines concentrate on one or two classes.
I. INTRODUCTION
The paper extends tensor-parallel motion planning to support diverse topological alternatives through black-box local planners, with theoretical coverage guarantees and distinct anytime policies. Experiments report diverse navigation solutions and competitive manipulation performance.
- Classical planners couple global exploration and local connection failures in sequential searches, while topologically diverse alternatives benefit navigation, manipulation, and task-level planning.
- GTMP samples intermediate vertex layers and realizes all adjacent-layer edges in batch-parallel tensor operations, evaluating many candidate paths simultaneously.
- The generalized framework accepts black-box local planners, including interpolation, sampling-based planning, trajectory optimization, and generative sampling.
- A single sampled graph covers every endpoint-fixed homotopy class admitting a δ-clear representative of bounded length.
- Anytime-GTMP uses fixed-budget random restarts for almost-sure class coverage, whereas AO-GTMP uses growing-budget informed expansion for almost-sure cost convergence.
- On 2D navigation, Anytime-GTMP returns topologically diverse solution batches; on 6–8 DoF manipulation, variants match state-of-the-art performance and attain the lowest mean path cost on 15 of 21 problems within 60 seconds.
B. Generalized GTMP Graph
The generalized GTMP graph samples vertices in intermediate layers, connects complete adjacent-layer bipartite pairs with a black-box local planner, and searches feasible chains in the resulting layered graph.
- A local planner receives two configurations, an effort budget, and a path-length limit, then either fails or returns a continuous collision-free path inside the query ellipsoid.
- The query ellipsoid contains configurations whose summed distances to the endpoints do not exceed the length limit, and paths within that limit remain inside it.
- The generalized graph includes an adjacent-layer edge exactly when the local-planner call succeeds, storing the returned path and its cost.
- A graph chain selects one vertex from each layer and requires every adjacent pair to be realized as an edge.
- A graph covers a homotopy class when one chain’s concatenated local paths is homotopic to a representative of that class.
IV. METHOD
The method builds a layered directed acyclic graph whose adjacent-layer edges are generated by a black-box local planner, then searches it with batched dynamic programming, optionally augmented by homotopy-class labels.
- Graph construction and search: Each local-planner call assigns a realized edge cost, while absent edges receive infinite cost.Admissible costs include path length and weighted length under the stated conditions.
- Graph construction and search: GTMP connects only adjacent layers, making the realized graph a directed acyclic graph searchable by value iteration.The shortest feasible chain is recovered through layered dynamic programming.
- Graph construction and search: The recursion computes minimum cost-to-go from each vertex by minimizing the current edge cost plus the next-layer cost.The terminal goal has zero cost-to-go.
- Implementation: The shared implementation computes cost matrices with the local planner and supports optional samples and value-tensor warm starts.The gtmp subroutine accepts start and goal data, a local-planner budget, and optional sample inputs.
- Class-aware search: Anytime-GTMP augments dynamic-programming states with homotopy-class labels to return a minimum-cost chain in every realized class.The class-aware sweep uses a class label accumulated along path concatenation and can be implemented as a batched tensor contraction.
C. Two Iteration Policies
The two policies share a feasibility-first and anytime workflow but differ in how they schedule graph budgets: fixed budgets for diversity versus growing budgets for cost optimality.
- Shared workflow: Both policies first run GTMP until a feasible chain is found, then continue under their selected anytime schedule.The first feasible path seeds either the class archive or the AO cost bound.
- Budget schedules: Anytime-GTMP holds M, N, and s fixed to target homotopy-class diversity.Its fixed-budget iterations support repeated exploration.
- Budget schedules: AO-GTMP holds s fixed while growing Mν and Nν monotonically to target cost optimality.The two policies therefore differ only in their budget schedules.
- Computational cost: Both policies incur Θ(MνNν^2) candidate-edge work, dominated by inter-layer edge evaluations.The local-planner calls dominate the search cost.
D. Anytime-GTMP
Anytime-GTMP repeatedly samples and evaluates layered graphs at fixed budgets, maintaining the lowest-cost path found for each homotopy class and selecting the best archived path overall.
- Stage operation: Each stage draws a fresh layered sample set, realizes edges with local planners, and runs class-augmented dynamic programming.All resulting solutions are inserted into a class-indexed archive.
- Archive update: The archive Aν stores the lowest-cost path per homotopy class, initialized with A0 ≡ ∅.The anytime output is the lowest-cost path across all archived classes.
- Guarantee: Any positive per-stage coverage probability yields almost-sure eventual coverage of the homotopy classes.This is the stated guarantee of Theorem 2.
E. AO-GTMP
AO-GTMP grows graph budgets under informed sampling, using epochs to manage changing layer grids, and achieves almost-sure convergence of the best cost to the optimum.
- Informed expansion: AO-GTMP holds s fixed and grows Mν and Nν monotonically while sampling within the informed set defined by the current cost bound.The informed set is an ellipsoid constrained by the available solution cost.
- Sample schedule: Within each epoch, M is fixed and Nν increases until the per-layer hit probability saturates; larger M begins a new epoch.Epochs account for shifts in the uniform grid as the layer count grows.
- Guarantee: Cost convergence cν → c* a.s. follows from Theorem 3.The guarantee assumes the stated optimal-path, planner, sampling-region, and schedule conditions.
- Planner reliability: The planner reach Λs(τ) is the longest edge solved with probability at least 1−τ under the local planner's success profile.This quantity links local-planner reliability to the expansion schedule.
V. THEORETICAL ANALYSIS
The analysis establishes when sampled waypoint chains remain homotopic to a δ-clear reference path and models local-planner success probabilistically. Coverage depends on sampling every layer and successfully connecting consecutive samples within a clearance-preserving length limit.
- Coverage conditions: Coverage reduces to hitting a reference-neighborhood waypoint set in every layer and connecting each consecutive pair with the local planner.The waypoint construction uses paths through the reference whose length is at most L/(M + 1) + 2r and clearance at least δ − r.
- δ-tube homotopy: A chain of waypoint-to-waypoint local-planner paths remains homotopic to the reference when each edge stays within the lemma’s ellipsoid length limit.For straight-line edges, the condition weakens to L/(M + 1) + r < δ.
- Local planner model: The local-planner assumption requires a non-increasing success profile q_s(ℓ) that approaches 1 as effort budget s grows.Whenever endpoints admit a ρ-clear path of length at most ℓ − ς, LP succeeds with probability at least q_s(ℓ).
- Local planner model: The clearance level is set to ρ = δ − r, because planners cannot maintain a uniform success rate through corridors of vanishing width.RRT-Connect confined to the query ellipsoid qualifies under the stated profile and is short-range exact.
A. Coverage from One Sampled Graph
Theorem 1 shows that one sampled layered graph covers a target homotopy class with probability approaching one as sampling and local-planner budgets increase. The same construction covers every δ-clear bounded-length class simultaneously.
- One-class coverage: A layer misses its waypoint region with probability at most (1 − p_m)^N, and a union bound aggregates misses across the M layers.If every layer is hit, each of the M + 1 local-planner calls succeeds with probability at least q_s(ℓ_M(r)).
- All-class coverage: The waypoint construction covers every δ-clear homotopy class of bounded length at once because only finitely many such endpoint-fixed classes exist.Additional local effort has diminishing benefit because the planner reach Λ_s(τ) grows sublinearly in local budget.
B. Anytime Policies
Anytime-GTMP repeatedly builds graphs and archives solutions, while AO-GTMP expands informed layered graphs with growing budgets. The former covers classes almost surely, and the latter converges almost surely to optimal cost under its assumptions.
- Class-aware search: Class-augmented value iteration computes a minimum-cost chain separately for every realized homotopy class in Θ(MN^2|K|) time.The dynamic-programming state combines the current vertex with a compositional class label.
- Anytime-GTMP: Anytime-GTMP has positive per-stage coverage probability p_cov and therefore enters every δ-clear class into its monotone archive almost surely.The expected number of stages before the first covering stage is at most 1/p_cov.
- Anytime-GTMP: Fresh independent stages make the probability that the first K stages all miss a class at most (1 − p_cov)^K.Borel–Cantelli then yields infinitely many covering stages almost surely.
- AO-GTMP: AO-GTMP fixes the local-planner budget and grows informed layer and sample budgets, treating the procedure as an informed AO-x instance on a layered DAG.The guarantee applies to path length and extends to weighted lengths.
- AO-GTMP: Under a δ-clear optimal path, short-range exactness, informed sampling coverage, and the stated fresh-sample schedule, the best path length c_ν converges to c* almost surely.The proof makes waypoint balls increasingly fine and reduces failure to the probability that some ball remains unhit.
- Empirical policy behavior: Figure 2 evaluates success-rate eCDFs over a 60-second budget on a logarithmic scale, highlighting iteration speed and local-planner budget allocation.The caption specifically identifies Anytime-GTMP SEV as iterating quickly when its local planner budget is low.
VI. EXPERIMENTS
Experiments use two local planners on specified hardware: straight-line collision-checked edges and RRT-Connect.
- Experimental setup: Experiments ran on an AMD Ryzen Threadripper PRO 5965WX 24-core CPU with 32 GB RAM and an NVIDIA RTX 4090.
- Experimental setup: Each policy was evaluated with straight-line edges using collision checking and with RRT-Connect.These are labeled SEV and RRTC, respectively.
A. Feasibility and Cost
On manipulation benchmarks, GTMP variants achieve competitive final feasibility and path costs, while local-planner effort shows diminishing returns. The method also exposes a practical trade-off between topological diversity and informed cost optimization, with broader evaluation still needed for high-DoF topology.
- Benchmark feasibility and cost: Within the full time budget, Anytime-GTMP (SEV) matches FCIT’s final success rate of approximately 85%.GTMP variants are rarely fastest to a first solution because of layered graph construction and local planner evaluation overhead.
- Benchmark feasibility and cost: AO-GTMP matches or beats the lowest mean path cost most often across Panda, UR5, and Fetch problems.It does so on 5/7 Panda, 7/7 UR5, and 5/7 Fetch problems, compared with 6/7, 3/7, and 3/7 for AORRTC.
- Local-planner budget: Path cost improves until roughly 400 to 600 RRT-Connect iterations per edge and then flattens.Under a fixed planning budget, moderate local effort with more global sampling therefore outperforms heavy local effort.
- Topological diversity: Anytime-GTMP covers the highest average number of homotopy classes on the 2D navigation benchmarks, while baselines return one path per query.The evaluation records path events over a 60 s budget and labels them with homotopy invariants.
- Topological diversity: AO-GTMP sample diversity spikes to 0.6 after the first feasible solution, then falls as the normalized cost bound tightens.The shrinking informed set narrows exploration toward near-optimal solutions, trading diversity for optimality.
- Scope boundary: Topological coverage has been evaluated on 2D navigation, while high-DoF manipulation remains a future evaluation target because homotopy classes are harder to verify there.The authors identify this as a scope boundary for validating topological coverage.