マルチメディア通信と分散処理ワークショップ平成8年10月
エージェントによる分散情報の管理と探索*
阿部康一
武田利治
丹野州宣
f
E-m
泊d
此
1
:
作
{
k
o
u
叫i
c
ω
h
i
，
t
地北
e
仙
d
伽
a
，
t
伽a
a
組:
nno}
陣
@et
凶n
.
戸y
z
.
y
翻a
碍g
肝a
御t
凶a
仇-屯也-
u
札.必品判u
a
配飢叫，氾ι
ι
吋
c
吋
J
.
山形大学工学部電子情報工学科
t
近年の World-Wide Web (WWW)の普及によるインターネットへの関心の高まりは、目覚しいものが ある.特に World-Wide Webによる個人での容易な情報の措佃は、瞬く聞にインターネット上に膨大な あらゆる情報を無秩序に抱濫させるに至り、ユーザが自分の必要とする情報をどのようにして探し出すか が大きな問題となって来ている.そのため、 World-WideWeb上の情報を対象とした様々な検察システム が盛んに研究・開発されている.しかしながら、いずれのシ九テムも単一ホストによる集中管理方式を採 用しており、現在のような胆大化した情報資源全体を管理するには限界があるように恩われる. そこで本研究では、 Wotld-Wide Webなどの情報資源を提供するサーパ自身が検察サーパとしての役割 をもっ分散情報の自己管理方式を提案する.本方式では、エージzントのマイグレーシgンによって、分 散配置された情報資源を相互に結び付け情報探嬬に利用する.これにより、インターネット上の情報資源 を効串的に管理し、ユーザの必要とする情報を探索することが可飽になると考えている.本文では、シス テムの基本概念と各エージェントの役割、コミュ=ケーション・プロトコルなどについて報告する.1
はじめに
近年のインターネットの一般的社会への普及、す なわち World-Wide Webの利用者の増加は目覚しい ものがある。今では、インターネット=World-Wide Webという図式が成り立つほどに World-Wide Webの利用者が急増している.特に、個人による自由な 情報の発信が可能ということで、多くの利用者によっ てインターネット上に情報が無秩序に分散・蓄積さ れ続けている.それにより、既存のインターネット 上の情報資源が World-Wide Webの影に隠れてしま うほどである。 そのため現在では、ユーザが自分の必要とする情 報をこの膨大な情報資源からどのようにして探し出 すかが最大の問題となってきている。最近では、膨 大な World-Wide Webの情報源から目的の情報を見 つけ出す士めに多種多様の検索システムが研究・開発 され続けている。一般に、この間屈を解決する方法 として、情報カタログを利用した検索方式が広く使 用されている.この方式では一般に、あらかじめ対 象とする情報に関するデータベース(情報カタログ) • AD lnfonnation Retrieval and M細 胞gementSystem OD
Dis凶butedCompu.ter Ne.tworks b回edon Age叫 Modcl
t Kouichi ABE
，
T，回hiluroTAKETA，
Kuninobu TANNO'Dcp町 凶entof Electrical岨 dlnCorma.tion Engiso創mng， Yamagata Univ，倒:sity を作成しておき、ユーザの検索要求を満たすオ宵報を カタログから検察して、その情報の一覧をユーザに 提示する。しかしこの場合、ユーザが情報検索サー ピスを行なうことのできる検察サーバを明砲に知っ ているということが前提である。また現在の World-Wide Webや NetNew8などの情報量を見てもわか
るように、単一ホストで情報資源全体を把揮するの は困難である.このようにインターネット上の情報 資源の極度の分散化、大規模化が現在の情報検索に おける大きな問題となってきている. 本研究では、従来の単一ホストによる集中型の情 報管理方式に対して複数のホストによる分散型の自 己情報管理方式を提案する.しかし、そのような分 散型自己情報管理方式においては各情報資源開の効 率的な検索、つまり相互に情報を結びつける方法が 必要がある.そこで、本研究ではマルチエージzン ト・モデルを導入し、その自律的なマイグレーション 機飽を利用する.さらに遺伝的アルゴpズムにもと づくエージzントの自樟再生産と最適エージェント への進化を介して、分散環境上における情報の効串 的な情報資源探索を実現する.本研究の究極的な目 標は、 Wor1d-Wide Webなどに限らずインターネッ ト上の全ての情報資源の効率的共有の実現である。 本文は、以下のように構成される。まず最初に、イ
ンターネット上における情報資源について述ペ、現 ピス毎に異なるクライアント(ユーザ・インタフェー 在の情報資源の管理方式と本研究で提案する分散し ス)を使用しなければならない。
た情報資源の自己管理方式とそれに応じた情報検索 現在は、 World-Wide Web用のブラウザがこれら 方式について述ペる.次に、この方式にもとづいた の情報資源にアクセスするための共通のユーザ・イ システムの概要について詳細に説明する。最後に、 ンタフzースとして利用できる.これにより、上記 今後の研究の方向性について述ペる. の情報資源への統ーしたユーザ・インタフェースの 提供がなされることになり、初心者にとってはかな
2 インターネット上の情報資源
り便利な環境になりつつある.実際、大多数のユー ザによって様々なプラウザがこれらの情報資源への2
.
1
情報資源と利用の仕方 インタフzースとして利用されている. インターネット上で利用できる情報資源には様々2
.
2
情報管理形式と情報検索方式 なものが存在する。その中で現在、非常に盛んに利 用されているのがWorld-Wide Webである.この 節では、インターネットよで広く利用されている情 報資源とその利用形体について簡単に述べる. • World-Wide Web: インターネット上の分散された情報をハイパー テキスト・ネットワークでまとめた分散情報シ ステム。ブラウザと呼ばれるクライアントを 利用して個人毎に自分の興味のある見出しを 辿って行くことにより情報を得る.専用の検索 サーバを持つ. • NeもNew目: インターネット上の世界規模の電子掲示版シス テム。様々な=ユース・グループがあり=ユー ス・P
ーダと呼ばれるクライアントを利用し、 自分の興味を持つ=ユース・グループの記事を 臨むことにより情報を得る.専用の検察サーバ を持つ。 - 叩onymou8FTP Service: 現在の情報検索システムのほとんどが、一つのサー パで各情報資源の情報カタログを管理している(図 2.1)0 しかし、インターネットのような大規模なコ ンピュータ・ネットワーク上の全情報を一つのサー バで管理するには限界がある。本研究では、以上の 問題を解決する方法として、図2.2に示すようなシス テム構造を提案する.このシステム構造では、各々 の情報資源が各自の情報カタログを所有する情報検 察サーパになることである.このとき各サーバでの 情報の検嬬は、専用の情報探索エージzントを用い て実行される. 図2.1:一般的な検察システムの構造 また、インターネット上に存在する各種情報検索 サービスは、一般にある限られた情報資源を対象と インターネット上でYフトウaアやドキュメン トなどを提供するサービスoUNIXなどのo
s
には標準でftpという名のクライアントが存 在し、それを利用して必要なYフトウzアな.ど を得る.ただし、事前に目的のソフトウェアな どの保存しているサーバなどを、 archieなど の専用の検索アプリケーションを用いて検察を 行う必要がある場合が多い. したシステムであることが多い.そこでは、同ーの これらの情報資源は、それぞれ，独立したサービス 情報を提供する情報資源から定期的にそのホストが としてインターネット上に数多く存在している。ユー 所有している情報のPストを受け取り、インターネッ ザは、目的の情報資源にアクセスするために、各サー ト上全体とはいかないが、大規模な情報カタログを作成し、それを使用することでユーザからの喪求に 応えている。 しかし、現在のような胞大化したインターネット 上の情報資源の情報を単一のホストで管理するには 限界がある。さらに、実際にユーザがこれらの情報 資源から必要な情報を探し出すためには、各情報資 源毎に専用の情報検索サービスを使用しなければな らないζともあげられる。本研究では、これらの問 題を情報の分散管理と情報探索エージェントによる 検索方式で解決を図る. 図2.2:本研究で提案する検索システムの構造
3 分散情報の共有
本システムの基本概念は、分散されている情報を ある特定の単一ホストで集中管理するのではなく、 その分散されている情報毎に自己管理し、それらを 相互に効率的に結び付けることである。3
.
1
マルチエージェント・モデル 本研究では、これらの検索サーパ聞の相互結合に エージェントの概念を導入する.現在、エージェン トという用語は人工知能分野とコンピュータ・ネッ トワーク分野において広く使用されている問。本研 究では、エージェントを次のように考える. 『人間や他のものの直接的な支毘・制御を受ける ことなく動き(自律性)、ある種のコミュニケーショ ン言語を通じて、その他のエージェント(あるいは 人間)と相互に影響し合う(社会性)もの。』 またマルチエージェント・モデル(図3.1)とは、複 数のエージzントがお互いに協カしてある目的を達 成するモデルをいう。本システムでは、ユーザの必 要とする情報を探し出すことが最終目的にあたる。 図3.1:マルチエージェント・モデル3
.
2
システムの構造 インターネット上における本システムの構造は、 図3.2に示すモデルとして表すことができる。図3.2 からも分かるように、本システムは3つの機能別領 域に分割される。すなわち、ユーザ・インタフェース 領域と情報探索領域、情報管理領域である。これら は大まかに言って、それぞれユーザ・インタフzー ス・エージェント、情報探索zージェント、情報管理 エージェントにより機能する.ユーザ・インタフェー ス・エージェントは、情報検索を行なう際にユーザ とのやり取りを行う.情報探索エージzントは、実 際にインターネット上で情報資源を探索し、目的の 情報を対象とする情報の情報資源から検察する.情 報管理エージェントは、各情報資源を管理するエー ジェントである。3
.
3
システムの機能 本システムはインターネット上のあらゆる情報資 源を効串的に共有することを究極的な目標としてい る.情報共有の基礎は、いかに効率的に目的の情報 を探し出すことができるかである.そのため現段階 では、分散情報の自己管理方式による検索サーバに 依存しない、動的にホスト環境に適応する情報探索 システムの構築および実験を目標としている。実装 においては、既存の環境を変更することなく本シス テムを導入でき、また、ユーザから見れば単に必要 な情報に闘するキーワードと情報資源名を入力する図3.2:システムの抵念図 だけで、目的の情報を入手することができるシステ ムの実現を目標に研究を進めている。 現在、プロトタイプ・システムとして以下の機能 を実装中であるa 1.検索サーバに独立な情報探索機能:
4
システム・エージェント
本節では、システム上で稼働する各エージェント について説明する。4
.
1
ユーザ・インタフェース・エージェント ユーザ・インタフェース・エージェントは、実際 にユーザから情報探索の要求を受け取るエージェン トである.そのため、初心者でも操作体系が容易に 理解できるインタフェースを備える必要があるa現時点では、 World-Wide WebのCGIのスクリプト として実装することを考えている。本システムでは、 このエージェントを“Communicatortlと呼ぶa ."1-ザ酢晶 S圃同町魁園町酬町民 輸摩繍.，ft
，
.
..鐘'審事績.
.
.
書
輸・ーー・す晶 .叶竃轟 図4.1:CommunicaLor状態適移図 決まった検索サーパに問い合わせるのではな く、情報探索エージェント自らが検察サーバを 決定し、検索しに行くこと(これを情報の探索4
.
2
情報探索エージェン卜管理工ージェン と呼ぶ)D ト 2.動的な環境適応機能: 情報探索エージェント管理エージェントは、情報探 情報探索エージェントがホスト環境とユーザか 索エージェントの統括、ユーザ・インタフェース・エー らのP
アクションによって、そのホストとユ} ~:r.ントからの探索依頼の下請け、情報探索エージェ ザに対して最適な情報探索エージェントへと進 ントの遺伝的操作を行うエージェントである。本シ 化していくこと。 3.情報カタログによる統ーした情報管理機能: World-Wide Web、臨むNew日などの情報資源 を区別することなく、一つのサーパ上で情報カ タログを用いることによって統ーして管理する こと。つまり、これはWorld-Wide Web専用 の検察サーパとかNetNews専用の検察サーパ とかと雷う区別がなくなることを意味する. 4.ブラウジング機能: 検索結果である情報資源からの情報を、ユーザ に分かりゃすい形式に変換(アイコン化やURL など)して、ユーザはそれらを選択するだけで その情報を得ることができるようにすることa ステムでは、このエージzントを“SeekersManager" と呼ぶ.-
缶
前
・
.
"
，
.
"~，，， 何色す畠 ~t~ "ttれほ. . %-!:I%:，.ト*'&O :U~::~ーや・:. ..嘩量附晶 白岡岡田畑圃・e包 圃悔a.胸la ..ーー・嗣，，0.
.
.
.
.
.
す
・笥.
.
ι
巴.
.
I
:
a
U. fiH. 図4止 SeekersManager状態遷移図各情報探索エージzントは、図4.3で示す形式で管 4.3.1 遺佳的アルゴリズム 理される。 ムでは、このエージェントを“InfoSeeker"と呼ぶ. イアントはサーパのホストに接続して、各種提供さ れるサービスを受ける.これに対して、マイグレー ションとは、クライアントとしてのエージェントが 実際にサーパ・ホストに移動し、そこでサービスを 受けたり、何らかの行動を起こしたりする.そして また、出発したホストに戻って来る仕組みである。 マイグレーション・号デルを使用することにより、 エージェントを用いた並列的情報探索と情報探索に おけるシステムの負荷分散を行うことが可能となる。 つまり、従来のように検索サーパに集中的に負荷が かかることもなく、またエージェントを通じた各情 報資源開の情報共有にも大きな役割を呆たす。 図4.3:InfoSeeker管理フォーマット
4
.
3
情報探索エージェント
情報探索エージェントは、実際にインターネット 上の各検索サーバ聞を移動(マイグレーションと呼 ぶ)しながら、目的の情報を探し出すエージzントで ある。このエージェントは、各クライアント・ホス トで一定の数だけ生成され、その時探索するサーパ、 検索結呆、探索時間の上限などをパラメータ(遺伝 子)として持つ。そして、一定サイクル毎に遺伝的ア ルゴりズムにもとづく遺伝的操作により、次世代の 情報探索エージェントを生成する。このサイクルを 繰り返すことにより、自分の生存するホスト環境と ユーザに適応していしさらに、検索結呆に対する ユーザからの評価や探索経験によって、より効率的 な情報探索を行うための学習機能も持つ。本システ⋮ ⋮
圃 . . 帽 図4.4:InfoSeeker状態遷移図 遺伝的アルゴpズム(GeneticAlgorithms: GA) は、生物進化(自然掬汰、突然変異)の原理に着想を 得たアルゴP
ズムである.遺伝的アルゴP
ズムでは、 図4.5に示すように問題の解侯舗を遺伝子として表 現する.この遺伝子によって構成されるのが染色体 であり、染色体上の遺伝子の位置を遺伝子座、遺伝 子の組合せパターンを遺伝子型という。また、この 遺伝子型にもとづいて形成された個体を表現型とい い、これらの個体が進化することによって解を求め るアルゴリズムである.個体の進化は、3種類の遺伝 的操作(週択掬汰、交叉、突然変異)を使用すること によって行なわれる向。本研究では、情報探索エー ジェントが個体として扱われる。 染色体 遺伝子三ーベ調麹姐亙￨見
遺伝子座 遺伝子型 図4.5:遺伝的アルゴリズムにおける個体 4.3.2 マイグレーション 一般的なサーバ・クライアント・モデルでは、クラ 4.3.3 情報探索エージエントの構造 情報探索エージェントは、ヘッダ部とボディ部か ら構成される。ヘッダ部は、Searched 検察したホスト名の履歴 Pre-Host 直前に検察したホスト名 Migration・Errors マイグレーションに失敗 した数 Home-Host 探索終了条件時に戻るホ スト名 Max-Hosts 探索する検察サーパ数の 上限 Max-Results 検索結果の上限 Time-Limit 探索時間の上限 Hosts 現在の探索サーバ数 Results 現在の検紫結果数 Tim倒 現在の探索時間 Date 探索を開始した日付 Agent-ID 情報探索エージsント詔 柾コード User 探索を依頼したユーザ名 (E-Mail address) Resources 検察する情報資源名 Keywords 検察用キーワード群 で構成される.また、ボディ部は、検索結呆を各情報 資源に応じた URL(UniおrmR怠80urceLoc叫or)で 記述したものである.
4
.
4
情報管理エージェント
情報管理エージzントは、情報資源を提供するサー パにおける情報の統ーした管理、情報探索エージェ ントからの検索依頼の処理を行うエージzントであ る。またよ現在のシステムの実装は、 UNIX上を前 提としている.このため、 World-Wide Webのサー パを MacintoshやWiDdows上で動作させている場 合は、情報管理エージェントなどが存在できない. そのため、そのようなマシンの代理的な情報管理を 行う機飽も備えている.本システムでは、このエー ジzントを“InfoM組 ager"と呼ぶ. %-l:Izシトfr.晶骨 四t.す晶:::~.. ::J・:L='~-ー・ ν Cllt恥a椅
.
.歳嘩曇暗轟 凶 ー " 町"
'
0
. . 民acu. 図4.6:lnfoManager状態遷移図 4.4.1 情報管理方式 各情報資源のf
僻創立、全て統ーしたフ泊ーマットで 記述された情報カタログによって管理されるa この 情報カタログは、InゐMangerによって各情報資源毎 に、自動的に作成・更新される。現在、 World-Wide Web、相onymousFTP service、NeもNeW8を対象に実験を進めているが、このとき各情報資源毎のカタ ログ作成時における情報の公開制限を行うための設 定ファイルを利用することもできる.情報カタログ のフォーマットを、図4.7に示す. 図 4上情報カタログのフォーマット また、各情報資源の情報カタログのための情報と キーワードは、それぞれ以下の規則に従って自動的 に対象となる情報ファイル (HTML文書、エユース の記事など)から取り出される。 • World-Wide Web:
H
τ
・ML文書中のタイトル、・ヘッダ、アンカー・ タグ・フィールドから取り出す. - 組onymo凶 FTPservice: 1s-1Rなどのテキスト・ファイルから取り出す. • NetNews: エユース記事のヘッダ・フィールド (Message.ID、Newsgroups
，
Subjectなど)と、本文から 取り出す. 4.4.2 情報検索方式 情報検索のパターンは、 (1)英語の大文字・小文字に関係なく、その文字列 を含む情報を検察する。 (2)英語の大文字・小文字を区別して、その文字列 を含む情報を検索する。 (3)正規表現を用いて情報を検察する. (4)与えられた文字列に正確に適合する情報を検 索する。 以上の4パターンである.また、検索文字列の結合 規則は、 (1)叩 d結合:キーワード群すべてを必ず含む情報 を検索する。 .:-$1%シト'"島町 ..串且砂.骨 備もす轟 ζt~ :l 1 .1:~-i-1I ν ..on骨.， tlttNtn .憲章.ft‘
刷副拘園調書." 岡崎闘相.'"晶 幅拘蜘臨町署・
・
ホ
九
州
Zマイグ alJlt_"':r.ト ザーIfロ畏" "-i-.=-寄せ晶 ~e・...・ AA晶 図4.8:GateKeeper状態適移図 検最ζ
?
1
<
名竺笠
f
W W W s加.yz.yamaga匂・U.BC伊 W W W 0 鈍p.yz.yamaga佃・u.ac.Jp 円P 0 n側s.yz.yamagE蜘-u.ac.Jp NEWS 0 検来4
(2)or結合:キーワード群の少なくとも一つのキー 園4.9:検策ホスト・テープルの7 *ーマット ワードを含む情報を検索する。 (3) noも結合:キーワードに完全にマッチする情報5
むすび
を除外するa (4) exact結合:キーワードに完全にマッチする情 報を検窮する。 である。情報管理エージェントは、上述の結合規則 にもとづいた検索文字列を情報探索エージzントか ら受け取り、検察を行う.4
.
5
サーバ・アクセス監観エージェント サーパ・アクセス監視エージsントは、情報探索 エージェントに次の検索ザーパ名を伝えたり、検察 候補のサーパ名を管理するエージェントである。本 システムでは、このエージェントを“GateKeeper" と呼ぶ. 4.5.1 検索ホスト・テーブル 情報探索エージェントのマイグレーション用に使 用する検索ホスト・テーブルのフォーマットは、図 4.9に示す栴遣を持つテキスト・ファイルである。 インターネット上の情報資源は、日々更新され唱 え続けている.そのため、それらの情報資源からど のようにして必要な情報を見つけ出すかが、重要な 問題となってきている。本研究では、この問題に対 する解決法として分散情報の共有を前提とした情報 探索システムを提案し、その構成と機能について述 ペた。さらに、システムにおける各エージェントの 機能などについて詳細に説明した. 今後の研究方針は、大学内のLAN(LocalArea Net -work)上でのプロトタイプ・システムによる実験結呆 を収集し、評価することである.その後、WAN(Wide Area Network)上での実験に拡張していく予定で ある。 参考文献 [1] RobertAnnatrong， Dayne Freit，略ThorstCDJωchlm・ S，岨.dTom Mit.chell， "Wd Wotchcr: A Le4rnifJg Ap. prenticc Jor .he Worltl Wide Wd"，
Schoal 01 Com-pu.tcr Science， CAnlegie MelloD U同 時 四ity，JADUAfY 20，(2J M. Sri国vωandLalit M. Patnaik
，
"Genetic Algorithm・ .: A Survep"， IEEE， June 1994， pp.l1.・26.同MichaelW
∞
l世idge岨 dNicbol国 R.Jennings“
，
'ln1el-ligent AgenC.:T1aeo1"1lond Practice"
