Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic

• URL: http://arxiv.org/abs/2112.14428v1
• Date: Wed, 29 Dec 2021 07:30:47 GMT
• Title: Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic
• Authors: Khen Elimelech, Vadim Indelman
• Abstract summary: We examine the problem of online decision making under uncertainty, which we formulate as planning in the belief space. We call this approach PIVOT: Predictive Incremental Variable Ordering Tactic. Applying this tactic can also improve the state inference efficiency.
• Score: 11.878820609988693
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we examine the problem of online decision making under uncertainty, which we formulate as planning in the belief space. Maintaining beliefs (i.e., distributions) over high-dimensional states (e.g., entire trajectories) was not only shown to significantly improve accuracy, but also allows planning with information-theoretic objectives, as required for the tasks of active SLAM and information gathering. Nonetheless, planning under this "smoothing" paradigm holds a high computational complexity, which makes it challenging for online solution. Thus, we suggest the following idea: before planning, perform a standalone state variable reordering procedure on the initial belief, and "push forwards" all the predicted loop closing variables. Since the initial variable order determines which subset of them would be affected by incoming updates, such reordering allows us to minimize the total number of affected variables, and reduce the computational complexity of candidate evaluation during planning. We call this approach PIVOT: Predictive Incremental Variable Ordering Tactic. Applying this tactic can also improve the state inference efficiency; if we maintain the PIVOT order after the planning session, then we should similarly reduce the cost of loop closures, when they actually occur. To demonstrate its effectiveness, we applied PIVOT in a realistic active SLAM simulation, where we managed to significantly reduce the computation time of both the planning and inference sessions. The approach is applicable to general distributions, and induces no loss in accuracy.

Related papers

• Predicting Probabilities of Error to Combine Quantization and Early Exiting: QuEE [68.6018458996143]
  We propose a more general dynamic network that can combine both quantization and early exit dynamic network: QuEE. Our algorithm can be seen as a form of soft early exiting or input-dependent compression. The crucial factor of our approach is accurate prediction of the potential accuracy improvement achievable through further computation.
  arXiv  Detail & Related papers  (2024-06-20T15:25:13Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• On efficient computation in active inference [1.1470070927586016]
  We present a novel planning algorithm for finite temporal horizons with drastically lower computational complexity. We also simplify the process of setting an appropriate target distribution for new and existing active inference planning schemes.
  arXiv  Detail & Related papers  (2023-07-02T07:38:56Z)
• involve-MI: Informative Planning with High-Dimensional Non-Parametric Beliefs [6.62472687864754]
  We calculate an information-theoretic expected reward, mutual information (MI), over a much lower-dimensional subset of the state, to improve efficiency and without sacrificing accuracy. We then develop an estimator for the MI which works in a Sequential Monte Carlo manner, and avoids the reconstruction of future belief's surfaces. This work is then evaluated in a simulation of an active SLAM problem, where the improvement in both accuracy and timing is demonstrated.
  arXiv  Detail & Related papers  (2022-09-23T13:51:36Z)
• Planning in Observable POMDPs in Quasipolynomial Time [21.03037504572896]
  We develop a quasipolynomial-time algorithm for planning in observable POMDPs. We assume that well-separated distributions on states lead to well-separated distributions on observations. We prove matching hardness for planning in observable POMDPs under the Exponential Time Hypothesis.
  arXiv  Detail & Related papers  (2022-01-12T23:16:37Z)
• Gradient-Based Mixed Planning with Discrete and Continuous Actions [34.885999774739055]
  We propose a quadratic-based framework to simultaneously optimize continuous parameters and actions of candidate plans. The framework is combined with a module to estimate the best plan candidate to transit initial state to the goal based on relaxation.
  arXiv  Detail & Related papers  (2021-10-19T14:21:19Z)
• Adaptive Belief Discretization for POMDP Planning [7.508023795800546]
  Many POMDP solvers uniformly discretize the belief space and give the planning error in terms of the (typically unknown) covering number. We propose an adaptive belief discretization scheme, and give its associated planning error. We demonstrate that our algorithm is highly competitive with the state of the art in a variety of scenarios.
  arXiv  Detail & Related papers  (2021-04-15T07:04:32Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)

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.