38

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 2
c から回答が来なければ, 処理を進めることはできな
4. 処理中断集合が空集合となっているものを選択
い. しかし, ここでエージェント a が \多くの契約者して, 計算を続ける.
4 では, 処理中断集合が空集合の計算プロセスを選択
はオプションを付けない" ということを知っていれば,b からの回答を待たずに先行的に準備を進めることがしている. これは, 処理中断集合が空集合であるものできる.
は, デフォルトの仮回答または実際の回答と矛盾して同様にエージェント b が \契約者 c は, 多くの場合おらず, 処理を進めても成功する可能性が高いと思わオプションを付ける" ということを知っていれば, 事れるからである.
本論文では, 他エージェントからの回答を待ってい前にエージェント a に対してそのこと報告をすることができ, a はその報告を受けて準備の修正を行なう.
るリテラルを集合として保存している. これにより,もしその後, c から \オプションをつけない" という回
他のエージェントからの回答が変化する場合に投機的答を b が受け取れば, b は a に対して先程の報告を訂計算の導入を行うことができる.
正し, さらに a は再度修正を行なう.
2 投機的計算導入の実現
この場合, エージェント a と b がそれぞれ投機的計以下では, 他エージェントからの回答が変化する場算を行なっている. もし回答が変化する場合に対応できなければ, エージェント b が先行的に出した回答を合に投機的計算を導入するための準備を行う．
エージェント a に送ることは危険性が高い. なぜなら
枠組
ば, エージェント b が出した回答は, 投機的計算の性質上, 保証されていないからである.
ここでは, 投機的計算の枠組の定義を述べる.
第2.1

定義 1

回答が変化する場合に対応するための手法の概略,.
1. 各エージェントは事前に質問に対するデフォルトの仮回答を用意する.
2. 各エージェントは, 用意した仮回答をもとに以降の処理を進める.

,,Q を負リテ, は「失敗による否定」を表す.Qをリテラルとしたときに, Q = Q と定義する.
Q を原子式としたとき Q を正リテラルは 以下のようになる.

ラルとする ここで

定義 2
n 個のエージェントからなるマルチエージェントにお,hI ; Si である. ここ, I は, エージェントの識別子の列 ha1; :::; an i であり, S は, エージェントでの個別投機的計算の枠組の列 hSa1 ; :::; San i を表し以下のように定義される.
各エージェントでの個別投機的計算の枠組 S は, h6, E , 1, Pi の４つ組であり, それぞれは以下の通りとする.
 6 : 定数の有限集合.6 の要素をエージェント識別子と呼ぶ.
 E : 外部述語と呼ばれる述語の集合.Q が外部述語を持つリテラルで,S がエージェント識別子のとき,Q@S を質問リテラルと呼ぶ. (Q@S ) を(Q)@S と定義する.
 1 : 以下の条件を満たす質問リテラルの基礎式
全ての外部述語 p を用いた基礎原子式 p(t1 ; :::; tn )と 全 て の エ ー ジェン ト S に 対 し て,1 に は

 もしデフォルトの仮回答を使って計算を進,められるならば そのまま続ける

ける投機的計算の枠組は ２つ組.

で

 またはデフォルトの仮回答とは矛盾する回答を使わなければ計算を進められなければ,,その矛盾する回答の集合を覚えておき 計算,.

は中断し 他の計算プロセスの処理を始める(ここで, この集合を処理中断集合と呼ぶ.)
3. 計算中に回答が返されたならば,(a) 現在計算中および中断されている全ての計算プロセスをチェックし, その中に回答と矛盾する仮定を使用しているものがあれば,その仮定を処理中断集合に移す.
(b) 処理が中断されている全ての計算プロセスの処理中断集合をチェックし, その中に回答と一致するものが含まれていれば, それを回答待ち集合から削除する.

39

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 3
準備p(t1 ; :::; tn )@S または (p(t1 ; :::; tn )@S ) のいず
れかが含まれているものとする. 1 をデフォルト
投機的計算の実行は, 以下の二つの過程からなる.
一つはプロセス簡約過程であり, もう一つは回答到着回答集合と呼ぶ.
 P : 一般論理プログラム過程である.
