論文の概要: Homomorphisms and Embeddings of STRIPS Planning Models

• arxiv url: http://arxiv.org/abs/2406.16555v1
• Date: Mon, 24 Jun 2024 11:43:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-25 15:04:12.035211
• Title: Homomorphisms and Embeddings of STRIPS Planning Models
• Title（参考訳）: STRIPS計画モデルの準同型と埋め込み
• Authors: Arnaud Lequen, Martin C. Cooper, Frédéric Maris,
• Abstract要約: 1つ目はGI完全であり、理論上は準多項式時間で解けることを示す。 残りの問題はNP完全であることが証明されているが、可能であれば同型を構築するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.594173051888471
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance $P$ and a sub-instance of another instance $P_0$ . One application of such a mapping is to efficiently produce a compiled form containing all solutions to P from a compiled form containing all solutions to $P_0$. We also introduce the notion of embedding from an instance $P$ to another instance $P_0$, which allows us to deduce that $P_0$ has no solution-plan if $P$ is unsolvable. In this paper, we study the complexity of these problems. We show that the first is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the remaining problems to be NP-complete, we propose an algorithm to build an isomorphism, when possible. We report extensive experimental trials on benchmark problems which demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.
• Abstract（参考訳）: 2つのSTRIPSプランニングインスタンスが同型かどうかを決定することは、プランニングインスタンスの比較の最も単純な形式である。 これはまた、計画インスタンス$P$と他のインスタンス$P_0$のサブインスタンスの間の同型を見つけることに関わる問題の特別なケースでもある。 そのような写像の1つの応用は、P に対するすべての解を含むコンパイルされた形式を、すべての解を含むコンパイルされた形式から$P_0$ に効率よく生成することである。 また、$P$ から別のインスタンス $P_0$ への埋め込みの概念を導入し、$P$ が解決不可能な場合、$P_0$ が解決計画を持たないことを推測する。 本稿では,これらの問題の複雑さについて考察する。 1つ目はGI完全であり、理論上は準多項式時間で解けることを示す。 残りの問題はNP完全であることが証明されているが、可能であれば同型を構築するアルゴリズムを提案する。 本稿では,事前処理における制約伝搬の適用がSATソルバの効率を大幅に向上することを示すベンチマーク問題に関する広範な実験実験について報告する。

関連論文リスト

• A Fast Algorithm for Consistency Checking Partially Ordered Time [9.594432031144716]
  イベントシステムの(おそらく不完全な)記述が一貫したものであるかどうかを判断する問題を考える。 この問題の古典的な複雑さは完全に解決されているが、POTの微細な複雑さについてはほとんど分かっていない。 ランタイムを$O*((0.26n)n)$でバウンドしたより高速なアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2023-05-25T10:36:49Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium [6.295616917309867]
  対称一般化固有値問題(SGEP)は数値線型代数の基本概念である。 現在の最先端のメソッドでは、イテレーション毎に$O(d2k)$ランタイムの複雑さが必要です。 我々は、この並列アプローチを$O(dk)$ランタイムの複雑さを達成するためにどのように修正するかを示す。
  論文  参考訳（メタデータ） (2022-06-10T11:03:58Z)
• Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
  本稿では,軽度条件下での有限個の判定問題に対して,対話型意思決定のための最初のインスタンス最適化アルゴリズムを設計する。 本研究の結果は, 具体的問題に着目し, 多腕バンディットの古典的ギャップ依存境界と, 線形バンディットに関する先行研究を復元した。
  論文  参考訳（メタデータ） (2022-06-06T02:56:10Z)
• Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings [9.066817876491053]
  我々は,生産者側の個々人の露出不公平さを最小限に抑えつつ,消費者側の実用性を最大化する一連のランキングを計算することの課題を考える。 幾何的対象 (polytope) と呼ばれる多面体(polytope) を導入し、その点が位置ベースモデルに対する全ての達成可能なアイテムの露出を表す。 提案手法は,アルゴリズムの複雑度と経験的実行時間の観点から,線形あるいは二次的なプログラミングベースラインと比較した。 我々の解は、BvN分解で達成された$(n-1)2 + 1$の代わりに、わずか$n$置換の分布として表すことができる。
  論文  参考訳（メタデータ） (2022-02-07T14:43:35Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
  論文  参考訳（メタデータ） (2021-07-05T00:51:02Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  非剛体形状マッチングのための凸混合整数プログラミングの定式化。 効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-28T09:54:06Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。