マルチエージェントの合意形成に関する基礎研究

集団的意思決定支援法の
実験環境に関する研究
北海道工業大学情報デザイン学科
大崎友之、三田村保、大堀隆文
研究背景

マルチエージェント研究
 エージェント＝環境（environment）の状態を知覚し，
行動を行うことによって環境に影響を与えることので
きる自律的主体
 マルチエージェント＝複数のエージェントが相互作用
を行う環境

集団的意思決定支援法の研究
 マルチエージェントの合意形成
 各エージェントが自分の意思を持ち、一つの意思に
まとめる
合意形成
合意された意思
（前順序関係、半順序関係）
まとめて一つの意思に
1の意思
（前順序関係、半順序関係）
エージェント１
2の意思
･･･
エージェント２
nの意思
･･･
エージェントn
合意形成
合意された意見
（前順序関係、半順序関係）
まとめて一つに
1の意思
（前順序関係、半順序関係）
c
c
e
a
b
c
d
e
d
d
a
d
b
e
a
b
nの意思
･･･
2の意思
e
c
a
a
b
c
d
e
b
a
b
1
0
0
0
0
1
1
0
0
0
1
1
1
1
1
0
1
0
1
0
0
1
0
0
1
a
b
c
d
e
1
0
0
0
1
0 0 0 0
0 1 0 0
1 1 0 0
0 1 1 0
0 0 1 1
エージェント１
c
d
エージェント２
e
a
b
c
d
e
･･･
a
b
c
d
e
1
0
0
0
1
0
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
エージェントn
研究内容

集団的意思決定支援法の実験環境の整備

エージェントの意思自動生成
 エージェントの意思を表す行列を生成実験

合意形成シミュレーション
 FISMを利用した合意形成
 合意形成のシミュレーションの実行および結果
エージェントの意思自動生成

エージェントの意思を自動的に生成

エージェントの意思を表す行列



自動生成実験

方法1



Warshallのアルゴリズム
方法3


ランダム生成
方法2

FISMを利用（前順序）
方法4


前順序関係＝反射性、推移性
半順序関係＝反射性、推移性、反対称性
FISMを利用（半順序）
作成する行列数（各方法共通）




n = 3･･･50個
n = 4･･･1,000個
n≧5･･･10,000個
前順序、半順序ともに作成した行列の平均生成率
方法1 ランダム生成

処理手順
 反射性をみたす行列Mをランダムで作成
 重複がないかチェックし、なければMを決定
 前順序、半順序の関係を満たしているかをチェック
方法1の結果
100%
90%
80%
70%
60%
平
50%
均
40%
30%
20%
10%
0%
3
4
5
6
7
8
9
10
選択肢ｎの数
前順序
半順序
この方法では、前順序、半順序ともにほとんど作成できない。
方法2 推移的閉包を利用

処理手順
 反射性を満たす行列Mをランダムで作成
 MをWarshallのアルゴリズムを利用し修正
 重複がないかチェックし、なければMを決定
b
a
c
方法2の結果
100%
90%
80%
70%
60%
平
50%
均
40%
30%
20%
10%
0%
3
4
5
6
7
8
9
10
選択肢ｎの数
前順序
半順序
前順序は方法1より若干作成できる量は増えたが前順序、
半順序ともに全体的には少ない。
FISM（Flexible Interpretive Structural Modeling）
部分可到達行列


Mii=1(反射性)
以下の条件を満たしていない



Mij= ｘ,Mik= 1,Mkj= 1
Mij= ｘ,Mik= 0,Mkj= 1
Mij= ｘ,Mkj= 1,Mki= 1
含意規則

以下の３種類の含意が存在する



1⇒1含意とは、xijに1を与えたとき、他の未知要素xpqを1とする含意である。
1⇒0含意とは、xijに1を与えたとき、他の未知要素xpqを0とする含意である。
0⇒0含意とは、xijに0を与えたとき、他の未知要素xpqを0とする含意である。
方法3 FISMを利用（前順序）

処理手順
 反射性で他が未知の初期行列Mを作成
 未知要素数が0になるまで以下を繰り返す
未知要素(Mij= ｘ)をランダムで選出
 Mijに{0,1}をランダムでセット
 Mijの値から含意規則を適用してMを更新

 重複がないかチェック
 半順序のチェック
方法3の結果
100%
90%
80%
70%
60%
平
50%
均
40%
30%
20%
10%
0%
3
4
5
6
7
9
8
10
20
30
選択肢ｎの数
前順序
半順序
前順序においては100％作成することが可能になった。
生成された行列のほとんどが前順序であり、半順序行列は少な
い。
方法4 FISMを利用（半順序）

処理手順
 反射性で他が未知の初期行列Mを作成
 未知要素数が0になるまで以下を繰り返す
未知要素(Mij= x)をランダムで選出
 Mijに{0,1}をランダムでセット



Mij が1のときMjiを0にする
Mijの値から含意規則を適用してMを更新
 重複がないかチェック
方法4の結果
100%
90%
80%
70%
60%
平
50%
均
40%
30%
20%
10%
0%
3
4
5
6
7
8
9
10
20
30
選択肢ｎの数
前順序
半順序
半順序、前順序ともに100％作成することができるようになった。
合意形成シミュレーション
1. 集団G に所属するエージェントMK を作成
2. 比較行列Cを作成
3. Cが既知行列になるまで以下を繰り返す
 未知要素(cij=ｘ)を選出(今回はランダム)
 cijの値を{0,1}に決定(今回は多数決)
 決定したcijの値から含意規則を適用してCを更新
合意形成シミュレーション



集団G = { Ak ：k = 1,2,･･･,K }
選択肢W = { O1,O2,･･･,ON }
エージェントAk がもつ意思を表す行列
Mk = [mkij]

実験条件
集団数 G=10
エージェント数 K=10
選択肢数 N=5～10,20,30
未知要素(cij=ｘ)を選出(ランダム)
cijの値を{0,1}に決定(多数決)
合意形成シミュレーション（１）
1. 集団G に所属するエージェントMK を作成
(MKは重複なく、半順序）
2. 比較行列Cを作成
C = [cij]
cij =
mij , (if m(1)ij = m(2)ij = ･･･ = m(k)ij)
x
合意形成シミュレーション（２）
3. Cが既知行列になるまで以下を繰り返す
 未知要素(cij=ｘ)を選出(今回はランダム)
 cijの値を{0,1}に決定(今回は多数決)
 cijの値から含意規則を適用してCを更新
合意形成の評価

一致度FIを以下のようにして求める
DI
(ｋ )
 [di ]
ｋ
ij
diｋij  mｋij  cij
N N
1
k
FI(k)  1 
|
di

ij |
n (n  1) i 1 j1
シミュレーション結果
100%
90%
80%
70%
60%
FI 50%
40%
30%
20%
10%
0%
5
6
7
9
8
選択肢 n の数
FI平均
最大値
10
20
30
最小値
選択肢が増加していくと一致度FIの最大値が減少し最小値が増加している
ことから選択肢が増えるほどばらつきが少なくなる
今後の課題

cijの決定方法


M(i,j)の決定方法




比較行列Cの（i,j）を随伴含意行列を使って決定
M(i,j)の値を確率で決定
エージェントの重み付けを行う
（i,j）の決め方とM（i,j）の決め方の組み合わせの全パターン
を検証
合意方法


集団で決定
個別にエージェント同士で決定し、全体の合意を得る方法
集団的意思決定支援法の
実験環境に関する研究
北海道工業大学情報デザイン学科
大崎友之、三田村保、大堀隆文

Download Report