第回マルチ・エージェントと協調計算ワークショップ

モバイルエージェント 系における分散制約充足
沼澤 政信 栗原 正仁 能登 正人

本論文では，モバイルエージェント系における分散総通信量がピークとなる困難な問題に対しては，制約充足について，いつ・どのような目的でエージェエージェントサイズがある程度大きくても総通信ントの移動が考えられるのか基本的な考察をする．そ量を抑制できる．の中から，実ネットワーク中を流れる総通信量を抑制はじめにする目的で移動する場合に焦点を当て，簡単な計算モデルを構成し，計算機シミュレーションにより，この近年のネットワーク技術の急速な発達により，コンモデルに基づく移動が総通信量に与える効果についピュータの利用形態は，単体で使用するというよりて定量的な評価をする．分散制約充足アルゴリズムとも，インターネットやしては分散などのネットワークを介アルゴリズムを仮定し，シミュして使用する環境になった．そのような分散環境に対レーションにより総通信量を測定した．その結果，以応した分散型ソフトウェアを柔軟に構築するために下のことがわかった．

エージェント技術が注目され，さらに最近ではそれを総通信量は，一般にリンク数の増加とともに急発展させたモバイルエージェントと呼ばれるホスト間激に増加し，ピークに達した後急激に減少する．

を移動するエージェント技術が有効であると考えられその後，緩やかに増加した後に緩やかに減少する．ている

エージェントサイズが，上限として定義したスクの内容を保持したまま別のホストに移動してタスよりも十分小さいときには，移動したほうが総通クを継続することができるため，ネットワーク上のコ信量が概ね削減できる．逆に，エージェントサインピュータ資源を有効利用することが可能である．よズが十分大きいときは，移動により総通信量はかく知られているモバイルエージェントシステムとしてえって増加する．

は，よる．モバイルエージェントは，途中のタ社による，東芝による，になどがある．

このような状況に対応して人工知能の分野におい，小樽商科大学商学部社会情報学科，ても，知的エージェントの実現基盤の一つとして知られている制約充足技術が，分散制約充足技術の研究に移行してきている，北 海 道 工 業 大 学 工 学 部 情
報デ ザ イ ン 学 科 ，．そこでさらに，分散型ソフトウェアの構築を考慮し，分散制約充足の計算モデルもモバイルエージェントに対応するように拡張すること，神奈川大学工学部電気電子情報工学科，は自然な研究の流れである．しかし，そのような研究例はまだみられない．エージェントが移動しようがしまいが，いわゆる位置透過性があるシステムにおい46

第回マルチ・エージェントと協調計算ワークショップては，エージェント間のメッセージ交換の媒体が異な

network

Host1

るだけで，メッセージの内容や交換のプロトコルが異Host2

RPCなるわけではないので，抽象的あるいは論理的な意

AB

味では両者に差異はない．しかし，実装レベルでは，実ネットワーク中を流れる総通信量，延いては，実行RPC (Remote Procedure Call)効率の面で大きな違いとなりうる．

(a) client/server

本論文ではそのような研究の第一歩として，まず，いつ・どのような目的でエージェントの移動が考えら

network

Host1

Host2

Movementれるのか基本的な考察をし，その中から，実ネット
A

ワーク中を流れる総通信量を抑制する目的で移動すA’

Bるケースに焦点を当て，簡単な計算モデルを構成する．そして，計算機シミュレーションにより，このモ(b) mobile agent

デルに基づく移動が総通信量に与える効果について定量的な評価をする．

図

処理形態の違い章では，モバイルエージェントと分散制約充足について概説し，その特徴を述べる． 章では，考えうことができるように設計されている．

る種々の移動方式を簡単に考察した後，通信量を移動

モバイルエージェントを用いてコード 転送し，それのトリガとする計算モデルを導入し，その評価のためぞれのホストでその転送されたコード を実行するたのシミュレーション実験について述べる． 章では，

めには，セキュリティ保護，障害対策，トラフィック実験結果に基づき，この計算モデルの特徴と有効性を増加，管理の手間の増加といった問題が複雑化する．

議論する． 章では，まとめと今後の課題を述べる．

しかしながら，不安定で間欠的な通信路を常時使用する必要がなく，通信コストの削減が可能となるなどモバイルエージェント と分散制約充足メリットが大きい．その理由は，従来のクライアント

