論文の概要: The Boundaries of Tractability in Hierarchical Task Network Planning

• arxiv url: http://arxiv.org/abs/2401.14174v1
• Date: Thu, 25 Jan 2024 13:34:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-26 14:32:59.343542
• Title: The Boundaries of Tractability in Hierarchical Task Network Planning
• Title（参考訳）: 階層型タスクネットワーク計画におけるトラクタビリティの境界
• Authors: Cornelius Brand, Robert Ganian, Fionn Mc Inerney, Simon Wietheger
• Abstract要約: 階層型タスクネットワーク計画における3つの古典的問題に対するトラクタビリティの複雑性理論的境界について検討する。 これら3つの問題はすべて、一定部分順序幅の原始的タスクネットワークにおいて、時間内に解くことができることを示す。
• 参考スコア（独自算出の注目度）: 15.926731632774768
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity-theoretic boundaries of tractability for three classical problems in the context of Hierarchical Task Network Planning: the validation of a provided plan, whether an executable plan exists, and whether a given state can be reached by some plan. We show that all three problems can be solved in polynomial time on primitive task networks of constant partial order width (and a generalization thereof), whereas for the latter two problems this holds only under a provably necessary restriction to the state space. Next, we obtain an algorithmic meta-theorem along with corresponding lower bounds to identify tight conditions under which general polynomial-time solvability results can be lifted from primitive to general task networks. Finally, we enrich our investigation by analyzing the parameterized complexity of the three considered problems, and show that (1) fixed-parameter tractability for all three problems can be achieved by replacing the partial order width with the vertex cover number of the network as the parameter, and (2) other classical graph-theoretic parameters of the network (including treewidth, treedepth, and the aforementioned partial order width) do not yield fixed-parameter tractability for any of the three problems.
• Abstract（参考訳）: 階層的タスクネットワーク計画の文脈における3つの古典的問題に対する複雑性理論的境界について検討する: 提供された計画の検証、実行可能計画の有無、与えられた状態が何らかの計画によって達成できるかどうか。 有限部分順序幅の原始的タスクネットワーク上では多項式時間で3つの問題を解くことができ(およびその一般化)、後者の2つの問題については、状態空間に証明可能な制限の下でのみ成立する。 次に,アルゴリズムによるメタ理論とそれに対応する下限を求めることで,多項式時間解法が原始的ネットワークから一般タスクネットワークへ持ち上げられるような厳密な条件を同定する。 Finally, we enrich our investigation by analyzing the parameterized complexity of the three considered problems, and show that (1) fixed-parameter tractability for all three problems can be achieved by replacing the partial order width with the vertex cover number of the network as the parameter, and (2) other classical graph-theoretic parameters of the network (including treewidth, treedepth, and the aforementioned partial order width) do not yield fixed-parameter tractability for any of the three problems.

関連論文リスト

• 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)

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

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