古典的プランニングにおけるヒューリスティック関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/16 01:19 UTC 版)
「自動計画」の記事における「古典的プランニングにおけるヒューリスティック関数」の解説
プランニング問題の計算複雑性は、問題に様々な仮定を入れることで下げることができることが知られている。この事実を利用して、与えられた問題に制約を加えた簡単な問題 (緩和問題)を解くことで、元の問題を解く際の枝刈りに用いる手法が多数提案されている。プランニングのおけるヒューリスティック関数とは、緩和によって簡単になった問題を解くことによって得られる緩和コストのことである。近年の研究は、特定のドメインに依存しないドメイン非依存ヒューリスティックの研究に集中している。 一方で、ドメイン依存ヒューリスティックの研究も、特定の重要な応用分野においては行われている。ドメイン依存ヒューリスティックの例としては、迷路における経路探索において、ゴールまでのユークリッド距離やマンハッタン距離をA*探索などのアルゴリズムにおいて使うことに相当する。この場合、ユークリッド距離は「壁の存在しない迷路」という緩和問題の解コストと捉えることができる。 注意したいのが、ここにおける「ヒューリスティック」と、焼きなまし法や遺伝的アルゴリズムなどの文脈における「ヒューリスティック手法」という言葉における「ヒューリスティック」とでは意味合いが異なるという点である。後者では解の収束性や実用的に得られる解の最適性などの理論的保証に問題があり、「実応用ではおおよそ動くヒューリスティック(勘)」という意味合いがあるのに対して、プランニングにおけるヒューリスティックはあくまで「アルゴリズムにとって人間の勘に相当するもの」という意味合いであり、また実際に分枝限定法の下界関数として振る舞うため解の最適性が証明されている。 以下には、特に古典的プランニングの代表的なドメイン非依存ヒューリスティックについて述べる。 削除効果緩和: 現在最も主要な緩和手法である。削除効果を持たないプランニング問題を最小ステップで解く最適解を得る問題は、NP完全である。この事実は、Landmark-Cut , Operator Counting など近年の枝刈り手法の基礎となっている。これらの手法では、緩和によってNP完全になった問題をさらに緩和してPに落とすことにより、計算量と緩和の質をバランスさせている。 ランドマーク: ある問題において、すべてのプランにおいて必ず現れるアクション/命題のことをランドマークと呼ぶ。このグループのヒューリスティックは、削除効果緩和を施した上で、さらに探索空間をランドマークに絞って探索することで多項式時間に落とす。 コスト分割 (Cost partitioning): ある問題Pのすべてのアクションにおいて、アクションのコストcをc=c_1+c_2 と分割し、分割されたコストをコストにもつ２つの問題P1,P2に複製することを考える。このとき、P1の最小解コストとP2の最小解コストの和はPの最小解コストの下界となる。このことを利用して、適切にコスト分割を施せば、それぞれの小さな問題を解くことでより高速に下界を得ることができる。 Abstraction : PDB, Merge-and-Shrink, Bisumlation Merge-and-Shrink
※この「古典的プランニングにおけるヒューリスティック関数」の解説は、「自動計画」の解説の一部です。
「古典的プランニングにおけるヒューリスティック関数」を含む「自動計画」の記事については、「自動計画」の概要を参照ください。
- 古典的プランニングにおけるヒューリスティック関数のページへのリンク
