Depth-Bounded Epistemic Planning

• URL: http://arxiv.org/abs/2406.01139v1
• Date: Mon, 3 Jun 2024 09:30:28 GMT
• Title: Depth-Bounded Epistemic Planning
• Authors: Thomas Bolander, Alessandro Burigana, Marco Montali,
• Abstract summary: 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.
• Score: 50.42592219248395
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose a novel algorithm for epistemic planning based on dynamic epistemic logic (DEL). The novelty is that we limit the depth of reasoning of the planning agent to an upper bound b, meaning that the planning agent can only reason about higher-order knowledge to at most (modal) depth b. The algorithm makes use of a novel type of canonical b-bisimulation contraction guaranteeing unique minimal models with respect to b-bisimulation. We show our depth-bounded planning algorithm to be sound. Additionally, we show it to be complete with respect to planning tasks having a solution within bound b of reasoning depth (and hence the iterative bound-deepening variant is complete in the standard sense). For bound b of reasoning depth, the algorithm is shown to be (b + 1)-EXPTIME complete, and furthermore fixed-parameter tractable in the number of agents and atoms. We present both a tree search and a graph search variant of the algorithm, and we benchmark an implementation of the tree search version against a baseline epistemic planner.

Related papers

• A Bayesian Approach to Online Planning [14.847090489758992]
  Combination of Monte Carlo tree search and neural networks has revolutionized online planning. We ask whether uncertainty estimates about the network outputs could be used to improve planning. We develop a Bayesian planning approach that facilitates such uncertainty quantification, inspired by classical ideas from the meta-reasoning literature.
  arXiv  Detail & Related papers  (2024-06-04T08:33:17Z)
• Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning [1.6574413179773757]
  We show that a more detailed theoretical understanding of MAB literature helps improve existing planning algorithms. We propose GreedyUCT-Normal, a MCTS/THTS algorithm with UCB1-Normal bandit for agile classical planning.
  arXiv  Detail & Related papers  (2023-05-16T22:46:37Z)
• IBBT: Informed Batch Belief Trees for Motion Planning Under Uncertainty [15.472200104646447]
  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.
  arXiv  Detail & Related papers  (2023-04-21T14:31:19Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction [27.33232096515561]
  Bayes-Adaptive Markov Decision Process (BAMDP) formalism pursues the Bayes-optimal solution to the exploration-exploitation trade-off in reinforcement learning. Much of the literature has focused on developing suitable approximation algorithms. We first define, under mild structural assumptions, a complexity measure for BAMDP planning. We then conclude by introducing a specific form of state abstraction with the potential to reduce BAMDP complexity and gives rise to a computationally-tractable, approximate planning algorithm.
  arXiv  Detail & Related papers  (2022-10-30T16:30:23Z)
• Iterative Depth-First Search for Fully Observable Non-Deterministic Planning [25.2935633334145]
  We develop a novel iterative depth-first search algorithm that solves FOND planning tasks and produces strong cyclic policies. Our algorithm is explicitly designed for FOND planning, addressing more directly the non-deterministic aspect of FOND planning.
  arXiv  Detail & Related papers  (2022-04-08T23:10:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces [63.22864716473051]
  We propose a novel BO algorithm which expands (and shifts) the search space over iterations. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates.
  arXiv  Detail & Related papers  (2020-09-05T14:24:40Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• 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.