分散システムの捕らえ方

自律分散協調コンピューティング
慶應義塾大学環境情報学部
徳田英幸
© H.Tokuda 2007
自律分散コンピューティング
 分散アルゴリズム
 自律性
 分散エージェント、マルチエージェント、自律ロボット
 分散性
 物理的な分散（コントロール＋データ）, p2pシステム
 フラットな構造
 協調性
 協調プロトコル
 複雑な問題に対する新しいアプローチ
 遺伝的アルゴリズム(GA)
 ニューラルコンピューティング
© H.Tokuda 2007
P2p型システム



peer: 端末ノード
peer-to-peer: 1対１の対等な協調作業形態
アプリケーション




ファイル共有、交換、配信: Chord, Napster, Gnutella, Winny
グループウェア: Grove
分散コンピューティング: SETI@home
分類

構造的p2pシステム




Deterministic algorithms
DHT (Distributed Hash Table)-based Systems
CAN (Content Addressable Network)
非構造的p2pシステム


Randomized algorithms
Search by Flooding alg.

E.g. MANET’s routing
© H.Tokuda 2007
DHT (Distributed Hash Table)



2^160 ノード（例：２＾4ノード）
Succ(i), Pred(i)
Routing Tableの作成




i = 0 ～ (m-1) <== ここではm=4であるので0～3
p = (NodeID + (2^i)) % (2^m)
RoutingTable = {[Finger(p)]}
Finger(p)[i] = succ(p+2^(i-1))
15
0
FT(0)={1,4,4,8}
1
FT(1)= {4,4,8,11}
2
14
FT(4)={8,8,11,14}
3
13
FT(8)={11,11,14,0}
4
12
5
11
6
10
9
8
© H.Tokuda 2007
7
FT(11) = {14,14,0,4}
FT(14)={0,0,4,8}
DHT (Distributed Hash Table)




Hash function: SHA-1 (160bit random value)
IP addr. Or Name => 2^160 Node id （例：２＾4 Node id）, O(log N) steps
Succ(i), Pred(i)
Routing Tableの作成




i = 0 ～ (m-1) <== ここではm=4であるので0～3
p = (NodeID + (2^i)) % (2^m)
RoutingTable = {[Finger(p)]}
Finger(p)[i] = succ(p+2^(i-1))
15
0
FT(0)={1,4,4,8}
1
Q: Nid=13? At 0
Route: Finger(p)[j] <=
Nid < Finger(p){j+1]
FT(1)= {4,4,8,11}
2
14
FT(4)={8,8,11,14}
3
13
FT(8)={11,11,14,0}
4
12
5
11
6
10
9
8
© H.Tokuda 2007
7
FT(11) = {14,14,0,4}
FT(14)={0,0,4,8}
DHT：ノードの追加・削除


Succ(i), Pred(i)
Routing Tableの作成




i = 0 ～ (m-1) <== ここではm=4であるので0～3
p = (NodeID + (2^i)) % (2^m)
RoutingTable = {[Finger(p)]}
Finger(p)[i] = succ(p+2^(i-1))
15
0
FT(0)={1,4,4,8}
1
FT(1)= {4,4,8,11}
2
14
13
FT(8)={11,11,14,0}
Node 10:
Succ(10) = 11
4
12
Pred(10) = 8
Node 8: Succ(8) =10
5
11
Node 11: Pred(11) = 10
Update each
Finger Table!！
FT(4)={8,8,11,14}
3
6
10
9
8
© H.Tokuda 2007
7
FT(11) = {14,14,0,4}
FT(14)={0,0,4,8}
自律分散協調コンピューティング
 分散アルゴリズム
 相互排除問題、デッドロック問題、etc
 複雑な問題に対する新しいアプローチ
 マルチエージェントシステム
 遺伝的アルゴリズム(GA)
 協調作業支援システム
 CSCWシステム
 グループウェア
 コミュニティウェア
© H.Tokuda 2007
マルチエージェントシステム
マルチエージェント
 システム特定の目的をもって行動するエー
ジェントが、他のエージェントと協調的に行動
するための性質、条件やエージェントが複数
存在するときに生じる現象、効果などについて
研究することを目的としている。
 特定の問題を部分問題に分割して解決してい
くことを主たる目的としていない。
© H.Tokuda 2007
マルチエージェントに関わる研究分野
 分散人工知能：知的エージェントの協調的な
問題解決
 分散協調ロボット：複数ロボットの協調作業
 CSCW：人間を支援するプログラム間の協調
