自動計画
以下には、特に古典的プランニングの代表的なドメイン非依存ヒューリスティックについて述べる。
削除効果緩和: 現在最も主要な緩和手法である。削除効果を持たないプランニング問題を最小ステップで解く最適解を得る問題は、NP完全である。この事実は、Landmark-Cut , Operator Counting など近年の枝刈り手法の基礎となっている。これらの手法では、緩和によってNP完全になった問題をさらに緩和してPに落とすことにより、計算量と緩和の質をバランスさせている。
ランドマーク: ある問題において、すべてのプランにおいて必ず現れるアクション/命題のことをランドマークと呼ぶ。このグループのヒューリスティックは、削除効果緩和を施した上で、さらに探索空間をランドマークに絞って探索することで多項式時間に落とす。
コスト分割 (Cost partitioning): ある問題Pのすべてのアクションにおいて、アクションのコストcをc=c_1+c_2 と分割し、分割されたコストをコストにもつ2つの問題P1,P2に複製することを考える。このとき、P1の最小解コストとP2の最小解コストの和はPの最小解コストの下界となる。このことを利用して、適切にコスト分割を施せば、それぞれの小さな問題を解くことでより高速に下界を得ることができる。
Abstraction : PDB, Merge-and-Shrink, Bisumlation Merge-and-Shrink