モバイルエージェント システム／サーバ方式とモバイルエージェント方式の二つのモバイルエージェントは，コンピュータ間の自律的処理形態を比べることにより，容易に理解することが移動能力を持つプログラムであり，エージェント自体できる．例えば，二つの異なるホストにいるエージェが利用者の代理人としてネットワーク上を自律的に移ント間で動しながら特定のタスクを遂行する．そのため，利用があるとき，クライアント／サーバ方式では，者はネットワークに逐一接続して作業する必要がな

回の要求と応答が回の要求を発行し，それに対する応答と間のネットワークい．通常のエージェントでも，それぞれのホスト間で上を往復することになる（図）．一方，モバイル遠隔通信機能を使ってホスト間でのメッセージ通信がエージェント方式（図可能であるが，ネットワークが不安定で間欠的であっ往復するだけでたり，低速もしくは費用の高い通信路を使用しなけれローカルに行うだけで済む．このばいけないといったケースが考えられるなど問題点も費用の高い通信路であったり，要求の回数が多い．なお，モバイルエージェントは技術の関連）では，エージェントが回の要求と応答は，上で回が，非常に万回，万回と増えていった場合を想定すると，移動してで議論されている他のエージェント技術とは異なり，処理を行う効果は高いと想像できる．

必ずしもインテリジェンスを持たないことが多いが，また，この処理形態の違いにより，もう一つ重要な本研究で扱うモバイルエージェントは，分散制約充足結果が生じる．クライアント／サーバ方式では，毎回という限定ながらもの基礎的な計算処理を能動的の要求と応答がネットワーク上を行き来するため，ホに実行し，移動先もそれ自身により選択し，移動する

スト間のコネクションは，常時維持しなければならな

47

第回マルチ・エージェントと協調計算ワークショップ

いのに対して，モバイルエージェント方式では，エーを構築した後，それを評価するためのシミュレーショ

ジェントが移動するときだけコネクションを確立すれン実験の条件を設定する．

ばよい．これは，電話回線でモデムを利用する場合の種々の移動方式通信や，無線を利用しているためコネクションが不安
定な携帯電話，移動体通信などの通信形態にとっては現在，モバイルエージェントを分散制約充足に導入非常に有利である．

した例はまだないので，研究の第一歩として，いつ・どのような目的で移動したらよいのかを検討する必

分散制約充足要がある．以下に，タイミングと移動の目的として考えられる基本的な移動方式を述べる．

制約充足問題（）は，離散値をとるいくつかの変数に割り当時間による移動てられる値の組合せのうち，与えられた制約をすべて一定時間，他のエージェントから何のメッセー満たす組合せを発見する探索問題である．分散制約充

ジ応答もないときに移動する．現在エージェント

足問題

は，制約充足問題の変数と制約が複数が存在しているホストが過負荷である，または何のエージェントに分散された問題とみなすことがでらかの理由でプラットフォームの状態が不具合でき，さまざまな問題が分散制約充足問題として定式化あるかもしれないと考えられるときに移動するされている．制約充足問題では，初期ため，本移動方式は，ネットワークで問題を解く状態において一つのアルゴリズムが全体の問題を見ときのロバスト性を高める効果が期待できると渡すことができるのに対し，分散制約充足問題の特徴考えられる．

は，初期状態はもちろんのこと，任意の時点において準局所最適時の移動

それぞれのエージェントは全体の状態を知らないことエージェントが準局所最適状態になったときにである．このため，各エージェントがどのような手順移動する．準局所最適の状態を抜け出すには多くで，どのような情報を交換し合えば，全体として制約のメッセージ交換が必要になる場合がある．本移を満たす解が発見できるかが問題となる．

動方式は，そのような場合，その負荷を軽減し得制約充足問題を解くアルゴリズムは，厳密解法である可能性を持つ．

る木探索アルゴリズムおよび近似解法である反復改メタレベルからの移動要求による移動善型アルゴリズムの二つに大きく分類される．前アプ リケーションに依存して，自分が求める者は整合性をとりながら部分解を拡張して探索木をエージェントに連絡をとり移動する．本移動方式

