L4KDE: Learning for KinoDynamic Tree Expansion

• URL: http://arxiv.org/abs/2203.00975v2
• Date: Sun, 17 Sep 2023 11:54:04 GMT
• Title: L4KDE: Learning for KinoDynamic Tree Expansion
• Authors: Tin Lai, Weiming Zhi, Tucker Hermans, Fabio Ramos
• Abstract summary: We present the Learning for KinoDynamic Tree Expansion (L4KDE) method for kinodynamic planning. L4KDE uses a neural network to predict transition costs between queried states, which can be efficiently computed in batch. We empirically demonstrate the significant performance improvement provided by L4KDE on a variety of challenging system dynamics.
• Score: 28.63535068379981
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the Learning for KinoDynamic Tree Expansion (L4KDE) method for kinodynamic planning. Tree-based planning approaches, such as rapidly exploring random tree (RRT), are the dominant approach to finding globally optimal plans in continuous state-space motion planning. Central to these approaches is tree-expansion, the procedure in which new nodes are added into an ever-expanding tree. We study the kinodynamic variants of tree-based planning, where we have known system dynamics and kinematic constraints. In the interest of quickly selecting nodes to connect newly sampled coordinates, existing methods typically cannot optimise to find nodes that have low cost to transition to sampled coordinates. Instead, they use metrics like Euclidean distance between coordinates as a heuristic for selecting candidate nodes to connect to the search tree. We propose L4KDE to address this issue. L4KDE uses a neural network to predict transition costs between queried states, which can be efficiently computed in batch, providing much higher quality estimates of transition cost compared to commonly used heuristics while maintaining almost-surely asymptotic optimality guarantee. We empirically demonstrate the significant performance improvement provided by L4KDE on a variety of challenging system dynamics, with the ability to generalise across different instances of the same model class, and in conjunction with a suite of modern tree-based motion planners.

Related papers

• WorldTree: Towards 4D Dynamic Worlds from Monocular Video using Tree-Chains [13.122536259577453]
  WorldTree is a unified framework that enables coarse-to-fine optimization based on inheritance-based partition tree structure for hierarchical temporal decomposition.<n>Our proposed method achieves 8.26% improvement of LPIPS on NVIDIA-LS and 9.09% improvement of reconstruction on DyCheck compared to the second-best method.
  arXiv  Detail & Related papers  (2026-02-12T11:38:35Z)
• Neural Ising Machines via Unrolling and Zeroth-Order Training [3.5808917363708743]
  We propose a data-driven for NP-hard Ising and Max-Cut optimization that learns the update rule of an iterative dynamical system.<n>We call this approach a long neural network parameterized Issing machine (NPIM)
  arXiv  Detail & Related papers  (2026-01-30T20:51:51Z)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)
• Hierarchical Quantized Diffusion Based Tree Generation Method for Hierarchical Representation and Lineage Analysis [49.00783841494125]
  HDTree captures tree relationships within a hierarchical latent space using a unified hierarchical codebook and quantized diffusion processes.<n> HDTree's effectiveness is demonstrated through comparisons on both general-purpose and single-cell datasets.<n>These contributions provide a new tool for hierarchical lineage analysis, enabling more accurate and efficient modeling of cellular differentiation paths.
  arXiv  Detail & Related papers  (2025-06-29T15:19:13Z)
• Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods [51.54704494242525]
  We propose a new unifying framework, Birch SGD, for analyzing and designing distributed SGD methods.<n>Using Birch SGD, we design eight new methods and analyze them alongside previously known ones, with at least six of the new methods shown to have optimal computational time complexity.<n>Our research leads to two key insights: (i) all methods share the same "iteration rate" of $Oleft(frac(R + 1) L Deltavarepsilon + fracsigma2 L Deltavarepsilon2right)$, where $R$
  arXiv  Detail & Related papers  (2025-05-14T08:37:45Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree. We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference. Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• Discovering Message Passing Hierarchies for Mesh-Based Physics Simulation [61.89682310797067]
  We introduce DHMP, which learns Dynamic Hierarchies for Message Passing networks through a differentiable node selection method. Our experiments demonstrate the effectiveness of DHMP, achieving 22.7% improvement on average compared to recent fixed-hierarchy message passing networks.
  arXiv  Detail & Related papers  (2024-10-03T15:18:00Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  Current state-of-the-art selectors utilize either hand-crafted ensembles that automatically switch between naive sub-node selectors, or learned node selectors that rely on individual node data. We propose a novel simulation technique that uses reinforcement learning (RL) while considering the entire tree state, rather than just isolated nodes.
  arXiv  Detail & Related papers  (2023-09-29T19:55:56Z)
• Social Interpretable Tree for Pedestrian Trajectory Prediction [75.81745697967608]
  We propose a tree-based method, termed as Social Interpretable Tree (SIT), to address this multi-modal prediction task. A path in the tree from the root to leaf represents an individual possible future trajectory. Despite the hand-crafted tree, the experimental results on ETH-UCY and Stanford Drone datasets demonstrate that our method is capable of matching or exceeding the performance of state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-26T12:18:44Z)
• CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial Optimization Problems [0.0]
  This paper proposes a search algorithm by expanding search space from a Markov chain to a depth limited tree based on SA. At each iteration, the algorithm will select the best near-optimal solution within the feasible search space by exploring along the tree in the sense of look ahead' Our results show that above the primals SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated NP-optimization problems.
  arXiv  Detail & Related papers  (2022-03-09T10:07:26Z)
• Deterministic Iteratively Built KD-Tree with KNN Search for Exact Applications [2.7325238096808318]
  K-Nearest Neighbors (KNN) search is a fundamental algorithm in artificial intelligence software with applications in robotics, and autonomous vehicles. Similar to binary trees, kd-trees become unbalanced as new data is added in online applications which can lead to rapid degradation in search performance unless the tree is rebuilt. We will present a "forest of interval kd-trees" which reduces the number of tree rebuilds, without compromising the exactness of query results.
  arXiv  Detail & Related papers  (2021-06-07T17:09:22Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• Interactive Reinforcement Learning for Feature Selection with Decision Tree in the Loop [41.66297299506421]
  We study the problem of balancing effectiveness and efficiency in automated feature selection. We propose a novel interactive and closed-loop architecture to simultaneously model interactive reinforcement learning (IRL) and decision tree feedback (DTF) We present extensive experiments on real-world datasets to show the improved performance.
  arXiv  Detail & Related papers  (2020-10-02T18:09:57Z)
• From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering [33.000371053304676]
  We present the first continuous relaxation of Dasgupta's discrete optimization problem with provable quality guarantees. We show that even approximate solutions found with gradient descent have superior quality than agglomerative clusterings. We also highlight the flexibility of HypHC using end-to-end training in a downstream classification task.
  arXiv  Detail & Related papers  (2020-10-01T13:43:19Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.