自動化された計画とスケジュール

自動計画とスケジューリングは、単にAI計画とも呼ばれ、^[1]人工知能の一分野であり、通常はインテリジェントエージェント、自律ロボット、無人車両によって実行される戦略またはアクションシーケンスの実現に関係しています。古典的な制御および分類の問題とは異なり、ソリューションは複雑であり、多次元空間で発見および最適化する必要があります。計画は意思決定理論にも関連しています。

既知の環境で利用可能なモデルがあれば、計画はオフラインで行うことができます。実行前に解決策を見つけて評価することができます。動的に未知の環境では、戦略をオンラインで修正する必要があることがよくあります。モデルとポリシーを適応させる必要があります。解決策は通常、人工知能でよく見られる反復的な試行錯誤のプロセスに頼ります。これには、動的プログラミング、強化学習、組み合わせ最適化が含まれます。計画とスケジュールを記述するために使用される言語は、アクション言語と呼ばれることがよくあります。

計画問題は、世界の可能な初期状態の説明、望ましい目標の説明、および一連の可能なアクションの説明が与えられた場合、(初期状態のいずれかに適用された場合に) 望ましい目標を含む状態 (このような状態は目標状態と呼ばれます) を生成することが保証される計画を合成することです。

計画の難しさは、採用されている単純化の仮定に依存します。問題が複数の次元で持つ特性に応じて、計画の問題のいくつかのクラスを識別できます。

• アクションは決定論的ですか、それとも非決定論的ですか? 非決定論的アクションの場合、関連する確率は利用できますか?
• 状態変数は離散的ですか、それとも連続的ですか? 離散的である場合、取り得る値は有限個だけですか?
• 現在の状態を明確に観察できますか? 完全な観察可能性と部分的な観察可能性があります。
• 初期状態はいくつありますか? 有限ですか、それとも任意の数ですか?
• アクションには持続時間がありますか?
• 複数のアクションを同時に実行できますか、それとも一度に実行できるアクションは 1 つだけですか?
• 計画の目的は、指定された目標状態に到達することでしょうか、それとも報酬関数を最大化することでしょうか?
• エージェントは 1 人だけですか、それとも複数ありますか? エージェントは協力的ですか、それとも利己的ですか? すべてのエージェントが個別に独自のプランを作成しますか、それともすべてのエージェントのプランが一元的に作成されますか?

最も単純な計画問題は、古典的な計画問題として知られており、次のように決定されます。

• 固有の既知の初期状態、
• 持続しないアクション、
• 決定論的な行動、
• 一度に1つしか取れない
• そして単一のエージェント。

初期状態は明確にわかっており、すべてのアクションは決定論的であるため、任意の一連のアクション後の世界の状態を正確に予測でき、観測可能性の問題は古典的な計画には関係ありません。

さらに、どのアクションが必要になるかは常に事前にわかっているため、計画はアクションのシーケンスとして定義できます。

非決定的なアクションやエージェントの制御外のその他のイベントでは、実行可能なアクションがツリーを形成し、プランはツリーのすべてのノードに対して適切なアクションを決定する必要があります。

離散時間マルコフ決定プロセス(MDP) は、次のような計画問題です。

• 持続しないアクション、
• 確率を伴う非決定論的行動、
• 完全な観測可能性、
• 報酬関数の最大化、
• そして単一のエージェント。

完全な観測可能性が部分的な観測可能性に置き換えられると、計画は部分的に観測可能なマルコフ決定プロセス(POMDP) に対応します。

エージェントが複数存在する場合は、ゲーム理論と密接に関連するマルチエージェント計画が存在します。

AI プランニングでは、プランナーは通常、入力ドメインが指定されていないプランナーとは対照的に、ドメイン モデル (ドメインをモデル化する一連の可能なアクションの説明) と、初期状態および目標によって指定される解決すべき特定の問題を入力します。このようなプランナーは、幅広いドメインのプランニング問題を解決できることを強調するために、「ドメイン独立」と呼ばれます。ドメインの代表的な例としては、ブロック スタッキング、ロジスティクス、ワークフロー管理、ロボット タスク プランニングなどがあります。したがって、単一のドメイン独立プランナーを使用して、これらすべてのさまざまなドメインのプランニング問題を解決できます。一方、ルート プランナーは、ドメイン固有のプランナーの典型です。

計画ドメインと特定の計画問題を表現するために最も一般的に使用される言語 (古典的計画用のSTRIPSやPDDLなど) は、状態変数に基づいています。世界の各可能な状態は状態変数への値の割り当てであり、アクションは、そのアクションが実行されたときに状態変数の値がどのように変化するかを決定します。状態変数のセットは、セット内で指数関数的なサイズを持つ状態空間を誘導するため、計画は、他の多くの計算問題と同様に、次元の呪いと組み合わせ爆発の影響を受けます。

計画問題を記述するための代替言語は、階層型タスク ネットワークです。階層型タスク ネットワークでは、一連のタスクが与えられ、各タスクはプリミティブ アクションによって実現されるか、他の一連のタスクに分解されます。これは必ずしも状態変数を伴うわけではありませんが、より現実的なアプリケーションでは、状態変数によってタスク ネットワークの記述が簡素化されます。

• 前方連鎖 状態空間探索、ヒューリスティックによる強化が可能
• 後方連鎖検索。状態制約の使用によって強化される可能性がある（STRIPS、graphplanを参照）。
• 部分順序計画

