Planning with SAT, Admissible Heuristics and A*(Rintanen; 2011)

Rintanen氏のPlanning as SAT論文4号の解説である。 先に紹介した3つの論文では対象はPlanのOptimalityとしてsatisfiableを想定したものであった。 この論文ではより高度なOptimality(というかsatisfiableはOptimalityをなにも保証していない)を保証するような探索についての考察を行うものである。すなわち、比較対象のsearch-basedなプランナはAあるいはIDAアルゴリズムにAdmissibleなヒューリスティック関数を使って探索を行うようなプランナである。

この論文において考察する問題は、ゴールを達成するような最小個数のアクションからなるプランを求めるというものである。 これは、actionのコストが一様であり、かつ直列プランニングの場合にはglobal optimalityと一致する。 ちなみに、最近僕が取り組んでいる研究のうちの一つはModel basedなプランナを使ってコスト付きの場合のGlobal Optimalityを保証する手法に関するものである。

比較対象のA*アルゴリズムは[Hart et. al.;1968]にて提案されたものであり、あるadmissibleなヒューリスティックのものでの探索では最小の展開ノード数で最適性を保証した解の探索を終えるものである。perferctなヒューリスティックのもとではゴール状態に到達するのに必要な最小のアクションに対応するノードだけを展開し探索過程を終えるため非常に効率的であると言える。一方で、h() = 0などの良くないヒューリスティックのもとでは解の長さに対して指数的なメモリを要求するという限界がある。

A系のアルゴリズムヒューリスティック関数の計算をSATでエミュレート可能であれば探索過程をSAT-based plannerで効率的にエミュレート可能であるが、一方でその逆は時に不可能である。 具体的には、問題サイズ(命題、アクションの個数)に対して線形程度のプランを求める時、Aでは指数オーダーのメモリが必要になる一方で、SATで定式化された問題では多項式程度のメモリしか必要としない。(SAT <= NP <= PSPACEなのでこのこと自体は自明) IDA[Korf; 1985]は、Aに対して大きなオーバーヘッドなく、必要とするメモリ領域を指数クラスから線形クラスに落とすことの出来る有名な手法である。 最悪時の比較ではSAT, IDAは同じ(時間/空間)計算量に属するものの、IDAよりはどのような場合にも悪くならないようなSATによるIDAのエミュレーションが存在すること、逆に、SATでは効率的に解ける一方で、AあるいはIDA*では指数的に計算量が悪くなるようなケースが存在することを示したのがこの論文の成果である。