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
• Authors: Dongliang Zheng, Panagiotis Tsiotras
• 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

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