論文の概要: Depth-Bounded Epistemic Planning
- arxiv url: http://arxiv.org/abs/2406.01139v1
- Date: Mon, 3 Jun 2024 09:30:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 01:38:29.413466
- Title: Depth-Bounded Epistemic Planning
- Title(参考訳): 深さ境界型てんかん計画
- Authors: Thomas Bolander, Alessandro Burigana, Marco Montali,
- Abstract要約: 本稿では,動的てんかん論理に基づく新しい計画法を提案する。
新規性は、計画エージェントの推論の深さを上界bに制限することである。
推論深度の境界b内における解を持つ計画タスクに関して、完全なものであることを示す。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): 本稿では,動的てんかん論理(DEL)に基づく新しいてんかん計画法を提案する。
新規性は、計画エージェントの推論の深さを上限bに制限することであり、計画エージェントは高次知識を少なくとも(モーダル)深さbにしか推論できないことを意味する。
このアルゴリズムは、b-bisimulationに関する一意の最小モデルを保証する新しい種類の標準的b-bisimulation収縮を利用する。
深度境界の計画アルゴリズムを音声で表す。
さらに、推論深さの有界b内にある解を持つ計画タスクに関して完備であることを示す(従って、反復的有界深化変種は標準的意味で完備である)。
推論深さの有界bについては、アルゴリズムは (b + 1)-EXPTIME 完全であることが示され、さらにエージェントと原子の数で固定パラメータが抽出可能である。
本稿では,木探索版とグラフ検索版をそれぞれ提案し,木探索版の実装をベースライン・エピステミック・プランナーに対してベンチマークする。
関連論文リスト
- A Bayesian Approach to Online Planning [14.847090489758992]
モンテカルロの木探索とニューラルネットワークの組み合わせは、オンライン計画に革命をもたらした。
ネットワークのアウトプットに関する不確実性推定が計画の改善に有効かどうかを問う。
このような不確実な定量化を促進するためのベイズ計画手法を開発し、メタ推論文学から古典的な考え方に着想を得た。
論文 参考訳(メタデータ) (2024-06-04T08:33:17Z) - Scale-Adaptive Balancing of Exploration and Exploitation in Classical Planning [1.6574413179773757]
我々は,MAB文献のより詳細な理論的理解が,既存の計画アルゴリズムの改善に役立つことを示す。
本稿では, UCB1-Normal bandit を用いた MCTS/THTS アルゴリズムである GreedyUCT-Normal を提案する。
論文 参考訳(メタデータ) (2023-05-16T22:46:37Z) - IBBT: Informed Batch Belief Trees for Motion Planning Under Uncertainty [15.472200104646447]
本研究では,動作計画と不確実性検出のためのIBBTアルゴリズムを提案する。
IBBTは、バッチ状態サンプリング、名目上の軌道構築、計算、およびグラフ上の探索の間でインターリーブし、信念空間の運動計画を見つける。
IBBTは非自明な動作計画を発見し,従来の類似手法と比較して高速であることを確認した。
論文 参考訳(メタデータ) (2023-04-21T14:31:19Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳(メタデータ) (2023-03-17T17:53:28Z) - Planning to the Information Horizon of BAMDPs via Epistemic State
Abstraction [27.33232096515561]
ベイズ適応マルコフ決定過程 (Bayes-Adaptive Markov Decision Process, BAMDP) は、強化学習における探索・探索のトレードオフに対するベイズ最適解を追求する形式である。
文献の多くは適切な近似アルゴリズムの開発に重点を置いている。
BAMDP計画の複雑さの尺度として,まず軽微な構造的仮定で定義する。
そして、BAMDPの複雑性を低減し、計算可能で近似的な計画アルゴリズムを生み出す可能性を備えた、特定の状態抽象化形式を導入することで、結論付ける。
論文 参考訳(メタデータ) (2022-10-30T16:30:23Z) - Iterative Depth-First Search for Fully Observable Non-Deterministic
Planning [25.2935633334145]
我々は,FOND計画課題を解き,強い循環ポリシーを生成する,新しい反復深度優先探索アルゴリズムを開発した。
提案アルゴリズムはFOND計画のために設計されており,FOND計画の非決定論的側面をより直接的に扱う。
論文 参考訳(メタデータ) (2022-04-08T23:10:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search
Spaces [63.22864716473051]
本稿では,反復により探索空間を拡大(およびシフト)する新しいBOアルゴリズムを提案する。
理論的には、どちらのアルゴリズムにおいても、累積的後悔は線形以下の速度で増大する。
論文 参考訳(メタデータ) (2020-09-05T14:24:40Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳(メタデータ) (2020-08-29T14:58:26Z) - Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
暗黙的な逐次計画の仮定に代わるものを検討する。
本稿では,最適計画の近似を行うため,Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS)を提案する。
計画順序に対するこのアルゴリズム的柔軟性は,グリッドワールドにおけるナビゲーションタスクの改善に繋がることを示す。
論文 参考訳(メタデータ) (2020-04-23T18:08:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。