プロセスは,(a) その計算を開始, または継続するかを判定する為の集合,(b) 計算の現在の状態,(c) そのプ
質問リテラル Q@S は, 以下の二つの意味を持っている.
ロセスで既につかわれたデフォルト ,(d) 最初に与えら
1. P のルール中の質問リテラル Q@S は,6 中の れた質問の変数に対する解代入,(e) 回答を返す相手,の 5 つの状態からなる.
エージェント S に対して行なう質問を表す.
2. 1 におけ る質問 リテラルは, 外部エージェン
一つの質問に対する証明を行うために, 一つのプロ
ト S への質問に対するデ フォルト の仮回答をセスリストが作成される. プロセスは, 場合分けのよ表す. もし,p(t1 ; :::; tn )@S 2 1S ならば, 質問うな選択肢がある場合に分岐し, 各プロセスは, おのp(t1 ; :::; tn ) に対する S のデフォルトの仮回答はおの別な分岐計算を表す. プロセス簡約過程では, 計yes であり,(p(t1; ::; tn))@S 2 1S ならば, 質 算を開始, または継続すると判定されたプロセスを新問 p(t1 ; :::; tn ) に対する S のデフォルトの仮回たなプロセスに変換する. プロセス簡約過程とは, 各答は yes である.
エージェントにおける通常のプログラムの処理に相当
先程の保険契約の例題をこの枠組を使用して表すと,するものである.
以下のようになる.
一方, 回答到着過程は, 他エージェントからの回答
枠組: h h a; b i, h Sa ; Sb i iが来たときの割り込み処理に相当するものである. 本Sa
論文と [1] [2] との差異は, 回答到着過程の手法の違い
 6a = fbg
である.[1] [2] では, エージェントからの返答を待って
 E a = fop cg
いる中断リテラルが 1 個だけであるのに対して, 本論 1a = fop c@bg
文では, 中断リテラルを集合としてプロセス中に保存
 P a:するという形にしている. そして, 中断リテラルの集
prepare(P )plan(P ):合が空集合ならば, そのプロセスは, 他エージェントから送られた実際の回答, もしくはまだ回答が返されplan(1)op c@b:ていないならば, 事前に準備した仮回答と矛盾していplan(2)op c@b:ないということになる. よって, そのプロセスを実行可能プロセスとし, また, そうでないときはプロセスSbを実行中断プロセスとしている.
 6b = fcg
定義 E b = fopg
プロセスは 5 つ組 hSGS; GS; AD; AN S; IDi とする.
 1b = fop@cg
ここで,
 Pb:
 SGS :他エージェント からの回答を待っている
op@c:
op c
GS 内の質問リテラルの集合. 処理中断集合と呼ぶ.
1a は,\契約者はオプションをつけない" という仮定
 GS :拡張リテラルの集合. ゴール列と呼ぶ.
 AD:質問リテラルの集合. 仮定デフォルトと呼ぶ.に, 1b は \契約者 c はオプションをつける" という仮
 AN S :初期ゴールにおける変数に対する解代入,定に相当する.
または他エージェントから送られた質問リテラル.
第2.200340

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 4リストの処理とは独立に行なわれる.
 ID:送信エージェント識別子.
SGS とは, 真偽値の値がデフォルトまたは実際に他既質問集合 AAQ 及び既回答集合 RF は, 各エーエージェントから来た回答の値と異なる質問リテラル
ジェント に対して各々ひとつずつ作成される. あるエージェントにおいて, 複数のプロセスリストが作成を格納する集合となる. この集合が空集合ならば, そのプロセスは現時点では仮定したデフォルト , またはされた場合でも, 各々のプロセスリストから同じ AAQを参照することにより, 質問の重複を避けることが可実際に来た回答とも矛盾していない. そのため, そのプロセスは成功する可能性が高く, 効果があると考え能となる.
られるのでそのプロセスの計算を開始, または継続す
ゴール G の証明について, 以下のように定義する.
る. 空集合でなければ, そのプロセスは計算を行なっ定義ても失敗する可能性が高いので, 中断して他のプロセスに実行を移す.
AN S は, 初期ゴールに変数が含まれている場合は
 ゴール G を証明する為のプロセスリスト中で,あるプロセスが SGS = ; かつ GS = ; となった
その変数に対する代入が格納され, 他エージェントから質問を受け, その質問の証明を行う場合は, 質問リ場合, ゴール G の証明に成功したとみなす.
 ゴール G を証明するためのプロセスリスト中のテラルが格納される.
