マルチエージェントによる分散協調問題解決*
北村泰彦
大阪市立大学工学部情報工学科
kitamura@info.eng.osaka-cu.ac.jp
http://www.kdel.info.eng.osaka-cu.ac.jp/kitamura/
1.はじめにこのところ「エ ージェント」と いう言葉を盛ん に耳にするよう になった．具 体的なアウトプッ トを期待してい るというよりも ，関心の方がむ しろ先行して いるように思える．本稿では， エージェントとは何かについて考えた後，分散協調問題解決の視 点からエージェ ント技術につい ての解説を行う ．また近年， 産業界で注目されている Enterprise Integration へのエージェント技術の応用について紹介を行う．
2.エージェントとは何か
2.1.特徴このところ「エ ージェント」と いう用語が様々 な研究者によっ て，様々な場 合に用いられており，いささか混乱気味である1 ．ここではエージェントの厳密 な定義というより も，関連するキ ーワードととも に，その言葉に 込められたエ ー
ジェントに要求される性質をまとめてみたい．
•*

自律性(autonomy)：エージェントは自律的なソフトウェアモジュールを指 す
ことが多い．ここで自律性とは外面的には，「ある与えられた環境の中で他の介在を必要とせずに存在できること」と定義できる．しばしば類似する概念であるオブジェク トとの違いを問わ れることが多いが ，これに対して所 2
は，「オブジェクトが器官，細胞などの生物部品に対応する概念であるのに対して，エージェントは生物個体に対応する概念である」と述べている．部品は単体では存在できないが，その集合体である生物個体は単体で存在しう
るわけである．また自律性は内面的には，「ある与えられた環境の中で他の指図なし にエージ ェントが 自らの判 断のみに よりふる まうこと ができる こと」とも定義できる．ここでは他者の指図を全く受付ないという意味ではなく，判断の主体がエージェントにあることを意味している．環境が複雑にな

TR96-2: 計測自動制御学会関西支部 30 周年記念講習会

••

ればそれだけ高度な判断が必要になり，エージェントに知性(intelligence)や適応性(adaptability)が要求される．
相互作用性(interaction)：エージェントは環境に存在する他のエージェントと通信し，相互作用することができる．エージェントは外部からのメッセージ
に対する自らの行動を調節する受動的なふるまいだけでなく，外部に積極的に働きかけることもでき，協調性(coordination)が要求される．またさらに ，他のエージェントと組織を構成して，集団としてふるまうこともあり，そこにはエージェントの社会性(social ability)が要求される．
代行性(agency)：エージェン トという言葉のもつ言 語的な意味は「代理人 」
である．エージェントはその利用者である人間の代理人として，利用者に接し，その命令や好みにしたがって行動することが要求される．

「エージェント 」という言葉は 以上の要求を一 つ以上満たすも のとして用い られている．さら に当然のことな がら，マルチエ ージェントとは 複数のエージ ェントから構成された分散システムを意味している．
2.2.背景近年，マルチエ ージェントシス テムが注目され るようになった 背景について 考
えてみよう．や はり最も大きな 要因は，パソコ ンとインターネ ットの普及に より分散システム を支えるインフ ラが急速に整え られてきたこと であろう．イ ン
ターネットを基 盤とした分散シ ステムにはこれ までの分散シス テムにはない 特徴があり，従来の分散処理技術をそのまま用いることができない．
••

ボトムアップ型情報ベース：インターネットにより構築される分散システム
は地球規模で，多種多数の情報ベースが相互接続されている．この分散シス
テムは統一的な設計基準に基づきトップダウン的に構築されるのではなく，それぞれ 個別に構 築された 情報ベー スが次々 と結合さ れてゆく ことによ り
ボトムアップ的に構築されてゆく．したがって局所情報ベースは個別に，また非同期に更新され，局所的には正しくても，全体的には整合性のない情報が存在することになる．このようなシステムに従来の中央集権的な視点を前提とした分散情報管理手法を用いることはできない．むしろ解決すべき問題に応じて，それぞれの情報ベース（エージェント）が自律的にふるまい，必要に応じ てその問 題に関わ るエージ ェント間 で調整を 図るよう な分権的 な
情報管理機構が望ましい．
オープン環境：インターネット上での電子取引などでは不特定多数の利用者がシステムにアクセスするようになる．このような取引を自動化する場合に•は，柔軟な交渉能力や様々な不正に対する頑健性を必要とする．従来の分散システム における プロトコ ルは固定 的なシス テムにお いて固定 的なメッ セージのや りとりを 扱う低レ ベルなも のに限ら れていた ．人間社 会におけ る
様々な取 引をベー スするよ うなエー ジェント 間プロト コル設計 のための 方法論が必要になる．
個別性：インターネットにより構築される分散システムには大量の情報が格納されているが，利用者の立場からすると必要な情報はそのごく一部であり，その要求は利用者毎に異なっている．したがって情報ベース側が利用者の要求にあわせた情報提供を行うには限度があり，利用者側で情報の取捨選択する機能が必要になる．そこでエージェントが代理人として，利用者の必要や好みに応じて，情報の検索，選択を行い，利用者に提供する機能が必要になる．

