Tensor Search Methods For Vectorizing Motion Planning

Motion planning is one of the most important cornerstones in robotics. Through decades of algorithmic innovation, most classical methods remain inherently sequential and computationally expensive. This limitation is especially pronounced in high-dimensional or time-critical scenarios, where a robot must generate or evaluate many planning candidates in parallel—across different environments, task configurations, or dynamic model perturbations. While recent advances in hardware accelerators (e.g., GPUs, TPUs) and vectorized machine learning frameworks like JAX and PyTorch have revolutionized batched computation for learning and simulation, the planning community has yet to fully utilize these benefits. This thesis addresses this gap by introducing a new class of tensor search methods that reformulate motion planning as a series of fixed-shape tensor operations, thereby enabling full pipeline vectorization across multiple planning instances.

The first contribution of this thesis is Motion Planning via Optimal Transport (MPOT), a local trajectory optimization method built on zero-order updates via entropic optimal transport. By constructing a randomly rotated polytope around each trajectory waypoint and solving for the optimal barycentric projection using the Sinkhorn algorithm, MPOT produces vectorized trajectory updates without relying on gradients. Notably, the whole MPOT pipeline consists only of matrix multiplications. This formulation supports simultaneous optimization of hundreds of trajectories in parallel, enabling fast multi-trajectory refinement.

The second contribution is Global Tensor Motion Planning (GTMP), a global planner that leverages a multipartite graph representation to enable structured path sampling and batched graph search. Rather than constructing a search tree, GTMP samples a layered, complete graph with fixed topology and uses dynamic programming to solve batched shortest-path problems via tensor operations. The approach allows simultaneous planning over batches of start-goal pairs and randomized environments. A spline extension produces smooth paths via interpolation, and theoretical guarantees ensure probabilistic completeness under graph growth. GTMP demonstrates strong empirical performance compared to classical and GPU-based baselines, while maintaining compatibility with JAX’s vmap and jit compilation for efficient execution on modern GPUs/TPUs.

The third contribution is Model Tensor Planning (MTP), a fully vectorized framework for sampling-based Model Predictive Control (MPC) under online domain randomization. MTP introduces high-entropy control trajectory generation through structured tensor sampling. By sampling over randomized multipartite graphs and interpolating control trajectories with B-splines and Akima splines, MTP ensures smooth and globally diverse control candidates. To tame the noise of exploration, MTP utilizes a beta-mixing strategy that blends local and global samples within the modified Cross-Entropy Method (CEM) update, balancing control refinement and exploration. MTP supports robust sim-to-real transfer by solving multiple perturbed dynamics models in parallel at runtime and outperforms strong baselines on manipulation and locomotion tasks.

Together, these contributions suggest a general framework for tensorized planning that aligns with the core design principles of modern accelerator-based computing: static tensor shapes and batched execution, which further comes with differentiability inherited from the machine learning libraries, implying differentiable planning. This thesis demonstrates that by treating motion planning as tensor computation, we can unlock scalable, high-throughput solutions that not only match but often exceed the performance of traditional methods—while opening the door to new applications in synthetic data generation, policy learning, and real-time sim-to-real transfer.

Die Bewegungsplanung ist eines der wichtigsten Fundamente der Robotik. Trotz jahrzehntelanger algorithmischer Innovationen bleiben die meisten klassischen Methoden inhärent sequenziell und rechnerisch aufwendig. Diese Einschränkung wird besonders in hochdimensionalen oder zeitkritischen Szenarien deutlich, in denen ein Roboter viele Planungskandidaten parallel generieren oder bewerten muss – über unterschiedliche Umgebungen, Aufgabenstellungen oder dynamische Modellvarianten hinweg. Während aktuelle Fortschritte bei Hardwarebeschleunigern und vektorisierten Machine-Learning-Frameworks wie JAX und PyTorch die batched Verarbeitung für Lernen und Simulation revolutioniert haben, werden diese Vorteile in der Planungs-Community bislang kaum ausgeschöpft. Diese Dissertation schließt diese Lücke durch die Einführung einer neuen Klasse von Tensor-Suchmethoden, welche Bewegungsplanung als eine Abfolge fester Tensoroperationen reformulieren und dadurch eine vollständige Vektorisierung der gesamten Pipeline über viele Planungsinstanzen hinweg ermöglichen.

