古典的プランニングにおける探索手法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/16 01:19 UTC 版)
「自動計画」の記事における「古典的プランニングにおける探索手法」の解説
現在最も多数派の探索手法は前方探索(Forward search)である。このカテゴリの基礎的なものとしては、A*(ダイクストラ法+ヒューリスティック関数)、反復深化A*(反復深化深さ優先探索+ヒューリスティック関数)、貪欲最良優先探索(Greedy Best First Search)などがある。 後方探索は、ゴールから逆にたどってどのようにすれば初期状態にたどり着けるかを探索する。後方探索には前方探索にない固有の技術的困難があり、近年では研究が停滞している。 ここ近年活発に研究され始めたものが双方向探索である。双方向探索は70年台に研究されていたが、探索の効率性を担保する理論的発展が得られず研究が衰退していた。2016年のMMアルゴリズムの発見によって前方探索と後方探索のフロンティアが探索深さの中心点で出会う保証がなされ、近年再び活発に研究が行われている。 またもや誤解を招く名称であるが、プランニング分野における Symbolic Planning (PDDLプランニングの分野全体が記号的AIに含まれるにもかかわらず) とは、二分決定図 / Binary Decision Diagram によって、多数の探索ノードを圧縮表現として保持、かつ圧縮されたまま操作する探索手法である。これは前方/後方探索のどちらにも対応しており、国際コンペティション IPC 2014 にてSymBA*プランナーが優勝している。 近年の新たな方向性としては、Top-K プランニングおよび多様性プランニング(Diverse Planning)がある。これは、実応用では複数の「次善の策」を用意しておくことが求められること、および(人間による間違ったモデリングにより)プランナの返却した最適解が現実の問題の最適解になっていないことを考慮して、複数の、質的に異なるプランを返却する。
※この「古典的プランニングにおける探索手法」の解説は、「自動計画」の解説の一部です。
「古典的プランニングにおける探索手法」を含む「自動計画」の記事については、「自動計画」の概要を参照ください。
- 古典的プランニングにおける探索手法のページへのリンク