2.3.分類
現在のところ提 案されているエ ージェントシス テムはその機能 の強調点に応 じて大きく三つに分類できる．
•••

問題解決エージェント：他のエージェントとの協調により問題を解決するエージェントである． 分散協調問題解 決やマルチエージェントシステムの 分野で研究されているエージェントである．
インタフェースエージェント：電子秘書のように利用者である人間をアシストするエージェントである．利用者の要求や好みに応じてネットワークにア
クセスし，必要な情報を提供する．ソフトウェアエージェント，ネットワー
クエージェントと呼ばれることがある．またエージェントの臨在感を協調したビリーバブルエージェントもこの範疇に含まれる．
モバイルエージェント：機動性のあるエージェントで，ネットワークを移動して必要な情報を収集する．Telescript エージェントが代表的である．実体は独立したシステムというよりもスクリプト言語とその実行環境である．

本稿ではこの中 で分散協調問題 解決における問 題解決エージェ ントについて 解説する．
3.分散協調問題解決
分散人工知能(Distributed Artificial Intelligence: DAI)は複数のエージェントから 構
成される組織に おけるエージェ ント間の相互作 用を研究の対象 としている． AI
が人間個人の知能をモデル化するのに対して，DAI は人間社会における相互作用

をモデル化する．DAI におけるエージェントはその自律性と相互作用性が強調されている．DAI は大きく分散協調問題解決とマルチエージェントシステムの研究に分類される3 ．分散協調問題解決ではエージェント全体に共通の目標が存在 することが前提と され，エージェ ントの協力によ りその目標を達 成するための 協
調手法が主な研 究の対象となる ．一方で，マル チエージェント システムはそ れ
ぞれのエージェ ントが個別の目 標を有し，エー ジェント間で生 じる競合を解 消する調整手法が 主な研究の対象 となる．二つの 研究分野を比較 すれば，マル チ
エージェントシ ステムの方がよ りオープンな環 境を前提として いるといえる ．
マルチエージェントシステムの解説に関しては他稿4,5 にゆずり，本稿では分散協調問題解決の技法に関して解説を行う．
3.1.分散協調問題解決の構造
分散協調問題解 決は複数のエー ジェントによる 協調的な問題解 決であり，一 般的な過程は以下の手順より成り立っている6 ．
1. 問題の割り当て：マネージャ（エージェント）に問題が与えられると部分問
題に分割し，部分問題を適切なワーカーに割り当てる．
2. 問題の解決：ワーカーが部分問題を解決する．
3. 解の統合：各ワーカーで得られた解をマネージャが統合し，全体解を得る．
以上の過程は再 帰的に実行され ることもある． すなわち部分問 題を割り当て られたワーカーエ ージェントはさ らにそれを分割 し，他のエージ ェントに割り 当
てることも可能 である．また， 対象とする問題 によっては必ず しも三つの全 てのステップを実 行する必要のな いものもある． 例えば以下に示 す二つの事例 を考えてみよう．
••

センサネットワーク：センサ（エージェント）が地理的に分散して配置されており，その中を航空機等の移動物体が通過する．エージェントは互いに情報交換して通過した物体の識別，進路，速度等を検出する．
工場スケジューリング：工場内に複数のロボット（エージェント）が存在し，工作専門あるいは運搬専門などそれぞれ専門分野が異なっている．エージェ
ントが効率的に動作できるスケジュールを与え，目標（製品の生産）を達成
する．

