動的問題のための協調探索手法

A Cooperative Search Scheme for Dynamic Problems
北村泰彦

鄭保創

辰巳昭治 奥本隆昭3

S. Misbah Deen ySummary. The importance of building a general framework for

distributed problem solving is coming to be acknowledged. Distributed search is one of such frameworks and de ned as to nd arequired path in a given graph by cooperation of multiple agents,
each of which is able to search the graph partially. In this paper,
we propose a new cooperative search scheme for dynamic problems where costs of links are changeable during search. To copewith the dynamic character, agents cooperate with each other byexchanging cost information that they keep. When the amountof exchanged information is large, the quality of solution is improved, but on the other hand it raises communication overhead.
Therefore, it is signi cant to know how much information optimizes the performance. We developed a testbed that simulates
a communication network and applied our scheme to the routing
problem which can be viewed as a dynamic problem where thecost of a link is de ned as its communication delay. We measured
its performance according to the amount of the cost informationexchanged.

1

はじめに分散問題解決は複数のエージ ェントによる協調的な問題解決手法を研究対象としており，すでに多くの研究事例が報告されている [Bond and Gasser88, Huhns 87, Gasser and Huhns 89, DAI 91]．しかしながら従来の研究は，いくつかの例外 [Kitamura and Okumoto 91, 横尾 92] を除いて，特定のアプリケーシ ョンやシステムに基づく実験的なアプローチがほとんどで，システ
ムや解決手法の一般的な比較や評価を行うことが困難であった．したがって，
3
yYasuhiko Kitamura, Zheng Bao Chauang, Shoji Tatsumi, Takaaki Okumoto. 大阪市立大学 工学部 情報工学科

DAKE Centre, University of Keele, ENGLAND

2MACC '92

分散問題解決の定式化や汎用的な問題解決手法に関する研究に関する重要性は高まりつつあるといえる [Durfee 91, 石田 92]．
従来の人工知能研究において，問題解決は探索を基礎として定式化 [Banerji83] され，発見的知識に基づく数々の探索アルゴリズム [Pearl 84] が提案されてきたように，分散問題解決においては分散探索に関する研究がその汎用的な問題解決手法を与えるものとして重要である [石田 92]．分散型経路探索は，与えられたグラフに対して各エージ ェントは部分的にしか探索できないという前提のもとで，出発ノードから目標ノードまでの経路を複数のエージ ェントの協力によ って発見する分散探索手法の一つである．
従来の分散型経路探索アルゴリズムとして波及型探索アルゴリズム [Kitamura and Okumoto 91] がある．探索は出発ノードをもつエージ ェントから開始され，いずれかのエージ ェントが目標ノードに到達するまで，探索が他のエージ ェントに徐々に広がって (波及して) ゆく．しかし，そこで扱われている問題はグラフのリンクのコストが固定されている静的問題であ った．それに対して，本研究ではリンクのコストが探索の過程で変化するような動的問題を対象にしている．このような問題の代表的な例として通信網における経路選択問題があげられる．通信ノードとリンクが複数のエージ ェントにより分散して管理されているという前提のもとで，この問題はメ ッセージが発生したノードからそのあて先のノードまでの適切な通信経路を求めるという分散型経路探索問題と見なすことができる．また，各リンクの通信遅延をコストとしたとき，その値はリンクに流入するメ ッセージの量に応じて動的に変化するので，この問題は動的問題の一つであるといえる．
動的問題に対応するために，本研究ではエージェントがコスト情報を互いに交換し，経路探索の要求が生じたときにはその情報をコストの推測値として利用する協調的な手法を提案する．本手法では，より正確な推測値が得られればより適切な経路が得られるが，そのためには頻繁な情報交換が必要となり，そのことが逆に通信オーバヘ ッドを招くという新たな問題が生じてくる．すなわち，協調による性能向上と通信量の増加によるオーバヘ ッドはトレードオフの関係にあり，全体の性能を最適化するような協調法を明らかにすることは分散問題解決の重要な研究課題の一つである [Durfee et al. 87]．
そのために本研究では，コスト情報交換のための通信量をパラメータ によって調整する機能を付加している．すなわち，  が小さい場合には多量の通信が行われるが，推測値は正確になり，大きい場合は通信量が抑えられる．本
研究では，問題に応じてどのような  の値が適しているのかを明らかにするために，通信網における経路選択問題を対象としてシミ ュレーシ ョン実験を行 った．その結果，最適な協調戦略が存在することが明らかにな った．

