波及型探索における通信制御法とその評価

Communication Control Schemes for Di using Search and TheirEvaluation
北村 泰彦3 寺西 憲一y 辰巳 昭治z 奥本 隆昭xSummary. Di using search is a distributed search scheme for distributed problem solving. An advantage of this scheme is to gain
speedup by making multiple agents share the load. As the search spreads
over agents, however, the communication overhead among agents increases. In this paper, we discuss how to control the communication tobalance the speedup with the communication overhead. We propose local and global control schemes, and evaluate them through simulations
on a distributed maze problem.

1

はじめに疎結合，複数のエージェントによる分散問題解決を分散探索ととらえて定式化しようとする試みがある [7] [10]．分散探索では複数のエージェントが協力することによって，単一のエージェントだけでは探索不可能な探索空間から解経路を発見することが目的となる．このような分散探索の研究においては以下の点が課題となる．
並列性の向上 どのように複数のエージェントが探索を分担すればより速く解を発見することができるか．
通信量の削減 分散問題解決においてエージェントは疎結合であり，通信コストは無視できない．いかにしてエージェント間の通信オーバヘッドを減少させればよいか．
計算量の削減 どのような情報をエージェントが交換すれば，個別のエージェントの計算量（探索量）を削減できるか．
解の質の向上 探索手法によっては必ずしも最適解が保証されないものもある．解がより最適解に近づくようにするにはどのようにすればよいか．
並列性の向上はこれまで並列探索の分野 [11] [12] において主に研究が進められているが，分散探索においても同様に重要である．通信量の削減は分散問題解決にお3

Yasuhiko Kitamura,

大阪市立大学 工学部

y Ken-ich Teranishi, 大阪市立大学 工学部
zx

Shoji Tatsumi,

大阪市立大学 工学部

Takaaki Okumoto,大阪市立大学 工学部

2

MACC '93

いて特に重要な課題であり，Lesser らの FA/C モデル [9] の動機の一つにもなっており，Durfee らの Partial Global Planning [1] においても考慮すべき要因の一つとなっている．ヒューリスティック探索において計算量の削減と解の質の向上はトレード オフの関係にあり，マルチエージェントの立場からこの問題に言及した研究としては Knight によるもの [3] があげられる．
分散探索手法は問題の性質やエージェントの組織，またエージェントをとりまく環境に依存すると考えられるが，本研究では波及型探索 [4] を取り上げる．波及型探
索は探索空間が各エージェントに分散して存在しているという前提のもとで，初期問題を持つエージェントから他のエージェントに徐々に探索範囲を波及させてゆくことによって大局解を求める系統的な分散探索手法の一つである．この手法は問題分割の方法があらかじめ与えられていないような場合でも利用可能であり，探索を各エージェントが分担して行うことにより並列性が向上する [7] [4]．しかしながら，波及型探索においては探索が他のエージェントに波及してゆくにつれ，エージェント間の通信オーバヘッドが急速に増加するという問題点があった [6]．そこで本論文
では波及型探索を対象として，分散探索における通信量削減の問題について考察し，その通信制御法を提案する．

2 分散問題解決における通信制御
従来の分散システムにおける通信と分散問題解決における通信との間には性質上の違いがある．前者の場合，その全てのメッセージがノード間で正しく転送されることが前提となっており，われわれはこのような通信を決定的通信と呼んでいる．
それに対して後者の場合は，必ずしも全ての通信要求が満たされなくても問題解決を行うことができる場合のある非決定的通信であるといえる．
分散探索を例に非決定的通信の説明してみよう．あるエージェントがある状態を展開して，OR 分岐となる n 個の子状態が得られたが，いずれの子状態に関してもそれ以上の探索が不可能で他のエージェントに依頼しなければならない状況を考える．このとき n 個すべての子状態に対して探索依頼を行えば，それから先の探索は並列に実行されることになるが，この探索依頼のためには n 個の探索依頼メッセージが必要になる．一方で単一の解を求めることが目的ならば，必ずしも n 個全ての子状態に対して探索依頼メッセージを送る必要がないかもしれない．
（ 最悪の場合はn 個全てが必要になる．）この場合は通信オーバヘッド が軽減される．このように通信要求の全てを満たす必要のない非決定的通信の場合は通信網の混雑状況に応じて，そのメリット (探索の並列性) とデ メリット ( 通信オーバヘッド ) を考慮して，適切な通信量調整を行う必要がある．