センサネットワ ークにおいては エージェントが すでに配置され ており，その センサ領域も決定 されているので ，エージェント が実行すべき部 分問題（セン サ領域内の信号処 理と解釈）はす でに自明となっ ている．そして 問題解決の重 要
な点は各センサの情報を統合して，全体的な解釈を行う解統合の過程にある．
次に，工場スケ ジューリングに おいてはロボッ ト毎に目標を設 定する必要が あり，問題の割り 当てが重要な課 題となる．部分 問題の解決がエ ージェント間 の調整により適切 に行われれば， 解の統合は自明 である．以上の ことから分散 協調問題 解決の ための 推論方 式は， 問題解 決と解 統合を 重視し た結果 共有 (result
sharing)方式と，問題の割り当てと解決を重視したタスク共有(task sharing)方式に分類することができる．
3.2.結果共有方式
結果共有方式は ボトムアップ型 の問題解決手法 である．各ワー カーは自らの 知識を用いて問題 の部分解となる 仮説をマネージ ャに送る．マネ ージャはワー カーから送られて くる仮説を組み 合わせて全体解 を構成する．し かしながら枠 ワーカーで得られ る情報は局所的 なものであり， また雑音などが 混じり信頼度 が低い場合もあり ，仮説から全体 解への導出は容 易ではない．本 節では，エー ジ
ェントが互いの 情報を参照しな がら問題解決を 進める黒板モデ ルとそれを分 散化した分散型解 釈モデル，局所 的に得られる部 分解の信頼度が 低い場合にお いてエージェントの協調により信頼度を向上させる FA/C 手法，自律的に動作する
エージェントが システム全体と して一貫性のあ る問題解決を行 うための調整 手法について紹介を行う．
3.2.1.黒板モデル
分散協調問題解決における結果共有 方式の基本となっているのは Hearsay-II 音
声理解システム7 に採用された黒板モデルである． 黒板モデルは問題解決に必要な専門知識を記 述した複数の知 識源，知識源か ら得られる仮説 を記述する共 通
データベースで ある黒板，スケ ジューラから構 成されている（ 図 1参照）． それぞれの知識源 は部分的な問題 解決を行うこと ができ，黒板を 通じて情報交 換を行うことがで きる．知識源の 動作は条件・行 動という対で表 すことができ ，黒板に条件に適 合する仮説が書 き込まれると行 動を引き起こし ，黒板の仮説 を更新する．黒板 は階層的な構造 をしており，最 下位レベルに書 き込まれた仮 説が，知識源の操 作により徐々に 上位レベルの仮 説に抽象化され てゆく．最上 位
レベルに仮説が 書き込まれると それが解になる ように設計され ている．スケ ジ
ューラは常に黒 板の状況を監視 し，仮説の信頼 度をもとに各々 の時点で適切 な知識源の起動を 行うようにスケ ジューリングを 行っている．こ のような黒板 モ
デルは，独立し た複数の知識源 が互いに協調し て問題解決を行 う協調型問題 解
決の一つの雛形を与えたといえる．

図 1：黒板モデル7
分散型解釈モデル8 は複数の黒板システムを通信路で結合した分散型黒板モデ ルである．ノードa間通信のために新たに ，受信用知識源と送信用知識源が付加 され，これら二種 類の知識源と通 信路を介して黒 板間の仮説交換 が行われる． 各
ノードは問題解 決における受け 持ち区域を表す 関連域の情報を 持っている． 受
信用知識源は通 信路に流される 情報のうち自ノ ードの関連域に 含まれるもの のみを選択して黒板に書き入れる．
さらに分散型解 釈モデルを拡張 した本格的な分 散協調問題解決 用実験ツール として DVMT(Distributed Vehicle Monitoring Testbed)が開発された9 ．DVMT は一種のセンサネットワ ークであり，分 散しているセン サからの情報を もとにその領 域を移動する自動車などの物体の進路 解析を行うシステムである．DVMT では 各ノードの動作を調整するために新たに目標黒板が導入された．この DVMT 上で以下に述べる結果共有方式に関する様々な手法が提案され，評価された．
3.2.2.FA/C10
結果共有方式で まず問題になっ たのはノード間 の通信量である ．もし，曖昧 な仮説が大量に存 在する分散型解 釈モデルで各ノ ードの黒板を無 矛盾で完全な ものにしようするならばそのために多量の通信が必要となる． Lesser はこのような従来の分散処理手法を completely accurate, nearly autonomous(CA/NA)法と呼んでいる． しかし分散型解釈モデルではこの条件を緩めて，たとえ各ノードの黒
板間に部分的な 矛盾が生じたと してもノードが 互いに協力する ことにより， 正aLesser らの研究ではエージェントのかわりにノードという用語が用いられている．

