IBBT: Informed Batch Belief Trees for Motion Planning Under Uncertainty

• URL: http://arxiv.org/abs/2304.10984v1
• Date: Fri, 21 Apr 2023 14:31:19 GMT
• Title: IBBT: Informed Batch Belief Trees for Motion Planning Under Uncertainty
• Abstract summary: In this work, we propose the Informed Batch Belief Trees (IBBT) algorithm for motion planning under motion and sensing uncertainties. IBBT interleaves between batch state sampling, nominal trajectory construction, computing, and search over the graph to find belief space motion plans. Our numerical investigation confirms that IBBT finds non-trivial motion plans and is faster compared with previous similar methods.
• Score: 15.472200104646447
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this work, we propose the Informed Batch Belief Trees (IBBT) algorithm for motion planning under motion and sensing uncertainties. The original stochastic motion planning problem is divided into a deterministic motion planning problem and a graph search problem. We solve the deterministic planning problem using sampling-based methods such as PRM or RRG to construct a graph of nominal trajectories. Then, an informed cost-to-go heuristic for the original problem is computed based on the nominal trajectory graph. Finally, we grow a belief tree by searching over the graph using the proposed heuristic. IBBT interleaves between batch state sampling, nominal trajectory graph construction, heuristic computing, and search over the graph to find belief space motion plans. IBBT is an anytime, incremental algorithm. With an increasing number of batches of samples added to the graph, the algorithm finds motion plans that converge to the optimal one. IBBT is efficient by reusing results between sequential iterations. The belief tree searching is an ordered search guided by an informed heuristic. We test IBBT in different planning environments. Our numerical investigation confirms that IBBT finds non-trivial motion plans and is faster compared with previous similar methods.

Related papers

• Accelerating Mixed Discrete-Continuous Motion Planning via Neural Graphs of Convex Sets [4.288763738857392]
  Motion planning problems such as collision-free navigation and contact-rich manipulation can be naturally formulated as optimization problems.<n>The Graphs of Convex Sets (GCS) framework offers a practical solution.<n>We replace the costly convex relaxation step required by nominal GCS with a single forward pass through a Graph Attention Network.<n>A ranking network then orders these candidates by their estimated cost.
  arXiv  Detail & Related papers  (2026-08-15T22:51:56Z)
• Conflict-Based Lazy Search for Fast Multi-Manipulator Planning [35.43395690369507]
  This article proposes a new planning algorithm called Conflict-Based Lazy Search (CBLS) for multimanipulator planning.<n>Our CBLS algorithm enhances Conflict-Based Search with precomputation and lazy search.<n>Since edge evaluation is the computational bottleneck of manipulator planning, LEA* uses lazy search and an edge queue to reduce the number of edge evaluations.
  arXiv  Detail & Related papers  (2026-07-05T05:40:46Z)
• Optimizing Trajectory-Trees in Belief Space: An Application from Model Predictive Control to Task and Motion Planning [12.236092368066332]
  This paper explores the benefits of computing arborescent trajectories (trajectory-trees) instead of commonly used sequential trajectories for partially observable robotic planning problems.<n>Unlike sequential trajectories, which model a single forward evolution of the system, trajectory-trees capture multiple possible contingencies.
  arXiv  Detail & Related papers  (2026-05-03T13:06:20Z)
• Autonomous Vehicle Path Planning by Searching With Differentiable Simulation [55.46735086899153]
  Planning allows an agent to safely refine its actions before executing them in the real world.<n>In autonomous driving, this is crucial to avoid collisions and navigate in complex, dense traffic scenarios.<n>Here we propose Differentiable Simulation for Search (DSS), a framework that leverages the differentiable simulator Waymax as both a next state predictor and a critic.
  arXiv  Detail & Related papers  (2025-11-14T07:56:34Z)
• Adaptive Test-Time Reasoning via Reward-Guided Dual-Phase Search [62.1546099504045]
  We propose a dual-phase test-time scaling framework that separates reasoning into planning and execution.<n>Specifically, we decompose reasoning trajectories and develop reward models for each phase, enabling the search to explore and prune plans and executions separately.<n> Experiments on both mathematical reasoning and code generation benchmarks demonstrate that our approach consistently improves accuracy while reducing computation redundant.
  arXiv  Detail & Related papers  (2025-09-29T19:27:23Z)
