Loading article…
自動計画およびスケジューリング（単にAIプランニングと呼ばれることもある） [ 1 ]は、人工知能の一分野であり、通常はインテリジェントエージェント、自律型ロボット、無人車両によって実行される戦略またはアクションシーケンスの実現に関係しています。古典的な制御および分類問題とは異なり、その解決策は複雑であり、多次元空間で発見および最適化する必要があります。プランニングは意思決定理論とも関連しています。
既知の環境で利用可能なモデルがある場合、計画はオフラインで実行できます。実行前に解決策を見つけて評価できます。動的に未知の環境では、戦略をオンラインで修正する必要がある場合が多く、モデルとポリシーを適応させる必要があります。解決策は通常、人工知能でよく見られる反復的な試行錯誤プロセスに頼ります。これには、動的計画法、強化学習、組み合わせ最適化などが含まれます。計画とスケジューリングを記述するために使用される言語は、アクション言語と呼ばれることがよくあります。
世界の可能な初期状態の説明、望ましい目標の説明、および可能な行動のセットの説明が与えられた場合、計画問題は、（どの初期状態に適用した場合でも）望ましい目標を含む状態（このような状態は目標状態と呼ばれる）を生成することが保証される計画を合成することです。
計画策定の難易度は、用いられる単純化の仮定によって左右される。計画策定の問題は、その様々な側面における特性に応じて、いくつかの種類に分類することができる。
最も単純な計画問題は、古典的計画問題として知られており、次のように定義されます。
初期状態は明確に既知であり、すべての行動は決定論的であるため、一連の行動後の世界の状態は正確に予測でき、観測可能性の問題は古典的な計画においては無関係である。
さらに、計画は一連の行動として定義できる。なぜなら、どのような行動が必要になるかは常に事前に分かっているからである。
非決定的な行動やエージェントの制御範囲外のその他の事象が発生すると、実行可能なシナリオはツリー構造を形成し、計画ではツリーの各ノードに対して適切な行動を決定する必要がある。
離散時間マルコフ決定過程（MDP）は、以下の特徴を持つ計画問題である。
完全な観測可能性が部分的な観測可能性に置き換えられると、計画は部分観測可能なマルコフ決定過程（POMDP）に対応する。
エージェントが複数存在する場合、マルチエージェントプランニングとなり、これはゲーム理論と密接に関連しています。
AIプランニングにおいて、プランナーは通常、ドメインモデル（ドメインをモデル化する一連の可能なアクションの説明）と、初期状態と目標によって指定される解決すべき具体的な問題を入力として受け取ります。入力ドメインが指定されていないプランナーとは対照的です。このようなプランナーは、幅広いドメインのプランニング問題を解決できることを強調するために「ドメイン非依存」と呼ばれます。ドメインの典型的な例としては、ブロックスタッキング、ロジスティクス、ワークフロー管理、ロボットタスクプランニングなどがあります。したがって、単一のドメイン非依存プランナーを使用して、これらすべてのさまざまなドメインのプランニング問題を解決できます。一方、ルートプランナーは、ドメイン固有のプランナーの典型例です。
プランニング領域や特定のプランニング問題を表現するために最も一般的に使用される言語（古典的プランニングのためのSTRIPSやPDDLなど）は、状態変数に基づいています。世界の各可能な状態は状態変数への値の割り当てであり、アクションは、そのアクションが実行されたときに状態変数の値がどのように変化するかを決定します。状態変数の集合は、その集合に対して指数関数的に大きくなる状態空間を誘導するため、プランニングは、他の多くの計算問題と同様に、次元の呪いと組み合わせ爆発の影響を受けます。
計画問題を記述する別の方法として、階層型タスクネットワークという概念がある。これは、一連のタスクが与えられ、各タスクは基本動作によって実現されるか、あるいは他のタスクの集合に分解されるかのいずれかである。必ずしも状態変数を用いる必要はないが、より現実的な応用においては、状態変数を用いることでタスクネットワークの記述が簡略化される。
アクションモデル学習（略してアクション学習とも呼ばれる）は、ソフトウェアエージェントが自身の環境内で実行可能なアクションの効果と前提条件に関する知識を作成および変更することに関わる機械学習の一分野である。この知識は通常、論理ベースのアクション記述言語で表現され、自動プランナーへの入力として使用される。
目標が変わると、行動モデルの学習が重要になります。エージェントがしばらく行動すると、その領域での行動に関する蓄積された知識を使用して、より良い意思決定を行うことができます。したがって、行動モデルの学習は強化学習とは異なります。それは、世界での高価な試行の代わりに、行動について推論することを可能にします。[ 2 ]行動モデル学習は帰納的推論の一形態であり、エージェントの観察に基づいて新しい知識が生成されます。
行動モデル学習の一般的な動機は、プランナーのための行動モデルを手動で指定することが、多くの場合、困難で時間のかかる、エラーが発生しやすい作業であるという事実です（特に複雑な環境では）。 [ 3 ] [ 4 ] [ 5 ]
時間計画は、古典的な計画と同様の方法で解決できます。主な違いは、複数の時間的に重複するアクションが同時に実行される可能性があるため、状態の定義には現在の絶対時刻と各アクティブなアクションの実行がどれだけ進んでいるかに関する情報を含める必要があることです。さらに、有理時間または実時間での計画では、古典的な計画や整数時間での計画とは異なり、状態空間は無限になる可能性があります。時間計画は、不確実性が関係するスケジューリング問題と密接に関連しており、時間付きオートマトンの観点からも理解できます。不確実性を伴う単純時間ネットワーク (STNU) は、制御可能なアクション、不確実なイベント、および時間制約を含むスケジューリング問題です。このような問題に対する動的制御可能性は、不確実なイベントが観測されたときに制御可能なアクションを反応的にアクティブ化してすべての制約が満たされることを保証する時間計画戦略を必要とするスケジューリングの一種です。[ 6 ]
状態空間が十分に小さい場合、確率的計画は価値反復法や方策反復法などの反復法で解決できます。部分観測性の場合、確率的計画は同様に反復法で解決できますが、状態ではなく信念空間に対して定義された価値関数の表現を使用します。
人工知能において、嗜好に基づく計画は、可能な限り多くのユーザー指定の嗜好を満たす計画を作成することに重点を置いた、自動化された計画およびスケジューリングの一形態です。多くの問題領域では、タスクはさまざまな一連のアクション（計画とも呼ばれる）によって達成できます。これらの計画は品質が異なる場合があります。問題を解決する方法は多数ありますが、一般的には、例えばコスト効率が良く、迅速で、安全な方法が好まれます。
選好に基づくプランナーは、特定の問題に対するプランを作成する際に、これらの選好を考慮に入れます。選好に基づくプランニングソフトウェアの例としては、PPLAN [ 7 ]やHTNPlan-P [ 8 ] (選好に基づく階層型タスクネットワーク(HTN) プランニング) などがあります。
決定論的プランニングは、階層型プランナーであるSTRIPSプランニングシステムで導入されました。アクション名は順序付けられ、これがロボットのプランとなります。階層型プランニングは、自動生成されたビヘイビアツリーと比較できます。[ 9 ]欠点は、通常のビヘイビアツリーはコンピュータプログラムほど表現力豊かではないことです。つまり、ビヘイビアグラフの表記にはアクションコマンドは含まれますが、ループやif-then文は含まれません。条件付きプランニングはこのボトルネックを克服し、 Pascalなどの他のプログラミング言語で知られている制御フローに似た精緻な表記法を導入します。これはプログラム合成に非常によく似ており、プランナーがインタプリタで実行できるソースコードを生成することを意味します。[ 10 ]
条件付きプランナーの初期の例としては、1970 年代半ばに導入された「Warplan-C」があります。[ 11 ]通常のシーケンスと、if-then ステートメントを含む複雑なプランの違いは何でしょうか。それは、プランの実行時の不確実性に関係しています。プランは、プランナーにとって未知のセンサー信号に反応できるという考え方です。プランナーは、事前に 2 つの選択肢を生成します。たとえば、オブジェクトが検出された場合はアクション A が実行され、オブジェクトがない場合はアクション B が実行されます。[ 12 ]条件付きプランニングの大きな利点は、部分的なプランを処理できることです。[ 13 ]エージェントは、最初から最後まですべてを計画する必要はなく、問題をチャンクに分割できます。これにより、状態空間が削減され、より複雑な問題が解決されます。
環境がセンサーを通して観測可能であり、センサーが故障する可能性がある場合、「条件付き計画」という。つまり、計画エージェントが不完全な情報の下で行動する状況である。条件付き計画問題では、計画はもはや一連の行動ではなく決定木となる。なぜなら、計画の各ステップは、古典的な計画の場合のように完全に観測可能な単一の状態ではなく、一連の状態によって表されるからである。[ 14 ]選択される行動は、システムの状況に依存する。たとえば、雨が降ればエージェントは傘を持っていくことを選択し、降らなければ傘を持っていかないことを選択するかもしれない。
Michael L. Littman は 1998 年に、分岐アクションを使用すると、プランニング問題がEXPTIME完全になることを示しました。[ 15 ] [ 16 ]連続プランニングの特殊なケースは、FOND 問題 (「完全に観測可能で非決定論的」) で表されます。目標が LTLf (有限トレース上の線形時間論理) で指定されている場合、問題は常に EXPTIME 完全です[ 17 ]。目標が LDLf で指定されている場合は 2EXPTIME 完全です。
適合計画とは、エージェントがシステムの状況について不確実であり、観測を行うことができない場合を指します。この場合、エージェントは現実世界について信念を持っていますが、例えばセンシング行動によってそれを検証することはできません。これらの問題は、古典的な計画と同様の手法で解決されますが、[ 18 ] [ 19 ]現在の状態に関する不確実性のため、状態空間は問題のサイズに対して指数関数的に大きくなります。適合計画問題の解は、一連の行動です。HaslumとJonssonは、適合計画の問題はEXPSPACE完全であり、[ 20 ]初期状況が不確実で、行動の結果に非決定性がある場合には2EXPTIME完全であることを示しました。[ 16 ]
Action model learning amir2008が呼び出されましたが、定義されていません (ヘルプ ページを参照してください)。{{cite conference}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite conference}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite conference}}: CS1 maint: 複数の名前: 著者リスト (リンク)AIプランニングにおける最近の進歩