Compact Belief State Representation for Task Planning

• URL: http://arxiv.org/abs/2008.10386v1
• Date: Fri, 21 Aug 2020 09:38:36 GMT
• Title: Compact Belief State Representation for Task Planning
• Authors: Evgenii Safronov, Michele Colledanchise and Lorenzo Natale
• Abstract summary: We develop a novel belief state representation based on cartesian product and union operations over belief substates. These two operations and single variable assignment nodes form And-Or directed acyclic graph of Belief State (AOBS) We show that AOBS representation is not only much more compact than a full belief state but it also scales better than Binary Decision Diagrams for most of the cases.
• Score: 8.521089975868131
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Task planning in a probabilistic belief state domains allows generating complex and robust execution policies in those domains affected by state uncertainty. The performance of a task planner relies on the belief state representation. However, current belief state representation becomes easily intractable as the number of variables and execution time grows. To address this problem, we developed a novel belief state representation based on cartesian product and union operations over belief substates. These two operations and single variable assignment nodes form And-Or directed acyclic graph of Belief State (AOBS). We show how to apply actions with probabilistic outcomes and measure the probability of conditions holding over belief state. We evaluated AOBS performance in simulated forward state space exploration. We compared the size of AOBS with the size of Binary Decision Diagrams (BDD) that were previously used to represent belief state. We show that AOBS representation is not only much more compact than a full belief state but it also scales better than BDD for most of the cases.

Related papers

• States Hidden in Hidden States: LLMs Emerge Discrete State Representations Implicitly [72.24742240125369]
  In this paper, we uncover the intrinsic ability to perform extended sequences of calculations without relying on chain-of-thought step-by-step solutions. Remarkably, the most advanced models can directly output the results of two-digit number additions with lengths extending up to 15 addends.
  arXiv  Detail & Related papers  (2024-07-16T06:27:22Z)
• Quantum Pseudorandom Scramblers [4.835091081509403]
  Quantum pseudorandom state generators (PRSGs) produce an output state that is computationally indistinguishable from a Haar random state. Known PRSG constructions provably fail on some initial states. We construct quantum Pseudorandom State Scramblers (PRSSs) which can produce a pseudorandom state on an arbitrary initial state.
  arXiv  Detail & Related papers  (2023-09-16T10:17:46Z)
• Measurement-assisted non-Gaussian gate for Schr\"odinger cat states preparation: Fock resource state versus cubic phase state [0.0]
  We consider the preparation of Schr"odinger cat states using a measurement-assisted gate based on the Fock resource state. We compare the efficiency of two schemes, that is, their ability to produce cat-like superpositions with high fidelity and probability of success.
  arXiv  Detail & Related papers  (2023-07-12T17:55:25Z)
• OpenPI-C: A Better Benchmark and Stronger Baseline for Open-Vocabulary State Tracking [55.62705574507595]
  OpenPI is the only dataset annotated for open-vocabulary state tracking. We categorize 3 types of problems on the procedure level, step level and state change level respectively. For the evaluation metric, we propose a cluster-based metric to fix the original metric's preference for repetition.
  arXiv  Detail & Related papers  (2023-06-01T16:48:20Z)
• Accelerating Reinforcement Learning with Value-Conditional State Entropy Exploration [97.19464604735802]
  A promising technique for exploration is to maximize the entropy of visited state distribution. It tends to struggle in a supervised setup with a task reward, where an agent prefers to visit high-value states. We present a novel exploration technique that maximizes the value-conditional state entropy.
  arXiv  Detail & Related papers  (2023-05-31T01:09:28Z)
• Probabilistic pure state conversion on the majorization lattice [0.0]
  Entanglement is among the most fundamental-and at the same time puzzling-properties of quantum physics. We show that the majorization lattice provides an efficient framework in order to characterize the allowed transformations of pure entangled states.
  arXiv  Detail & Related papers  (2023-03-17T16:10:50Z)
• Witnessing superpositions of causal orders before the process is completed [0.0]
  What is the most general representation of a quantum state at a single point in time? Can we adapt the current formalisms to situations where the order of quantum operations is coherently or incoherently superposed?
  arXiv  Detail & Related papers  (2022-09-19T16:47:53Z)
• Training and Inference on Any-Order Autoregressive Models the Right Way [97.39464776373902]
  A family of Any-Order Autoregressive Models (AO-ARMs) has shown breakthrough performance in arbitrary conditional tasks. We identify significant improvements to be made to previous formulations of AO-ARMs. Our method leads to improved performance with no compromises on tractability.
  arXiv  Detail & Related papers  (2022-05-26T18:00:02Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  We study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones.
  arXiv  Detail & Related papers  (2021-07-07T12:51:04Z)
• Discrimination of quantum states under locality constraints in the many-copy setting [18.79968161594709]
  We prove that the optimal average error probability always decays exponentially in the number of copies. We show an infinite separation between the separable (SEP) and PPT operations by providing a pair of states constructed from an unextendible product basis (UPB) On the technical side, we prove this result by providing a quantitative version of the well-known statement that the tensor product of UPBs is a UPB.
  arXiv  Detail & Related papers  (2020-11-25T23:26:33Z)
• Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounders [62.54431888432302]
  We study an OPE problem in an infinite-horizon, ergodic Markov decision process with unobserved confounders. We show how, given only a latent variable model for states and actions, policy value can be identified from off-policy data.
  arXiv  Detail & Related papers  (2020-07-27T22:19:01Z)

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.