PaperlayerView exact revision on arXiv

Source-linked AI summary

Anytime Global Tensor Motion Planning

Sai Coumar, An T. Le, Zachary Kingston

arXiv:2608.25830v1cs.RO

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.

    Source: §I · p. 1

  • 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.

    Source: §I · p. 1, §IV · p. 3, C. Two Iteration Policies · p. 4

  • 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.

    Source: §I · p. 1, §VII · p. 6

  • Takeaways & Limitations

    Anytime-GTMP supports batches of topologically diverse solutions, while AO-GTMP targets asymptotic cost optimality through informed expansion on a layered DAG.

    Source: §I · p. 1

Abstract

from arXiv · show

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.Source: §I · p. 1
  • GTMP samples intermediate vertex layers and realizes all adjacent-layer edges in batch-parallel tensor operations, evaluating many candidate paths simultaneously.Source: §I · p. 1
  • The generalized framework accepts black-box local planners, including interpolation, sampling-based planning, trajectory optimization, and generative sampling.Source: §I · p. 1, §II · p. 1
  • A single sampled graph covers every endpoint-fixed homotopy class admitting a δ-clear representative of bounded length.Source: §I · p. 1, §II · p. 2
  • 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.Source: §I · p. 1
  • 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.Source: §I · p. 1

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.Source: B. Generalized GTMP Graph · pp. 2–3
  • 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.Source: B. Generalized GTMP Graph · p. 3
  • The generalized graph includes an adjacent-layer edge exactly when the local-planner call succeeds, storing the returned path and its cost.Source: B. Generalized GTMP Graph · p. 3
  • A graph chain selects one vertex from each layer and requires every adjacent pair to be realized as an edge.Source: B. Generalized GTMP Graph · p. 3
  • A graph covers a homotopy class when one chain’s concatenated local paths is homotopic to a representative of that class.Source: B. Generalized GTMP Graph · p. 3

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

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.Source: B. Graph Search on the Layered DAG · p. 3

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.Source: B. Graph Search on the Layered DAG · p. 4

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.Source: C. Two Iteration Policies · p. 4

Budget schedules

  • Anytime-GTMP holds M, N, and s fixed to target homotopy-class diversity.Its fixed-budget iterations support repeated exploration.Source: C. Two Iteration Policies · p. 4
  • 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.Source: C. Two Iteration Policies · p. 4

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.Source: C. Two Iteration Policies · p. 4

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.Source: D. Anytime-GTMP · p. 4

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.Source: D. Anytime-GTMP · p. 4

Guarantee

  • Any positive per-stage coverage probability yields almost-sure eventual coverage of the homotopy classes.This is the stated guarantee of Theorem 2.Source: D. Anytime-GTMP · p. 4

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.Source: E. AO-GTMP · p. 4

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.Source: E. AO-GTMP · p. 4

Guarantee

  • Cost convergence cν → c* a.s. follows from Theorem 3.The guarantee assumes the stated optimal-path, planner, sampling-region, and schedule conditions.Source: E. AO-GTMP · p. 4

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.Source: E. AO-GTMP · p. 4

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.Source: §V · p. 4

δ-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 < δ.Source: §V · p. 4

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(ℓ).Source: §V · p. 5
  • 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.Source: §V · p. 5

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)).Source: A. Coverage from One Sampled Graph · p. 5

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.Source: A. Coverage from One Sampled Graph · p. 5

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.Source: B. Anytime Policies · p. 5

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.Source: B. Anytime Policies · p. 5
  • 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.Source: B. Anytime Policies · p. 5

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.Source: B. Anytime Policies · p. 5
  • 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.Source: B. Anytime Policies · pp. 5–6

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.Source: Figure 2 · p. 6

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.Source: §VI · p. 6
  • Each policy was evaluated with straight-line edges using collision checking and with RRT-Connect.These are labeled SEV and RRTC, respectively.Source: §VI · p. 6

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.Source: A. Feasibility and Cost · p. 6
  • 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.Source: A. Feasibility and Cost · p. 6

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.Source: A. Feasibility and Cost · p. 6

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.Source: B. Topological Diversity · p. 6
  • 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.Source: B. Topological Diversity · p. 6

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.Source: §VII · p. 6

Related papers

Loading 2608.25830v1…