論文の概要: Computing Plan-Length Bounds Using Lengths of Longest Paths
- arxiv url: http://arxiv.org/abs/2006.01011v2
- Date: Mon, 1 Mar 2021 11:17:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 07:16:57.966543
- Title: Computing Plan-Length Bounds Using Lengths of Longest Paths
- Title(参考訳): 最長経路長を用いた計画長境界計算
- Authors: Mohammad Abdulaziz and Dominik Berger
- Abstract要約: 提案手法は,計画長の上限値の計算に有効であることを示す。
計算された上界は、以前の境界技術による境界よりもかなり良い(多くの場合、桁違いのオーダー)ことを示す。
- 参考スコア(独自算出の注目度): 10.965065178451104
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We devise a method to exactly compute the length of the longest simple path
in factored state spaces, like state spaces encountered in classical planning.
Although the complexity of this problem is NEXP-Hard, we show that our method
can be used to compute practically useful upper-bounds on lengths of plans. We
show that the computed upper-bounds are significantly (in many cases, orders of
magnitude) better than bounds produced by previous bounding techniques and that
they can be used to improve the SAT-based planning.
- Abstract(参考訳): 我々は、古典的な計画に現れる状態空間のように、分解された状態空間における最も長い単純な経路の長さを正確に計算する手法を考案する。
この問題の複雑さはNEXP-Hardであるが,本手法は計画長の上限値の計算に有効であることを示す。
計算された上界は, 従来の境界技術による境界よりも有意に(多くの場合, 桁数)良く, SATに基づく計画の改善に有効であることを示す。
関連論文リスト
- Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳(メタデータ) (2023-02-14T22:12:16Z) - The expected sum of edge lengths in planar linearizations of trees.
Theory and applications [0.16317061277456998]
平面配置における期待和と射影配置における期待和の関係を示す。
エッジ長の和の期待値を計算するために,$O(n)$-timeアルゴリズムを導出する。
本研究は, 並列コーパスに適用し, 依存関係構造に対する公式制約の強度が増大するにつれて, 実際の依存性距離とランダムベースラインとのギャップが減少することを示した。
論文 参考訳(メタデータ) (2022-07-12T14:35:07Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳(メタデータ) (2022-05-30T16:22:53Z) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。
特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。
以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文 参考訳(メタデータ) (2022-02-08T16:39:57Z) - Near-optimal estimation of smooth transport maps with kernel
sums-of-squares [81.02564078640275]
滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。
生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。
そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-03T13:45:36Z) - Scalable Anytime Algorithms for Learning Formulas in Linear Temporal
Logic [2.631744051718347]
トレースを分類する公式を学習する際の問題点を考察する。
既存の解には2つの制限がある: それらは小さな公式を超えてスケールせず、結果を返すことなく計算資源を消費する。
我々は,両問題に対処する新しいアルゴリズムを導入する。我々のアルゴリズムは,従来よりも桁違いに大きい式を構築でき,いつでも可能である。
論文 参考訳(メタデータ) (2021-10-13T13:57:31Z) - Approximate Novelty Search [7.57024681220677]
幅に基づく探索アルゴリズムは、好ましく定義された新規性の尺度に従って状態を優先順位付けすることで計画を求める。
新規性および幅に基づく探索の近似を得るための新しい手法を提案する。
論文 参考訳(メタデータ) (2021-05-17T09:21:48Z) - What to Do When You Can't Do It All: Temporal Logic Planning with Soft
Temporal Logic Constraints [28.072597424460472]
ソフト仕様の集合から最適な選択を満足する無限軌跡を見つけることを目的とした時間論理計画問題を考える。
提案アルゴリズムはまず,計画問題を最小限のコストで計算できる製品を構築する。
このような短いラッソを計算することは難しいが、短いラッソを合成するための効率的なグリージーなアプローチも導入する。
論文 参考訳(メタデータ) (2020-08-05T04:18:59Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳(メタデータ) (2020-06-21T15:32:21Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z) - A New Arc-Routing Algorithm Applied to Winter Road Maintenance [0.0]
本稿では, 比較的一般的なアークルーティング問題の大規模インスタンスについて検討し, 実用的制約を取り入れた。
そこで我々は,数千の交差点や道路セグメント上の道路網を数分で解き,良好なスケーリングが可能なビンパッキングに基づく新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2020-01-23T08:44:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。