古典的プランニングとSTRIPS

古典的プランニングは、決定論的で完全に観測可能な静的環境において、前提条件と効果によるSTRIPS形式のアクションの表現を用いて、目標を達成するための一連のアクションを見つける問題に対処します。

Definition

古典的プランニングは、完全に既知の初期状態を目標を満たす状態に変換する一連の決定論的アクションを探索するものであり、各アクションは適用されるために満たされるべき条件とそれがもたらす変化によって記述されます。

Scope

このトピックでは、古典的プランニングモデルとその仮定（決定論的アクション、完全な観測可能性、単一エージェント、原子的な時間）、状態とアクションのSTRIPSおよびADL/PDDL表現、順方向（進行）および逆方向（回帰）の状態空間探索と部分順序プランニングの基本的な解決方法、および命題プランニングの計算複雑度について扱います。ヒューリスティックなガイダンスとプランニンググラフは関連トピックで扱われ、非決定論的または確率論的なバリアントは範囲外です。

Core questions

• 古典的プランニングモデルを定義する仮定は何であり、それらはいつ適切であるか？
• STRIPS表現は、状態を命題に、アクションを前提条件と追加/削除効果にどのように分解するか？
• 進行探索と回帰探索はプランニング戦略としてどのように異なるか？
• 古典的プランニングは一般的にどの程度計算的に困難か？

Key concepts

• 決定論的で完全に観測可能なモデル
• STRIPSの前提条件と効果
• 追加リストと削除リスト
• PDDLとADL
• 進行（順方向）探索
• 回帰（逆方向）探索
• 部分順序プランニング
• プラン存在の複雑性

Key theories

STRIPS表現

STRIPSは、世界を一連の真の命題として記述し、各アクションを前提条件リストと追加・削除リストによって記述します。これにより、アクションの適用は単に命題を追加・削除するだけであり、この分解されたモデルはほとんどすべての古典的プランナーの基盤となっています。

進行探索と回帰探索

古典的プランは、初期状態から適用可能なアクションを適用して前方に探索する（進行）か、目標から回帰したサブゴールを計算して後方に探索する（回帰）ことによって見つけることができます。部分順序プランニングは、アクションの完全な順序付けへのコミットメントを緩和します。

プランニングの複雑性

命題STRIPSプランが存在するかどうかを決定することは、一般的にPSPACE完全であり、プランニングがなぜ難しいのかを形式的に説明し、それを実用的にするためのヒューリスティックおよび構造的手法を動機づけています。

Clinical relevance

古典的プランニングの表現は、ロボットのタスクプランニング、自動組み立ておよびロジスティクス、そして決定論的アクションを順序付けて目標を達成する必要があるあらゆるアプリケーションにおける共通のインターフェースです。PDDLベースの古典的プランナーは、この分野および国際プランニング競技会の主力となっています。

History

STRIPSは1971年頃にSRIでShakeyロボットを制御するために開発され、古典的プランニングを定義する前提条件/効果アクションモデルを導入しました。部分順序プランニングは1970年代から80年代にかけて成熟し、Bylanderは1994年に命題プランニングのPSPACE完全性を確立し、その後PDDL標準がこの分野のベンチマークを統一しました。

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

古典的プランニングの仮定は何ですか？

古典的プランニングは、決定論的で完全に観測可能な静的環境で行動する単一のエージェントを仮定し、アクションは単位時間を要し、初期状態は完全に既知であるとします。これらの仮定のいずれかを緩和すること、例えば不確実性や並行性を許容することは、古典的モデルを超えるより豊かなプランニング問題につながります。

STRIPSの追加リストと削除リストは何を意味しますか？

STRIPSアクションが適用されると、その追加リストにある命題は真になり、削除リストにある命題は偽になります。その他のすべての命題は変更されません。この単純な更新ルールが、STRIPSをアクションが世界をどのように変化させるかのコンパクトで計算上便利な表現にしています。