自動計画
非決定的プランニングに対する古典的な探索アルゴリズムの代表的なものに、Value IterationおよびAO*アルゴリズムがある。 Value Iterationはヒューリスティクスを用いない知識なし探索であるため、ダイクストラ法の非決定的プランニングへの拡張と捉えることができる。 この理解のもとでは、AO*はValue Iterationにヒューリスティクスを足した知識有り探索版であり、またA*を非決定的プランニングに拡張したものとも捉えられる。 ダイクストラやA*と同様、AO*は、許容的ヒューリスティック関数(厳密な下界関数)を用いれば最適ポリシーを発見できる。 これらのアルゴリズムは確率的プランニングにも同様に適用できる。
非決定的プランニングのうち、解ポリシーにループを含む必要がある場合(すなわち、ポリシーが非DAGとなる場合)AO*は適切な解を生成しない。この点を改善したのがLAO*である。
非決定的環境に対する確率的探索アルゴリズムの代表的なものとして、モンテカルロ木探索(MCTS)がある。 確率的アルゴリズムであること(アルゴリズムが乱択に基づくこと)と、環境の振る舞い(アクション)が確率的であることは別の概念であることに注意したい。 確率的アルゴリズムであるMCTSは、時間を無限大にとる極限では最適解に収束するが、実時間ではこれは保証されない。
自動計画(じどうけいかく、英: Automated planning and scheduling)は、人工知能のテーマの1つであり、戦略や行動順序の具体化をすること。典型的な例として、知的エージェント、自律型ロボット、無人航空機などでの利用がある。古典的制御システムや統計分類問題とは異なり、自動計画の解は複雑で未知であり、多次元空間における発見と最適化が必要となる。
例えば、右図は Blocksworld (つみ木の世界) と呼ばれる、教科書でよく使われるSTRIPS問題の例を示している。初期状態は積み木が地面に置いてある状態、ゴールは積み木がA,B,Cの順で積まれている状態である。この問題のプランは、ロボットアームが積み木を運ぶ動作に相当する。今日では、STRIPS入力形式に拡張を加えたen:PDDLが主に使われている。
プランニングの難しさは、前提の単純化(不確実性、観測可能性、並列性、時間、連続変数)をどの程度行うかに依存する。そのため、単純化のレベルによりその様々な変種が存在し、またそれに適したアルゴリズムが提案されている。単純化したモデルは現実世界をモデル化するのに必ずしも実用的であるとは限らないが、実用的な場合も存在するし、またその存在意義には、単純なモデルで発見された知見は基礎的であり、より複雑なモデルにも適用できるはずだという期待が込められている。 ただし注意したいのは、最も基礎的な古典的プランニングでさえその計算複雑性クラスがPSPACE完全であり、すでにあきれるほど難しいという事実である。 拡張を加えることは、問題が上位の複雑性クラス(例えばEXPTIME)などに繰り上がることを意味している。