ID は, 質問 を送ったエー ジェント の識 別子であ全てのプロセスが中断された場合, すなわち全プる. エージェント S からエージェント S への質問はロセスで SGS 6= ; となった場合, このゴール G
Q@S f rom S という形で送られ, この場合,ID = Sの証明に失敗したとみなし,G とする.となる. また, エージェントに対する質問がユーザー証明の失敗の定義は, ゴール G を証明するための証明から与えられた場合は,ID = u とする.
木において, 全ての枝に, 事前に用意した仮定デフォ
定義
ルトと異なるリテラルが現れるため, 失敗する可能性
プロセスにおいて, SGS = ; となるプロセスを実行が高くなる. それ故, ゴール G の証明も失敗する可能
可能プロセス, SGS 6= ; となるプロセスを実行中断性が高くなる. このため, ゴール G の証明を失敗したプロセスとする.とみなし,G としている.
第6004,計算状態を 以下のリスト及び集合で定義する.

2.3

プロセス簡約過程,,以下の簡約過程では エージェント S において 各定義 5

 プロセスリスト P S とは, 実行可能プロセス, 実行中断プロセスの集合である

.

.

,,.

.

初期ゴールに対して独立に行なう.

,初期ステップ : あるエージェント S で 初期ゴール列
GS に対して実行可能プロセス,,初期ゴールが与えられた場合は 以下の処理を各々の,h;; GS; ;; ;; IDi を証= RFS = ; とし, 以下のス
テップ , ステップ , ステップ を繰り返す.

プロセスリスト P S は 初期ゴールが与えられる度に.

,は 変化しないことを表す エージェント S に複数の

 既回答集合 RF とは, 実際に他エージェントか,,とにする もし 書き換えが書かれてていない場合に.

ら返答された質問リテラルの集合である,それぞれ N ewP SS N ewAAQS N ewRFS と書くこ

 既質問集合 AAQ とは, 他エージェントに送られた質問リテラルの集合である,

ステップで新しく書き換わった P SS AAQS RFS を明手続きに与え AAQS,

新たに作成される また 一つのエージェント内で あ1る初期ゴール GS から作成されたプロセスリストの,ステップ 1:

処理は 他の初期ゴール GS 0 から作成されたプロセス

41

