自動計画
無線ネットワークでつながった多数のロボットを用いた倉庫管理など、複数の分散エージェントを用いたプランニング問題を考える。 この問題をSTRIPSプランニングとして定式化すると、STRIPSが完全情報問題を前提としているため、問題の計算量がエージェントの数に従って指数爆発する。 この問題を解決するために提案されたのが、 MA-STRIPS 言語を用いるマルチエージェントプランニング問題である。 マルチエージェントプランニング問題は、すべてのアクションがエージェント引数を持ち、エージェント間での情報交換が制限される。 このクラスの問題の計算複雑性や、問題を解く様々なアルゴリズムが提案されている。 実応用上の要求から特に経路探索問題が重点的に研究されており、この場合には MAPF (Multi-Agent Path Finding) と呼ばれる。
プランニング問題の計算複雑性は、問題に様々な仮定を入れることで下げることができることが知られている。 この事実を利用して、与えられた問題に制約を加えた簡単な問題 (緩和問題)を解くことで、元の問題を解く際の枝刈りに用いる手法が多数提案されている。 プランニングのおけるヒューリスティック関数とは、緩和によって簡単になった問題を解くことによって得られる緩和コストのことである。 近年の研究は、特定のドメインに依存しないドメイン非依存ヒューリスティックの研究に集中している。
一方で、ドメイン依存ヒューリスティックの研究も、特定の重要な応用分野においては行われている。 ドメイン依存ヒューリスティックの例としては、迷路における経路探索において、ゴールまでのユークリッド距離やマンハッタン距離をA*探索などのアルゴリズムにおいて使うことに相当する。 この場合、ユークリッド距離は「壁の存在しない迷路」という緩和問題の解コストと捉えることができる。
注意したいのが、ここにおける「ヒューリスティック」と、焼きなまし法や遺伝的アルゴリズムなどの文脈における「ヒューリスティック手法」という言葉における「ヒューリスティック」とでは 意味合いが異なるという点である。後者では解の収束性や実用的に得られる解の最適性などの理論的保証に問題があり、「実応用ではおおよそ動くヒューリスティック(勘)」という意味合いがあるのに対して、 プランニングにおけるヒューリスティックはあくまで「アルゴリズムにとって人間の勘に相当するもの」という意味合いであり、 また実際に分枝限定法の下界関数として振る舞うため解の最適性が証明されている。
この種類の研究では、主に2つの問題が主眼となる。1つ目は、対象となるソルバへの変換が多項式時間で行えるか、そして2つ目は対象となるソルバが枝刈りを行いやすいようにいかに追加の冗長な制約 (SATにおける項、整数計画における不等式制約) を与えるかである。
2つ目の、より主流の探索手法は、状態空間探索である。 状態空間探索の研究にも2つのカテゴリがある。 まず1つ目のカテゴリはヒューリスティック関数の開発である。 ヒューリスティック関数は、状態空間探索における探索ノードに対する評価関数であり、探索ノードを順位づけし、分枝限定法における下界関数として振る舞い枝刈りに寄与する。 2つ目のカテゴリは探索手法の開発である。 それぞれの探索手法は、ヒューリスティクス関数を持ちいてどのように状態空間を探索するかを決定し、これはメモリの使用量、実行時間、解の質(quality)や性質(characteristics)に影響する。 探索手法と評価関数は独立であり、おおよそ任意の探索手法と任意の枝刈り手法を組み合わせることができる。
不完全情報を取り入れたプランニングは、「センサなしでも確実に実行できるプランを生成する」Conformant Planning,「センサによる観測アクションを含めた実行プランを生成する」Contingent Planning に分類される。