自動計画

出典: フリー百科事典『ウィキペディア（Wikipedia）』

自動計画（英: Automated planning and scheduling）は人工知能のテーマの1つであり、戦略や行動順序の具体化をすること。典型的な例として、知的エージェント、自律型ロボット、無人航空機などでの利用がある。古典的制御システムや統計分類問題とは異なり、自動計画の解は複雑で未知であり、多次元空間における発見と最適化が必要となる。

既知の環境で既存のモデルがあれば、計画はオフラインで実行できる。解を見つけると、実行の前にそれを評価する。動的な未知の環境では、戦略をオンラインで改訂する必要が生じることが多い。モデルやポリシーはその環境に合わせて修正する必要がある。人工知能によく見られる試行錯誤の反復過程が必要となることが多い。自動計画には、動的計画法、強化学習、組合せ最適化が含まれる。

自動計画器は一般に、外界の初期状態、目標とされる最終状態、とりうるアクションの集合という3つの入力を必要とする。これらは STRIPS のような形式言語で符号化される。自動計画器は初期状態から最終状態へと状態を変化させる一連のアクションの計画を生成する。計画問題を記述する他の言語としては階層型タスクネットワーク (HTN) があり、タスクを階層的に細分化することで一連の基本的アクションの計画を生成する。

自動計画の難しさのレベルは前提の単純化（時間の単位、各アクションにかかる時間の決定性、観測可能性）をどの程度行うかに依存する。古典的な自動計画器はなるべく前提を単純化しており、よく研究されている。主な技法としては、状態空間探索における前向き連鎖や後向き連鎖があり、条件間の関係についての知識を利用することで強化したり（Graphplan）、問題に固有のヒューリスティックを用いたり、計画空間を探索したり、命題充足可能性問題に変換したり（Satplan）といったものがある。

決定性の前提を排除して確率的なモデルによる不確実さを採用した場合、マルコフ決定過程 (MDP) や部分観測マルコフ決定過程 (POMDP) のためのポリシー生成という問題が生じる。