Der erste Beitrag dieser Arbeit ist Motion Planning via Optimal Transport (MPOT), eine Methode zur lokalen Trajektorienoptimierung, die auf Nullordnungs-Updates mittels entropischem Optimaltransport basiert. Durch die Konstruktion eines zufällig rotierten Polytops um jeden Trajektorienpunkt und die Berechnung der optimalen baryzentrischen Projektion mittels des Sinkhorn-Algorithmus erzeugt MPOT vektorisierte Trajektorienupdates ohne Gradienten. Bemerkenswert ist, dass die gesamte MPOT-Pipeline ausschließlich aus Matrixmultiplikationen besteht. Diese Formulierung erlaubt die gleichzeitige Optimierung von Hunderten Trajektorien in Parallelität und ermöglicht eine schnelle Multi-Trajektorien-Verfeinerung.

Der zweite Beitrag ist Global Tensor Motion Planning (GTMP), ein globaler Planer, der eine multipartite Graphstruktur nutzt, um strukturierte Pfadabtastung und batched Graphsuche zu ermöglichen. Anstelle eines Suchbaums erzeugt GTMP einen geschichteten, vollständigen Graphen mit fixer Topologie und verwendet dynamische Programmierung, um batched Kürzeste-Wege-Probleme mittels Tensoroperationen zu lösen. Dieser Ansatz ermöglicht gleichzeitige Planung über viele Start-Ziel-Paare und randomisierte Umgebungen hinweg. Eine Spline-Erweiterung erzeugt glatte Pfade durch Interpolation, und theoretische Garantien sichern probabilistische Vollständigkeit bei wachsender Graphgröße. GTMP zeigt eine starke empirische Leistung im Vergleich zu klassischen und GPU-basierten Methoden und ist vollständig kompatibel mit der vmap- und jit-Kompilation von JAX zur effizienten Ausführung auf modernen GPUs/TPUs.

Der dritte Beitrag ist Model Tensor Planning (MTP), ein vollständig vektorisierter Ansatz zur sampling-basierten Model Predictive Control (MPC) unter Online-Domain-Randomisierung. MTP ermöglicht die Erzeugung hochentropischer Steuertrajektorien durch strukturiertes Tensorsampling. Durch Sampling über randomisierte multipartite Graphen und Interpolation von Steuertrajektorien mittels B-Splines und Akima-Splines stellt MTP glatte und global diverse Steuerungskandidaten sicher. Zur Kontrolle des Explorationsrauschens wird eine beta-Mischstrategie verwendet, die lokale und globale Samples im modifizierten Cross-Entropy-Methoden-Update kombiniert und so zwischen Verfeinerung und Exploration ausbalanciert. MTP unterstützt robuste Sim-to-Real-Übertragung, indem es zur Laufzeit viele gestörte Dynamikmodelle parallel löst, und übertrifft starke Baselines in Manipulations- und Lokomotionsaufgaben.

Insgesamt schlagen diese Beiträge einen allgemeinen Rahmen für tensorisierte Planung vor, der mit den Grundprinzipien moderner beschleunigter Berechnung übereinstimmt: feste Tensorformen, batched Ausführung und – durch die ML-Bibliotheken – Differenzierbarkeit, was zukünftig differenzierbare Planung ermöglicht. Diese Arbeit zeigt, dass durch die Behandlung von Bewegungsplanung als Tensorberechnung skalierbare Hochdurchsatzlösungen möglich sind, die klassische Methoden nicht nur erreichen, sondern oft übertreffen – und zugleich neue Anwendungen in der synthetischen Datengenerierung, im Policy Learning und in der Echtzeit-Sim-to-Real-Übertragung eröffnen.