反応的な計画

人工知能において、リアクティブ プランニングとは、自律エージェントによるアクション選択の技術群を指します。これらの技術は、2 つの点で従来のプランニングとは異なります。まず、タイムリーに動作するため、非常に動的で予測不可能な環境にも対処できます。次に、現在のコンテキストに基づいて、常に次のアクションを 1 つだけ計算します。リアクティブ プランナーは、エージェントの優先順位と動作を記述する格納構造であるリアクティブ プランを頻繁に (常にではありませんが) 利用します。リアクティブ プランニングという用語は、少なくとも 1988 年にまで遡り、より現代的な用語である動的プランニングと同義です。

リアクティブ プランを表現する方法はいくつかあります。どの方法も、基本的な表現単位と、これらの単位をプランに組み込む手段を必要とします。

条件アクション ルール、または if-then ルールは、 if condition then actionという形式のルールです。これらのルールは、プロダクションと呼ばれます。ルールの意味は次のとおりです。条件が満たされている場合は、アクションを実行します。アクションは、外部 (何かを拾って移動するなど) または内部 (内部メモリに事実を書き込む、または新しいルール セットを評価するなど) のいずれかになります。条件は通常ブール値であり、アクションは実行されるか、実行されないかのいずれかになります。

生成ルールは比較的フラットな構造に編成されることもありますが、多くの場合、何らかの 階層に編成されます。たとえば、サブサンプション アーキテクチャは相互接続された動作のレイヤーで構成され、各レイヤーは実際には適切な入力に応じて動作する有限状態マシンです。これらのレイヤーは単純なスタックに編成され、上位レイヤーが下位レイヤーの目標を包含します。他のシステムでは、ツリーを使用したり、現在最も重要な目標/ルール サブセットを変更するための特別なメカニズムを含めたりすることができます。フラット構造は比較的簡単に構築できますが、単純な動作の記述しか許可されなかったり、構造の欠如を補うために非常に複雑な条件が必要になったりします。

分散アクション選択アルゴリズムの重要な部分は、競合解決メカニズムです。これは、特定の瞬間に複数のルールの条件が満たされている場合に、提案されたアクション間の競合を解決するメカニズムです。競合は、たとえば次のように解決できます。

• 事前にルールに固定の優先順位を割り当てること、
• 設定の割り当て（例：Soarアーキテクチャ）
• ルール間の相対的な効用を学習する（例：ACT-R）、
• ある種の計画を活用する。

エキスパート システムでは、ルールを選択するために最新性などの他のより単純なヒューリスティックがよく使用されますが、単純なアプローチでは大規模なシステムで適切な動作を保証することは困難です。

競合解決は、相互に排他的なアクションを実行するルールにのみ必要です (Blumberg 1996 を参照)。

この種の反応型計画の限界については、Brom (2005) で説明されています。

有限状態マシン(FSM) は、システムの動作のモデルです。FSM は、コンピュータ サイエンスで広く使用されています。エージェントの動作のモデル化は、FSM の可能な用途の 1 つにすぎません。エージェントの動作を記述するために使用される一般的な FSM は、一連の状態とこれらの状態間の遷移で構成されます。遷移は、実際には条件アクション ルールです。すべての瞬間に、FSM の 1 つの状態だけがアクティブであり、その遷移が評価されます。遷移が行われると、別の状態がアクティブになります。つまり、一般に、遷移は次の形式のルールです: if condition then activate-new-state。ただし、一部のシステムでは、遷移を「自己」状態に接続して、実際に状態を変更せずに遷移アクションを実行できるようにすることもできます。

FSM によって動作を生成する方法は 2 つあります。これらは、設計者が状態に何を関連付けるかによって決まります。つまり、それらは「行為」またはスクリプトのいずれかになります。「行為」とは、FSM が特定の状態である場合にエージェントが実行する必要があるアトミック アクションです。このアクションは、すべてのタイム ステップで実行されます。ただし、後者の場合の方が一般的です。この場合、すべての状態はスクリプトに関連付けられ、スクリプトは、FSM が特定の状態にある場合にエージェントが実行する必要がある一連のアクションを記述します。遷移によって新しい状態がアクティブになると、以前のスクリプトは単に中断され、新しいスクリプトが開始されます。

スクリプトが複雑な場合は、複数のスクリプトに分割して、階層型 FSM を利用できます。このようなオートマトンでは、すべての状態にサブ状態を含めることができます。アトミック レベルの状態のみが、スクリプト (複雑ではありません) またはアトミック アクションに関連付けられます。

計算上、階層型 FSM は FSM と同等です。つまり、各階層型 FSM は従来の FSM に変換できます。ただし、階層型アプローチの方が設計が容易です。階層型FSM を使用するコンピューター ゲーム ボットの ASM の例については、Damian Isla (2005) の論文を参照してください。

if-then ルールと FSM はどちらもファジー ロジックと組み合わせることができます。条件、状態、アクションはそれぞれブール値や「はい/いいえ」ではなく、近似値でスムーズです。その結果、特に 2 つのタスク間の遷移の場合、結果として生じる動作はよりスムーズに遷移します。ただし、ファジー条件の評価は、明確な条件の評価よりもはるかに遅くなります。

アレックス・シャンパンダールの建築をご覧ください。

