自動計画

自動計画（じどうけいかく、英: Automated planning and scheduling）は、人工知能のテーマの1つであり、戦略や行動順序の具体化をすること。典型的な例として、知的エージェント、自律型ロボット、無人航空機などでの利用がある。古典的制御システムや統計分類問題とは異なり、自動計画の解は複雑で未知であり、多次元空間における発見と最適化が必要となる。 機械であるか人間であるかに関わらず、周囲の状況が既知で、その構造がよく理解されている場合、計画や戦略というものは行動する前にあらかじめ組み立てておく(計算しておく)ことができる。一方未知の環境では、周囲の状況が明らかになるにつれて、戦略の修正を迫られる場合も多い。前者はオフラインプランニング、静的プランニングなどと呼ばれ、後者は動的プランニング、オンラインプランニングなどと呼ばれる。計画の修正のことを特にリプランニングとも呼ぶ。いずれのプランニングでも、人工知能によく見られる試行錯誤の反復過程が必要となることが多い。自動計画には、動的計画法、強化学習、組合せ最適化が含まれる。 プランナ(自動計画器)は一般に、外界の初期状態、目標とされるゴール、とりうるアクションの集合という3つの入力を必要とする。これらは STRIPS をはじめとする形式言語で記述される。STRIPSはプログラミング言語のような見た目をしているため、ある程度人間にも読め、かつ機械可読である。プランナ(自動計画器)は初期状態からゴール状態へと状態を変化させる一連のアクションの計画を生成する。例えば、右図は Blocksworld (つみ木の世界) と呼ばれる、教科書でよく使われるSTRIPS問題の例を示している。初期状態は積み木が地面に置いてある状態、ゴールは積み木がA,B,Cの順で積まれている状態である。この問題のプランは、ロボットアームが積み木を運ぶ動作に相当する。今日では、STRIPS入力形式に拡張を加えたen:PDDLが主に使われている。 プランニングの難しさは、前提の単純化（不確実性、観測可能性、並列性、時間、連続変数）をどの程度行うかに依存する。そのため、単純化のレベルによりその様々な変種が存在し、またそれに適したアルゴリズムが提案されている。単純化したモデルは現実世界をモデル化するのに必ずしも実用的であるとは限らないが、実用的な場合も存在するし、またその存在意義には、単純なモデルで発見された知見は基礎的であり、より複雑なモデルにも適用できるはずだという期待が込められている。 古典的プランニング (Classical Planning) は、それらの前提を全て単純化した基礎的なモデルである(不確実性なし、完全情報、アクションの並列実行なし)。人工知能黎明期から存在し、よく研究されている。主な技法としては、状態空間探索における前向き連鎖や後向き連鎖があり、条件間の関係についての知識を利用することで強化したり（Graphplan）、問題に固有のヒューリスティックを用いたり、充足可能性問題（Satplan）や整数計画問題に変換したりといったものがある。 不完全情報を取り入れたプランニングは、「センサなしでも確実に実行できるプランを生成する」Conformant Planning,「センサによる観測を用いた実行プランを生成する」Contingent Planning などがある。 不確実性を取り入れたプランニングは Probabilistic Planning と呼ばれる。不確実性と不完全情報は似ているようで似ていない。確実で不完全な情報は、観測を行えば確実な情報を得ることが出来る。一方、不確実で完全な情報の例とは、例えばサイコロの1の目が「正確に1/6の確率で」出ることに対応する。 連続変数を許すプランニングは Numeric Planning と呼ばれ、卑近な例ではピタゴラスイッチのような(重さ、角度などを考慮に入れた)問題を解けることを目指す。 特に、連続空間を対象にするプランニングは Motion Planning とも呼ばれ、ロボットアームの動作や、建物内を移動するロボットの経路探索に応用できる。 同時並行に複数のアクションを実行できるプランニング問題は スケジューリング問題、ないしTemporal Planning問題とも呼ばれる。オペレーションリサーチではスケジューリング問題がよく研究されているが、それらがある特定の決められた問題ドメイン (例:特定の種類の組み立て問題や特定の種類の配送問題など) を解くことを目標としているのに比べて、AIおよび自動プランニング・スケジューリングでの目標は、与えられるまで未知の問題ドメインを解くことが出来る汎用問題解決機を実現することである。 計画問題を記述する他の言語としては階層型タスクネットワーク (HTN) があり、タスクを階層的に細分化することで一連の基本的アクションの計画を生成する。 決定性の前提を排除して確率的なモデルによる不確実さを採用した場合、マルコフ決定過程 (MDP) や部分観測マルコフ決定過程 (POMDP) のためのポリシー生成という問題が生じる。 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} かはまだ証明されていない。 プランニング問題の計算複雑性は、問題に様々な仮定を入れることで下げることができることが知られている。 この事実を利用して、与えられた問題に制約を加えた簡単な問題 (緩和問題)を解くことで、元の問題を解く際の枝刈りに用いる手法が多数提案されている。 以下には、特に古典的プランニングの緩和手法と関連する制約について述べる。 削除効果を持たないプランニング問題: 削除効果を持たないプランニング問題を最小ステップで解く最適解を得る問題は、NP完全である。この事実は、Landmark-Cut , Operator Counting など近年の枝刈り手法の基礎となっている。 ハッブル宇宙望遠鏡では、短期計画システム「SPSS」と長期計画システム「Spike」が使われている。 ^ Bylander, Tom. "The computational complexity of propositional STRIPS planning." Artificial Intelligence 69.1 (1994): 165-204. ^ Bylander et al. ^ Helmert, Malte, and Carmel Domshlak. "Landmarks, critical paths and abstractions: what's the difference anyway?." ICAPS. 2009. ^ Davies, Toby O., et al. "Sequencing Operator Counts." ICAPS. 2015. ^ SPSS ^ Spike STRIPS アクターモデル ソフトウェアエージェント マルコフ連鎖 メッセージ リアクティブプランニング 計画 進化的計算 制約プログラミング DNA - JOpt Route Planning Demonstrator 自動旅程計画のJavaアプレットによるデモ International Conference on Automated Planning and Scheduling