23h;; ;; AD; AN S; IDi というプロセスが

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 5プロセスリスト P SS 中に出現した場合,ID = S なfh;; ff ail(BS )g [ GS ; AD; AN S; IDig
らば AN S をエージェント S に返し, ID = u なら L が基礎質問リテラル Q@S のとき
ばユーザーに対し AN S を出力する. また, プロセス
0 L 62 AAQ かつ  L 62 AAQ ならば,リスト中の全てのプロセスが実行中断プロセスとなっエージェント S に質問 Q@S f rom S を送り,た場合は,AN S の否定を S に返す, または u に出力
N ewAAQS = AAQS [ fLg とする.
する.
0 L 2 RFS ならば,ステップ
さもなければ, プロセスリスト から実N ewP S =P S [ fh;; GS ; AD [ fLg; AN S; IDig とする.
行可能プ ロセス h;; GS; AD; AN S; IDi を選び, さ0  L 2 RFS ならば,らに, GS から拡張 リテラルを選び, P S = P S 0fh;; GS; AD; AN S; IDig および GS = GS 0 fLg
N ewP S =P S [fhfLg; GS ; AD [fLg; AN S; IDig とする.とする.
0 さもなければ L 2 1 ならば,ステップ上で選ばれたリテラル L に対して以下
N ewP S =を行なう.
P S [ fh;; GS ; AD [ fLg; AN S; IDig
 L が正リテラルならば,とする.
N ewP S = P S [0 さもなれければ  L 2 1 ならば,fh;; (fbody(R)g [ GS ); AD; AN S; IDij
N ewP S = P S [ fhfLg; GS ; AD; AN S; IDig
R 2 P and 9most general uni er(mgu) とする.
s.t. head(R) = Lg L が基礎負リテラルならば,回答到着過程
N ewP S = P S [ fh;; N ewGS; AD; AN S; IDig
こ こ で は, 回 答 が 到 着 し た 場 合 に つ い て の 処
ここで N ewGS =理 手 法 を 説 明 す る. あ る エ ー ジェン ト S か ら
ff ail(body (R))jR 2 P and 9mgu 
エー ジェント S に対し て回答 Q が返 されたとき,
s.t. head(R) = Lg [ GS
S は 以 下 の 処 理 を 行 う. 以 下 の 処 理 過 程 で は,新し く書き換わった SGSS ,ADS ,RFS をそ れぞれ L が f ail(BS ) という式ならば,
N ewSGSS ,N ewADS ,N ewRFS とする. もし, 書き
0 もし, BS = ; ならば N ewP S = P S :換えが書かれていなければ, 変化しないことを表す.
0 もし, BS 6= ; ならば BS から B を選び,
 プロセスの処理
BS = BS 0 fB g とし,
P S 中の全てのプロセスに対して以下を行う．
＊ B が正リテラルならば,
Q@S 2 SGSS ならば,
N ewP S = P S [N ewSGSS = SGSS 0 fQ@S g かつfh;; N ewGS [ GS ; AD; AN S; IDig
N ewADS = ADS [ fQ@S g
ここで N ewGS =ff ail((fbody(R)g [ BS ))jQ@S 2 ADS ならば,R 2 P and 9mgu  s.t. head(R) =N ewSGSS = SGSS [ fQ@S g かつBg
N ewADS = ADS 0 fQ@S g＊ B が基礎負リテラルまたは,基礎質問リテラルならば,上記の処理後, SGSS = ; となっているプロセス
N ewP S = P S [(実行可能プロセス) を選択し計算を進める. そうfh;; f B g [ GS ; AD; AN S; IDig[
第00000000

2:0000003:0000002.4000000{00000{000004210 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 6行なう. この時, ag が \true" となっていれば, 他エーでないプロセス (実行中断プロセス) は計算を中断する．
ジェントからの メッセージが来ているので, Answer
File を読み込み, 投機的計算に他エージェントのメッ RFS の処理
Q@S 62 RFS かつ Q@S 62 RFS ならば,セージを反映させる. その後,Flag File を \false" とN ewRFS = RFS [ fQ@S g
書き換える.
Q@S 2 RFS ならば,保険契約の例題における全体の構成は, 図 2 の通り
N ewRFS = RFSとなる. なお,c は投機的計算を行なうエージェントで
Q@S 2 RFS ならば,はなく,c からエージェント b への回答はユーザーがN ewRFS = RFS [ fQ@S g 0 fQ@S g行なう.
この処理は, 各エージェントからの最新の回答だ
Javaけを蓄えておくということを表す.
CMessage Server
第{000{00{03 計算機上への実装

0.

提案した手法の計算機上への実装を行なった シス

prologJava
Message Server

Agent Bprolog

Java
Message Server

Agent A

1 のようになる.
投機的計算部分に prolog を, 通信部分に Java を用いテムの構成は図図2

Java
Send Message
prolog

全体図

Java
Message Server

4 実行例

Answer File
Flag File.
以下で, エージェント a に prepare(P ) を与えた場合の実行履歴を示す.
最初に, エージェント a の履歴を示す.
1. P Sa = fh;; fprepare(P )g; ;; ;; ;ig,
AAQ = ;, RF = ;2. P Sa = fh;; fplan(1)g; ;; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
3. P Sa = fh;; fop c@bg; ;; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
4. P Sa = fh;; ;; fop c@bg; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
AAQa = fop c@bg

歴を示す

Agent

図1

,実行例として 先に述べた保険契約の問題の実行履

システム構成.
,Flag File に \false"と書き込み, Answer File には何も書き込まないでおく.
prolog では, 投機的計算を進める過程において, 質
問リテラルが出現した場合, またはゴールの証明に成功もしくは失敗した場合, 質問リテラルまたは回答を対象となるエージェントの Message Server に送信する.
一方,Java で作成した Message Server では, 他エージェントからのメッセージを受け取った場合,Flag Fileを \true" と書き換え, 実際の メッセージを Answer
File に書き込む.
prolog では,1 ステップ毎に Flag File のチェックをて実装を行なった 初期状態ではエージェント a からエージェント b にop c@b f rom a という質問を送る

43

10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17 7たことによって, それまで計算を行っていたプロセ
こ こ で, a は b か ら 回 答 が 来 る 前 に, デ フォルト
ス h;; ;; fop c@bg; fP = 1g; ;i 中の op c@b
op c@b を使用して P = 1 という解を得た.
が処理中断集合に移される. このプロセスは処理
第,つぎに エージェント a から中断集合が空集合でなくなるので, 実行中断プロ

op c@b f rom a とセスとなり, 別のプロセスの計算が行なわれる.

.

いう質問を受け取ったエージェント b の履歴を示す

1. P Sb = f= 2 となる.

a が出力する解は P

h;; fop cg; ;; fop c@bg; aig,
AAQb = ;,RFb = ;2. P Sb = fh;; ff ail(op@cg; ;; fop c@bg; aig
3. P Sb = fh;; fop@cg; ;; fop c@bg; aig
4. P Sb = f
hfop@cg; ;; ;; fop c@bg; aig
AAQb = fop@cg
エージェント b から c に対して,op@c f rom b

ここで,c からエージェント b に対して,op@c という回答がきたとする. この時 エージェント b では以下.
1. P Sb = fのようになる

h;; ;; fop@cg; fop c@bg; aig
RFb = fop@cg
先程まで SGS に入っていた op@c が AD に移された. これにより SGS = ; かつ GS = ; となるプロセスが出現し, op c@b の証明が成功した,とみなされ エージェント a に回答される,.

エージェント a は 先程とは翻った回答をエーという質問を送る.

ジェント b から受けることになる この時のエー, op@c は b のデフォルトと一致しない,中断される. また,op c を証明するための計算プロセスが全て中断されたため, このゴールの証明に失敗したものとみなし, (op c), すなわちop c@b がエージェント a に対して回答される.
続いて, このエージェント b からの回答を受け取ったエージェント a の履歴を示す.
(a) P Sa = fhfop c@bg; ;; ;; fP = 1g; ;i;h;; fplan(2)g; ;; fP = 2g; ;ig
RFa = fop c@bg(b) P Sa = fh;; fplan(2)g; ;; fP = 2g; ;ig;
hfop c@bg; ;; ;; fP = 1g; ;ig(c) P Sa = fh;; fop c@bg; ;; fP = 2g; ;ig;
hfop c@bg; ;; ;; fP = 1g; ;ig(d) P Sa = fh;; ;; fop c@bg; fP = 2g; ;ig;
hfop c@bg; ;; ;; fP = 1g; ;ig
履歴 (a) において, b から回答 op c@b を受け取っ

ジェント a は以下のようになる

ここで,(a) P Sa = f

ため 処理中断集合に入り この計算プロセスは.

h;; ;; fop c@bg; fP = 1g; ;ig;
hfop c@bg; ;; ;; fP = 2g; ;ig
RFa = fop c@bg,

エージェント a から 再び解 P,= 1 が得られる.

この実行履歴で示した通り エージェント a は翻った

,回答をエージェント b から受け取ることになるが 最.

,新の回答に基づいた解が得られる また この履歴で,は示していないが エージェント b が c から翻った回,答を受け取った場合でも エージェント a の場合と同様にして最新の回答に基づいた解が得られる

5 おわりに.

,

本論文における成果は 投機的計算の手法を拡張し,他のエージェントからの回答が変化するという場合に,対処することが出来る手法の提案を行なった事 また,その手法を計算機上に実装し 動作の確認を行なった.

,ことである 今後の課題としては 応用問題による効果の検証が挙げられる

44.

第10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

謝辞,

本研究を進めるにあたり 北海道大学の原口 誠先生

,

,

参考文献

,

[1] Satoh,K., Inoue,K., Iwanuma,K., Sakama,C.,\Speculative Computation by Abduction under Incomplete Communication Environments", Proceed-

大久保 好章先生 神戸大学の井上 克己先生 和歌山,

大学の坂間 千秋先生 山梨大学の岩沼 宏治先生に貴,ings of the Fourth International Conference on.

MultiAgent Systems,to appear(2000)[2] 佐藤, 井上, 岩沼, 坂間, 不完全通信環境下におけるアブダクションによる投機的計算, 人工知能学会知識ベース研究会資料, SIG-KBS-9904, pp.43 - 48 (2000)[3] 山本, 佐藤, マルチエージェントシステムへの投機的計算導入手法, 第 15 回人工知能学会全国大会 (2001)

重なご助言 ご指摘をいただきました ここに謝意を.

8

示します45