しい解を導き出せる手法として functionally accurate and cooperative(FA/C)法を提案した．すなわ ち，下位レベル の黒板では矛盾 が存在するかも しれないが， 中
間レベルでデー タ交換を行い， 互いに修正する ことにより，上 位レベルでは 正
しい解がでるよ うにしている． 中間レベルでの 仮説は抽象化が なされており ，下位レベルでの仮説交換に比べ通信量が少なくてすむ．FA/C 法は不確定なデー
タの解釈を行う分散協調的解法の以後の研究のベースになっている11 ．
3.2.3.協調機構12
分散型解釈モデ ルではスケジュ ーラはそれぞれ のノードに分散 して存在する ので，各ノードの 処理は冗長にな ったり不適切で あったりするこ とが多くなる ．
そのためには各 ノードの自律性 は保ちつつも， システム全体で 一貫性のある 問
題解決を行う必要が生じてきた．そこで， Durfee らは DVMT システムにおいて
目標黒板を用い た制御機構を強 化することによ り，複数のノー ドが協調して より一貫性のある 問題解決を行う 調整機構を研究 し，以下の三つ の手法を提案 した．
1. 組織構造(organizational structure)の利用：組織構造とはネットワーク全体における各ノードの役割，地位，行動の記述であり， DVMT では各ノードの関連域に仮説や目標を送る時期や対象ノード，内部あるいは外部から得られる
目標の選択法，目標の評価法を記述することにより実現している．このような組織構造を利用することにより，不 適切なノード間通信が減少する． すなわち分 散協調問 題解決に おけるノ ードの役 割を明示 的にする ことによ り
システムの一貫性を高めたといえる．ただし組織構造は静的な構造でしかな
く，あるノードで局所的に生じた雑音の影響が他のノードに波及することを避けることができない．すなわち組織というのは固定的なものであるのでそれが不適切である場合には十分に機能しないということである．
2. 局所計画(planning)の利用：これは状況に応じた適切な知識源の起動の順序を記述した「計画」を利用することによって，各ノードで局所的に生じる雑音などの影響を減らそうとしたものである．計画をうまく利用するために各ノードの状況を適切に把握する必要がある．黒板に記述される仮説や目標を参照するにはその量が多すぎるので，それらの情報を圧縮したものとして新たに抽象化黒板が導入された．従って，この DVMT のスケジューラでは目標用黒板を用いた短期計画，抽象化黒板による中期計画，組織構造による長期計画をもとにそのノードにおける知識源の起動順序を決定している．以上の手法により，ノードの自律性が向上し，ノード内部における局所的な問題解
決能力は大幅に改善された．しかし，ネットワーク全体でより一貫性のある

3.

問題解決を行うためには局所的な問題解決能力の向上だけでなく，ノード間の協調処理が必要になる．
メタレベル通信(meta-level communication)の利用： ノード間の抽象化黒板の情報を互いに交換することにより，互いに他ノードの状況を把握しようとするものである．すなわちノードの自律性だけでなく，協調性が強化された．
しかしながら，メタレベルの通信を多くすればするほどより協調的な問題解決が可能となるが，そのためのノード間の通信量が大きくなり，大規模なネットワークでは逆効果になってしまう．協調処理と通信量の減少とはトレードオフの関係であることが示された．

Durfee らは以上の協調機構を Partial Global Planning 機構として統一化を図った
13,14．
3.3.タスク共有方式
タスク共有方式では初期問題を分解し，部分問題を各エージェントに割り当て，それぞれのエー ジェントが部分 問題を解決する ことにより全体 的な問題解決 が進められる．こ こでの研究課題 はいかにして部 分問題を適切な エージェント に割り当てられる かという問題割 り当てと，部分 問題間での競合 解消にある． 本
稿では問題割り 当てのための代 表的な手法とし て契約ネットプ ロトコル，競 合解消の手法として分散制約充足について述べる．
3.3.1.契約ネットプロトコル15,16
問題割り当ては オペレーション ズリサーチや分 散処理における スケジューリ ン
グ技法や負荷分 散技法との関連 が深いが，一般 にスケジューリ ング問題は計 算
量の面から，最適解を求めることが困難な NP 完全問題に分類される17 ．それに加えて，分散協調問題解決では以下に示すような不確定性がある．
•••

割り当てるべき問題はあらかじめ明示的に与えられないかもしれない．すな
わち問題解決の過程で問題が分割されてゆく場合には，あらかじめスケジュールすることが不可能である．
それぞれ のエージ ェントに 関する完 全な大局 的情報を 用いるこ とはでき な
い．すなわち，大局的情報を得るためには通信コストがかかる上，故障も含めてエー ジェント は非同期 に動作す るので完 全な情報 を持つこ とは不可 能である．
オープンな環境ではエージェントの関係は対等である．すなわち，あるエー
ジェントが問題割り当てに関して，他のエージェントを完全に制御することができない．
したがって，こ のような環境に おいては，動的 な問題割り当て を行わなけれ ばならないが，分 散問題解決の手 法としては人間 社会の交渉過程 をメタファと した以下に示す契約ネットプロトコルが提案されている．
[契約ネットプロトコル]
Step1: 問題を持つエ ージェントは その問題を通知 メッセージを 用いて，他の エージェントに知らせる．
Step2: エージェントは受け取った通知メッセージの中から選択を行い， その解決コストを記述した入札メッセージを送り返す．
Step3: 入札メッセー ジを受け取っ たエージェント はその中で， 最もよいもの を選択し，判定メッセージを用いて問題を入札したエージェントに割り当てる．
契約ネットプロ トコルでは，エ ージェントが対 等の立場で局所 判断と相互選 択に基づき，問題が割り当てられてゆく(契約が結ばれてゆく)．
3.3.2.分散制約充足18
複数のエージェ ントに割り当て られた部分問題 が独立でない場 合には，エー ジ
ェント間で競合 が生じる．横尾 らはエージェン ト間での競合解 消問題は分散 制
約充足問題として定式化した．分散制約充足問題の例を図 2にあげよう．3 つのエージェントが存在し，エージェントはそれぞれ変数 P1,P2,P3 への値の割り当てをおこなう．ただし大局的な制約として，P1≠P3， P2 ≠ P3 という条件 が与えられている とする．それぞ れのエージェン トが個別に変数 を割り当てを お
こなっては充足解が得られない場合がある．