• 命題充足可能性問題（satplan ）への還元。
• モデル検査への還元- どちらも本質的には状態空間を横断する問題であり、古典的な計画問題はモデル検査問題のサブクラスに対応します。

時間計画は、古典的な計画と同様の方法で解決できます。主な違いは、複数の時間的に重なり合うアクションが同時に実行され、持続時間も伴う可能性があるため、状態の定義には、現在の絶対時間と、各アクティブ アクションの実行がどの程度進んでいるかに関する情報を含める必要があることです。さらに、有理時間または実時間での計画では、古典的な計画や整数時間での計画とは異なり、状態空間が無限になる場合があります。時間計画は、不確実性を伴うスケジューリング問題と密接に関連しており、時間付きオートマトンの観点からも理解できます。不確実性を伴う単純な時間ネットワーク (STNU) は、制御可能なアクション、不確実なイベント、および時間的制約を伴うスケジューリング問題です。このような問題の動的制御可能性は、不確実なイベントが観測されると、すべての制約が満たされることが保証されるように、制御可能なアクションを反応的にアクティブ化する時間計画戦略を必要とするタイプのスケジューリングです。^[2]

状態空間が十分に小さい場合、確率的計画は、値反復やポリシー反復などの反復法で解決できます。部分的観測可能性がある場合、確率的計画は同様に反復法で解決されますが、状態ではなく信念の空間に対して定義された価値関数の表現を使用します。

嗜好ベースの計画では、計画を作成することだけでなく、ユーザーが指定した嗜好を満たすことも目的としています。MDP に対応するような、より一般的な報酬ベースの計画とは異なり、嗜好には必ずしも正確な数値があるわけではありません。

決定論的計画は、階層型プランナーであるSTRIPS計画システムで導入されました。アクション名は順番に並べられ、これがロボットの計画となります。階層型計画は、自動生成された動作ツリーに例えることができます。^[3]欠点は、通常の動作ツリーはコンピュータプログラムほど表現力に富んでいないことです。つまり、動作グラフの表記にはアクションコマンドが含まれますが、ループや if-then ステートメントは含まれません。条件付き計画はボトルネックを克服し、 Pascalなどの他のプログラミング言語で知られている制御フローに似た精巧な表記を導入します。これはプログラム合成に非常に似ており、プランナーはインタープリターで実行できるソースコードを生成します。^[4]

条件付きプランナーの初期の例としては、1970年代半ばに導入された「Warplan-C」があります。^{[5]通常のシーケンスと、if-then文を含む複雑なプランの違いは何でしょうか。それは、プランの}実行時の不確実性と関係しています。プランナーにとって未知のセンサー信号にプランが反応できるというアイデアです。プランナーは事前に2つの選択肢を生成します。たとえば、オブジェクトが検出された場合はアクションAが実行され、オブジェクトが見つからない場合、アクションBが実行されます。^{[6]条件付きプランニングの主な利点は、}部分的なプランを処理できることです。^[7]エージェントは最初から最後まですべてを計画する必要はなく、問題をチャンクに分割できます。これにより、状態空間が削減され、より複雑な問題を解決できます。

環境がセンサーを通して観測可能で、それが不完全である可能性がある場合、私たちは「コンティンジェント プランニング」について語ります。つまり、プランニング エージェントが不完全な情報に基づいて行動する状況です。コンティンジェント プランニングの問題では、プランは一連のアクションではなく、決定木になります。これは、プランの各ステップが、古典的なプランニングの場合のように単一の完全に観測可能な状態ではなく、一連の状態によって表されるためです。^[8]選択されるアクションは、システムの状態によって異なります。たとえば、雨が降れば、エージェントは傘を取ることを選択し、降らなければ、傘を持たないことを選択するかもしれません。

マイケル・L・リットマンは1998年に、分岐アクションにより計画問題がEXPTIME完全になることを示した。^{[9] [10]}連続計画の特定のケースは、FOND問題（「完全に観測可能で非決定的」）によって表される。目標がLTLf（有限トレースの線形時間論理）で指定されている場合、問題は常にEXPTIME完全^[11]であり、目標がLDLfで指定されている場合は2EXPTIME完全である。

順応計画とは、エージェントがシステムの状態について不確実であり、観察ができない状態です。この場合、エージェントは現実世界についての信念を持ちますが、たとえば感知行動によってそれを検証することはできません。これらの問題は、古典的な計画と同様の手法で解決されますが、^{[12] [13]}、現在の状態に関する不確実性のため、状態空間は問題のサイズに対して指数関数的です。順応計画問題の解決策は、一連の行動です。Haslum と Jonsson は、順応計画の問題はEXPSPACE完全であり、^[14]初期状況が不確実で、行動の結果に非決定性がある場合、2EXPTIME 完全であることを実証しました。^[10]

• ハッブル宇宙望遠鏡は、 SPSSと呼ばれる短期システムとSpikeと呼ばれる長期計画システムを使用しています^[要出典]。

• アクション記述言語
• 俳優モデル
• 人工知能の応用
• 自動計画とスケジューリングに関する国際会議
• 制約充足問題
• 反応的な計画
• スケジューリング（コンピューティング）
• 戦略（ゲーム理論）

リスト

• SMTソルバーのリスト
• 制約プログラミング言語の一覧
• 新興技術のリスト
• 人工知能の概要

• Vlahavas, I. 「計画とスケジュール」。EETN。2013年12月22日時点のオリジナルよりアーカイブ。

• 自動計画とスケジューリングに関する国際会議