Monte Carlo Tree Search with Tensor Factorization for Optimization Problems in Robotics

The gist The proposed Tensor Train Tree Search (TTTS) leverages tensor factorization to exploit implicit correlations among different branches within the decision tree, significantly reducing both computation and storage overhead for Monte Carlo Tree Search in robotics

Problem Formulation and Motivation

Optimization problems in robotics, such as inverse kinematics, motion planning, and contact-rich manipulation, require addressing nonlinear kinematics, complex contact dynamics, long-horizon correlations, and multi-modal optimization landscapes. Existing methods often suffer from combinatorial complexity when applied naively to Monte Carlo Tree Search (MCTS), resulting in slow convergence and excessive storage space in high-dimensional domains. The paper proposes TTTS to address this limitation by leveraging tensor factorization to exploit the structure of the decision tree, aiming for a compact, linear-complexity representation.

Tensor Train Tree Search Mechanism

TTTS addresses the combinatorial complexity of MCTS by expressing the decision tree with linear complexity O(λN d), where λ is a scaling factor. This is achieved by representing a high-dimensional tensor of size O(Nd) using a sequence of third-order TT cores, denoted as Tb(i1,..., id) ≈ T1:,i1,: T2:,i2,: · · ·Td:,id: (4). The node value computation at depth j is efficiently computed via tensor contractions as qi[j] = N Xj+1 ij+1=0 · · · X Nd id=0 Qb(i1,..., ij,ij+1,..., id) ≈ Q1:,i1,: · · · Qj:,ij:, N Xj+1 ij+1=0 · · · X Nd id=0 Qj+1:,ij+1,: · · · Qd:,id: (5).

Efficiency and Theoretical Guarantees

The TT-based representation enables fully parallelized tree search with linear time and space complexity, supporting efficient decision-making. Proposition 1 establishes that TT structure enables exact MCTS node value computation in O(N dr2), an exponential improvement over the O(Nd) complexity of explicit tree evaluation. Furthermore, Proposition 2 establishes that the TT model provides a near-optimal surrogate, meaning its best solution deviates from the true global optimum by at most 2ϵ, where ϵ is the TT approximation error. Proposition 3 establishes that TTTS achieves the same asymptotic completeness as MCTS, meaning it asymptotically approaches the true global optimum given sufficient iterations.

Application and Experimental Results

Experimental results across inverse kinematics, motion planning around obstacles, legged robot manipulation, multi-stage motion planning, and bimanual whole-body manipulation demonstrate the efficiency of TTTS for generalized robot optimization over a diverse set of tasks. For instance, in 3-DOF and 7-DOF inverse kinematics with collision avoidance, TTTS recovers the global optimum while being faster than state-of-the-art baselines like TTGO. In motion planning around obstacles, TTTS achieves performance comparable to PRM+TO while requiring less computation time. For bimanual whole-body manipulation, TTTS achieves a 100% success rate against CMA-ES under similar computational budgets.

Conclusion and Future Work

TTTS successfully combines global search with local refinement, providing a compact TT representation that serves as an informative global guide for MCTS. The work suggests that low-rank TT approximations are effective when the decision tree is genuinely low-rank, and the combination with UCB-driven search ensures asymptotic global convergence. Future work includes extending TTTS to stochastic settings and exploring Quantized Tensor Train (QTT) decomposition for multi-resolution embedding. The paper also notes that integrating logic-geometric programming (LGP) can be supported by TTTS, offering improved computational efficiency over traditional hierarchical frameworks.

How it works

1. We propose a general formulation for optimization problems in robotics that can handle nonlinear dynamical systems, non-convex constraints, hybrid stateaction spaces, and multi-modal solution discovery.

2. We introduce the use of Tensor Train (TT) to approximate decision trees by exploiting their inherent structural redundancies, yielding a highly compact representation. This formulation enables fully parallelized tree search with linear time and space complexity, supporting efficient decision-making.

3. We provide theoretical analysis establishing TTTS’s computational efficiency and asymptotic completeness for global optimum identification.

Key Contributions

The main contributions are as follows:

1. We propose a general formulation for optimization problems in robotics that can handle nonlinear dynamical systems, non-convex constraints, hybrid stateaction spaces, and multi-modal solution discovery.

2. We introduce the use of Tensor Train (TT) to approximate decision trees by exploiting their inherent structural redundancies, yielding a highly compact representation. This formulation enables fully parallelized tree search with linear time and space complexity, supporting efficient decision-making.

