論文の概要: Symbolic Search for Optimal Planning with Expressive Extensions
- arxiv url: http://arxiv.org/abs/2204.00288v1
- Date: Fri, 1 Apr 2022 08:41:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-04 14:47:46.712324
- Title: Symbolic Search for Optimal Planning with Expressive Extensions
- Title（参考訳）: 表現的拡張を用いた最適計画のための記号探索
- Authors: David Speck
- Abstract要約: 計画問題のいくつかの性質は、それらを捕捉しモデル化するために標準的な古典的計画形式を表現的に拡張する必要がある。
公理による計画、国家依存の行動コストによる計画、過剰加入計画、トップk計画について検討する。
- 参考スコア（独自算出の注目度）: 4.36572039512405
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In classical planning, the goal is to derive a course of actions that allows
an intelligent agent to move from any situation it finds itself in to one that
satisfies its goals. Classical planning is considered domain-independent, i.e.,
it is not limited to a particular application and can be used to solve
different types of reasoning problems. In practice, however, some properties of
a planning problem at hand require an expressive extension of the standard
classical planning formalism to capture and model them. Although the importance
of many of these extensions is well known, most planners, especially optimal
planners, do not support these extended planning formalisms. The lack of
support not only limits the use of these planners for certain problems, but
even if it is possible to model the problems without these extensions, it often
leads to increased effort in modeling or makes modeling practically impossible
as the required problem encoding size increases exponentially.
In this thesis, we propose to use symbolic search for cost-optimal planning
for different expressive extensions of classical planning, all capturing
different aspects of the problem. In particular, we study planning with axioms,
planning with state-dependent action costs, oversubscription planning, and
top-k planning. For all formalisms, we present complexity and compilability
results, highlighting that it is desirable and even necessary to natively
support the corresponding features. We analyze symbolic heuristic search and
show that the search performance does not always benefit from the use of a
heuristic and that the search performance can exponentially deteriorate even
under the best possible circumstances, namely the perfect heuristic. This
reinforces that symbolic blind search is the dominant symbolic search strategy
nowadays, on par with other state-of-the-art cost-optimal planning
strategies...
- Abstract（参考訳）: 古典的な計画において、目標は、知的エージェントが自分たちが見いだすあらゆる状況から、その目標を満たすものへと移動できるようにする一連の行動を引き出すことである。
古典的な計画法は、ドメインに依存しない、すなわち特定のアプリケーションに限らず、様々なタイプの推論問題を解くのに使うことができる。
しかし実際には、計画問題のいくつかの性質は、それらを捕捉しモデル化するために標準的な古典的計画形式を表現的に拡張する必要がある。
これらの拡張の重要性はよく知られているが、ほとんどのプランナー、特に最適なプランナーはこれらの拡張計画形式を支持していない。
サポートの欠如は、特定の問題に対するこれらのプランナーの使用を制限するだけでなく、たとえこれらの拡張なしで問題をモデル化することができるとしても、しばしばモデリングの労力を増加させ、必要な問題エンコーディングサイズが指数関数的に増加するにつれてモデリングを事実上不可能にする。
本論文では,古典的計画の異なる表現的拡張に対して,コスト最適計画のための記号的探索法を提案する。
特に,公理による計画,国家依存行動コストによる計画,過剰加入計画,トップk計画について検討する。
すべての形式について、複雑性とコンパイル可能性の結果を示し、それに対応する機能をネイティブにサポートすることが望ましいこと、さらには必要であることを強調する。
記号的ヒューリスティック探索を分析し,探索性能が必ずしもヒューリスティックの利用の恩恵を受けるとは限らないこと,検索性能が最善の状況,すなわち完全ヒューリスティックにおいても指数関数的に低下することを示した。
これは、シンボリックブラインド検索が現在主流のシンボリック検索戦略であり、他の最先端のコスト最適化計画戦略と同等であることを補強するものだ。
関連論文リスト
- On The Planning Abilities of OpenAI's o1 Models: Feasibility, Optimality, and Generalizability [59.72892401927283]
さまざまなベンチマークタスクでOpenAIのo1モデルの計画能力を評価する。
その結果,o1-preview は GPT-4 よりもタスク制約に順応していることがわかった。
論文 参考訳（メタデータ） (2024-09-30T03:58:43Z) - Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
CodePlanは、テキストコード形式の計画を生成し、追跡するフレームワークで、高いレベルの構造化された推論プロセスの概要を擬似コードで示します。
CodePlanは、洗練された推論タスク固有のリッチなセマンティクスと制御フローを効果的にキャプチャする。
反応を直接生成するのに比べて25.1%の相対的な改善が達成されている。
論文 参考訳（メタデータ） (2024-09-19T04:13:58Z) - Unified Task and Motion Planning using Object-centric Abstractions of
Motion Constraints [56.283944756315066]
本稿では,タスクとモーションプランニングを一つの検索に統一するTAMP手法を提案する。
我々のアプローチは、オフザシェルフAIサーチの計算効率を活用して、物理的に実現可能な計画が得られるような、オブジェクト中心の動作制約の抽象化に基づいている。
論文 参考訳（メタデータ） (2023-12-29T14:00:20Z) - Learning adaptive planning representations with natural language
guidance [90.24449752926866]
本稿では,タスク固有の計画表現を自動構築するフレームワークであるAdaについて述べる。
Adaは、プランナー互換の高レベルアクション抽象化と、特定の計画タスク領域に適応した低レベルコントローラのライブラリを対話的に学習する。
論文 参考訳（メタデータ） (2023-12-13T23:35:31Z) - A Planning Ontology to Represent and Exploit Planning Knowledge for Performance Efficiency [6.87593454486392]
我々は,エージェントを世界の初期状態から望ましい目標状態へ移動させる一連の行動を見つけることを目的として,自動計画の問題を考える。
利用可能なプランナと多様なプランナドメインが多数用意されていると仮定し、適切なプランナを特定し、ドメインのパフォーマンスを向上させるために活用できる不可欠な情報を持っている。
論文 参考訳（メタデータ） (2023-07-25T14:51:07Z) - A Framework for Neurosymbolic Robot Action Planning using Large Language Models [3.0501524254444767]
本稿では,象徴的タスク計画と機械学習アプローチのギャップを埋めることを目的としたフレームワークを提案する。
大規模言語モデル(LLM)を計画ドメイン定義言語(PDDL)と互換性のあるニューロシンボリックタスクプランナーに訓練する根拠
選択されたドメインにおける予備的な結果から, (i) テストデータセットの95.5%の問題を1,000個のサンプルで解決し, (ii) 従来のシンボルプランナーよりも最大13.5%短いプランを作成し, (iii) 計画の可利用性の平均待ち時間を61.4%まで削減する。
論文 参考訳（メタデータ） (2023-03-01T11:54:22Z) - Temporal Planning with Incomplete Knowledge and Perceptual Information [0.0]
本稿では,時間的計画枠組み内での緊急計画構築を組み合わせた新しい計画手法を提案する。
本研究では,不完全かつ(ii)知識認識行動をモデル化するために,計画ドメイン定義言語(PDDL)の小さな拡張を提案する。
また,様々な問題に対して優れた性能を示す新しい計画領域も導入した。
論文 参考訳（メタデータ） (2022-07-20T07:26:08Z) - Safe-Planner: A Single-Outcome Replanner for Computing Strong Cyclic
Policies in Fully Observable Non-Deterministic Domains [0.22940141855172028]
我々は、古典的ドメインの集合に非決定論的ドメインをコンパイルするために、単一出力決定に依存する、Safe-Plannerと呼ばれるオフラインのリプランナーを導入する。
実験により,この手法により,SPは誤った計画の生成を回避できるが,強い解に直結する弱い計画を生成することができることを示した。
論文 参考訳（メタデータ） (2021-09-23T16:20:35Z) - Task Scoping: Generating Task-Specific Abstractions for Planning [19.411900372400183]
オープンスコープの世界モデルを用いた特定のタスクの計画は、計算的に難解である。
本稿では,初期条件,目標条件,タスクの遷移力学構造に関する知識を活用するタスクスコーピングを提案する。
タスクスコーピングは、関連要因やアクションを決して削除せず、その計算複雑性を特徴づけ、特に有用である計画上の問題を特徴づける。
論文 参考訳（メタデータ） (2020-10-17T21:19:25Z) - 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) - STRIPS Action Discovery [67.73368413278631]
近年のアプローチでは、すべての中間状態が欠如している場合でも、アクションモデルを合成する古典的な計画が成功している。
アクションシグネチャが不明な場合に,従来のプランナーを用いてSTRIPSアクションモデルを教師なしで合成するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-30T17:08:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。