反応型プランは、人工ニューラル ネットワークやフリーフロー階層などのコネクショニスト ネットワークによっても表現できます。基本的な表現単位は、ユニットに「抽象的なアクティビティ」を供給する複数の入力リンクと、そのアクティビティを次のユニットに伝播する出力リンクを持つユニットです。各ユニット自体はアクティビティ トランスデューサーとして機能します。通常、ユニットは階層構造で接続されます。

コネクショニスト ネットワークの利点は、第一に、結果として生じる動作が、明確な if-then ルールや FSM によって生成される動作よりもスムーズであること、第二に、ネットワークが適応的であることが多いこと、第三に、抑制のメカニズムを使用できるため、動作を規範的に記述することもできることです (ルールを使用すると、動作を規範的にしか記述できません)。ただし、この方法にはいくつかの欠点もあります。第一に、設計者にとって、if-then ルールと比較して、ネットワークで動作を記述するのははるかに複雑です。第二に、特に適応機能を利用する場合は、比較的単純な動作しか記述できません。

典型的なリアクティブ プランニング アルゴリズムは、if-then ルールを評価したり、コネクショニスト ネットワークの状態を計算したりするだけです。ただし、一部のアルゴリズムには特別な機能があります。

• Rete 評価: 適切なロジック表現 (明確なルールにのみ適しています) を使用すると、ルールを各タイム ステップで再評価する必要がなくなります。代わりに、前のステップからの評価を保存するキャッシュ形式を使用できます。
• スクリプト言語: 場合によっては、ルールまたは FSM がアーキテクチャのプリミティブそのものになります (例: Soar )。ただし、多くの場合、リアクティブ プランはスクリプト言語でプログラムされ、ルールはプリミティブの 1 つにすぎません (JAM や ABL など)。

ステアリングは、エージェントのナビゲーションに使用される特別な反応技術です。反応ステアリングの最も単純な形式は、センサー入力をエフェクター出力に直接マッピングし、追従または回避できるBraitenberg 車両で採用されています。より複雑なシステムは、エージェントに影響を及ぼす引力または反発力の重ね合わせに基づいています。この種のステアリングは、Craig Reynolds のボイドに関するオリジナルの研究に基づいています。ステアリングによって、次の単純な形式を実現できます。

• 目標に向かってナビゲーション
• 障害物回避行動
• 壁に従う行動
• 敵が近づいている
• 捕食者回避
• 群衆の行動

ステアリングの利点は、計算効率が非常に高いことです。コンピュータゲームでは、この技術で何百ものNPCを操作できます。ただし、より複雑な地形（建物など）の場合は、ステアリングを経路探索（Milani [1]など）と組み合わせる必要があります。経路探索は計画の一形態です。

• 行動ベースのAI

• Blumberg, B.: Old Tricks, New Dogs: 動物行動学とインタラクティブな生き物。マサチューセッツ工科大学博士論文 (1996 年)。
• Brom, C.: 階層的反応計画: その限界はどこにあるのか? MNAS ワークショップの議事録。エディンバラ、スコットランド (2005)
• ブライソン、J.：設計による知性：複雑な適応エージェントを設計するためのモジュール性と調整の原則。マサチューセッツ工科大学博士論文（2001年）
• Champandard, AJ: AI ゲーム開発: 学習と反応行動を備えた合成生物。New Riders、米国 (2003)
• Grand, S.、Cliff, D.、Malhotra, A.: Creatures: 家庭娯楽のための人工生命自律ソフトウェアエージェント。In: Johnson, WL (eds.): Proceedings of the First International Conference on Autonomous Agents。ACM press (1997) 22-29
• Huber, MJ: JAM: BDI 理論に基づくモバイル エージェント アーキテクチャ。第 3 回国際自律エージェント会議 (Agents'99) の議事録。シアトル (1999) 236-243
• Isla, D.: Halo 2 における複雑さの処理。Gamastura online、03/11 (2005)
• ミラニ、A.、ポッジョーニ、V.、反応環境における計画。計算知能、23(4)、439-463、ブラックウェル・ワイリー、(2005)[2]
• Reynolds, CW「群れ、群れ、群れ群：分散行動モデル」Computer Graphics、21(4) (SIGGRAPH '87 Conference Proceedings) (1987) 25-34。
• de Sevin、E. Thalmann、D.:仮想人間の行動選択の動機づけモデル。Computer Graphics International (CGI)、IEEE Computer SocietyPress、ニューヨーク (2005)
• Softimage/Behavior 製品。Avid Technology Inc.
• Tyrrell, T.: 行動選択の計算メカニズム。博士論文。エディンバラ大学認知科学センター (1993)
• van Waveren、JMP: Quake III アリーナ ボット。修士論文。デルフト工科大学 ITS 学部 (2001)
• ウールドリッジ、M. マルチエージェントシステム入門。ジョン・ワイリー・アンド・サンズ（2009）
• Pogamut2。Unreal Tournament 2004 での高速エージェント プロトタイピング用プラットフォーム。JJ Bryson が設計および開発したリアクティブ プランナー POSH を使用。
• [3] ワーサム、RH、ガウドル、SE、ブライソン、JJ、「本能：生物学にヒントを得たインテリジェント組み込みシステム向けリアクティブプランナー」、認知システム研究（2018）

• Creatures は、Grand らによる反応型計画の実装です。