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