論文の概要: A Structural Complexity Analysis of Hierarchical Task Network Planning

• arxiv url: http://arxiv.org/abs/2401.14174v2
• Date: Wed, 22 Jan 2025 12:41:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-23 13:28:52.602796
• Title: A Structural Complexity Analysis of Hierarchical Task Network Planning
• Title（参考訳）: 階層型タスクネットワーク計画における構造的複雑度解析
• Authors: Cornelius Brand, Robert Ganian, Fionn Mc Inerney, Simon Wietheger,
• Abstract要約: 階層型タスクネットワーク計画の文脈における3つの古典的問題の複雑性理論解析を行う。 プリミティブネットワークの自然クラスにおける3つの問題に対する新しいアルゴリズムと対応する下位境界を求める。 また,プリミティブ・タスク・ネットワークから一般タスク・ネットワークへの解答時間を持ち上げるためのアルゴリズム的メタ理論も取得し,その前提条件が厳密であることを証明した。
• 参考スコア（独自算出の注目度）: 14.845310803203724
• License:
• Abstract: We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus lies on identifying structural properties which yield tractability. We obtain new polynomial algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Finally, we analyze the parameterized complexity of the three problems.
• Abstract（参考訳）: 階層型タスクネットワーク計画(英語版)の文脈における3つの古典的問題の複雑性理論解析を行い、与えられた計画の検証、実行可能な計画が存在するかどうか、与えられた状態に到達できるかどうかを検証した。 我々の焦点は、トラクタビリティをもたらす構造的特性の同定である。 プリミティブネットワークの自然なクラスにおける3つの問題に対する新しい多項式アルゴリズムと対応する下界を求める。 また,プリミティブ・タスク・ネットワークから一般タスク・ネットワークへの多項式時間可解性を持ち上げるためのアルゴリズム的メタ理論も取得し,その前提条件が厳密であることを証明した。 最後に、3つの問題のパラメータ化複雑性を分析する。

関連論文リスト

• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  本稿では, ニューラルネットワーク幅の上下境界を定義し, 問題となるデータセットのポリトープ構造から情報を得る。 本研究では,データセットのポリトープ構造を学習したニューラルネットワークから推定できる逆条件を探索するアルゴリズムを開発した。 MNIST、Fashion-MNIST、CIFAR10といった一般的なデータセットは、顔の少ない2つ以上のポリトップを用いて効率的にカプセル化できることが確立されている。
  論文  参考訳（メタデータ） (2024-02-04T08:57:42Z)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
  論文  参考訳（メタデータ） (2023-12-15T21:31:30Z)
• What Planning Problems Can A Relational Neural Network Solve? [91.53684831950612]
  本稿では,計画問題のポリシーを表すリレーショナルニューラルネットワークの回路複雑性解析について述べる。 回路幅と深さの増大に関して,計画問題には3つの一般的なクラスが存在することを示す。 また、政策学習のためのニューラルネットワーク設計におけるこの分析の有用性についても解説する。
  論文  参考訳（メタデータ） (2023-12-06T18:47:28Z)
• Invariant Representations of Embedded Simplicial Complexes [0.0]
  多くの分野において、三角メッシュやグラフのような埋め込み単純複体を解析することは重要な問題である。 本稿では, 位相情報と幾何学情報のみを用いて, サブディビジョン不変およびアイソメトリー不変の方法で, 組込みsimplicial Complexを解析するための新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2023-02-27T07:49:05Z)
• Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
  離散化に基づくアルゴリズムを設計する際の2つの大きな疑問は、離散化をどのように生成し、いつそれを洗練するかである。 オンライン強化学習のための木に基づく階層分割手法の統一的理論的解析を行う。 我々のアルゴリズムは操作制約に容易に適応し、我々の理論は3つの面のそれぞれに明示的な境界を与える。
  論文  参考訳（メタデータ） (2021-10-29T15:06:15Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。 我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
  論文  参考訳（メタデータ） (2021-10-18T18:00:36Z)
• Computing Complexity-aware Plans Using Kolmogorov Complexity [0.9137554315375922]
  有限水平決定性有限オートマトンを出力として計算する複雑性を考慮した計画法を提案する。 本稿では,2つのアルゴリズムで低複素性ポリシーを求め,第1のアルゴリズムで低複素性最適ポリシーを求める。 移動ロボットの単純なナビゲーションタスクにおけるアルゴリズムの評価を行い,そのアルゴリズムは直感と一致する低複雑さのポリシーを導出する。
  論文  参考訳（メタデータ） (2021-09-21T16:25:04Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Automated Search for Resource-Efficient Branched Multi-Task Networks [81.48051635183916]
  我々は,多タスクニューラルネットワークにおける分岐構造を自動的に定義する,微分可能なニューラルネットワーク探索に根ざした原理的アプローチを提案する。 本手法は,限られた資源予算内で高い性能の分岐構造を見いだすことができる。
  論文  参考訳（メタデータ） (2020-08-24T09:49:19Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)

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

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