方法
 人工生命：生命的存在の集団行動、生態系
 仮想現実：仮想現実空間中に可視化された複
数エージェントおよび人間の相互作用
© H.Tokuda 2007
システムの捕らえ方
 構成論的手法
 Top-down, bottom-up手法
 Client-server model
 自己組織論的手法
 自律的にシステムを構成
 群知能、集団行動
 アリの巣
 都市のかたち
 自律型ロボットシステム
© H.Tokuda 2007
構成論的手法
 協調方法を定義したアーキテクチャの構築
 全体に対して個々のエージェントの役割が位置づ
けられる。
 コミュニケーションプロトコルの設計
 マスタースレーブ的な協調、機能分割的な協調
 位置的、機能的分散処理の重視
 工学的な効率、システム動作解析可能性の重視
© H.Tokuda 2007
自己組織論的手法
 協調的行動を発現するアーキテクチャの構築
 全体は、個々のエージェントのインタラクションの結果として
創出される。




システムダイナミクスの研究
柔軟性、頑健性の重視
自律性に基づく協調
生物、社会現象の模倣
© H.Tokuda 2007
マルチロボットシステム




基本アイデア：複数ロボットの協調作業
背景：分散環境の整備、集中的システムの限界
特徴：柔軟性、頑健性、並列性、拡張性
応用：清掃、点検、運搬作業、Flexible
Manufacturing, 宇宙ロボット、エンターテイメント
© H.Tokuda 2007
自律性とは？
 自律：
 自分で自分の行為を規制すること
 外部からの制御から脱して、自身の立てた規範に従って行
動すること
 自立：
 他の援助や支配を受けず自分の力で身を立てること
 自律性をプログラムするとは？
 エージェントを作るとは？
© H.Tokuda 2007
知的エージェントとは？
 知的エージェントは、ある環境をセンサで知覚
し、ある環境にエフェクタを通して動作するも
のである。
 自律ロボットエージェント
 センサ：カメラ、赤外線センサ
 エフェクタ：手、足などを制御するモータ
© H.Tokuda 2007
環境の多様性




アクセス可能 vs アクセス不能
決定的 vs 非決定的
静的 vs 動的
離散的 vs 連続的
© H.Tokuda 2007
知的エージェントとは？（２）
環境
センサ群
知覚動作
？
エージェント
動作
エフェクタ
© H.Tokuda 2007
エージェント指向コンピューティング
 新しい自律分散協調システム作りのパラダイムの１
つ
 問題解決の質や性能の向上
 コンピュータ・ヒューマンインタラクションの高度化
 システムモデリングと設計支援
 AI分野での知的エージェント
 エージェント指向プログラミング
 IT分野でのソフトウェアエージェント
© H.Tokuda 2007
自律分散協調システム
問題解決のパラダイム
創発システムのパラダイム
自律分散コンピューティング
 分散アルゴリズム
 自律性
 分散エージェント、マルチエージェント、自律ロボット
 分散性
 物理的な分散（コントロール＋データ）
 フラットな構造
 協調性
 協調プロトコル
 複雑な問題に対する新しいアプローチ
 遺伝的アルゴリズム(GA)
 ニューラルコンピューティング
© H.Tokuda 2007
問題解決手法のパラダイム
 問題空間探索手法
 問題空間と解空間
 Goal & Subgoal
 発見的手法
Ａ
Ｂ
 Generate & Test
Ｆ
Ｈ
© H.Tokuda 2007
Ｃ
Ｇ
Ｉ
Ｊ
Ｄ
Ｅ
問題解決手法のパラダイム
 問題空間探索手法
 問題空間と解空間
 Goal & Subgoal
Ａ
Ｂ
 発見的手法
 Depth first
 Breadth first
Ｈ
 Best-first & eval fct.
Ｆ
 GA
 Generate & Test
© H.Tokuda 2007
Ｃ
Ｇ
Ｉ
Ｊ
Ｄ
Ｅ
問題空間と解空間の概念
5
2
e.g., 8-puzzle
3
1
6
4
2
7
3
1
5
6
4
7
8
8
2
4
5
3
2
5
1
6
1
6
7
8
4
7
1
2
3
4
5
6
7
8
© H.Tokuda 2007
3
8
2
3
1
5
6
4
7
8
世代の概念
 Life game
 J. H. ConwayのLife Game
 Life gameのルール
 盤面上にいくつかの石（生命体）を置く．（初期集団）
 盤面のある場所が空いていて、しかもその場所と隣り合う