Communication Control Schemes for Di

using Search and Their Evaluation3

これまでも分散問題解決においては通信オーバヘッドを考慮した協調手法に関する研究が行われてきた．例えば，階層的な問題解決を行う FA/C モデル [9] ではエージェント間の通信量を少なくするために，下位レベルでの情報交換を避け，情報の抽象度を上げて上位レベルでの情報交換を行うようにしている．しかし FA/C モデ
ルにおける通信量削減の手法はシステム設計時に決定された固定的なものであったので，エージェントを取り巻く環境の変化に対しても動的に対応可能な手法として，

Partial Global Planning[1]

では通信オーバヘッドを考慮したエージェントの問題解決行動計画を立案するようにしている．しかしながらこれらの手法は以下の 2 つの点において問題がある．まず，通信制御はエージェントの推論過程を経て決定されるので，通信網の状況が即座に反映されにくく，通信路の混雑状況に敏感な通信制御が行われにくい．また，通信制御は局所的な推論に基づいているので，大局的には必ずしも適切な制御ができるとは限らない．このような局所制御の問題点は本稿のなかでも議論されている．
本研究においては従来の分散問題解決で行われてきた推論に基づく通信制御と，従来の分散システムで行われてきた通信網レベルでの通信制御 [6] の中間段階における通信制御を議論の対象にしている．このような中間段階をおくことによって，通信網の混雑状況を反映した，より敏感な通信制御が行えるという利点がある．本論
文で分散探索の一手法である波及型探索を対象にその通信制御手法を提案し，その評価をおこなっている．

3 波及型探索における通信制御

3.1

波及型探索

波及型探索は問題が状態空間グラフとして与えられ，その部分グラフ（探索可能領域）が複数のエージェントに分散して存在するときに，エージェントの協力により初期状態から目標状態までの解経路を系統的に求める分散探索手法である [4] [5]．
前提として，状態空間グラフのいずれの部分もシステムを構成するいずれかのエージェントの探索可能領域に含まれるとする．また，複数のエージェントの探索可能領域に含まれる状態のことを接続状態と呼び，各エージェントはどのエージェントと接続状態を共有しているか既知であるとする．
波及型探索は初期状態を探索可能領域に含むエージェントに探索依頼メッセージが送られることにより開始される．
（ 目標状態は全エージェントで既知と仮定する．
）
探索依頼メッセージを受け取ったエージェントはその初期状態がまだ発見されたものでなければ開状態に加える．各エージェントは開状態集合が空でない間，探索戦略に従って探索を探索可能領域内で進める．接続状態を発見すれば，それから先の4

MACC '93

探索を探索依頼メッセージを用いてその状態を共有しているエージェントに依頼する．そして，いずれかのエージェントが目標状態を発見すると探索は終了である．
波及型探索では探索が初期状態を探索可能領域に持つエージェントから他のエージェントへと徐々に波及してゆき，並行して探索が行われることにより探索の並列性が向上する．一方で探索が多数のエージェントに波及するにつれ，探索依頼のためのメッセージが増加し，通信オーバヘッド が大きくなる [4]．そこでエージェント間の通信を制限する通信制御法が必要になる．

