論文の概要: On the Computational Complexity of Stackelberg Planning and Meta-Operator Verification: Technical Report

• arxiv url: http://arxiv.org/abs/2403.17826v1
• Date: Tue, 26 Mar 2024 16:06:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-27 14:37:40.658748
• Title: On the Computational Complexity of Stackelberg Planning and Meta-Operator Verification: Technical Report
• Title（参考訳）: Stackelberg計画とメタオペレータ検証の計算複雑性について:技術報告
• Authors: Gregor Behnke, Marcel Steinmetz,
• Abstract要約: Stackelberg Planingは、最近導入されたシングルターン2プレイヤー対逆計画モデルである。 本稿では,Stackelberg計画における最初の理論的複雑性解析を行う。 しかし、計画期間の制限の下では、Stackelberg計画は複雑性階層のレベルを高くし、古典的な計画へのコンパイルが最悪のケースで指数的な計画長の増加をもたらすことを示唆している。
• 参考スコア（独自算出の注目度）: 11.510666867429387
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stackelberg planning is a recently introduced single-turn two-player adversarial planning model, where two players are acting in a joint classical planning task, the objective of the first player being hampering the second player from achieving its goal. This places the Stackelberg planning problem somewhere between classical planning and general combinatorial two-player games. But, where exactly? All investigations of Stackelberg planning so far focused on practical aspects. We close this gap by conducting the first theoretical complexity analysis of Stackelberg planning. We show that in general Stackelberg planning is actually no harder than classical planning. Under a polynomial plan-length restriction, however, Stackelberg planning is a level higher up in the polynomial complexity hierarchy, suggesting that compilations into classical planning come with a worst-case exponential plan-length increase. In attempts to identify tractable fragments, we further study its complexity under various planning task restrictions, showing that Stackelberg planning remains intractable where classical planning is not. We finally inspect the complexity of meta-operator verification, a problem that has been recently connected to Stackelberg planning.
• Abstract（参考訳）: Stackelbergプランニング(スタックルバーグプランニング)は、最近導入されたシングルターンの2人対戦型プランニングモデルであり、2人のプレイヤーが2人目のプレイヤーがゴールを達成するのを妨げている1人目のプレイヤーの目的である、ジョイント・クラシック・プランニング・タスクで行動している。 これにより、スタックルバーグ計画は古典的な計画と一般的なコンビネータゲームの間のどこかで問題となる。 しかし、正確にはどこに? Stackelbergの計画に関するすべての調査は、実際的な側面に焦点を当てている。 Stackelberg計画の最初の理論的複雑性解析を行うことで、このギャップを埋める。 一般に、Stackelberg計画は古典的な計画ほど難しいものではない。 しかし、多項式計画長制限の下では、スタックルバーグ計画は多項式複雑性階層の上位レベルであり、古典計画へのコンパイルは最悪のケースで指数的な計画長の増加をもたらすことを示唆している。 トラクタブルフラグメントを同定するために、様々な計画課題の制約の下でその複雑さをさらに研究し、古典的計画がそうでない場所でもスタックルバーグ計画が難解であることを示す。 メタオペレータ検証の複雑さは,Stackelberg計画に最近関係した問題である。

関連論文リスト

• Parallel Strategies for Best-First Generalized Planning [51.713634067802104]
  汎用計画(GP)は、複数の古典的な計画インスタンスを解くことができるアルゴリズムのようなソリューションの自動合成を研究するAIの研究分野である。 現在の進歩の1つはBest-First Generalized Planning (BFGP) の導入である。 本稿では,並列探索手法をBFGPに適用し,性能ギャップを埋める上で重要な要素であることを示す。
  論文  参考訳（メタデータ） (2024-07-31T09:50:22Z)
• TravelPlanner: A Benchmark for Real-World Planning with Language Agents [63.199454024966506]
  我々は,旅行計画に焦点を当てた新しい計画ベンチマークであるTravelPlannerを提案する。 豊富なサンドボックス環境、400万近いデータレコードにアクセスするためのさまざまなツール、計画意図とリファレンスプランを慎重にキュレートした1,225のツールを提供する。 包括的評価では、現在の言語エージェントがそのような複雑な計画タスクを処理できないことが示されており、GPT-4でさえ0.6%の成功率しか達成できない。
  論文  参考訳（メタデータ） (2024-02-02T18:39:51Z)
