自動計画
自動計画は、利用可能な行動の形式的な記述が与えられた場合に、世界の初期状態を望ましい目標状態に変換する行動のシーケンスを計算することに関心を持つ人工知能の分野である。
Definition
自動計画とは、各行動が世界の状態をどのように変化させるかのモデルが与えられた場合に、初期状態から目標を確実に達成する計画、すなわち順序付けられた（または部分的に順序付けられた）行動の集合を計算することである。
Scope
この分野は、計画問題の表現（状態、事前条件と効果を伴う行動、目標）と、それらを解決するアルゴリズムを扱う。具体的には、決定論的で完全に観測可能なドメインにおける古典的計画、計画グラフとヒューリスティック探索手法、階層的タスクネットワーク計画、および時間、リソース、スケジューリングへの拡張が含まれる。STRIPSやPDDLといった標準的な形式主義と計画の複雑性についても論じる。確率的不確実性下での計画は、不確実性下での推論と関連し、データからの行動モデルやポリシーの学習は、機械学習のサブフィールドに属する。
Sub-topics
Core questions
- 行動、状態、目標は、大規模なドメインを記述するのに十分コンパクトにどのように表現されるか？
- 指数関数的に大きな状態空間にもかかわらず、計画問題はどのように効率的に探索されるか？
- 許容可能で有益なヒューリスティクスは、ドメイン記述からどのように自動的に導出されるか？
- 計画はどのように階層的に構造化でき、時間とリソースの制約はどのように組み込まれるか？
Key concepts
- 状態、行動、目標
- 事前条件と効果
- STRIPSとPDDL
- 順方向および逆方向状態空間探索
- 計画グラフ
- ドメイン非依存ヒューリスティクス
- 階層的タスクネットワーク
- 時間計画とスケジューリング
Key theories
- STRIPS行動表現
- STRIPS形式主義は、命題の集合に対する事前条件と追加/削除効果によって行動を記述し、計画を明示的な世界状態の列挙ではなく、記号的状態を介した探索にするコンパクトで因数分解された表現を提供する。
- 計画のためのドメイン非依存ヒューリスティック探索
- 現代のプランナーは、計画をヒューリスティック探索として捉え、例えば削除効果を無視したり、因果構造を利用したりすることで、問題記述からヒューリスティクスを自動的に導出し、強力な汎用性能を可能にしている。
- 問題クラスの階層としての計画
- 計画は、古典的な決定論的計画から、階層的、時間的、リソース制約のあるバリアントまで多岐にわたり、それぞれが特徴的な表現と複雑性を持ち、自動計画の標準理論において体系化されている。
Clinical relevance
自動計画は、ロボット工学および自律システム、宇宙船およびミッション運用、ロジスティクスおよびサプライチェーン、製造、ゲームおよび物語生成に応用されている。これらの技術から派生したプランナーは、実際の自律宇宙船を制御し、複雑なワークフローを調整してきた。
History
自動計画は、1971年頃にSRIのShakeyロボットのためにSTRIPSで始まり、計画を行動記述に対する定理証明として位置づけた。この分野は、部分順序計画、Graphplanの画期的な進歩（1995年）、そして1990年代後半以降の高速なドメイン非依存ヒューリスティック探索プランナーとPDDL標準の台頭を経て発展し、国際計画コンペティションを通じてその進捗が追跡されている。
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- 自動計画は一般的な探索とどう違うのか？
- 自動計画は探索の一種であるが、不透明な後続関数ではなく、行動の宣言的で因数分解された記述（事前条件と効果）に基づいて機能する。この構造により、プランナーはヒューリスティクスを自動的に導出し、どの行動が関連するかを推論できるが、これは一般的な探索ではできない。
- PDDLとは何か？
- PDDL（Planning Domain Definition Language）は、計画ドメインと問題（オブジェクト、述語、行動、初期状態、目標）を記述するための標準言語である。これにより、国際計画コンペティションのように、ドメイン非依存プランナーを共通のベンチマークで比較することが可能になる。