たどり完全な解を求める．後者は変数に制約を満足は，タスクとして分散制約充足だけを行う研究レしない値を割り当てた状態から制約違反を局所的にベルのエージェントシステムには付加されるも改善していくものであり，横尾，平山によって提のではない．しかし，このタスク機能を一部とし案された反復改善型分散制約充足アルゴリズム（分て包含する現実のアプ リケーションにおいては散「 メタレベル」での要求によって移動する必要が）が効果的な状態空間探索法の一つとし生ずることもあり得ると考えられる．て注目されている．

計算負荷による移動モバイルエージェント 間の分散制約充足

自分が存在しているホストマシンの負荷が所定

本章では，モバイルエージェントと分散制約充足のの値を超えたときに移動する．本移動方式では，二つの技術を結びつけてモバイルエージェント間で資源の効率的な利用が期待できると考えられる．の制約充足方式を提案する．はじめに，考えうるいく通信量による移動つかの移動方式を列挙し，次に，そのうちの一つであメッセージの累積量が所定の量を超えたときる通信量に基づく移動方式を詳細化した計算モデルに，一方のエージェントが他方のエージェントの48

第回マルチ・エージェントと協調計算ワークショップいるホストマシンへ移動する．本移動方式は，非ジェントが移動するための初期値である．直観的に，常に汎用的な単純な方法であり，通信コストの削メッセージ通信量がエージェントサイズより相対的に減が期待できると考えられる．

小さいうちは移動することによってかえって大きな通以下では，「通信量による移動」に基づく考え方で具信量の増加をまねくので，しきい値の考えうる最小の体的に計算モデルを構築し，基盤となる分散制約充足値という意味で初期値をエージェントサイズと等しアルゴリズムとして分散くした．以上の準備のもとで，エージェント がエーアルゴリズムを採用してシミュレーションを実施し，移動が通信量ジェントに与える効果について評価する．

理は以下の手順に従う．とメッセージ交換したときに実行すべき処

メッセージサイズ

通信量をしきい値とする移動方式
任意の分散制約充足アルゴリズムが与えられたとメッセージサイズする．そのアルゴリズムは，必ずエージェントが他のメッセージサイズ
もし，エージェントとメッセージ交換しながら制約充足のたならば以下の処理（）をする

めの計算を実行しているようにモデル化されているを与えると仮定する．我々は，各エージェント が現在自分のいるホストと異なるホストにいるエージェント〜

エージェントとのいるホスト へ移動する

メッセージ交換（送信，受信）する部分のプログラム

エージェントサイズ

コード に手を入れ，エージェントにこれまでの通信量の累積を把握させる．そして，それがあるしきい値を超えれば，エージェント分散制約充足アルゴリズムの処理が他のホストに移動して，その後本来の計算を続行するような計算モデルを構築したい．そのような制限の下でもさらにいくつかのバリエーションが考えられるが，本論文ではこれから最初に，しきい値を満たす前は，各エージェント間述べるような最も単純なものの一つを考察の対象とでメッセージ交換を行いながら，メッセージサイズしたい．

をエージェント間で交換するメッセージ，，に累積していく．その後，メッセージつあたり累積量がしきい値を超えたときに，エージェントは，のサイズ（ メッセージサイズ）は簡単のため固定されメッセージ交換したすべてのエージェントの中で個々ていると仮定し，それをと正規化して通信量の単のメッセージ量が最も多いエージェントのいるホス位とする．エージェントについて，トに移動する．このとき，総通信量にエージェントサ

エージェント

総メッセージ累積量

エージェントが複数の場合は，その中から非決定的に総通信量選択し移動先を決める．しきい値は移動するたびにしきい値倍にしていく．これは，データ構造の分野で配列や，ハッシュ表のサイズを動的に拡張する際にも用いられエージェントサイズ とする．エージェ

る考え方の一つとほぼ同様で，単純ながらも自然な考とそれぞれ表し，初期値の設定は，，イズを累積する．なお，メッセージ量の最大値をもつとのメッセージ累積量，えである．

ントサイズは，エージェントの大きさ（すなわち，プ

本研究では，基盤となる分散制約充足アルゴリズム

ログラムコード およびエージェントの状態を表すデー
タの量）であり，エージェントが一回移動するのにかとして分散かる通信量でもある．簡単のために，これも固定されステムを実ネットワーク上に実装するのではなく，性ていると仮定する．移動条件の初期しきい値は，エー能の事前評価を目的とし， 台のマシン上でのシミュ

