論文の概要: Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems
- arxiv url: http://arxiv.org/abs/2504.15668v1
- Date: Tue, 22 Apr 2025 07:45:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-30 21:43:12.674052
- Title: Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems
- Title（参考訳）: ハイブリッド計画問題における不可解性説明のための必然的方法の探索
- Authors: Mir Md Sajid Sarwar, Rajarshi Ray,
- Abstract要約: 計画問題の解決不可能を説明することは、説明可能なAI計画において重要な研究の関心事である。
本稿では,ハイブリッドシステムにおける計画問題の未解決性を解析・説明するためのメカニズムとして,サブプロブレム同定という同じ哲学を採用することを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Explaining unsolvability of planning problems is of significant research interest in Explainable AI Planning. AI planning literature has reported several research efforts on generating explanations of solutions to planning problems. However, explaining the unsolvability of planning problems remains a largely open and understudied problem. A widely practiced approach to plan generation and automated problem solving, in general, is to decompose tasks into sub-problems that help progressively converge towards the goal. In this paper, we propose to adopt the same philosophy of sub-problem identification as a mechanism for analyzing and explaining unsolvability of planning problems in hybrid systems. In particular, for a given unsolvable planning problem, we propose to identify common waypoints, which are universal obstacles to plan existence; in other words, they appear on every plan from the source to the planning goal. This work envisions such waypoints as sub-problems of the planning problem and the unreachability of any of these waypoints as an explanation for the unsolvability of the original planning problem. We propose a novel method of waypoint identification by casting the problem as an instance of the longest common subsequence problem, a widely popular problem in computer science, typically considered as an illustrative example for the dynamic programming paradigm. Once the waypoints are identified, we perform symbolic reachability analysis on them to identify the earliest unreachable waypoint and report it as the explanation of unsolvability. We present experimental results on unsolvable planning problems in hybrid domains.
- Abstract（参考訳）: 計画問題の解決不可能を説明することは、説明可能なAI計画において重要な研究の関心事である。
AI計画文学は、計画問題に対するソリューションの説明を作成するためのいくつかの研究成果を報告している。
しかしながら、計画問題の未解決性を説明することは、ほとんどオープンで検討された問題である。
計画生成と自動問題解決に対する広く実践されたアプローチは、一般に、タスクをサブプロブレムに分解して、目標に向かって徐々に収束させることである。
本稿では,ハイブリッドシステムにおける計画問題の未解決性を解析・説明するためのメカニズムとして,サブプロブレム同定という同じ哲学を採用することを提案する。
特に,ある解決不可能な計画問題に対して,計画上の共通の障害である共通経路点を同定することを提案する。
この研究は、当初の計画問題の未解決性の説明として、計画問題のサブプロブレムや、これらの経路ポイントのいずれにも到達不可能な部分として、そのような経路ポイントを想定している。
本稿では,コンピュータ科学において最も長い共通部分列問題の例として,動的プログラミングパラダイムの実証的例として一般的に広く用いられている問題として,問題をキャストすることで,新たなウェイポイント同定法を提案する。
ひとたびウェイポイントが特定されると、それらに対してシンボル的到達可能性分析を行い、到達不能な最初期のウェイポイントを特定し、未解決性の説明として報告する。
ハイブリッドドメインにおける解決不可能な計画問題の実験的結果を示す。
関連論文リスト
- Introduction to AI Planning [0.0]
注記は州モデルの導入から始まり、古典的な計画の探求に移る。
最も広範なセクションは階層的タスクネットワーク(HTN)計画に特化している。
講演ノートは、計画ドメイン定義(PDDL)言語に関するボーナス章で終わる。
論文 参考訳（メタデータ） (2024-12-16T10:38:04Z) - Unified Task and Motion Planning using Object-centric Abstractions of
Motion Constraints [56.283944756315066]
本稿では,タスクとモーションプランニングを一つの検索に統一するTAMP手法を提案する。
我々のアプローチは、オフザシェルフAIサーチの計算効率を活用して、物理的に実現可能な計画が得られるような、オブジェクト中心の動作制約の抽象化に基づいている。
論文 参考訳（メタデータ） (2023-12-29T14:00:20Z) - Automated Process Planning Based on a Semantic Capability Model and SMT [50.76251195257306]
製造システムと自律ロボットの研究において、機械で解釈可能なシステム機能の仕様に「能力」という用語が用いられる。
セマンティック能力モデルから始めて、AI計画問題を自動的に生成するアプローチを提案する。
論文 参考訳（メタデータ） (2023-12-14T10:37:34Z) - What Planning Problems Can A Relational Neural Network Solve? [91.53684831950612]
本稿では,計画問題のポリシーを表すリレーショナルニューラルネットワークの回路複雑性解析について述べる。
回路幅と深さの増大に関して,計画問題には3つの一般的なクラスが存在することを示す。
また、政策学習のためのニューラルネットワーク設計におけるこの分析の有用性についても解説する。
論文 参考訳（メタデータ） (2023-12-06T18:47:28Z) - 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) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。
TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。
TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文 参考訳（メタデータ） (2023-10-06T01:40:09Z) - A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist
Scheduling Problems [11.66506213335498]
ホイストスケジューリングは、自律デバイスの開発で産業応用の電気めっきのボトルネックとなっている。
適応型PDDLの形で新しい時間計画問題としてホイストスケジューリング問題を定式化する。
この問題に対するソリューションメソッドの評価に使用できる実生活ベンチマークインスタンスのコレクションを提供する。
論文 参考訳（メタデータ） (2022-12-11T05:30:44Z) - Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion
Planning [36.300564378022315]
本稿では,移動環境における移動操作問題を解決するための学習可能なタスク・アンド・モーション・プランニング(TAMP)アルゴリズムを提案する。
本アルゴリズムのコアは,タスク計画,目標,初期状態を考慮したトランスフォーマーに基づく新しい学習手法であるPIGINetであり,タスク計画に関連する運動軌跡の発見確率を予測する。
論文 参考訳（メタデータ） (2022-11-03T04:12:04Z) - Temporal Planning with Incomplete Knowledge and Perceptual Information [0.0]
本稿では,時間的計画枠組み内での緊急計画構築を組み合わせた新しい計画手法を提案する。
本研究では,不完全かつ(ii)知識認識行動をモデル化するために,計画ドメイン定義言語(PDDL)の小さな拡張を提案する。
また,様々な問題に対して優れた性能を示す新しい計画領域も導入した。
論文 参考訳（メタデータ） (2022-07-20T07:26:08Z) - Anytime Stochastic Task and Motion Policies [12.72186877599064]
本稿では,タスクと動作計画を統合するための新しい手法を提案する。
我々のアルゴリズムは確率論的に完全であり、いつでも実現可能な解ポリシーを計算できる。
論文 参考訳（メタデータ） (2021-08-28T00:23:39Z) - Multiple Plans are Better than One: Diverse Stochastic Planning [26.887796946596243]
計画上の問題では、望ましい仕様を完全にモデル化することはしばしば困難です。
特に、人間とロボットの相互作用において、そのような困難は、プライベートまたはモデルに複雑である人間の好みによって生じる可能性がある。
我々は、最適に近い代表行動の集合を生成することを目的とした、多種多様な計画と呼ばれる問題を定式化する。
論文 参考訳（メタデータ） (2020-12-31T07:29:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。