3.2 通信制御手法
波及型探索においては各エージェントは探索が接続状態まで到達すると探索依頼メッセージを発生する．探索が多数のエージェントに広がると多数の探索依頼メッセージが通信路に集中し，このことが通信オーバヘッドを大きくする原因となっている．本研究における通信制御はエージェント内において通信路に流入する以前の段階で行われる．すなわちエージェントで発生する探索依頼メッセージを一旦，通信バッファに入れ，選択的に通信路に送るようにする．ここでの通信制御手法はその選択基準に応じて局所的手法と大局的手法の二つに区分される．局所的手法ではエージェントの局所情報のみに基づき，並行して送られる探索依頼メッセージの上限数を制限する手法である．また大局的手法ではトークンを用いることにより，システム全体で並行して送られる探索依頼メッセージの総数を制限する手法である．

3.2.1

局所的手法

局所的手法ではエージェント毎に並行探索依頼数の上限を導入する．これにはその上限を固定する静的な方法と通信路の混雑に応じて変化させる動的な方法の二つがある．ここで並行探索依頼数とはエージェントが送出した探索依頼のメッセージ数から探索終了のメッセージ数を引いたものである．すなわちその時点で処理中の探索依頼数で，RQ C で表すことにする．
静的手法はエージェント毎にこのカウンタの値が設定値 rq max を越えないようにすることである．そこで探索依頼メッセージが発生すると，一旦通信バッファに入れ， RQ C

 rq max が成り立つときのみそのメッセージを通信路に送り出す．

次に動的手法は，上限数 rq max を通信路の混雑状況に応じて各エージェントで自動的に調整する手法である．すなわち，通信路が混雑している場合は上限数を抑え，空いている場合は上限数を上げるようにする．このために通信路の混雑を観測する必要があるが，その尺度としてメッセージが送られときに，それに対応する ACKメッセージが返ってくるまでのターンアラウンド タイムを用いることにする．

Communication Control Schemes for Di

3.2.2

using Search and Their Evaluation

5

大局的手法

