自動計画
機械であるか人間であるかに関わらず、周囲の状況が既知で、その構造がよく理解されている場合、計画や戦略というものは行動する前にあらかじめ組み立てておく(計算しておく)ことができる。一方未知の環境では、周囲の状況が明らかになるにつれて、戦略の修正を迫られる場合も多い。前者はオフラインプランニング、静的プランニングなどと呼ばれ、後者は動的プランニング、オンラインプランニングなどと呼ばれる。計画の修正のことを特にリプランニングとも呼ぶ。いずれのプランニングでも、人工知能によく見られる試行錯誤の反復過程が必要となることが多い。自動計画には、動的計画法、強化学習、組合せ最適化が含まれる。
プランナ(自動計画器)は一般に、外界の初期状態、目標とされるゴール、とりうるアクションの集合という3つの入力を必要とする。これらは STRIPS をはじめとする形式言語で記述される。STRIPSはプログラミング言語のような見た目をしているため、ある程度人間にも読め、かつ機械可読である。プランナ(自動計画器)は初期状態からゴール状態へと状態を変化させる一連のアクションの計画を生成する。
古典的プランニング (Classical Planning) は、それらの前提を全て単純化した基礎的なモデルである(不確実性なし、完全情報、アクションの並列実行なし)。人工知能黎明期から存在し、よく研究されている。計算複雑性クラスはPSPACE完全に属する。 STRIPSプランニングはクラスPSPACE完全に属し、一般に「計算量理論に基づき難しい」と考えられているNP完全問題以上に難しいと考えられている。ただし、 N P ≤ P S P A C E {\displaystyle NP\leq PSPACE} であっても N P ≠ P S P A C E {\displaystyle NP\not =PSPACE} かはまだ証明されていない。
プランニング問題を解く手法の研究は主に2つのカテゴリに大別できる。 1つ目のカテゴリは、誤解を招く名称であるが、プランニング分野における Model-based Planning である。このグループの手法は、PDDLによって表現された問題を充足可能性問題(Satplan)や整数計画問題 に変換して解く。