自動計画
2008年の "How Good is Almost Perfect?." (AAAI08 Best Paper) という論文によって、 ヒューリスティック関数をどれだけ改善しても、完璧なヒューリスティック(緩和を行わない=計算するのにもとの問題を解くのと同じだけの計算量がかかるので非実用的)を得ない限り究極的には指数爆発が避けられないケースがあることが示された。 以来、上記2つとは独立した探索手法の改善、ないし枝刈り手法が求められている。
このうち代表的な手法に、対称性検知(symmetry breaking)、行き止まり検知(dead-end detection)、Dominance Pruning、Partial Order Pruningなどがある。 対称性検知は、探索グラフのうちisomorphicな部分グラフを検知して、その一つを残してすべて枝刈りする。 行き止まり検知は、現在のノードからはゴールにたどり着けないことを、実際にゴールを探索し尽くすことなく検知する。 Dominance Pruningは、「あるノードが別のノードよりも悪い」ことを、ヒューリスティクス関数/下界関数による分枝限定法とは別の仕組みで検知する。 Partial Order Pruningは、順序を入れ替えただけのアクションの列のうち、一つを残して枝刈りする。
アクションの実行結果に不確実性を取り入れたプランニングは 非決定的プランニング(Nondeterministic Planning) と呼ばれる。 非決定的プランニングのもとでは、一つのアクションの結果として複数の実行結果がありえ、どの状態に遷移するかがわからない。 古典プランニングの解がアクションの列であるプランを返すのに対し、非決定的プランニングの解はアクションのDAGであるポリシーである。 これは、非決定性の影響でアクションの実行結果が枝分かれするからである。 非決定的プランニングの探索グラフは、アクションの非決定性を表現できるAND-OR木である。
非決定的プランニングのうち、それぞれの結果について遷移確率があたえられる場合を 確率的プランニング(Probabilistic Planning) と呼ぶ。 確率的プランニングはマルコフ決定過程 (MDP) として定式化される。また、不完全情報での確率的プランニングは部分観測マルコフ決定過程 (POMDP) によってモデル化される。
非決定/確率的プランニング問題を表現するモデル言語として、PDDLの拡張言語、Probabilistic PDDL (PPDDL) が2004年に提唱され、コンペティションおよび実応用で用いられている。
またもや誤解を招く名称であるが、プランニング分野における Symbolic Planning (PDDLプランニングの分野全体が記号的AIに含まれるにもかかわらず) とは、二分決定図 / Binary Decision Diagram によって、多数の探索ノードを圧縮表現として保持、かつ圧縮されたまま操作する探索手法である。これは前方/後方探索のどちらにも対応しており、国際コンペティション IPC 2014 にてSymBA*プランナーが優勝している。
近年の新たな方向性としては、Top-K プランニングおよび多様性プランニング(Diverse Planning)がある。 これは、実応用では複数の「次善の策」を用意しておくことが求められること、および(人間による間違ったモデリングにより)プランナの返却した最適解が現実の問題の最適解になっていないことを考慮して、 複数の、質的に異なるプランを返却する。