論文の概要: An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types
- arxiv url: http://arxiv.org/abs/2501.15249v2
- Date: Thu, 30 Jan 2025 04:07:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-31 11:52:56.297543
- Title: An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types
- Title（参考訳）: バッグ型一般化計画のための音響・完全抽象化法
- Authors: Hao Dong, Zheyuan Shi, Hemeng Zeng, Yongmei Liu,
- Abstract要約: 一般的なプランニングは、複数の類似のプランニングインスタンスを解決するための単一のプランを見つける方法に関するものだ。
本稿では,バッグブル型を用いた一般化計画のための音響・完全抽象化手法を提案する。
- 参考スコア（独自算出の注目度）: 8.575617900074327
- License:
- Abstract: Generalized planning is concerned with how to find a single plan to solve multiple similar planning instances. Abstractions are widely used for solving generalized planning, and QNP (qualitative numeric planning) is a popular abstract model. Recently, Cui et al. showed that a plan solves a sound and complete abstraction of a generalized planning problem if and only if the refined plan solves the original problem. However, existing work on automatic abstraction for generalized planning can hardly guarantee soundness let alone completeness. In this paper, we propose an automatic sound and complete abstraction method for generalized planning with baggable types. We use a variant of QNP, called bounded QNP (BQNP), where integer variables are increased or decreased by only one. Since BQNP is undecidable, we propose and implement a sound but incomplete solver for BQNP. We present an automatic method to abstract a BQNP problem from a classical planning instance with baggable types. The basic idea for abstraction is to introduce a counter for each bag of indistinguishable tuples of objects. We define a class of domains called proper baggable domains, and show that for such domains, the BQNP problem got by our automatic method is a sound and complete abstraction for a generalized planning problem whose instances share the same bags with the given instance but the sizes of the bags might be different. Thus, the refined plan of a solution to the BQNP problem is a solution to the generalized planning problem. Finally, we implement our abstraction method and experiments on a number of domains demonstrate the promise of our approach.
- Abstract（参考訳）: 一般的なプランニングは、複数の類似のプランニングインスタンスを解決するための単一のプランを見つける方法に関するものだ。
抽象化は一般化計画の解法として広く用いられ、QNPは一般的な抽象モデルである。
最近、Cuiらにより、計画が一般化された計画問題の健全かつ完全な抽象化を解くことが示されている。
しかし、一般化計画のための自動抽象化に関する既存の研究は、完全性だけでなく、健全性を保証することはほとんどできない。
本稿では,バッグブル型を用いた一般化計画のための音響・完全抽象化手法を提案する。
我々は、有界QNP(bounded QNP, BQNP)と呼ばれるQNPの変種を用いて、整数変数を1つだけ増加または減少させる。
BQNP は決定不能であるため,BQNP に対して不完全な解法を提案し,実装する。
本稿では,バグのある古典的計画事例から,BQNP問題を自動的に抽象化する手法を提案する。
抽象化の基本的な考え方は、オブジェクトの識別不能なタプルのバッグごとにカウンタを導入することである。
我々は、適切なバッグ可能なドメインと呼ばれるドメインのクラスを定義し、そのようなドメインに対して、自動手法で得られるBQNP問題は、インスタンスが与えられたインスタンスと同一のバッグを共有するが、バッグのサイズが異なるような一般的な計画問題の健全かつ完全な抽象化であることを示す。
したがって、BQNP問題に対する解の洗練された計画は、一般化された計画問題の解である。
最後に,多くの領域における抽象化手法と実験を実装し,アプローチの可能性を実証する。
関連論文リスト
- Planning with OWL-DL Ontologies (Extended Version) [6.767885381740952]
フルパワー表現型DLをサポートするブラックボックスを提案する。
主要なアルゴリズムは、OWLによるPDDLへの計画仕様の書き直しに依存している。
いくつかのドメインからのベンチマークセットの実装を評価した。
論文 参考訳（メタデータ） (2024-08-14T13:27:02Z) - Depth-Bounded Epistemic Planning [50.42592219248395]
本稿では,動的てんかん論理に基づく新しい計画法を提案する。
新規性は、計画エージェントの推論の深さを上界bに制限することである。
推論深度の境界b内における解を持つ計画タスクに関して、完全なものであることを示す。
論文 参考訳（メタデータ） (2024-06-03T09:30:28Z) - Unified Task and Motion Planning using Object-centric Abstractions of
Motion Constraints [56.283944756315066]
本稿では,タスクとモーションプランニングを一つの検索に統一するTAMP手法を提案する。
我々のアプローチは、オフザシェルフAIサーチの計算効率を活用して、物理的に実現可能な計画が得られるような、オブジェクト中心の動作制約の抽象化に基づいている。
論文 参考訳（メタデータ） (2023-12-29T14:00:20Z) - 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) - Conditional Generation with a Question-Answering Blueprint [84.95981645040281]
我々は、条件生成を不透明にし、より根底的にレンダリングするための有用な中間表現としてのプランニングを提唱する。
我々は、最先端の質問生成技術を利用して、自動的に青写真を得る。
我々はTransformerベースのモデルを開発し、それぞれが生成した出力にブループリントを組み込む方法が異なる。
論文 参考訳（メタデータ） (2022-07-01T13:10:19Z) - Automatic Verification of Sound Abstractions for Generalized Planning [6.327435698167334]
一般計画は、計画問題の集合に対する一般解の計算を研究する。
音の抽象化は、一般的な計画問題に対する正確性を保証するものである。
論文 参考訳（メタデータ） (2022-05-24T08:48:30Z) - Scaling-up Generalized Planning as Heuristic Search with Landmarks [9.653976364051564]
一般化計画は通常、与えられたアルゴリズム的解の空間における探索として扱われる。
この種のソリューション評価は、計画インスタンスの表現において明示されていないどんなサブゴール情報も無視する。
GPのノード拡張は、古典的なプランニングインスタンスのバッチ全体にわたってすべての子ノードを評価する必要があるため、実行時のボトルネックである。
論文 参考訳（メタデータ） (2022-05-10T12:42:48Z) - Learning General Policies from Small Examples Without Supervision [18.718037284357834]
一般化計画は、計画ドメインの複数のインスタンスを一度に解決する一般的なポリシーの計算に関するものです。
近年、これらのポリシーは2つのステップで計算可能であることが示されている。まず、定性的数値計画問題(QNP)の形で適切な抽象化をサンプル計画から学習する。
本稿では,サンプルプランやqnpプランナーを必要とせず,より表現力のある汎用ポリシーを計算するための代替手法を提案する。
論文 参考訳（メタデータ） (2021-01-03T19:44:13Z) - Planning with Learned Object Importance in Large Problem Instances using
Graph Neural Networks [28.488201307961624]
現実の計画問題は、数百から数千ものオブジェクトを巻き込むことが多い。
単一推論パスにおけるオブジェクトの重要性を予測するためのグラフニューラルネットワークアーキテクチャを提案する。
提案手法では,プランナと遷移モデルをブラックボックスとして扱い,既製のプランナで使用することができる。
論文 参考訳（メタデータ） (2020-09-11T18:55: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) - STRIPS Action Discovery [67.73368413278631]
近年のアプローチでは、すべての中間状態が欠如している場合でも、アクションモデルを合成する古典的な計画が成功している。
アクションシグネチャが不明な場合に,従来のプランナーを用いてSTRIPSアクションモデルを教師なしで合成するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-30T17:08:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。