49

アルゴリズムを採用するが，シ第回マルチ・エージェントと協調計算ワークショップズ

Agent 1

Agent 2で表す．

Agent 3

実験結果と考察
シミュレーション実験の結果として実験 ，実験および実験 （エージェント数がAgent 6

Agent 5Agent 4，のときの総通信量のグラフをそれぞれ図および）〜図に示す．
図

はじめに，エージェント数が十分多い実験（ 図 ，分散グラフ色塗り問題の例

図）において，比較の基準となるエージェントサイズがレーション・システムとして実現している．

（すなわち移動しないケース）のグラフの特徴を確認する．リンク数が増加していくと，ある狭シミュレーション実験

い範囲で急激に総通信量が増加し，そのピークを超えると急激に減少している．これはいわゆる「相転移」

分散制約充足問題の代表的な例題として分散グラフ色塗り問題がある．グラフ色塗り問題とは，任意のなどと呼ばれる現象としてよく知られているグラフと色数が与えられ，グラフ上の隣り合うノードの後，総通信量は緩やかに増加に転じた後，再度，緩を異なる色で塗るものである．このグラフのノードやかに減少する．

．そをエージェントとみなすことで，分散グラフ色塗り問

次に，このグラフを他の（ 移動する場合の）エー題のエージェントネットワークが得られる．色数 ，ジェントサイズのケースと比べてみる．エージェント

エージェント数 ，リンク数サイズが十分小さい場合には，リンク数にかかわらの分散グラフ色塗り問に示す．

ず，移動しない（固定した）ときの総通信量よりも移色の分散グラフ色塗り問題をランダ ムに発生さ動したときの総通信量の方が概ね削減できていること

題の例および解を図に示す条件で，がわかる．逆に，直観的にも明らかなことだが，エー通信量に関する移動のシミュレーション実験を行う．

ジェントサイズがあまりにも大きい場合は，移動するせ，メッセージサイズをとして表ことによりその移動に必要な大きな通信量が加算さ表
エージェント数

実験内容リンク数れるため，総通信量は移動しないときよりもかえって大きくなってしまう．さらに，重要なこととして，リエージェントサイズ

実験

〜

実験〜

実験〜

実験

〜

エージェントサイズの場合も，実験〜抑えられていることがわかる．これは，今回設定したンク数が（図）付近（図では付近）の最も難しい問題による通信量のピークが，いずれののケースより低く移動基準が，過大な通信量を抑制するように働くこと
実験では，リンク密度 〜によるものと考えられる．の範囲でリンクのエージェントサイズがある程度小さければ移動の本数をパラ メータとして設定し，各エージェント数）に対してリンク数を変化させていき，各効果があり，逆にある程度を超えて大きければ移動はエージェントサイズでの通信量をそれぞれ求める．リ

逆効果となることがわかった．そこで，移動が効果的ンク数ごとにでありうるようなエージェントサイズの上限を求め（〜回ずつ問題を解き，そのときの平均前てみる．エージェント数に加えてリンク数が既知とし後付近の値のところで最も難しい問題が存在するこて与えられたときは，エージェントサイズをパラメーとが知られている．便宜上，エージェントをタとして今回のような実験をして，移動しないケー移動させない（固定した）ケースをエージェントサイ

スと比較すれば上限は自明な方法で実験的に求めら値をとる．なお，この問題では，リンク密度50

第回マルチ・エージェントと協調計算ワークショップ
Agent: 30, Threshold: AgentSize×120000

Agent: 150, Threshold: AgentSize×12500000

エージェントサイズ： １０
エージェントサイズ： ７０
エージェントサイズ：３００
エージェントサイズ：∞

エージェントサイズ：１００
エージェントサイズ：５００
エージェントサイズ：９００
エージェントサイズ：∞

2000000
15000

総通信量

総通信量

1500000
10000

1000000

5000
50000000050

図100150
リンク数200250実験 （エージェント 数：0）

図2000

3000

5000

60007000）

はリンク数の上限値である．

今回の実験から求めた

エージェントサイズ：１００
エージェントサイズ：３００
エージェントサイズ：５００
エージェントサイズ：∞

4000
リンク数

実験 （エージェント 数：

ただし，Agent: 90, Threshold: AgentSize×1
4000001000の概算値の一部を表に示す．

総通信量300000