2分散型経路探索問題

まず，分散型経路探索問題を定式化する．[北村 92]

A Cooperative Search Scheme for Dynamic Problems
2.1

3

グラフ

準備としてグラフに関する基本的な用語を定義しておく．
グラフ (graph)G はノード (node) の集合 N (=6 ;) と有向リンク (directedlink) の集合 L( N 2 N ) の組< N; L >で表される．本稿では N が有限である有限グラフのみを扱うことにする．また (n; n) 62 L とする．グラフ< N; L >の部分グラフとは N  N; L  L; L  N 2 N を満たす< N ; L >のことである．
あるグラフ< N; L >に対して，(ni ; nj ) 2 L であれば，nj は ni の子 (child)，ni は nj の親 (parent) と呼ぶ．節点の列 (n0 ; n1 ; . . . ; nm )(m  1) は 8k (0 k  m 0 1) : `k;k+1 (= (nk ; nk+1 )) 2 L の時に n0 から nm への経路 (path) と呼び，m を経路の長さ (length) と呼ぶ．リンクにコスト (cost) が c : L ! R(ただし R は正の実数の集合) として与えられる場合には，経路 (n0 ; n1 ; . . . ; nm )のコストは km=01 c(`k;k +1 ) で与えられる．
0P0000000

2.2

問題と解

2.3

エージ ェントの能力