ちょうど３個の場所に生命体が存在するならば、次の世代
にはその空いた場所に新しい生命体が誕生する．
 また、すでに存在する生命体については、隣り合う場所に
住む生命体が１個以下、または４個以上になると、過疎ま
たは過密のため、次の世代には、死んでしまう．
© H.Tokuda 2007
世代の概念 (2)
 世代の概念
*
*
*
*
*
*
*
*
© H.Tokuda 2007
*
*
*
*
*
*
...
Life.cで世代計算
 a[i, j]のマトリックスに生命体をセット
b[i][j]に周囲の生命体の数
a[i][j]に次世代生命体をセット
。。。
/* calculate the next generation */
for (i = 0; i <= N + 1; i++)
for (j = 0; j <= M + 1; j++) {
if (b[i][j] != 2)
a[i][j] = (b[i][j] == 3);
b[i][j] = 0;
}
｝
© H.Tokuda 2007
遺伝的アルゴリズム(Genetic
Algorithm: GA)
 生物進化（選択淘汰・突然変異）の原理に着
想したアルゴリズム
 基本的には，Generate-and-Test型のアルゴリ
ズム
 Holland, "Adaptation in Natural and
Artificial Systems" (1975)
 1985 1st Conf. on Genetic Algorithm
at CMU
© H.Tokuda 2007
問題空間と解空間の概念
5
2
3
1
6
4
2
7
3
1
5
6
4
7
8
8
2
4
5
3
2
5
1
6
1
6
7
8
4
7
1
2
3
4
5
6
7
8
© H.Tokuda 2007
3
8
2
3
1
5
6
4
7
8
世代の概念
 Life game
 J. H. ConwayのLife Game
 Life gameのルール
 盤面上にいくつかの石（生命体）を置く．（初期集団）
 盤面のある場所が空いていて、しかもその場所と隣り合うちょうど
３個の場所に生命体が存在するならば、次の世代にはその空い
た場所に新しい生命体が誕生する．
 また、すでに存在する生命体については、隣り合う場所に住む生
命体が１個以下、または４個以上になると、過疎または過密のた
め、次の世代には、死んでしまう．
© H.Tokuda 2007
世代の概念 (2)
 世代の概念
*
*
*
*
*
*
*
*
© H.Tokuda 2007
*
*
*
*
*
*
...
遺伝的アルゴリズム(Genetic
Algorithm: GA)
 生物における遺伝のメカニズムの応用
 Generate-and-Test型のアルゴリズム
 多点情報を利用した確率的な探索方法の一
つ
 ３つの遺伝的オペレータ
 選択 (selection)
 交叉 (crossover)
 突然変異 (mutation)
© H.Tokuda 2007
基本的な処理手順
 Step 1: 初期集団の生成
 Step 2: 終了条件が満たされるまでループ




適応度の評価
選択
交叉
突然変異
© H.Tokuda 2007
選択と交叉
...
© H.Tokuda 2007
３つの遺伝的オペレータ
 選択
 集団における適応度の分布に従って、次世代に生存する個体群
を確率的に決定する。
 交叉
 二つの個体間で染色体を組み換えることによって新しい個体を生
成するもので、両親の優れた部分形成を子に継承させる。
 突然変異
 染色体上のある遺伝子を確率的に起き換え、新し
い個体を作り出す。
© H.Tokuda 2007
TSP (Travelling Salesman Problem)
 巡回セールスマン問題
 すべての都市を１度ずつ訪問する．
 巡回コストを最小にする経路を見つける．
2
1
10
3
8
9
5
4
7
© H.Tokuda 2007
6
GSによるTSPの解法
親１　[9 8 4 5 6 7 1 3 2 10]
親2 [8 7 1 2 3 10 9 5 4 6]
問題の文字列にコード化
文字列の集団populationを作る
文字列を評価する
子１　[9 8 4 2 3 10 1 6 5 7]
子１　[8 10 1 5 6 7 9 2 4 3]
表価値　＝ 1/ 巡回経路長　評価値に応じて淘汰を受ける
遺伝的操作により
新しいpopulationを生成する。
© H.Tokuda 2007
500都市問題の解
 プリントアウト参照
© H.Tokuda 2007
CSCWシステム
 Computer Supported Cooperative Work
 Irene Greif, Paul Cashman (1984)
 グループワークの中で、コンピュータの役割に注目す