表の計算結果

200000

エージェント数

100000

00500

図1000

1500
リンク数

2000

実験 （エージェント 数：2500）

れる．しかし，分散環境においては一般にエージェン
トは問題の全体を知らないので，エージェント数のみ表は知っているとして，リンク数を知らない場合の上限からわかるように，エージェント数を固定したとき，エージェントサイズを定義してその概数を試算しておくことが興味深い．

が十分小さいときはであることから，移動が効果的であるといそのようなヒューリスティクスはあまり厳密に論じてえる．逆に， が十分大きいときはも意味が薄いので，本論文では非常に単純なものだけことから，移動は効果的でないといえる．そこで，先を以下に述べる．

ほど論じた上限として，を満たす最大のの値を採用する．その値は毎に定まることから，はじめに，エージェント数が ，エージェントサイズがのときの総通信量をリンク数で表す（図〜図の関数としてと表すことにする．表の一本一本の折れ線がその近似値を表および図から補間によって求めたに示す．のような関数の実例を表している）．そこで，表の関数との平均的な差を以下の式で定める．

51であるの近似値

第回マルチ・エージェントと協調計算ワークショップ
激に増加し，ピークに達した後急激に減少する．

Border line

その後，緩やかに増加した後に緩やかに減少する．

境界線

エージェントサイズが，上限として定義したエージェントサイズよりも十分小さいときには，移動したほうが総通
移動は効果なし

信量が概ね削減できる．逆にエージェントサイズが十分大きいときは，移動により総通信量はかえって増加する．

移動が効果的総通信量がピークとなる困難な問題に対しては，エージェントサイズがある程度大きくても総通信00306090120150

量を抑制できる．

エージェント数

図

移動の境界線

今後の課題は以下のとおりである．
分散

きわめて大まかな指針として，リンク数が未知の場合，メッセージサイズをズムの場合について検討する．としたときのエージェ

ントサイズが，エージェント数のおよそ節で示したような通信量以外の移動方法につ倍程度以内のときは，移動による通信量の削減が期待できる．
エージェントを実装するクラスファイルを各ホストにいて検討する．
つのホストに多数のエージェントが集中すると，事前に置いておくなど，実装上の工夫でこの条件をタイムが各エージェントに分配されてエージェント当りの計算スピード が減少する問満たせば，通信量の削減という理由だけで，エージェ題があるので，それを解決するモデルを考えたントを移動させる正当な理由となり得る．

い．つまり，上記のただし，エージェントサイズがこの指針より大きいときに本方式が役に立たないというわけではない．
リンク数が既知で，特に，計算量的に「難しい問題」を発生させるようなリンク数のときには，多少エーつの検討事項を踏まえた上で，複合的要因により移動を決定する方法の検討を行う．
実際のモバイルエージェント系に実装を行い，シミュレーションとの比較を行う．

ジェントサイズが大きくても，それを大きく上回るメッセージ量を削減できるので効果が大きい．また，節で述べたような種々の理由で移動そのものが効

謝辞 本研究の一部は，文部科学省科学研究費（課題番号果を発揮することもあり得る．

）の補助によって行われた．

参考文献

おわりに
本研究では，モバイルエージェント系における分散制約充足について，いつ・どのような目的でエージェントの移動が考えられるのか基本的な考察をし，その中から，総通信量を抑制する目的で移動するケースに焦点を当て，簡単な計算モデルを構成した．次に，分散制約充足アルゴリズムとして分散アルゴリズム以外の分散アルゴリアルゴリズムを仮定し，シミュレーションにより総通信量を測定した．その結果，以下のことが確認できた．
総通信量は，一般にリンク数の増加とともに急52

本位田真一 飯島正 大須賀昭彦 エージェント技術
共立出版
長尾確編著 エージェントテクノロジー最前線 共立出版
新谷虎松 大囿忠親 福田直樹 モバイルエージェ
ントの応用 マルチエージェントシステムのためのモビリティの利用 人工知能学会誌

第回マルチ・エージェントと協調計算ワークショップ

横尾真 平山勝敏の新しい展開：分散 動的 不完全人工知能学会誌平山勝敏 横尾真 分散不完全制約充足問題 人工知能学会誌

横尾真 平山勝敏 分散：反復改善型分散
制約充足アルゴリズム 情報処理学会論文誌

53