問題 (problem) は 3 項組< G; ns ; ng > により与えられる．ここで G =<N; L >はグラフであり， ns ; ng 2 N はそれぞれ，出発ノード (start node)，目標ノード (goal node) と呼ばれる．問題< G; ns ; ng > に対して，ns から ng への任意の経路が解となり，解のコストはその経路のコストとして与えられる．
さて，ある解が存在したとき，そのコストよりも小さいコストをもつ解が存在しなければ，その解は最適解 (optimal solution) であるという．問題解決の過程でリンクのコストが変化しない問題を静的問題 (static problem)，変化する問題を動的問題 (dynamic problem) と呼ぶ．
分散型経路探索問題は複数のエージ ェント (agent) の協力によ って解決される．このエージ ェントの集合をコミュニテ ィ(community) と呼び，C で表す．
エージ ェントは計算プロセスであり，探索アルゴリズムの実行や他エージ ェントとのメ ッセージのやり取りが可能であるとする．
各エージ ェントは領域知識 (domain knowledge)DKa =< Na ; La >と接続
知識 (connection knowledge) CKa =< Na ; C >が利用可能であると仮定する．
(a はエージ ェント識別子を表している．) 領域知識とは，与えられた問題のグラフ G =< N; L >に対して，そのエージェントが探索可能な領域をあらわすもので，以下の条件を満たすと仮定する．

 8a 2 C : Na  N; La  Na 2 Na ; La  L. すなわち，各エージェントは問題のグラフの部分グラフが探索可能である．したがって，単一のエージ ェントによ って解経路全体が発見されない場合がある．
 N = [a C Na ; L = [a C La ．問題のグラフを構成するいかなるノード，リンクもいずれかのエージェントの領域知識に含まれる．すなわち，コ22

4MACC '92
ミュニティ内のエージェントの協力によって解経路を発見することができる．

 8a; b 2 C : a 6= b ) La \ Lb = ;. エージ ェントの領域知識内のリンクに重複がない．すなわち，非冗長なシステムである．
次に，接続知識は領域知識の関係を示すもので，ノードとエージェントの組で表される．あるノードが複数エージ ェントの領域知識に含まれているとき，そのノードのことを接続ノード (connective node) と呼ぶ．また，そのノードによ ってそれらのエージ ェントは互いに接続 (connect) しているという．接続知識に関しては以下の仮定をおく．

 8a 2 C; 8n 2 Na ; 8b 2 C 0 fag : n 2 Na \ Nb , (n; b) 2 CKa : すなわち，各エージェントの接続知識にはそのエージェントの全ての接続ノードと接続エージ ェントとの組が含まれている．

2.4 経路探索アルゴリズム
非分散の経路選択問題は古典的な問題の一つで，従来の集中型探索アルゴリズム [野下 85] を用いることにより容易に解決できる．しかし本稿で対象としている分散型経路探索問題をそのようなアルゴリズムを用いて解決するためには，リンクのコスト情報を分散して管理しているエージ ェントから中央の一台のエージ ェントに集める必要がある．集中型アルゴリズムには，中央のエージ ェントの故障が網全体に致命的であるとい った信頼性の面や，負荷と通信が一台のエージ ェントに集中するとい った効率の面から問題がある．
一方，分散型アルゴリズムとしては，従来の探索アルゴリズムを分散化した波及型探索アルゴリズム [北村 92] がある．そこでは出発ノードをもつエージ ェントから探索が開始される．エージ ェントは領域知識の範囲で探索を続け，接続ノードまで到達すると，接続知識を用いてそれから先の探索をノードが接続しているエージ ェントに依頼する．そして，いずれかのエージ ェントが目標ノードを発見すれば探索は終了する．すなわち，探索は出発ノードをもつエージ ェントから順次，他のエージ ェントに波及してゆく．問題が静的である場合，このアルゴリズムを利用して最適解も求めることは可能であり，集中型アルゴリズムと比較しても信頼性，効率の面で優 っている．しかし動的問題の場合には以下の問題がある．波及型推論アルゴリズムでは一つの経路をエージ ェントの協力によ って求めるが，リンクのコストは動的に変化するので最適経路が求められたときには，そのコストはすでに変化しているかもしれない．したが って，波及型探索アルゴリズムは動的問題には適していない．
本稿では 4章において，エージェントがリンクのコストを交換しあうことにより，動的問題に適応可能な協調探索手法について提案する．

A Cooperative Search Scheme for Dynamic Problems

5

C 12

21
C 21

C 41

C 14

C 23

C 32

C 43

43C 34

Figure 1. 通信網

3

通信網経路選択問題

通信網経路選択問題は動的な分散型経路探索問題のひとつである．通信網は通信ノードと通信リンクからなるグラフとみなすことができる．また通信リンクのコストはその混雑度を示す通信遅延として与えられる．問題はある通信ノード (出発ノード) で発生したメッセージをそのあて先のノード (目標ノード) までのできるだけコストの小さい経路 (解) を求めることである．1
エージェントは複数の通信ノードやリンクを管理することができるが，ここでは簡単のために，一つのエージ ェントは一つの通信ノードとそのノードから出ている通信リンクのみを管理すると仮定する．したが って以下の議論
では，ノードとエージ ェントを同一視する．ここで，管理とはメ ッセージのスイ ッチングと局所通信リンクの通信遅延監視を意味している．以上の前提から，長さ 2 以上の経路選択には複数のエージ ェントの協力が必要になるといえる．
例えば，Figure 1で示されるような 4 つのノードと 8 つのリンクから構成される通信網を考える．ノード 1 はリンク C12 と C14，ノード 2 はリンク
C21 と C23，ノード 3 はリンク C32 と C34，ノード 4 はリンク C41 と C43を管理しており，その通信遅延を監視している．この通信網において，ノード 1 にノード 3 宛のメ ッセージの送信要求がある場合，その経路にはノード2 を経由するものと，ノード 4 を経由するものとの二つがあり，適切な通信路選択を行うためには４つのリンク (C12,C23,C14,C43) の通信遅延を知る必要がある．ノード 1 はリンク C12 と C14 の通信遅延のみが既知であるので，リンク C23 と C43 の遅延情報をもつノード 2 と 4 との協力が必要になる．
1 この問題はリンクのコストがそのリンクを流れるメ ッセージの量に応じて変化する動的問題であり，最適解を定義することは難しい．

6MACC '92

通信網における経路選択アルゴリズムには大きく分類して，非適応 (nonadaptive) アルゴリズムと適応 (adaptive) アルゴリズムに分類される [Tanenbaum 88]．非適応アルゴリズムは通信網のトポロジーや通信遅延の変化に適応しないアルゴリズムで，静的問題のためのアルゴリズムであるといえる．それに対して，適応アルゴリズムは動的問題のためのアルゴリズムであるといえるが，それはさらに大局 (global) アルゴリズム，局所 (local) アルゴリズム，分散 (distributed) アルゴリズムに分類される．大局アルゴリズムは各ノードの情報を一台の RCC(Routing Control Center) と呼ばれる計算機に集中させ，その計算機で経路選択テーブルを作成して，各ノードに再び分散させるという手法である．この方式では RCC には網からの全ての情報が集められるので比較的正しい経路選択ができ，各ノードは経路選択のための計算をする必要がないという利点がある. 一方で，網全体の経路選択の計算は多量であり，その負荷や通信が RCC に集中し，RCC の故障が網全体に致命的であるという問題点がある．
それに対して，局所アルゴリズムはノードが自分で集めた情報のみで経路選択を行う手法である．負荷の分散や信頼性の面で大局アルゴリズムよりも優れているが，集めた情報の局所性から経路選択が不正確になるという欠点がある．分散アルゴリズムは大局アルゴリズムと局所アルゴリズムを組み合わせたもので，経路選択は局所的に行われるが，それに必要な情報はノード間で交換される．次章で提案する手法は分散アルゴリズムの一つといえるが，従来の手法は一定の時間ごとに遅延情報の交換を行なう周期的 (同期的) な交換であるのに対し，本稿で提案する手法は各リンクの通信遅延の変化に応じて情報交換を行うしきい値を用いた (非同期的な) 交換であり，通信網の状況に対してより敏感な手法であるといえる．

4動的問題のための分散型経路探索手法

本章では通信網における経路選択問題を例題として，動的問題のための分散型経路探索手法を提案する．

4.1 経路選択
本稿で提案する方法では，送るべきメ ッセージをもつノードが目標ノードまでの全経路を求めてからそれに従 ってメ ッセージを送るのではなく，隣接する接続ノードを一つだけ決定して，その接続ノードにメ ッセージを送り，接続ノードから目標ノードまでの残りの経路選択はそのノードに委ねるという手法を用いる．2 したが って，メ ッセージ転送中のリンク遅延の変化に対応することができる．
すなわち，メッセージの存在するノードを n0 ，メッセージのあて先のノードを ng ，n0 の接続ノードを n1 ; . . . ; np とすれば，メ ッセージはこのいずれか
2 これはコンピ ュータネ ットワークにおけるデータグラムサービスに対応する．

A Cooperative Search Scheme for Dynamic Problems

7のノードを経由して ng に送られる．すなわち，接続ノード nj を経由して送られる遅延を( ) = c(n0 ; n ) + c(n ; n )で定義すれば，選択すべき接続ノードは c(n ) = min1
c nj

jjkg

j p(1)( )c nj を満たす nkとなる．
さて，この手法において，よりよい経路を求めることはより適切な接続ノードを決定することと等価になる．しかし，仮定からメッセージをもつノードは接続ノードまでの遅延を正確に知ることができるが，それから先の目標ノードまでの遅延は推測値を用いなければならない．すなわち，式 (1) におc(nj ; ng ) を用いなければいて，第 1 項の値は正確であるが，第 2 項は推測値 ~ならない．そこで，本稿では推測に必要な遅延情報をノード間で交換するという手法を用いる．

4.2

遅延情報の更新

ノードは経路選択に必要な通信遅延の推測のために互いに情報を交換する．すなわち，ノード n0 において，そのノードが管理しているリンクの遅延 c(n0 ; nj )(1  j  p) に変化があ ったとき，遅延情報テーブルを更新し，他の全てのノードにその変化を通知する．この遅延情報を受け取 ったノードはその影響を自らの遅延情報テーブルに反映させる．
リンクの遅延は動的に変化するので，推測値の精度を上げるためには頻繁にノード間で情報交換を行う必要がある．ところが，このことは通信量の増加を引き起こし全体の性能を低下させてしまうという問題を抱えている．推測値の精度と通信量の増加はトレードオフの関係にあるといえるが，全体性能を最適にする通信量を求めるということが本方式における興味深い問題となる．
ここで遅延情報交換のための通信量を調整する機構を導入する．まず，リンクの遅延を知らせる時にはその値を記録しておく．(初期値は 0 である．) 次にコストを知らせるときはその変化の絶対値が 以上になったときのみに行う．
すなわち， c(n0 ; nk ) 0 c (n0 ; nk ) >  の時に他のノードに通知し，c (n0 ; nk ) =c(n0 ; nk ) とする．この  の値を変化させることにより，通信量を変化させることができる．すなわち，  を小さくすれば多くのメ ッセージが送られ，推測値の精度は高くなる．反対に を大きくすれば推測値の精度は低くなるが，通信量は減少する．
050

シミ ュレーシ ョン実験

シミ ュレーシ ョン実験を Figure 1に示す通信網モデルに基づき行 った．それ
ぞれの通信リンクは一本の待ち行列と見なしている．すなわち，リンクに流入するメッセージは待ち行列に入れられ， 1 単位時間ごとに他方のノードに送られる．このモデルにより，待ち行列内のメ ッセージ数によりそのリンクの通信遅延が表される．

8MACC '92

メ ッセージはノード 1,2,4 において発生し，全てノード 3 宛であるとする．ノード 3 はメ ッセージを受け取ると，確認メ ッセージを送り返す．ノード 2 と 4 で発生したメ ッセージは固定的にそれぞれ，リンク C23 と C43 を経由してノード 3 に送られるが，ノード 1 で発生するメ ッセージにはリンク
C12,C23 と C14,C43 を経由する二つの経路が存在し，経路選択を行う必要がある．すなわち，d(C 12) + d(C 23) < d(C 14) + d(C 43) であれば C12 を，d(C 12) + d(C 23) > d(C 14) + d(C 43) であれば C14 を，d(C 12) + d(C 23) =d(C 14) + d(C 43) であれば等確率で C12 あるいは C14 のいずれかを選択する．(d(C ) はリンク C の通信遅延あるいはその推測値を表している．) ノー
ド 3 からノード 1 への確認メ ッセージの転送も同様に経路選択が行われる．
ノード 1,2,4 で発生するメッセージはポアソン過程 [野口 82] に従い，その発生率をそれぞれ g1 ; g2 ; g4 とする3 ．また，ノード 2 と 4 の発生率は式 (2) を用いて変化させている． ここで t は現在時刻を表す．

+ P2 sin(!t + )(2)
リンクの遅延情報はノード 2,4 からノード 1,3 にパラメータ にしたがって制御メ ッセージによ って送られる．すなわち，ノード 2 と 4 はそれぞれ，リンク C23 と C43 の遅延情報をノード 1 に，リンク C21 と C41 の通信遅延をノード 3 に送る．
P1

パラメータ にしたがって，経路選択の性能がどのように変化するかを見るために実験を行った．発生率はそれぞれ，g1 = 0:5，g2 = 0:5+0:45 sin(2t=1000)，
g4 = 0:5 + 0:45 sin(2t=1000 +  ) とした．したが って，ノード 2 と 3，ノード 4 と 3 の間の通信は 1000 単位時間の周期ごとに混雑が繰り返されることになり，その位相は逆になる．したが って，ノード 1 と 3 の間のメ ッセージ
送信はノード 2 と 4 でのメ ッセージ発生に応じてリンクの切り替えをしなければ適切な経路選択ができなくなる．
まず，比較のために通信路 2 と 4 からの遅延情報の転送に全く通信遅延がかからないという理想的な場合についてシミ ュレーシ ョンを行 ってみた．このことにより，遅延情報転送のための通信オーバヘッドを無視して， の値に応じて性能がどのように変化するかを見ることができる．性能の評価値としてはノード 1 からのメ ッセージの送信に対して確認のメ ッセージが戻 ってくるまでの通信遅れを用い，本シミ ュレーシ ョンでは 100,000 個のメ ッセージの平均値を用いた．すなわちこの値が小さいほどよい経路選択が行われていることがわかる．その結果を Figure 2(exclusive) に示す．傾向として が大きくなるにつれ，性能が低下していることがわかる．
次に遅延情報の転送に通信オーバヘッドが存在する場合，すなわち通常のメ ッセージと遅延情報を知らせる制御メ ッセージを同一のリンクを用いて転送した場合のシミ ュレーシ ョン結果を Figure 2(inclusive) に示す．この場合は が小さい時には通信オーバヘッドが大きくなり，性能の低下を引き起こし13 発生率を g とすれば，メ ッセージの発生間隔は平均 =g 単位時間の指数分布にしたがう．

A Cooperative Search Scheme for Dynamic Problems

9Delay
6.2

6.0

5.8

5.6

5.4
inclusive
exclusive
5.2

δ

5.00102030

Figure 2. シミ ュレーシ ョン結果ている．また，  が大きい時は通信遅延の推測値の精度が悪化し，不適切な経路選択が行われるようになるので，同じく性能の低下が見られる．また，が大きくなると，制御メ ッセージの通信量が減るので，理想的な場合との差が小さくなってゆく．このシミュレーションにおいては = 5 が最適という結果が出ている．

6

まとめ

通信網における経路選択問題を例題として，動的問題のための分散経路探索手法について述べた．本手法では各ノードで行われる経路選択を接続ノードまでにとどめ，それから先の経路選択を接続ノードに委ねることにより，リンクのコストの動的変化に対応している．また，接続ノードを適切に選択するために，リンクのコスト変化をノード間で交換し，それを推測値として用いている．したが って，適切な経路選択を行うためには推測値を正確に保つ必要があり，そのためにエージ ェント間で多くの通信が必要になる．しかしこのことは通信オーバヘ ッドを招き，全体の性能を低下させるというトレードオフの関係が成り立つことがわかる．そこで，本研究ではパラメータ によ10MACC '92

り通信量を制御する機構を導入し，全体の性能を最適にする通信量が存在することをシミ ュレーシ ョン実験を通して明らかにした．
今後の課題としては以下のものが挙げられる．

 一般的な評価 ：シミュレーション実験により，ある特定の問題に対して全体の性能を最適にする通信量が存在することが明らかになった．この値はネットワークの形状，メッセージの発生率，混雑の周期などに大きく依存すると思われる．一般の場合においてこの値をいかにして求めるかが今後の課題となる．
 パラメータ の自動調整 ：メ ッセージの発生率や混雑の周期などは動的に変化することが予想される．したがって，全体の性能を最適にするよ
うに の値をエージ ェント自身が自律的に調整するような機構が必要になる．
 大規模ネットワークへの応用 ：今回のシミュレーションでは小規模のネットワークを対象に実験を行ったが，提案した手法を大規模なネットワー
クに対して適用すれば，大量の制御メッセージが発生することが予想され，それを抑える仕組みが必要になる．例えば，ノード間の経路が長い場合には細かな遅延情報の変化を知らせたところで，その情報が到着した時点では役に立たない可能性が大きくなる．従って，ノード間の経路の長さに応じて の値を大きくするような手法が考えられる．
謝辞 本論文に関して貴重なご意見を頂いた第 2 回 MACC ワークシ ョップ参
加者の皆様，特に慶応大学理工学部所真理雄先生に感謝いたします．

参考文献[Banerji 83] Ranan B. Banerji.

人工知能. 共立出版, 1983.

[Bond and Gasser 88] Alan H. Bond and Les Gasser, editors.

tributed Arti cial Intelligence.

Readings in Dis-Morgan Kaufman Publishers, Inc., San Mateo,

California, 1988.

[DAI 91] Special section on distributed art cial intelligence.

on System, Man, and Cybernetics

IEEE Transactions, Vol. 21, No. 6, November/December 1991.

[Durfee 91] Edmund H. Durfee. The distributed arti cial intelligence melting pot.

IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, No. 6, pp.1301{1306, November/December 1991.

et al.
on Computers[Durfee87] Edmund H. Durfee, Victor R. Lesser, and Daniel D. Corkill. Co-herent cooperation among communicating problem solvers.

IEEE Transactions, Vol. C-36, No. 11, pp.1275{1291, November 1987.

[Gasser and Huhns 89] Les Gasser and Michael N. Huhns, editors.

Arti cial Intelligence, Volume II
California, 1989.

Distributed. Morgan Kaufman Publishers, Inc., San Mateo,

A Cooperative Search Scheme for Dynamic Problems[Huhns 87] Michael N. Huhns, editor.

Distributed Arti cial Intelligence

11. MorganKaufman Publishers, Inc., Los Altos, California, 1987.
[Kitamura and Okumoto 91] Yasuhiko Kitamura and Takaaki Okumoto. Di

using

inference: An inference method for distributed problem solving. In S. M. Deen,editor,1991.

Cooperating Knowledge Based Systems 1990

[Pearl 84] Judea Pearl.

Heuristics. Addison-Wesley, 1984.

[Tanenbaum 88] Andrew S. Tanenbaum.
[, pp. 79{94. Springer-Verlag,

Computer Networks. Prentice-Hall, 1988.

横尾 92] 横尾真, エドモンド H. ダーフィ, 石田亨, 桑原和宏. 分散充足制約による分散協調問題解決の定式化とその解法. 電子情報通信学会論文誌 D-I, Vol. J75-D-I,No. 8, pp.704{713, 1992.

[石田 92] 石田亨, 桑原和宏. 分散人工知能 (1):協調問題解決. 人工知能学会誌, Vol. 7,No. 6, pp.945{954, 1992.

[北村 92] 北村泰彦, 辰巳昭治, 奥本隆昭. 状態空間表現による分散型問題解決の定式化. 電子情報通信学会人工知能と知識工学研究会, AI92-48, 1992.

[野下 85] 野下浩平, 高岡忠雄, 町田元. 基本的算法. 岩波書店, 1985.

[野口 82] 野口正一, 木村英俊, 大庭弘太郎. 情報ネットワークの理論. 岩波書店, 1982.