• LLM-Assist: Enhancing Closed-Loop Planning with Language-Based Reasoning [65.86754998249224]
  従来のルールベースプランナとLCMベースのプランナを併用した,新しいハイブリッドプランナを開発した。 当社のアプローチでは,既存のプランナが苦労する複雑なシナリオをナビゲートし,合理的なアウトプットを生成すると同時に,ルールベースのアプローチと連携して作業する。
  論文  参考訳（メタデータ） (2023-12-30T02:53:45Z)
• Skip-Plan: Procedure Planning in Instructional Videos via Condensed Action Space Learning [85.84504287685884]
  Skip-Plan(スキップ・プラン)は、訓練ビデオにおけるプロシージャ計画のための凝縮された行動空間学習法である。 アクションチェーン内の不確実なノードやエッジをスキップすることで、長いシーケンス関数と複雑なシーケンス関数を短いが信頼できるものに転送する。 我々のモデルは、凝縮された作用空間内のアクションシーケンス内で、あらゆる種類の信頼できる部分関係を探索する。
  論文  参考訳（メタデータ） (2023-10-01T08:02:33Z)
• Scaling-up Generalized Planning as Heuristic Search with Landmarks [9.653976364051564]
  一般化計画は通常、与えられたアルゴリズム的解の空間における探索として扱われる。 この種のソリューション評価は、計画インスタンスの表現において明示されていないどんなサブゴール情報も無視する。 GPのノード拡張は、古典的なプランニングインスタンスのバッチ全体にわたってすべての子ノードを評価する必要があるため、実行時のボトルネックである。
  論文  参考訳（メタデータ） (2022-05-10T12:42:48Z)
• Classical Planning in Deep Latent Space [33.06766829037679]
  Latplanは、ディープラーニングと古典的計画を組み合わせた教師なしアーキテクチャである。 ラトプランは、象徴的な潜在空間における目標状態への計画を見つけ、視覚化された計画実行を返します。
  論文  参考訳（メタデータ） (2021-06-30T21:31:21Z)
• Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks [28.488201307961624]
  現実の計画問題は、数百から数千ものオブジェクトを巻き込むことが多い。 単一推論パスにおけるオブジェクトの重要性を予測するためのグラフニューラルネットワークアーキテクチャを提案する。 提案手法では,プランナと遷移モデルをブラックボックスとして扱い,既製のプランナで使用することができる。
  論文  参考訳（メタデータ） (2020-09-11T18:55:08Z)
• Think Too Fast Nor Too Slow: The Computational Trade-off Between Planning And Reinforcement Learning [6.26592851697969]
  計画と強化学習は、シーケンシャルな意思決定に対する2つの重要なアプローチである。 計画と学習のトレードオフが重要であることを示す。 提案手法は,探索時間(長期計画)からモデルフリーなRL(計画なし)まで多岐にわたる新しい計画学習アルゴリズムのスペクトルを同定し,その中間に最適な性能を実現する。
  論文  参考訳（メタデータ） (2020-05-15T08:20:08Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  暗黙的な逐次計画の仮定に代わるものを検討する。 本稿では,最適計画の近似を行うため,Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS)を提案する。 計画順序に対するこのアルゴリズム的柔軟性は,グリッドワールドにおけるナビゲーションタスクの改善に繋がることを示す。
  論文  参考訳（メタデータ） (2020-04-23T18:08:58Z)
• The Efficiency of Human Cognition Reflects Planned Information Processing [40.51474966524166]
  タスク全体の構造の関数として、人々がどのように計画し、メタプランを行うべきかを予測します。 人々の反応時間は、情報処理の計画的な利用を反映している。 計画計画のこの定式化は、人間と機械の両方における階層的計画、状態抽象化、認知制御の機能に関する新たな洞察を提供する。
  論文  参考訳（メタデータ） (2020-02-13T20:34:33Z)
• STRIPS Action Discovery [67.73368413278631]
  近年のアプローチでは、すべての中間状態が欠如している場合でも、アクションモデルを合成する古典的な計画が成功している。 アクションシグネチャが不明な場合に,従来のプランナーを用いてSTRIPSアクションモデルを教師なしで合成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-30T17:08:39Z)

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

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