3. We provide theoretical analysis establishing TTTS’s computational efficiency and asymptotic completeness for global optimum identification.

Comparison with Other Methods

TTGO relies on direct TT sampling instead of UCB-driven tree search, while MCTS operates without TT guidance. CMA-ES is a gradient-free, sampling-based method well-suited to robotic problems with nonlinear objectives and obstacle avoidance constraints. TTTS is the fastest among the successful methods, confirming that TT guidance substantially accelerates the search. The results highlight that TTGO does not achieve asymptotic convergence because it lacks UCB-driven exploration.

Ablation Studies

The ablation studies show that TT-Tree Initialization alone does not yield the global optimum, highlighting the limitations of using TT approximation by itself. However, after performing TT-Tree Search and Refinement, the final task-space error is zero, indicating that the globally optimal solution was successfully found. The comparison in real-world bimanual whole-body manipulation shows that TTTS achieves a 100% success rate against CMA-ES under similar computational budgets.

Conclusion

In this work, we present Tensor Train Tree Search (TTTS), which combines tensor factorization with Monte Carlo Tree Search for generalized robot optimization. The key idea is to represent the full decision tree as a high-dimensional tensor and obtain a compact TT approximation covering all candidate branches. This TT model serves as an informative global guide, in which node values at every layer are efficiently computed via TT contractions, concentrating early exploration near high-value regions. Furthermore, UCBdriven strategic search in MCTS is employed for asymptotic global convergence. We demonstrate the effectiveness of TTTS across diverse domains in simulation, including inverse kinematics, motion planning around obstacles, planar pushing with face switching, and legged robot manipulation. Furthermore, a real-world experiment on bimanual wholebody manipulation highlights the practical efficiency of TTTS in enabling fast sampling-based model predictive control.

References

Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. Advances in neural information processing systems, 30, 2017.

Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43.

Guillaume MJ B Chaslot, Mark HM Winands, and H Jaap van Den Herik. Parallel monte-carlo tree search. In Computers and Games: 6th International Conference, CG 2008, Beijing, China, September 29-October 1.

Xianyi Cheng, Sarvesh Patil, Zeynep Temel, Oliver Kroemer, and Matthew T Mason. Enhancing dexterity in robotic manipulation via hierarchical contact exploration. IEEE Robotics and Automation Letters (RA-L), 9(1):390–397.

Howie Choset, Kevin M Lynch, Seth Hutchinson, George A Kantor, and Wolfram Burgard. Principles of robot motion: theory, algorithms, and implementations. MIT press.

Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P. Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions. Foundations and Trends in Machine Learning, 9(4-5):249–429.

Remi Coulom. Efficient selectivity and backup operators in monte carlo tree search. In International conference on computers and games, pages 72–83.

Robin Deits and Russ Tedrake. Computing large convex regions of obstacle-free space through semidefinite programming.

1. This system can solve complex optimization problems like inverse kinematics, motion planning around obstacles, and contact-rich manipulation by formulating them over a general robot optimization formulation: max x∈omegax J(x), s.t. ϕ(x) ≤ 0, ψ(x) = 0 (Equation 3).

2. The system can handle hybrid state-action spaces and multi-modal solution discovery by discretizing the continuous domain into a finite grid, resulting in a d-layer decision tree with branching factor Nj (Section 4).

3. It can perform efficient global decision making by reducing the combinatorial complexity of Monte Carlo Tree Search from O(Nd) to linear time and space complexity, achieved through tensor factorization: TTTS leverages Tensor Train (TT) to reduce combinatorial complexity to linear complexity in both storage and computation (Section 5).

4. The system can achieve near-optimal initialization by using the compact TT model as a global prior: the TT model serves as an informative global guide, in which node values at every layer are efficiently computed via TT contractions, concentrating early exploration near high-value regions (Section 8).

5. It can guarantee asymptotic global convergence to the true optimum through a UCB-driven strategy: UCBdriven strategic search in MCTS is employed for asymptotic global convergence (Section 8), ensuring that given sufficient iterations, it asymptotically approaches the true global optimum.

6. The system can solve mixed-integer nonlinear programming (MINLP) problems by leveraging the joint modeling of discrete and continuous variables: TTTS naturally supports the joint modeling of logic and geometric variables, offering improved computational efficiency over traditional hierarchical frameworks (Section 8).

7. The system can support real-time Model Predictive Control (MPC) for bimanual whole-body manipulation by rapidly finding high-quality solutions: TTTS first approximates the decision tree in TT format, which accelerates convergence toward promising regions, making it suitable for real-time MPC.