• ETS: Efficient Tree Search for Inference-Time Scaling [61.553681244572914]
  One promising approach for test-time compute scaling is search against a process reward model. diversity of trajectories in the tree search process affects the accuracy of the search, since increasing diversity promotes more exploration. We propose Efficient Tree Search (ETS), which promotes KV sharing by pruning redundant trajectories while maintaining necessary diverse trajectories.
  arXiv  Detail & Related papers  (2025-02-19T09:30:38Z)
• Depth-Bounded Epistemic Planning [50.42592219248395]
  We present a novel algorithm for planning based on dynamic epistemic logic. The novelty is that we limit the depth of reasoning of the planning agent to an upper bound b. We show it to be complete with respect to planning tasks having a solution within bound b of reasoning depth.
  arXiv  Detail & Related papers  (2024-06-03T09:30:28Z)
• Cyclical Log Annealing as a Learning Rate Scheduler [0.0]
  A learning rate scheduler is a set of instructions for varying search stepsizes during model training processes. This paper introduces a new logarithmic method using harsh restarting of step sizes through descent gradient.
  arXiv  Detail & Related papers  (2024-03-13T14:07:20Z)
• Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
  We design reinforcement learning algorithms for Graphon Mean-Field Games (GMFGs) We aim to learn the Nash Equilibrium (NE) of the regularized GMFGs when the graphons are unknown. These algorithms are the first specifically designed for learning graphons from sampled agents.
  arXiv  Detail & Related papers  (2023-10-26T16:19:24Z)
• STAMP: Differentiable Task and Motion Planning via Stein Variational Gradient Descent [35.96763689715956]
  Planning for sequential robotics tasks often requires integrated symbolic and geometric reasoning. TAMP algorithms typically solve these problems by performing a tree search over high-level task sequences while checking for kinematic and dynamic feasibility. We propose a novel approach to TAMP called Stein Task and Motion Planning (STAMP) that relaxes the hybrid optimization problem into a continuous domain.
  arXiv  Detail & Related papers  (2023-10-03T03:53:51Z)
• A fast topological approach for predicting anomalies in time-varying graphs [0.0]
  A persistence diagram (PD) from topological data analysis (TDA) has become a popular descriptor of shape of data with a well-defined distance between points. This paper introduces a computationally efficient framework to extract shape information from graph data. In a real data application, our approach provides up to 22% gain in anomalous price prediction for the cryptocurrency transaction networks.
  arXiv  Detail & Related papers  (2023-05-11T01:54:45Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Learning Graph Search Heuristics [48.83557172525969]
  We present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigations from data. Our function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5% on average.
  arXiv  Detail & Related papers  (2022-12-07T22:28:00Z)
• Learning to Search in Task and Motion Planning with Streams [20.003445874753233]
  Task and motion planning problems in robotics combine symbolic planning over discrete task variables with motion optimization over continuous state and action variables. We propose a geometrically informed symbolic planner that expands the set of objects and facts in a best-first manner. We apply our algorithm on a 7DOF robotic arm in block-stacking manipulation tasks.
  arXiv  Detail & Related papers  (2021-11-25T15:58:31Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• CNN Encoder to Reduce the Dimensionality of Data Image for Motion Planning [1.244705780038575]
  We propose a CNN encoder capable of eliminating useless routes for motion planning problems. In all evaluated scenarios, our solution reduced the number of iterations by more than 60%.
  arXiv  Detail & Related papers  (2020-04-10T15:44:52Z)
• Methods of Adaptive Signal Processing on Graphs Using Vertex-Time Autoregressive Models [0.0]
  The concept of a random process has been recently extended to graph signals. The online version of this problem was proposed via the adaptive framework. Experiments are conducted to shed light on the potential, the potential, and the possible research attempt of this work.
  arXiv  Detail & Related papers  (2020-03-10T12:42:27Z)
• Hallucinative Topological Memory for Zero-Shot Visual Planning [86.20780756832502]
  In visual planning (VP), an agent learns to plan goal-directed behavior from observations of a dynamical system obtained offline. Most previous works on VP approached the problem by planning in a learned latent space, resulting in low-quality visual plans. Here, we propose a simple VP method that plans directly in image space and displays competitive performance.
  arXiv  Detail & Related papers  (2020-02-27T18:54:42Z)

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.