論文の概要: Optimal Planning in a Dynamic World

• arxiv url: http://arxiv.org/abs/2610.03312v1
• Date: Fri, 02 Oct 2026 13:50:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.402687
• Title: Optimal Planning in a Dynamic World
• Title（参考訳）: 動的世界における最適計画
• Abstract要約: 本稿では,開始時刻関数として最適計画をコンパクトに符号化する複合到着時刻関数(cATF)というデータ構造を提案する。 我々は,グラフ探索に基づく汎用計画アルゴリズムを提供し,スカラーコストではなくエッジに沿って関数を伝搬することにより,cATFを組み立てる。
• 参考スコア（独自算出の注目度）: 9.595401499690814
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Background: We address the problem of planning when the set of feasible states or actions changes over time. For example, in the problem of path planning among moving obstacles (sometimes known as SIPP), the feasibility of being at a particular location can change as the obstacles move. Or, the action of boarding a particular train is feasible only while it is stopped at the station. This dynamism means that the optimal plan and its duration can change depending on when execution begins. In practice, execution start time is often unknown until planning has completed or another agent gives the go-ahead. However, most prior planning work either ignores dynamism or assumes a known start time. This makes it straightforward to assess state and action feasibility but is impractical for some applications. Objectives: In this paper, we relax the assumption of a known start time. We define the setting of {\em any-start-time planning} and provide algorithms for it. Methods: We present a data structure called a compound arrival time function (cATF) that compactly encodes the optimal plan as a function of start time. We provide general-purpose planning algorithms, based on heuristic graph search, that assemble cATFs by propagating functions along edges instead of scalar costs. Results: We prove that the size of a cATF is at most linear in the problem size. An experimental evaluation of an implementation for the specific problem of SIPP shows that, on difficult problems, agents that rely on replanning often fail, while any-start-time algorithms using cATFs can quickly look up the optimal plan once the execution start time is known. Conclusions: By enabling efficient representations and reasoning for time-dependent plans, this work provides a foundation for planning in dynamic worlds.
• Abstract（参考訳）: 背景: 実現可能な状態や行動の集合が時間とともに変化するとき、計画の問題に対処する。 例えば、動く障害物(SIPPと呼ばれることもある)間の経路計画の問題では、障害物が動くにつれて特定の位置にいる可能性も変化する。 または、駅で停車する間のみ、特定の列車に乗車する動作が可能である。 このダイナミズムは、実行開始時によって最適な計画とその期間が変化することを意味する。 実際には、計画が完了するか、他のエージェントが先手を打つまで、実行開始時間はしばしば不明である。 しかしながら、ほとんどの以前の計画作業はダイナミズムを無視したり、既知のスタートタイムを仮定する。 これにより、状態とアクションの実現可能性を簡単に評価できますが、いくつかのアプリケーションでは現実的ではありません。 目的:本稿では、既知の開始時間の仮定を緩和します。 我々は、任意の起動時間計画の設定を定義し、それのためのアルゴリズムを提供します。 方法: 開始時刻関数として最適計画をコンパクトに符号化する複合到着時刻関数(cATF)というデータ構造を提案する。 我々は、スカラーコストではなくエッジに沿って関数を伝播させることにより、cATFを組み立てるヒューリスティックグラフ探索に基づく汎用的な計画アルゴリズムを提供する。 結果: cATF のサイズは問題サイズにおいて最も線形であることが証明された。 SIPPの特定の問題に対する実装を実験的に評価したところ、難しい問題に対して、再計画に依存するエージェントは失敗することが多く、cATFを用いた任意の起動時アルゴリズムは実行開始時間を知るとすぐに最適な計画を見出すことができる。 結論: 時間に依存した計画の効率的な表現と推論を可能にすることで、この研究は動的世界の計画の基礎を提供する。

関連論文リスト

• Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game [26.665033202052257]
  本稿では,Countdownと呼ばれるゲームを中心とした計画ベンチマークを作成する手順を提案する。 本稿では,この課題が,計画能力評価のための理想的なベンチマークと関連するデシラタの多くにどのように適合するかを論じる。 その結果、24 Game(Countdownの特殊な場合)のような他の領域とは異なり、提案した動的ベンチマークは既存のLCMベースのアプローチでは極めて困難であることが判明した。
  論文  参考訳（メタデータ） (2025-08-04T21:01:03Z)
• Hindsight Planner: A Closed-Loop Few-Shot Planner for Embodied Instruction Following [62.10809033451526]
  本研究は,Large Language Models (LLM) を用いた Embodied Instruction following (EIF) タスクプランナの構築に焦点をあてる。 我々は,このタスクを部分観測可能なマルコフ決定プロセス (POMDP) として構成し,数発の仮定で頑健なプランナーの開発を目指す。 ALFREDデータセットに対する我々の実験は、プランナーが数ショットの仮定で競争性能を達成することを示す。
  論文  参考訳（メタデータ） (2024-12-27T10:05:45Z)
• The Road Less Scheduled [45.01813613035411]
  最適化停止ステップTの仕様を必要としない既存の学習率スケジュールは、Tに依存する学習率スケジュールにより大幅に改善される。 本稿では,スケジュールを全面的に活用することで,この停止時間を回避するアプローチを提案する。 我々のスケジュール自由アプローチは運動量を持つ標準スケジュールに余分なハイパーパラメータを導入しない。
  論文  参考訳（メタデータ） (2024-05-24T16:20:46Z)
• Planning and Acting While the Clock Ticks [15.783791140860528]
  時間的プレッシャーのある問題では、最初のアクションを実行する前に、タイミングが厳しすぎて計画が完了できない。 計画終了前にアクションを発行(実行)できる並列計画と実行という,新たな問題設定を提案する。
  論文  参考訳（メタデータ） (2024-03-21T19:18:47Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  具体的AIのためのタスクプランニングは、最も難しい問題の1つだ。 In-paintingとしての計画」というタスク非依存の手法を提案する。 提案するフレームワークは,様々な具体的AIタスクにおいて,有望なパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2023-12-02T10:07:17Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。 ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-25T20:28:55Z)
• A Formal Metareasoning Model of Concurrent Planning and Execution [22.963769931698874]
  この作業は、計画と実行を同時に行う、原則付きタイムアウェアエグゼクティブの基盤となるものです。 時間内に解決可能な特別事例を特定し, 欲求解アルゴリズムを開発し, 探索問題から抽出した事例を検証した結果, 有望な実用性を実現する方法がいくつか見出された。
  論文  参考訳（メタデータ） (2023-03-05T13:05:26Z)
• Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion Planning [36.300564378022315]
  本稿では,移動環境における移動操作問題を解決するための学習可能なタスク・アンド・モーション・プランニング(TAMP)アルゴリズムを提案する。 本アルゴリズムのコアは,タスク計画,目標,初期状態を考慮したトランスフォーマーに基づく新しい学習手法であるPIGINetであり,タスク計画に関連する運動軌跡の発見確率を予測する。
  論文  参考訳（メタデータ） (2022-11-03T04:12:04Z)
• Learning to Search in Task and Motion Planning with Streams [20.003445874753233]
  ロボット工学におけるタスク計画問題と動作計画問題は、個別のタスク変数に対するシンボリック計画と、連続状態および動作変数に対する動作最適化を組み合わせたものである。 対象と事実の集合を最優先的に拡張する幾何学的情報に基づく記号プランナを提案する。 ブロックスタッキング操作タスクにおいて,このアルゴリズムを7DOFロボットアームに適用する。
  論文  参考訳（メタデータ） (2021-11-25T15:58:31Z)
• STRIPS Action Discovery [67.73368413278631]
  近年のアプローチでは、すべての中間状態が欠如している場合でも、アクションモデルを合成する古典的な計画が成功している。 アクションシグネチャが不明な場合に,従来のプランナーを用いてSTRIPSアクションモデルを教師なしで合成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-30T17:08:39Z)

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

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