る概念や基本姿勢に関する研究
 コンピュータ支援（ＣＳ）という支援手段、協調作業（Ｃ
Ｗ）という支援対象の２つの異なる視点を合わせもっ
た概念
© H.Tokuda 2007
グループウェア
 Group ware: Peter and Trudy Johson-Lenz
(1978)
 共通の仕事や目的のために働く利用者のグループを
支援し、共有作業環境を提供するコンピュータシステ
ム
 個人作業環境と協調作業環境とのシームレスな結合
 時間、空間、メディア間のシームレスな結合
© H.Tokuda 2007
グループウェアの分類
 同期対面型：時間、場所、情報を共有（例：発
想支援システム）
 同期分散型：時間、情報を共有（例：ビデオ会
議システム）
 非同期対面型：場所、情報を共有（例：グルー
プメモリ）
 非同期分散型：情報を共有（例：ソフトウェア共
同開発システム）
© H.Tokuda 2007
グループウェアの３つの側面
社会的側面
人間的側面
技術的側面
© H.Tokuda 2007
グループウェアの３つの側面（２）
 技術的な側面：システムのデザイン、開発、運
用、評価
 人間的な側面：個人の感情と感性、プライバ
シーの保護、相互依存
 社会的な側面：制度、慣習、社会的な関係へ
の配慮
© H.Tokuda 2007
基盤技術




ネットワーク
コミュニケーション支援
感性インタフェース
協調作業環境
© H.Tokuda 2007
創発システムに向けて
慶應義塾大学環境情報学部
徳田英幸
情報システムにおける自律分散協調
 自律分散協調システムのねらい
 自己組織性
 創発のメカニズム
 自律分散協調コンピューティング




アドホックネットワークプロトコル
ソフトウェアエージェント
自律ロボット
p2pアプリケーション
© H.Tokuda 2007
自律性について
 社会システム
 ガバナンスモデル
 電子政府モデル
 地方自治体モデル
 教育、交通、安全システム
 スマート交差点問題
 自律分散協調モデル
 創発とは？
 Waveは、どう起るか？
 ロボット自動整列問題
 ロボットよ、コンパスを持って協調せよ！
 掃除ロボット問題
 どのようなアルゴリズムが良いか？
© H.Tokuda 2007
協調性について
 協調メカニズム
 協調プロトコル
 どのような協調パターンがあるのか？
 どのように記述するのか？
 なぜ協調するのか？
 自然なプロトコル
 生物システム
 人工的なプロトコル





Client-Server
Ethernet’s MAC Layer
競売プロトコル
回覧板プロトコル
その他多種多様なプロトコル。。。
© H.Tokuda 2007
創発システムについて
 複数の要素が有機的に関係し合って、相互作用を通
して全体としてまとまった機能を発現している要素の
集まり
 相互作用が変わればシステムの機能も変わる！
 弱い創発システム
 ミクロな要素の動きが集まって全体にわたるマクロなパター
ンが創発するシステム
 強い創発システム
 環境変化に適応できる創発するシステム
© H.Tokuda 2007
創発のかたち
 上位層でのかたち
 グループ、群、コミュニティ
 水の対流
 サッカー場のウェーブ
 自律型ロボットの整列問題
© H.Tokuda 2007
共通する性質は？
 自分と同じ能力の要素が沢山存在する
 沢山の要素が広い空間に分散している
 すべての要素が共通の方法で（自分の近くの
要素とだけ）情報の交換をする
 すべての要素が同時並列的にうごく
 すべての要素が同じ状況になるように動く(同
じ評価関数をもっている）
© H.Tokuda 2007
演習：wave2.c
 どのように協調するのか？
 実行例…
© H.Tokuda 2007
Wave programの作成
 配布されたwave2.cプログラムを改良して、
競技場で起こるwave 現象をsimulateできるようにす
る。
＜初期状態＞＜次世代生成部分＞
＊ソースコード
＊出力結果
＊考察
これをもとに、創発を起こす上でもっとも重要な要因
について議論せよ。
© H.Tokuda 2007
StarLogo @ MIT
© H.Tokuda 2007
創発のギャップ
 人間 vs. 自律型ロボット
 個の非プログラム性
 個の学習・動的適応性
 多様な個
 多様な価値観
 情動的な行動
 同期性
 個の密度
 population density
 全体の規模
 Scalability
 実空間上の行動 vs. ネットワーク上の行動
© H.Tokuda 2007
前半部分のまとめ
慶應義塾大学環境情報学部
徳田英幸

Download Report