論文の概要: 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.
関連論文リスト
- Exploring the loss landscape of regularized neural networks via convex duality [42.48510370193192]
本稿では,正規化ニューラルネットワークのロスランドスケープのいくつかの側面について論じる。
まず、その双対を用いて凸問題の解集合を特徴づけ、さらに全ての定常点を特徴づける。
ソリューションセットの特徴付けと接続結果は、異なるアーキテクチャに拡張可能であることを示す。
論文 参考訳（メタデータ） (2024-11-12T11:41:38Z) - The Complexity of Optimizing Atomic Congestion [14.845310803203724]
アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。
非常に単純なネットワークでも問題は非常に難解なままである。
我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
論文 参考訳（メタデータ） (2023-12-15T21:31:30Z) - A Structural Complexity Analysis of Synchronous Dynamical Systems [33.788917274180484]
同期力学系における3つの問題について検討する。
これら3つの問題は、古典的な意味では難解であることが知られている。
定常木幅の例においても, いずれも難解であることを示す。
論文 参考訳（メタデータ） (2023-12-12T10:49:33Z) - What Planning Problems Can A Relational Neural Network Solve? [91.53684831950612]
本稿では,計画問題のポリシーを表すリレーショナルニューラルネットワークの回路複雑性解析について述べる。
回路幅と深さの増大に関して,計画問題には3つの一般的なクラスが存在することを示す。
また、政策学習のためのニューラルネットワーク設計におけるこの分析の有用性についても解説する。
論文 参考訳（メタデータ） (2023-12-06T18:47:28Z) - Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
まず、3層ニューラルネットワークがコンパクトな集合上のインジケータ関数を近似するように設計可能であることを示す。
その後、これは単純複体へと拡張され、その位相構造に基づいて幅の上界が導かれる。
トポロジカルアプローチを用いて3層ReLUネットワークの普遍近似特性を証明した。
論文 参考訳（メタデータ） (2023-05-25T14:17:15Z) - The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
本研究では,スカラー値を持つ一層ネットワークのクラスとユークリッドノルムで有界な入力について検討する。
隠蔽層重み行列のスペクトルノルムの制御は、一様収束を保証するには不十分であることを示す。
スペクトルノルム制御が十分であることを示す2つの重要な設定を解析する。
論文 参考訳（メタデータ） (2022-02-13T07:12:02Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z) - Global Convergence of Three-layer Neural Networks in the Mean Field
Regime [3.553493344868413]
平均場系では、ニューラルネットワークは適切にスケールされ、幅は無限大になる傾向にあり、学習ダイナミクスは平均場限として知られる非線形かつ非自明な動的限界に傾向がある。
最近の研究は、この分析を2層ネットワークに適用し、グローバル収束保証を提供した。
平均場における非正規化フィードフォワード三層ネットワークに対する大域収束結果を示す。
論文 参考訳（メタデータ） (2021-05-11T17:45:42Z) - Bounding the Complexity of Formally Verifying Neural Networks: A
Geometric Approach [1.9493449206135296]
ReLUニューラルネットワーク(NN)の複雑さを正式に検証することを検討する。
本稿では,2つの異なるNNに対して,検証問題は2種類の制約を満たすことを示す。
両方のアルゴリズムは、NNパラメータをハイパープレーンを用いてNNアーキテクチャの効果に効率的に変換する。
論文 参考訳（メタデータ） (2020-12-22T00:29:54Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。