Fugu-MT 論文翻訳(概要): Pseudo-Boolean Proof Logging for Optimal Classical Planning

論文の概要: Pseudo-Boolean Proof Logging for Optimal Classical Planning

arxiv url: http://arxiv.org/abs/2504.18443v1
Date: Fri, 25 Apr 2025 15:54:09 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-02 19:15:53.831322
Title: Pseudo-Boolean Proof Logging for Optimal Classical Planning
Title（参考訳）: Pseudo-Boolean Proof Loggingによる最適古典計画
Authors: Simon Dold, Malte Helmert, Jakob Nordström, Gabriele Röger, Tanja Schindler,
Abstract要約: 擬似ブール制約に基づく下界証明書を生成するための一般的なフレームワークについて述べる。 A*$アルゴリズムを改良して,過度なオーバーヘッドで最適性の証明を生成する方法を示す。
参考スコア（独自算出の注目度）: 9.688823478031852
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We introduce lower-bound certificates for classical planning tasks, which can be used to prove the unsolvability of a task or the optimality of a plan in a way that can be verified by an independent third party. We describe a general framework for generating lower-bound certificates based on pseudo-Boolean constraints, which is agnostic to the planning algorithm used. As a case study, we show how to modify the $A^{*}$ algorithm to produce proofs of optimality with modest overhead, using pattern database heuristics and $h^\textit{max}$ as concrete examples. The same proof logging approach works for any heuristic whose inferences can be efficiently expressed as reasoning over pseudo-Boolean constraints.
Abstract（参考訳）: 本研究では,従来の計画課題の下位境界証明書を導入し,課題の未解決性や計画の最適性を証明するために,独立した第三者が検証できる方法を提案する。本稿では,疑似ブール制約に基づく低バウンド証明書を生成するための一般的なフレームワークについて述べる。ケーススタディでは、パターンデータベースヒューリスティックスと$h^\textit{max}$を具体例として、$A^{*}$アルゴリズムを修正して、モデムオーバーヘッドで最適性の証明を生成する方法を示す。同じ証明ロギングアプローチは、擬ブール制約に対する推論として効率的に表現できる任意のヒューリスティックに対して有効である。

関連論文リスト

Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment [54.787826863212146]
推論時間計算は、言語モデルのパフォーマンスをスケールするための強力な軸を提供する。我々は, (i) 応答品質, (ii) 計算量の観点から, 推論時アライメントアルゴリズムの性能を解析する。我々は$textttInferenceTimePessimism$を紹介した。これは推論時間計算の故意使用を通じて報酬ハッキングを緩和する新しいアルゴリズムである。
論文参考訳（メタデータ） (2025-03-27T18:00:08Z)
Certifying Pareto-Optimality in Multi-Objective Maximum Satisfiability [9.078413809849447]
マルチオブジェクトMaxSAT(MO-MaxSAT)最適化手法のVeriPB証明形式に基づく証明ロギングを提案する。最先端のマルチオブジェクトMaxSATソルバにVeriPBの証明ロギングを実装することで,MO-MaxSATの証明ロギングを合理的なオーバーヘッドで拡張可能であることを実証的に示す。
論文参考訳（メタデータ） (2025-01-29T09:01:26Z)
Graph-Structured Speculative Decoding [52.94367724136063]
投機的復号化は、大規模言語モデルの推論を加速する有望な手法として登場した。本稿では, 有向非巡回グラフ(DAG)を応用して, 起案された仮説を管理する革新的な手法を提案する。我々は1.73$times$から1.96$times$に顕著なスピードアップを観察し、標準投機的復号法を大幅に上回った。
論文参考訳（メタデータ） (2024-07-23T06:21:24Z)
e-COP : Episodic Constrained Optimization of Policies [12.854752753529151]
本稿では,制約付き強化学習(RL)のための第1ポリシー最適化アルゴリズムを提案する。提案アルゴリズムは, エピソード設定に適応したSoTA (non-episodic) アルゴリズムと類似あるいは良好な性能を示す。
論文参考訳（メタデータ） (2024-06-13T20:12:09Z)
Stopping Bayesian Optimization with Probabilistic Regret Bounds [1.4141453107129403]
我々は,ある点が与えられた条件を満たす確率に基づいて,事実上の停止規則を基準に置き換えることを検討する。我々は,モンテカルロの停止規則を,サンプル効率が高く,推定誤差に頑健な方法で評価する実用的なアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-02-26T18:34:58Z)
An Efficient Rehearsal Scheme for Catastrophic Forgetting Mitigation during Multi-stage Fine-tuning [55.467047686093025]
このような忘れを緩和するための一般的なアプローチは、微調整中に以前のタスクからサンプルをリハーサルすることである。側方損傷のリハーサルを優先するサンプリング手法である textttbf mix-cd を提案する。我々の手法は計算効率が高く、実装が容易で、計算制約のある設定においていくつかの主要な連続学習手法より優れています。
論文参考訳（メタデータ） (2024-02-12T22:32:12Z)
Forward LTLf Synthesis: DPLL At Work [1.370633147306388]
有限トレース(LTLf)上での線形時間論理の合成のための新しいAND-ORグラフ探索フレームワークを提案する。このようなフレームワーク内では、Davis-Putnam-Logemann-Loveland (DPLL)アルゴリズムにインスパイアされたプロシージャを考案し、次に利用可能なエージェント環境の動きを生成する。また,状態公式の構文的等価性に基づく探索ノードの等価性チェックも提案する。
論文参考訳（メタデータ） (2023-02-27T14:33:50Z)
Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata [2.1777837784979273]
ケット除去(BE)における簡潔表現の活用最も可能性の高い説明と重み付けされた制約満足度ベンチマークの結果は、FABEがしばしば芸術の状態を上回ります。
論文参考訳（メタデータ） (2021-08-09T09:31:46Z)
Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文参考訳（メタデータ） (2021-07-12T21:30:41Z)
Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文参考訳（メタデータ） (2021-04-19T17:22:11Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)
Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
論文参考訳（メタデータ） (2020-08-18T04:34:21Z)
Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry [16.574508244279098]
本稿では,重み付き1次モデルカウントを効率的にバウンドする新手法であるApproxWFOMCを提案する。このアルゴリズムは、様々な一階確率表現を推論する。本稿では,このアルゴリズムが一階確率モデルにおいて,既存の近似的および高精度な推論手法よりも優れていることを示す。
論文参考訳（メタデータ） (2020-01-15T12:21:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。