≠
P1

P2

P3

≠
P1=1

P1=2

P2=2

P3=1

P3=2

図 2：分散制約充足問題の例
この問題を解決 するためのアル ゴリズムの一つ として非同期バ ックトラック ア
ルゴリズムが提案されている．

[非同期バックトラックアルゴリズム]
Step1: 各エージェントは自分の解を局所的に求める．
Step2: 大局的制約にかかわるエージェントは ID 番号の小さいものから大きいものへ，解を OK メッセージを用いて知らせる．
Step3: OK メッセージを受け取ったエージェントはその解を記録し，自分の解との無矛盾性を確認する．矛盾が存在すれば自分の解を他の可能な解に置き換え，その解を Step2 と同じように OK メッセージを用いて他のエージェントに知らせる．置き換えが不可能な場合は，そのエージェント以外の解集合を NOGOOD メ
ッセージを用いて矛盾した解を持つ最も ID 番号の大きいエージェントに送る．
Step4: NOGOOD メ ッ セー ジ を 受 け取 っ た エー ジ ェ ン トは 無 矛 盾性 の 確 認 を
Step3 と同様に行う．NOGOOD メッセージがそれ以上送れない状態になると解が存在せずに終了する．
以上のアルゴリズムではエージェントの全順序関係を示す ID 番号を用いること
により，エージェントの解が ID 番号の大きいものに集められてゆく．解に矛盾の存在する場合には NOGOOD メッセージが逆の方向 に送られてゆくことに より，非同期バックトラックが行われ，アルゴリズムの完全性が保証される．
この手法はエー ジェント間の制 約が密接になっ てくると制約を 満たす解を求 めるために必要な 通信量が大きく なり，通信コス トの大きい場合 には性能が低 下する．充足解を 求めるためのも う一つの手法は 一つのエージェ ントに情報を 集中させて，その エージェントに より充足解を求 めようとする手 法である．た だ
し，求解を集中 的に行うことは ，それだけ並列 性が低下するこ とでもあり， 本
手法において分 散か集中かは通 信オーバヘッド と並列性のトレ ードオフの関 係にあるといえる．
4.Enterprise Integration
4.1.CALSCALSb とはデジタル化された情報を組織間で共有し，企業活動全般の合理化，効率化を図ろうとするコンセプトとイニシアティブの総称である19,20 ．デジタル化

b

CALS の語源は Computer Aided Logistic Support（全産業的電子取引システム），Computer-aided

Acquisition and Logistic Support（生産・調達・運用支援統合システム），Computer Acquisition andLife-cycle Support（生産・調達・運用支援情報システム），Commerce At Light Speed（継続的な調達と製品ライフサイクルの支援）というように時間とともに変化し，その概念自体拡大している．

