古典的プランニング
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/16 01:19 UTC 版)
古典的プランニング (Classical Planning) は、それらの前提を全て単純化した基礎的なモデルである(不確実性なし、完全情報、アクションの並列実行なし)。人工知能黎明期から存在し、よく研究されている。計算複雑性クラスはPSPACE完全に属する。STRIPSプランニングはクラスPSPACE完全に属し、一般に「計算量理論に基づき難しい」と考えられているNP完全問題以上に難しいと考えられている。ただし、 N P ≤ P S P A C E {\displaystyle NP\leq PSPACE} であっても N P ≠ P S P A C E {\displaystyle NP\not =PSPACE} かはまだ証明されていない。 プランニング問題を解く手法の研究は主に２つのカテゴリに大別できる。１つ目のカテゴリは、誤解を招く名称であるが、プランニング分野における Model-based Planning である。このグループの手法は、PDDLによって表現された問題を充足可能性問題（Satplan）や整数計画問題 に変換して解く。この種類の研究では、主に２つの問題が主眼となる。１つ目は、対象となるソルバへの変換が多項式時間で行えるか、そして２つ目は対象となるソルバが枝刈りを行いやすいようにいかに追加の冗長な制約 (SATにおける項、整数計画における不等式制約) を与えるかである。 ２つ目の、より主流の探索手法は、状態空間探索である。状態空間探索の研究にも２つのカテゴリがある。まず１つ目のカテゴリはヒューリスティック関数の開発である。ヒューリスティック関数は、状態空間探索における探索ノードに対する評価関数であり、探索ノードを順位づけし、分枝限定法における下界関数として振る舞い枝刈りに寄与する。２つ目のカテゴリは探索手法の開発である。それぞれの探索手法は、ヒューリスティクス関数を持ちいてどのように状態空間を探索するかを決定し、これはメモリの使用量、実行時間、解の質(quality)や性質(characteristics)に影響する。探索手法と評価関数は独立であり、おおよそ任意の探索手法と任意の枝刈り手法を組み合わせることができる。
※この「古典的プランニング」の解説は、「自動計画」の解説の一部です。
「古典的プランニング」を含む「自動計画」の記事については、「自動計画」の概要を参照ください。
- 古典的プランニングのページへのリンク