大局的手法はシステム全体の並行探索依頼の総数を制限する手法である．分散的にこれを実現するためには何らかの工夫が必要であるが，本研究ではこれを実現するために探索依頼を許可するトークンを用い，並行探索依頼総数の上限数と同数のトークンをコミュニティ内に分配することにより大局的な通信制御を行っている．
最初全てのトークンは波及型探索を開始するエージェントに集められており，波及型探索が広がるにつれトークンも他のエージェントに分配してゆく．トークンの分 1) を用い，依頼するエージェントのトークン保有数を N token としたとき， dd 1 N tokene 個のトークンを配にあたっては分配率と呼ばれるパラメータ d(0 < d

探索依頼メッセージとともに分配することにする．したがって d が大きい場合には多くのトークンが探索の前線に送られることになる．
このトークンの導入により，並列探索依頼の総数を大局的制御が可能になったが，トークンをいかにして適切なエージェントに分散させるかということが新たな課題となる．すなわち，基本的にトークンは探索前線のエージェントに分配されてゆくが，分配率をどの程度にすればよいのかが課題となる．あまり速く探索前線のエージェントにトークンを分配してしまうと，前線での探索が失敗した場合に，トークンを一旦後方のエージェントに戻して新たな探索依頼を補給してもらう必要があり，トークンの後戻りのためのオーバヘッド が大きくなる．また逆に，トークンの分配が遅すぎると，後方で必要数以上のトークンが留まり，探索の前進が妨げられることになる．すなわち，トークンの分配に関しては探索の前進と探索依頼の補給の間でうまくバランスとる必要があり，これらの点を次節において評価する．

4

評価と考察
本章ではこれまでに述べた通信制御手法を迷路探索問題 [2] [6] を用いて評価を行う．評価には 120

2 120 の格子状迷路を用い，64 台のエージェントに格子状に分割され，入口から出口までの経路を波及型探索を用いて求めている．ここで障害率とは迷路中で通過不可能な障害物の存在率を表している．
エージェント間の通信路は 1 本のキューでモデル化されている．キューが空でない場合は，通信コストパラメータ C-Cost により定められる時間毎にメッセージが取り出され，あて先のエージェントに渡される．ただし，エージェントが探索において一つの状態の展開に要する時間を一律に 1 単位時間としている．従って，このモデルにおいては，一定時間内にエージェントで送信されるメッセージ数が増えると，キューが長くなり，メッセージの通信遅延は大きくなる．

6

MACC '93

4.1

局所的手法

まず，各エージェントの並行依頼数の上限 rq max を 1,2,4,8, 無限大 (inf) に変化させた場合の探索時間 S-Time(障害率 30% ，エージェント数 64) を図 1 に示す．一般に，並行依頼数の上限を大きくすると，それだけ探索が多くのエージェントに分散し，並列的に探索が進むが，その反面，通信量が増加する．この結果からもわかるように，通信コストが小さい間は上限数の多いものが優っているが，大きくなるにつれ上限数の少ないものの性能が優るようになる．
次に上限値を自動調整する場合の結果を同じく図 1(auto) に示す．その結果，通信コストが小さい場合は良い性能が得られたが，通信コストが大きくなるとそれほどの性能が得られない．この理由は通信路の混雑の少ないで探索初期の時点で，探索が多数のエージェントに広がってしまい，個別のエージェントあたりの上限数は抑えられていても，全体として多量の通信が行われるからであり，ここに局所的手法の問題点と総量規制の必要性が明らかになっている．

1500

800

700
1200

S-TimeS-Time600
900

rq_max1

Number of tokens

500

52

10460025400

8300
0.04.20.2

0.40.60.850inf

100

auto

auto
1.03000.00.1

0.20.30.4

0.5

0.6

0.7

C-CostC-Cost図1 局所的手法の性能

図2 大局的手法の性能（トークン数の変化）

大局的手法

実験では局所的手法と大局的手法を併用した．すなわちエージェントは RQ C

0.8

rq max， RQ C  N token の両方を満たすときに探索依頼を行える． まず最初にトークン数を変化させたもの (障害率 30% ，分配率 50%) を図 2 に示す．局所的手法 (auto) との比較において，十分な数のトークンを分散させれば大局的手法が優っており，通信コストが大きい場合にその差は顕著である．一般に，局所的手法の上限数の変化と同様に通信コストが小さい場合はトークン数を多くし，大きい場合にCommunication Control Schemes for Di

using Search and Their Evaluation7

トークン数を少なくすればよい結果が得られている．
つぎにトークンの分配率を変化させたもの (障害率 30% ，トークン数 50) を図 3に示す．分配率に関しては通信コストが低い場合，トレード オフの関係が成り立ち，分配率が大きすぎても，小さすぎてもよい性能が得られない．これは分配率が大きすぎると探索は速く波及するが，広く波及しないので並列性が低く，性能が向上しない．逆に小さすぎると探索の波及が遅くなってしまうからだと予想される．また，通信コストが大きい場合には探索があまり広がらないように分配率を高くするとよい性能が得られる．
最後に障害率を変化させた場合 (トークン数 50 ，通信コスト 0.2) の分配率 (D-Rate) の効果を図 4 に示す．障害率が高いとそれだけ探索後戻りの回数が多くなり，多くのトークンを前線に進めてしまうことは得策ではない．したがって，障害率が高い場合には分配率を小さめにしたほうがよい結果がでている．

400

2300

Minimum point
2000
380
1700

1400

340

S-TimeS-Time360

Distribution rate

Obstacle rate
25%
1100

30%
35%

10%
800

30%

40%50%

320

70%

50090%
300
0.050.1

0.2

0.3

0.4

200
0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

C-CostD-Rate

図3 大局的手法の性能（分配率の変化）

図4 大局的手法の性能（障害率の変化）

1.0

まとめ
本稿では分散問題解決における通信制御の問題を取り上げ，通信要求に非決定的な性質を持つ波及型探索のための通信制御法の提案と評価を示した．本手法はエー
ジェントにおけるメッセージの発生自体を制御するのではなく，発生したメッセー
ジを一旦通信バッファに取り込み，選択的に通信路に送り出すことにより通信制御を行っている．このことにより従来の推論に基づく制御に比べて，通信路の状況により敏感な制御をおこなうことができる．
通信制御法としては局所的，大局的の二つのものを提案し，迷路探索問題のシミュレーション実験を通してその評価を行った．局所的手法はそれぞれのエージェントが

8MACC '93

自律的に通信の調整を行うものであるが，一旦探索が多数のエージェントに広がると十分な効果が出ないことが明らかになった．そこで総量規制の手法として，トークンを用いることにより分散的な大局的制御手法を提案し，通信コストが大きい通信路においても十分な効果が得られることを明らかにした．
本稿における大局的手法において，トークンの分配は分配率により規定された一定の割合でおこなわれているが，今後は交渉 [8] などの手法を導入することにより，より適切なエージェントへの分配が重要な課題となる．また，局所的手法においては通信路の状態に応じて上限数を自動調整する手法を提案したが，ターンアラウン
ド タイムとの関係はアドホックな手法を用いている．そこでこれらの調整に学習機能を含めることも有用であると考えられ，これも今後の課題としたい．
参考文献
[ 1 ]

Edmund H. Durfee and Victor R. Lesser. Partial global planning: A coordination frame-work for distributed hypothesis formation.

IEEE Transactions on Systems, Man, and Cyber-netics, Vol. 21, No. 5, pp. 1167{1183, September/October 1991.
[ 2 ]Toru Ishida and Richard E. Korf.

Moving target search.

InProceedings of the 1991

International Joint Conference on Arti cial Intelligence, pp. 204{210, 1991.
[ 3 ]Kevin Knight.

Are many reactive agents better than a few deliberative ones?

InPro-ceedings of the 1993 International Joint Conference on Arti cial Intelligence, pp. 432{437,1993.
[ 4 ]Yasuhiko Kitamura and Takaaki Okumoto. Di

distributed problem solving.

using inference: An inference method forIn S. M. Deen, editor,

Cooperating Knowledge Based Systems

1990, pp. 79{94. Springer-Verlag, 1991.

北村泰彦, 辰巳昭治, 奥本隆昭. 状態空間表現による分散型問題解決の定式化. 電子情報通信学
会人工知能と知識工学研究会, AI92-48, 1992.
[ 6 ] 北村泰彦, 寺西憲一, 辰巳昭治, 奥本隆昭. 分散探索における通信制御. 情報処理学会学会人工知能研究会, 89-5, 1993.
[ 7 ] 北村泰彦, 小川均. 分散探索に基づく分散問題解決モデル. 計測と制御, Vol. 33, No. 1, pp.
[ 5 ]21{26, 1994.
[ 8 ]桑原和宏, 石田亨. 分散人工知能 (2):交渉と均衡化. 人工知能学会誌, Vol. 8, No. 1, pp. 17{25,1993.
[ 9 ]Victor R. Lesser and Daniel D. Corkill.

Functionally accurate, cooperative distributedsystems. IEEE Transactions on System, Man an Cybernetics, Vol. SMC-11, No. 1, pp. 81{96,January 1981.
[ 10 ]

Victor R. Lesser.

An overview of DAI: Viewing distributed AI as distributed search.

Journal of Japanese Society for Arti cial Intelligence, Vol. 5, No. 4, pp. 392{400, 1983.
[ 11 ]

Curt Powley and Richard E. Korf. Single-agent parallel window search.

IEEE Transac-tions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 5, pp. 466{477, 1991.
[ 12 ]

V. Nageshwara Rao and Vipin Kumar. Parallel depth

rst search. part I. Implementation.

International Journal of Parallel Programming, Vol. 16, No. 6, pp. 479{499, 1987.