された情報の活 用により，コス トダウン，品質 向上，迅速生産 などのメリッ トがあり，それは 一組織にとどま らず，それに関 わる全ての組織 体に与えられ ること に な る ． こ の結 果 ， 全 体 と して 合 理 的 で 無 駄の な い 企 業 統 合 (Enterprise
Integration)が実現されることになる．
現在のところ，CALS 実現のためのインフラともいえる企業間情報の標準化に関する議論が多い が，本稿ではそ のようなインフ ラが整備された 上でのマルチ エージ ェン ト技 術の 応 用に つい て University of Toronto の Mark Fox らに よ るEnterprise Integration に関する研究について紹介を行う．
4.2.Enterprise Integration21
情報通信技術を インフラとする 今後の企業社会 を生き抜いて行 くためには， 各
企業は全世界を 視野に入れた競 争力が必要とな る．将来的には ，企業の競争 力の基準となるも のは，単に労働 力や資本だけで はなく，情報の アクセス能力 と企業内の行動決 定に関する調整 能力になるとい う時代が来るで あろう．従来 の企業組織に関す る基本的な考え 方は階層構造で あった．これに より管理職の 負荷は軽減する反 面，正しい情報 を必要なときに 得られなかった り，各部門間 での調整も複雑に なるといった組 織の硬直性が問 題になる．より 柔軟な行動や 意
思決定を行うためには，組織は階層型から水平型へと構造変換する必要がある．
各部門がタスク に関連する情報 にアクセスでき ，その行動が他 の部門にどの よ
うに影響するか を理解し，組織 の目標を最適化 するような選択 肢を選ぶこと が重要になる．す なわち構成員の 職階よりも個別 の知識がより重 要になる．こ のためには情報ア クセス，意思決 定支援，行動実 行支援のための 情報技術が重 要になる．
企業における情 報処理と通信技 術は急速に進歩 しているが，実 際にはソフト ウェアがそれに伴 っていないのが 現状である．個 別の意思決定を 支援するソフ ト
ウェアは大量に あるのだが，組 織を越えた情報 アクセスと意思 決定を支援で きるものが存在し ない．エージェ ント技術は人と 計算機を柔軟に 統合し，大規 模
分散組織におけ る情報の収集と 分配，意思決定 と行動の調整を 支援すること が期待できる．
4.3.Supply Chain Management22
供給網管理は Enterprise Integration における典型的な具体例である．すなわち顧客からの受注， 要求の分散，製 造計画，資材調 達，在庫管理， 資材や製品の 運搬などが密接に連携したネットワークを構成している． このような供給網においては各部門毎 に様々な意思決 定が必要になる が，それが企業 全体としても 統制の取れたもの になっていなけ ればならない． その意味からも 供給網管理は 本

来，集中化され ているべきであ るが，企業と市 場のダイナミッ クスがこれを 困難にしている． すなわち顧客か らの注文の取り 消し，製造機器 の故障，資材 コ
ストの変動など により，計画や スケジュールを その都度，変更 しなければな らない．以上のよ うな予期しない 外乱に対して迅 速に対処してゆ くためには， 中
央集権的な意思決定機構でなく，分散協調的な意思決定機構が望ましい．
Integrated Supply Chain Management (ISCM)プロジェクトでは複数の協調的エージ
ェントによる供 給網管理機構の 実現を目指して いる．各エージ ェントは部分 的な供給網管理を遂行し，関連するエージェントと調整しながら意思決定を行う．
エージェントには機能エージェントと情報エージェントの 2 種類が存在し，機能エージェント が供給網の計画 と制御，情報エ ージェントが情 報と通信サー ビスの提供により機能エージェントを支援している．
本稿では以下， 情報エージェン トによる情報管 理・提供機構， また制約充足 に基づく機能エージェント間での調整機構について紹介する．
4.4.情報エージェントによる情報の管理と提供23
情報エージェン トはエージェン ト化された知識 ・データ管理シ ステムであり ，
企業ネットワー クを流れる情報 に対して一貫性 を保ちながら選 択的なアクセ ス
を利用者に許すものである．情報エージェントの機能には以下のものがある．
•
•
•
•
•
•
•
•
•
•

機能エージェント間で共有される情報の永続的保持機能
既存の情報と領域知識から新しい情報を推論できる演繹機能
時間に関する常識的表現と推論機能
協調的行動や問題解決に利用できる協調モデルの明示的表現機能必要とするエージェントに対する内容指向情報配送機能
エージェ ント間の 信念の一 貫性を保 持するマ ルチエー ジェント の信念管 理
機能エージェントと組織のモデル化機能
マルチエージェント環境における分散競合管理機能
情報の一貫性管理機構
モデルの変化管理機構

本稿ではこの中 からエージェン ト技術と特に関 連の深い，内容 指向情報配送 と分散競合管理について述べる．
4.4.1.内容指向情報配送
内容指向情報配 送機能は情報の 内容とエージェ ントの興味に応 じて情報を適 切なエージェント に配送する機能 である．この機 能実現のための 必須の能力は ，ある情報がある エージェントの 興味を満たすか をいかにして判 定するかとい うものである．情 報エージェント ではこれはサー ビスの分類と認 識により実現 されている．
情報を必要とするエージェントはその内容を subscribe メッセージを用いて情報
エー ジ ェ ン ト に 通 知 す る． ま た 情 報 を 提 供 す る エー ジ ェ ン ト は そ の 内 容 を
advertise メッセージを用いて情報エージェントに通知する．情報エージェントは
情報提供エージ ェントから受け 取った情報に対 して，分類や推 論をした後に 必要とするエージ ェントに配送す る．すなわち情 報エージェント は情報配送に 関
してエージェント間の仲介を行うわけである．
ここで具体例を示そう．エージェント 1 は重量が 5000 グラム以上の部品に興味があるとし，そのことを subscribe メッセージを用いて情報エージェントに通知する．一方エージェント 2 は「部品 p-111 は c-12 と c-13 から組み立てられている．」，「部品 c-12 の重量は 2700 グラムである．」，「部品 c-13 の重量は 3400
グラムである． 」という情報を 情報エージェン トに通知する． 情報エージェ ン
トはエージェント 2 からの情報をもとに，「部品 p-111 の重量は 6100 グラムである」との推論を行う．そこでエージェント 1 に対して得られた情報を通知す
る．その後，エージェント 2 から「部品 c-12 の重量は 1000 グラムである．」という変更の通知を受け取ると，情報エージェントはエージェント 1 に対して先の情報が変更になったことを伝える．
以上のように情 報エージェント は収集してきた 情報に推論機能 を用いて付加 情報を得たうえで，その情報を必要とするエージェントに配送する．
4.4.2.分散競合管理
マルチエージェント推論システム において，p&q=>false となるような矛盾は しばしば生じる．エージェントがそのような矛盾に遭遇した場合には p あるいは qを指示する信念 を削除しなけれ ばならない．こ のような機能を 実現するため に信用度と削除コストに基づく手法が用いられている．
例えば，ある自動車会社において，販売部門エージェントはその売れ筋から「新車のエンジンは v6 型エンジンにする」という言明 A をしたとする．一方で設計部門エージェントは現場の判断で「新車のエンジンは 14 型エンジンにする」という言明 B をしたとする．これらの二つの言明は両立しない．情報エージェン
トは信用度(credibility)と削除可能度(deniability)をもとにこれらの言明のいずれ かを選択する．信 用度は言明を生 み出したエージ ェントに関わる ことである． 先の例における販 売部門エージェ ントと設計部門 エージェントと の比較では， 車の製造に直接携わるという点において設計部門エージェントの信用度（言明 B）

の方が販売部門エージェントの信用度（言明 A）に優るであろう．一方，削除可
能度は言明を利用するエージェントに関わることである．例えば，言明 B を先に得ていた資材調達部門エージェントが 14 型エンジンの外部調達を決定していたとする．このばあい言明 B の不採用は，外部調達のキャンセルを意味し，そのコストは大きく，削除可能度は言明 A に比べて低くなる．
4.5.機能エージェント間での制約緩和
供給網管理にお いては機能エー ジェント間には 様々な制約が存 在し，それら を常に充足する必 要がある．エー ジェント間の制 約は制約グラフ として表すこ とができる．各エ ージェントには 一つ以上のタス クが割り当てら れており，タ ス
クは制約に従う 必要がある．し たがって実行可 能な制約グラフ を見つけるこ とが問題となる． しかしながら， あるイベントが 生じると，もは や全ての制約 を満たすことがで きない場合があ る．その場合に はできるだけ全 体に影響を与 えないように制約 を緩和する必要 がある．制約緩 和問題は過制約 の制約グラフ から修正コスト最小の実行可能な制約グラフを求める問題である．
Beck らは制約緩和問題に対して分散的な交渉アプローチではなく，むしろ集中的な調停(mediated)アプローチを採用している．ここで，運用管理エージェント L，
資源管理エージェント RM，受注管理エージェント OA，3 台の工場エージェン
ト（工作機械 M1 1， M1 2 をもつ F1 ，M2 1， M2 2 をもつ F2 ，工作機械 M3 1， M3 2 をもつ F3 ）による制約緩和の例を示そう．三つの注文 O1 ,O2 ,O3 があり，発注時刻
は t1 ，納期は t3 である．工作機械のスケジュールは表のように与えられたとする．
表 1：工作機械スケジュール

時刻 t1 に O3 に関する A1 3 の作業を M1 2 で実行するように依頼があったとする．受注管理エージェントはそのような顧客からの要望を運用管理エージェントに伝える．運用管理エージェントは以下の二つの選択肢を得る．
1. 作業 A1 1 と A1 2 を他の機械に移動させる．
2. 製品の納期を延期する．
そして管理エージェントは以下のように，それぞれの選択肢に対してその評価

のための情報を他のエージェントから集める．1 番目の選択肢に関しては，• L から RM：M12 の代わりになる機械はあるか？
• RM から L：M22 が利用可能だ．しかし質は低下する．
• L から OA：注文 O1 ,O2 で質を落とすとコストはどれくらいになるか？
• OA から L：それぞれ 3 だ．
また 2 番目の選択肢に関しては，• L から OA：各注文の納期を遅らせるコストはどれほどか？
• OA から L： O1 に関しては，1 日毎に 5 で，遅くとも t6 までに．
• OA から L： O2 に関しては，1 日毎に 5 で，遅くとも t6 までに．
• OA から L： O3 に関しては，1 日毎に 2 で，遅くとも t6 までに．
以上のように制約グラフをもとに情報をあつめコスト最小の選択肢を選ぶ．
5.まとめ
本稿ではエージ ェントとは何か という問いに答 えた後，マルチ エージェント によ る 分 散 協 調 問 題 解 決 手 法 に つ い て 代 表 的 な 研 究 事 例 を 紹 介 し ， Enterprise
Integration への応用事例についての紹介を行った．4 章での応用事例は必ずしも3章で紹介した自律分散的な手法をそのまま応用したものではない．むしろ集中的な問題解決手 法を重視したオ ーソドックスな ものとなってい る．これは現 時点における提供 できる技術と要 求される技術の ギャップを示し ているのかも しれない．しかし インターネット の普及とともに 将来的にはオー プン環境に適 応できる情報処理 システムの必要 性は高まり，そ れとともに分散 協調処理技術 の重要性も高くなると予想される．
参考文献
1

石田亨：エージェントを考える，人工知能学会誌，10(5):663-667 (1995).

2

所真理雄：マルチエージェントシステム研究の目指すもの，コンピュータソフトウェ

ア，12(1):78-84 (1995).
3

A.H. Bond and L. Gasser: An analysis of problems and research in distributed artificial

intelligence, Readings in Distributed Artificial Intelligence, Morgan Kaufmann, pp.-35(1988).
4

桑原和宏，石田亨：分散人工知能(2)：交渉と均衡化，人工知能学会誌，
8(1):17-25 (1993).

5

大沢英一：マルチエージェント環境における交渉のモデル，人工知能学会誌，

10(5):690-696 (1995).
6

R.G. Smith and R. Davis: Framework for cooperation in distributed problem solving, IEEE

Transaction on Systems, Man, and Cybernetics, SMC-11(1):61-70 (1981).

7

L.D. Erman, F. Hayes-Roth, V.R. Lesser, and D.R. Reddy: Hearsay-II 音声認識システム：

不確実性の解決のための知識の統合，bit 別冊コンピュータサイエンス，pp.53-91，共立出版 (1981).
8

V.R. Lesser and L.D. Erman: Distributed interpretation: a model and experiment, IEEE

Transactions on Computers, C-29(12):1144-1163 (1980).
9

V.R. Lesser and D.D. Corkill: The distributed vehicle monitoring testbed: a tool forinvestigating distributed problem solving networks, The AI Magazine, Fall, 15-33, (1983).
10

V.R. Lesser and D.D. Corkill: Functionally accurate, cooperative distributed systems, IEEE

Transactions on Systems, Man, and Cybernetics, SMC-11(1):81-96 (1981).
11

V.R. Lesser: A Retrospective View of FA/C Distributed Problem Solving, IEEE Transactions

on Systems, Man, and Cybernetics, SMC-21(6):1347-1362 (1991).
12

E.H. Durfee, V.R. Lesser, and D.D. Corkill: Coherent cooperation among communicatingproblem solvers, IEEE Transactions on Computers, C-36(11):1275-1291 (1987).
13

E. H. Durfee and V.R. Lesser: Partial global planning: a coordination framework for

distributed hypothesis formation, IEEE Transactions on Systems, Man, and Cybernetics,
SMC-21(5):1167-1183 (1991).
14

E.H. Durfee: Coordination of Distributed Problem Solvers, Kluwer Academic Publishers(1988).
15

R.G. Smith: The contract net protocol: high-level communication and control in a distributed

problem solver, IEEE Transactions on Computers, C-29(12):1104-1113 (1980).
16

R. Davis and R.G. Smith: Negotiation as a Metaphor for Distributed Problem Solving,

Artificial Intelligence, 20:63-109 (1983).
17

野下浩平他：基本的算法，岩波書店(1985).

18横尾真他：分散制約充足による分散協調問題解決の定式化とその解法，電子情報通信学会論文誌，J75-D-I(8):704-713 (1992).
19後藤龍男：CALS：21 世紀における企業情報システムの国際標準確立と企業統合に向けて，情報処理，36(1):1-7 (1995).
20

末松千尋：CALS の世界：競争優位の最終兵器，ダイアモンド社 (1995).

21Mark S. Fox: 40 Month Progress Report NSERC Industrial Research Chair in Enterprise

Integration, http://www.ie.utoronto.ca/EIL/overview/overview.html.
22

J. Christopher Beck and Mark S. Fox: Supply Chain Coordination via Mediated Constraint

Relaxation, Proceeding of the First Workshop on Distributed Artificial Intelligence (1994).
23

Mihai Barbuceanu and Mark S. Fox: The Information Agent: An Infrastructure forCollaboration in the Integrated Enterprise, Proceedings of CKBS94, 257-294 (1994).